What Hashing Buys and What It Gives Up

Read the second column of that table. Six of the seven questions cost O(m + n) on a hash table, which means examining the entire structure. These are not slow operations; they are operations the structure cannot do, answered only by giving up and looking at everything.

A question that asks for a comparison with a binary search tree is asking for this list.

What else it gives up

The worst case is O(n), not O(1). Every figure above is an average. One bad hash function or one hostile key set collapses the table to a list, as chapter 104 printed.

Memory. A hash table must be kept well under full, so slots are deliberately empty; chaining adds a pointer per record on top.

M = 1009

print("space at various load factors, 1009 buckets:")
print("%10s %10s %16s %22s"
      % ("alpha", "records", "empty buckets", "slots per record"))
for alpha in (0.5, 0.66, 0.75, 1.0):
    n = int(alpha * M)
    print("%10.2f %10d %16d %22.2f"
          % (alpha, n, M - min(n, M), M / n))

print()
print("at Python's threshold of about 0.66, a third of the table is empty")
print("by design. a sorted array wastes nothing, and a balanced tree wastes")
print("two pointers per record instead.")
print()
print("so the comparison is not 'hashing wastes space'. it is: hashing")
print("wastes EMPTY SLOTS, a tree wastes POINTERS, and a sorted array")
print("wastes nothing but cannot insert in less than O(n).")

space at various load factors, 1009 buckets:
     alpha    records    empty buckets       slots per record
      0.50        504              505                   2.00
      0.66        665              344                   1.52
      0.75        756              253                   1.33
      1.00       1009                0                   1.00

at Python's threshold of about 0.66, a third of the table is empty
by design. a sorted array wastes nothing, and a balanced tree wastes
two pointers per record instead.

so the comparison is not 'hashing wastes space'. it is: hashing
wastes EMPTY SLOTS, a tree wastes POINTERS, and a sorted array
wastes nothing but cannot insert in less than O(n).

It depends entirely on the hash function. A balanced tree needs only that keys can be compared. A hash table needs a function matched to the actual keys, and chapter 102 showed what a mismatch costs.

No partial matching. A hash table can find "Bhavesh" and cannot find "every name beginning Bh", because a prefix has a different hash from the whole key. A sorted structure or a trie does prefix search naturally. This matters for any search box.

The iteration order is unstable. Chapter 100 showed the same keys coming out in different orders from tables of different sizes, and a rehash changes it again mid-program.

The head to head table

The decision rule

Use a hash table when every question is "give me the record with this exact key". That is the majority of lookups in real programs, which is why hash tables are everywhere.

Use a balanced tree when any question involves order: ranges, nearest, sorted output, minimum, maximum, successor. Giving up O(1) for O(log n) is a small price; discovering later that the structure cannot answer the question at all is not.

Use a sorted array when the data is built once and then only read. No insertion cost to pay, no pointers, binary search, and perfect cache behaviour.

Use both when both kinds of question are asked. Real systems commonly keep a hash table for exact lookups and an ordered index for ranges over the same records. The cost is the extra memory and keeping the two consistent.

Quick revision

• Buys: O(1) average insert, search and delete, with a cost that does not grow with the number of records; a simple implementation; no ordering needed on the keys; and no sensitivity to insertion order.
• Gives up every question about order. Minimum, maximum, range, successor, sorted traversal and rank all cost O(m + n), which means examining the whole structure.
• Those are not slow operations; they are operations the structure cannot perform.
• Gives up the worst case guarantee: O(n) if the hash function fails on the keys given.
• Gives up memory: the table must be kept well under full, so at Python's threshold a third of it is empty by design, and chaining adds a pointer per record.
• Gives up partial matching: a prefix has a different hash from the key, so no prefix search.
• Gives up a stable iteration order, which changes with the table size and after every rehash.
• Decision: hash table for exact key lookups, balanced tree for anything involving order, sorted array for data built once and then read, and both together when both kinds of question are asked.

Test yourself

1. State the central advantage of hashing in one sentence. Insert, search and delete are O(1) on average, so the cost of a lookup does not depend on how many records are stored.

2. Name four advantages besides speed. A simple implementation; no ordering required on the keys, only equality and a hash; immunity to the order in which keys arrive, unlike a binary search tree; and performance that does not degrade as the data grows, provided the load factor is maintained.

3. List the specific questions a hash table cannot answer efficiently. The smallest key, the largest key, all keys in a range, the next or previous key, all keys in sorted order, and the k-th smallest key. Each costs O(m + n), which means examining the entire table.

4. Why is "it is unordered" an inadequate answer? Because it does not say what is lost. The precise statement is that six distinct and common queries fall from O(log n) on a balanced tree to O(m + n) on a hash table, which is examining everything.

5. Compare the space overheads of a hash table, an AVL tree and a sorted array. A hash table keeps slots deliberately empty, about a third of the table at a load factor of 0.66, and chaining adds a pointer per record. An AVL tree stores two pointers and a balance factor per node. A sorted array has no overhead at all but cannot insert in less than O(n).

6. Why can a hash table not do prefix matching? Because a prefix hashes to a different slot from the full key, so there is no relationship between where "Bh" would go and where "Bhavesh" is.

7. Give the decision rule. A hash table when every query is for an exact key; a balanced tree when any query involves order; a sorted array for data built once and then only read; and both a hash table and an ordered index when both kinds of query occur.

8. What must be said alongside "search is O(1)"? That it is an average. The worst case is O(n), reached when the hash function fails to spread the keys actually given.