2

What are the pitfalls of using the power of two hash table sizes, instead of prime-numbered sizes, used traditionaly? Does using a prime number guarantees fixing the deficiencies of the naive hash functions (like i.e. xoring key bytes) or it is just a "shotgun debugging"? What simpler hash function would work with the power of two table sizes without clustering the keys too close?

Nash Gold
  • 53
  • 6
  • The hash function returns a number that could be larger than the size of the array of buckets. If the table size is prime, you use `%` (modulus) to get the actual bucket, while, if the table size is a power of 2, you use bit masking, with is much faster than division. Problem with masking is that, if the hash function is poor (i.e. if it doesn't distribute lower bits well), there might be many collisions. But resizing is very simple (just double the number of buckets). On the other hand, using `%` always requires a prime number of buckets, so doubling the number of buckets wouldn't work – fps Oct 05 '20 at 00:40
  • Does this answer your question? [Java: A "prime" number or a "power of two" as HashMap size?](https://stackoverflow.com/questions/15437345/java-a-prime-number-or-a-power-of-two-as-hashmap-size) – fps Oct 05 '20 at 00:40
  • @fps, unfortunately that Java answer doesn't provide any links to papers discussing the problem or why the prime numbers work at all. So I should just ensure that higher bits get permuted with lower bits? But that sounds more expensive than `%` - to permute 32-bit value bits one needs at least four table lookups - for each byte, and even then any single permutation is not guaranteed to work with a particular key set (i.e. one needs to pick permutation adaptively, during table resize). Are there any x86 opcodes to do the bit permutation? – Nash Gold Oct 05 '20 at 10:43
  • No, you don't have to permute any bits. You only need a good hash function, that's all. The hash function must distribute lower bits well, the same as higher bits, that's my point. Why would permutations require 4 table lookups? I don't follow all that permutations stuff, I believe you are overthinking this. Regarding `%` requiring prime numbers, it's because dividing by non prime numbers produces reminders that collide much more than dividing by prime numbers (this is math, I don't remember the proof now, but it's fairly easy) – fps Oct 05 '20 at 13:05
  • Because `tbl1[dwbyte1]+tbl2[dwbyte2]+tbl3[dwbyte3]+tbl4[dwbyte4]` and tables larger than 8bit would put too much pressure onto cache. Of course one can apply these tables while doing the string hash, but that implies you hash byte-by-byte. Still no idea how one would hash a c-string faster than byte-by-byte. C/C++ needs a better base string type. – Nash Gold Oct 05 '20 at 17:36
  • But 64-bit processor operate on 4 and 8 bytes per cycle. Masking and shifting, etc is super fast. Again, you are overthinking this too much – fps Oct 05 '20 at 17:46
  • Yeah, but there is no way to permute a qword in a register - you still have to apply tables byte-wise. x86 SIMD has gather operation, but I doubt you can efficiently initialize 4-bit tables for it for each nibble. So the hash I currently use goes like following `for (int i = 0; c=str[i]; i++) hash ^= hsh_tbls[i&3][c];` – Nash Gold Oct 05 '20 at 19:22

0 Answers0