News for hackers. Stuff that matters.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints by valarauca1 on Tuesday May 09, 2017 @01:01AM (#14297841)
It's a sorted array because your sorting by 2 keys (A,B). A is the hash, normally a u32 or u64. B is the probe count, also normally the same sized b/c system ints are easy.

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.

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.