I've been considering what would happen if an engine had expensive eval or move ordering and visited 10-100 times fewer nps than the top AB engines. At such precision and speed, and possibly larger entry size, a more conservative and flexible TT entry replacement strategy would probably be needed, still not as easy as in the current NN engines that are compute bound.
Hence I've been searching for alternatives to fixed-size buckets. I guess chaining is too impractical for chess because of frequent cache misses, so open addressing methods are better candidates.
Let me give an example. When introduced to Robin Hood hashing,
I visited the link and found a comment by Wolfgang Brehm (posted 12 hours ago, oh irony) linking to the Github page detailing his invention called the patchmap.dragontamer5788 wrote: ↑Mon Nov 11, 2019 4:31 pm I do believe the "best hash table" award goes to linear probing with robin hood hashing these days, but I guess that's a bit off topic. Cuckoo hashing has some nifty parallel implementations for what its worth.
Wolfgang's article cited there acknowledges slowish deletion and a cost of insertion that grows steeply as the load factor approaches 1, but in chess, there's no need to delete an entry on demand (except clearing the whole table) nor to always search for an empty slot during insertion - with a good enough replacement strategy, after a cheap lookup shows no match but a collision, only a few (but, optionally, a less limited variable number of) adjacent entries will usually be probed before a replaceable one is found. As a bonus, the patchmap never requires rehashing.This approach might sound very similar to the one suggested in "Ordered Hash Tables" (01 January 1974) O. Amble D. E. Knuth but there is a mayor difference in that the hash tables there are ordered first by the hash of the keys and then by the value of the key. If the entries are however only ordered by the hash value there exists a global order, which all of a sudden allows advanced search strategies like interpolation search and binary search.
In fact the approach is much more similar to robin hood hashing with linear probing because if two keys collide at the same position the key whose hash value is lower will also have been displaced more and will therefore displace the key with the larger hash value, therefore keeping up the same order. There has however been no hash table using robin hood hashing with linear probing that takes advantage of this fact.