The overhead of storing hashed values inside the hashtable is not to be neglected.
If my key type has a fast hash function, maybe I don't need to store the hashed value. But if e.g. I have a hashset of char*s, I definitely don't want to rehash. Storing those hashes alongside the pointers effectively halves my load factor, from a cache-friendliness point of view. There goes the whole load-factor advantage.
Maybe Robin Hood hashing still wins by letting me use linear probing, which is more cache-friendly than (say) the quadratic probing you'd normally have to do. But this is getting sketchier...
In addition, it's not clear to me that the cost of the swaps is entirely negligible in the common case when the elements of the hashtable are more than one or two words wide. Certainly not if you have to run a constructor to do the move instead of just memcpy'ing the elements.
I like the idea, but it is not (to me) obviously a knockout win.
If you don't need to store the hash value because your hash function is simple, you don't… Nothing about the (linear) robin hood collision handling strategy forces an explicit representation of the hash value. However, it is true that C++ makes some data structures slower than they should be.
If my key type has a fast hash function, maybe I don't need to store the hashed value. But if e.g. I have a hashset of char*s, I definitely don't want to rehash. Storing those hashes alongside the pointers effectively halves my load factor, from a cache-friendliness point of view. There goes the whole load-factor advantage.
Maybe Robin Hood hashing still wins by letting me use linear probing, which is more cache-friendly than (say) the quadratic probing you'd normally have to do. But this is getting sketchier...
In addition, it's not clear to me that the cost of the swaps is entirely negligible in the common case when the elements of the hashtable are more than one or two words wide. Certainly not if you have to run a constructor to do the move instead of just memcpy'ing the elements.
I like the idea, but it is not (to me) obviously a knockout win.