Skip to main content

Hashing and different hash functions

Short answer

Hashing maps a key to a table address via a hash function, enabling O(1) average operations. Common hash functions include the division method (k mod m), mid-square (middle digits of k²), folding (split key into parts and add), digit extraction, and the multiplication method (floor(m*(k*A mod 1))).

Define hashing and demonstrate different hash functions.

Hashing is a technique of storing and retrieving records directly by computing their address from the key with a hash function h(k). The records are kept in a hash table of size m, so insert, search and delete take O(1) time on average. When h(k1) = h(k2) for different keys, a collision occurs and must be resolved.

A good hash function is easy to compute and spreads keys uniformly over 0 to m−1.

Common hash functions

  1. Division method: h(k) = k mod m. Choose m as a prime not close to a power of 2. Example: k = 1234, m = 11: h = 1234 mod 11 = 2.
  2. Mid-square method: square the key and take the middle digits. Example: k = 4567, k² = 20857489; the middle two digits are 57, so h(k) = 57.
  3. Folding method: divide the key into equal parts and add them, ignoring the final carry if required. Example: k = 123456789 gives 123 + 456 + 789 = 1368; keeping the last three digits h(k) = 368. (Boundary folding reverses alternate parts before adding.)
  4. Digit extraction: pick selected digits of the key. Example: take 1st, 3rd and 5th digits of 98765432: 9, 7, 5, giving h(k) = 975.
  5. Multiplication method: h(k) = ⌊m·(k·A mod 1)⌋ with 0 < A < 1 (for example A ≈ 0.618).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 8 questions →