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.
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.