CBHTs: choosing the no. of buckets
The load factor of a hash table is the average number of entries per bucket, n/m.
If n is (roughly) predictable, choose m such that the load factor is likely to be between 0.5 and 0.75.
- A low load factor wastes space.
- A high load factor tends to cause some buckets to have many entries.
Choose m to be a prime number.
- Typically the hash function performs modulo-m arithmetic. If m is prime, the entries are more likely to be distributed evenly over the buckets, regardless of any pattern in the keys.