Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
by dastbe on Tuesday May 09, 2017 @01:14AM
(#14297879)
So if A is the hashed-to index into your table, then B is a function of A. When you are doing your linear probe and you see a value along with its probe count, it either
1. Has a higher probe count, this means it's hash is further away than yours => less than yours
2. Has a lower probe count than yours. This means its hash is closer than yours => greater than yours
3. Is equal in probe count to yours. That means it's in the same bucket => equal to yours.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
by dryman on Tuesday May 09, 2017 @01:26AM
(#14297925)
When I first see "sorted array", my first impression is it is sorted by the "original key". If we look for the hashed value in hash table, all hash tables are "sorted array" with this definition.
Also there's a finial mod in linear probing h(k, i) = (k + i) mod N. With this mod you may have different key/probe combination that messed up the order.
Strictly speaking the Robin Hood "sort" isn't purely lexiconally ordered. A larger A value maybe replaced a smaller A, with a much larger B.
But this relation nonetheless is just a weird solution to build a cmp function one. One that arguably doesn't work in a strict sense. But one that _nearly_ works.