Content
A hash table, or hash map, is a data structure h containing <key, value> pairs. In absence of key conflicts, given a key k, h[k] can be retrieved in time O(1). On average, hash tables are more efficient than search trees for locating values.
Hash Table Operations
- search: O(1) when there is no key conflict
- insert: O(1) amortized for some hash functions
- delete: O(1) amortized for some hash functions
Hash Function
Hash function maps a key directly to its address in the hash table.
Requirements of hash functions:
- Uniform distribution, to reduce collision possibility
- Avoid clustering to improve lookup efficiency
Frequently used hashing functions:
- modular hashing: h(k) k % m, for some m. m is usually the number of buckets
- multiplicative hashing: multiply k by a very large number: h(k) = floor(m * frac(k*a)), where k is the integer key, a is a real number, frac() gets the fractional part of a real number, and floor returns the next smallest integer. This is more prone to clustering.
- Cyclic redundancy checks (CRC): Suitable for longer stream of data, h(k) = CRC(stream-of-data-so-far)
- Cryptographic hash functions: make it computationally infeasible to get key from hash.
- Pre-compiled hash, if keys are available beforehand.