A new fast hash table in response to Google’s new fast hash table

Re:A new fast hash table in response to Google’s new fast ha... by ztorkelson on Tuesday May 29, 2018 @05:23PM (#17183033)

That's not a very charitable interpretation of the GP. He's not criticizing hash tables because they aren't radix trees. He's criticizing this and other hash table implementations because they have undesirable performance characteristics with respect to his needs, and noting an alternative data structure which he has found to be more suitable. I think that's fair game.

Note that there exist hash table implementations which support incremental resizing.

I do agree, though, that it's a leap to go from "hash tables with this property are inappropriate under these constraints" to "hash tables with this property should not be considered further", precisely because there is such a broad spectrum of data structure requirements across the industry.

[ Parent | on HN ]

Re:A new fast hash table in response to Google’s new fast ha... by eternalban on Wednesday May 30, 2018 @09:06AM (#17187336)

> Note that there exist hash table implementations which support incremental resizing.

Rather, there exist hash table algorithms that support incremental resizing.

http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/cours...

[ Parent | on HN ]

Re:A new fast hash table in response to Google’s new fast ha... by stochastic_monk on Tuesday May 29, 2018 @10:44PM (#17184622)

Additionally, a hash table could be implemented in such a way that it could be updated during resizing. As long as you set up locks in the right places, you could spend the extra memory to do an out-of-place rehash and allow both concurrent writers and your rehashing thread to write to the new table. It's doable, if difficult and error-prone.

[ Parent | on HN ]