Hash displace and compress
Hash displace and compress
Main paper can be found here.
- CHD algorithm for generating perfect hash functions
- input is a set of 'n' keys, to be mapped to a space of 'm' numbers
- 2-level hashing approach
- first hash puts all input keys into 'r' buckets
- then there'll be multiple random hash functions
- out of which, one will be allocated to a given bucket
- 2 parameters controlling the behavior
- lambda - number of keys per bucket (r = ceil(n / lambda))
- alpha - table load factor (m = ceil(n / alpha)
- in practice, heuristic hash functions proposed by Jenkins in "Algorithm Alley: Hash functions" Dr.Dobbs article is being used
- also supports k-perfect hash functions (but not my interest currently!)