The Hash Table ADT

is_empty on a new table: True
   insert Aarti     -> inserted
   insert Bhavesh   -> inserted
   insert Chetna    -> inserted
   insert Devdatta  -> inserted
   insert Esha      -> inserted

size             : 5
search Chetna    : 91
search Farhan    : MISSING (absent, a distinct value)
contains Esha    : True

insert Aarti again: replaced - a repeat REPLACES
Aarti is now      : 82
size is unchanged : 5

delete Devdatta  : True
delete Devdatta  : False - again, declared not an error
size             : 4

a stored None is still distinguishable from absent:
   search Gauri  : None  contains: True
   search Farhan : MISSING  contains: False

Every operation on that table did one hash calculation and then looked only inside one bucket. The number of records stored never entered into it.

The order is not merely unspecified. It changes.

class HashTable:
    def __init__(self, buckets=11):
        self._buckets = [[] for _ in range(buckets)]

    def insert(self, key, value):
        self._buckets[key % len(self._buckets)].append((key, value))

    def keys(self):
        return [k for chain in self._buckets for k, _v in chain]


KEYS = [15, 3, 27, 8, 41, 19, 6]

for buckets in (7, 11, 13):
    t = HashTable(buckets)
    for k in KEYS:
        t.insert(k, str(k))
    print("the same keys in a %2d bucket table come out as %s"
          % (buckets, t.keys()))

print()
print("inserted in this order      :", KEYS)
print("sorted, which a tree gives  :", sorted(KEYS))
print()
print("none of the three listings matches the insertion order,")
print("and none of them is sorted. the order is an accident of the")
print("table size and the hash function, so it must never be relied on.")

the same keys in a  7 bucket table come out as [15, 8, 3, 19, 27, 41, 6]
the same keys in a 11 bucket table come out as [3, 15, 27, 6, 8, 41, 19]
the same keys in a 13 bucket table come out as [27, 15, 41, 3, 19, 6, 8]

inserted in this order      : [15, 3, 27, 8, 41, 19, 6]
sorted, which a tree gives  : [3, 6, 8, 15, 19, 27, 41]

none of the three listings matches the insertion order,
and none of them is sorted. the order is an accident of the
table size and the hash function, so it must never be relied on.

This is the ADT's real limitation and it belongs in any comparison answer. A hash table cannot give you the smallest key, the largest key, the keys between two bounds, or the keys in order, at any price better than looking at all of them. A balanced binary search tree gives all four in O(log n). Chapter 108 sets that out properly.

A mutable key destroys the table

The rule "a key must be immutable" sounds like a language detail. It is not. A key's hash decides which bucket holds it, so if the key changes after insertion, the record is in the wrong bucket and can never be found again.

class SimpleTable:
    def __init__(self, buckets=7):
        self._buckets = [[] for _ in range(buckets)]

    def _slot(self, key):
        return sum(key) % len(self._buckets)     # a hash over a list of numbers

    def insert(self, key, value):
        self._buckets[self._slot(key)].append((key, value))

    def search(self, key):
        for k, v in self._buckets[self._slot(key)]:
            if k == key:
                return v
        return "ABSENT"

    def every_record(self):
        return [pair for chain in self._buckets for pair in chain]


t = SimpleTable()
key = [1, 2, 3]                   # a MUTABLE key
t.insert(key, "the record")

print("slot chosen at insert :", t._slot(key))
print("search finds it       :", t.search(key))
print()

key.append(10)                    # the key is changed AFTER insertion
print("the key is mutated to :", key)
print("slot it would now hash to:", t._slot(key))
print("search finds it       :", t.search(key))
print()
print("the record is still in the table:", t.every_record())
print("but it is unreachable: the hash now points at a different bucket.")
print()
print("this is why Python REFUSES a list as a dictionary key:")
refused_with = None
try:
    {}[[1, 2, 3]] = "x"
except Exception as exc:
    refused_with = type(exc).__name__
print("   a list used as a dict key raises:", refused_with)
print("   (the wording of the message differs between Python versions,")
print("    so only the exception TYPE is quoted here.)")
print("the error is not a restriction. it is the language refusing to")
print("let you build the broken table above.")

slot chosen at insert : 6
search finds it       : the record

the key is mutated to : [1, 2, 3, 10]
slot it would now hash to: 2
search finds it       : ABSENT

the record is still in the table: [([1, 2, 3, 10], 'the record')]
but it is unreachable: the hash now points at a different bucket.

this is why Python REFUSES a list as a dictionary key:
   a list used as a dict key raises: TypeError
   (the wording of the message differs between Python versions,
    so only the exception TYPE is quoted here.)
the error is not a restriction. it is the language refusing to
let you build the broken table above.

The record is in the table and cannot be found. The language's refusal to accept a list as a key is a correctness guarantee, and that is the answer to give if asked why only immutable types may be keys.

What the ADT does not settle

Deliberately, and this is the point of an ADT:

• which hash function is used, chapters 101 and 102;
• how collisions are handled, chapters 104 to 106;
• how many buckets there are and when that changes, chapter 107.

All three can be replaced without a single caller changing, because the promise, insert, search, delete, is unchanged by any of them. That is chapter 8's argument, and the hash table is its best example in this paper.

Quick revision

• The hash table ADT stores key and value pairs: insert, search, delete, contains, size, is_empty, keys.
• The same ADT is called a dictionary, a map, an associative array or a symbol table; strictly, dictionary is the ADT and hash table is one implementation.
• Insert, search and delete are O(1) AVERAGE and O(n) worst case; writing O(1) without "average" misses the distinction.
• keys() is O(m + n), because all m buckets must be examined, and the order is not specified.
• The order actually changes with the table size, so it must never be relied on.
• A hash table offers no minimum, maximum, range query or sorted walk; a balanced tree gives all four in O(log n).
• An implementation must declare what it does with a repeated key, a missing key on search, and a missing key on delete.
• A missing-key sentinel must be distinct, or a stored None becomes indistinguishable from absent.
• Keys must be immutable: a key mutated after insertion leaves its record in the wrong bucket, present but unreachable.
• The ADT fixes none of the hash function, the collision strategy or the bucket count, so all three can be changed without touching a caller.

Test yourself

1. List the hash table ADT's operations with their average and worst case costs. insert, search, delete and contains are O(1) average and O(n) worst case. size and is_empty are O(1). keys, values and items are O(m + n), where m is the bucket count.

2. Why is the worst case O(n)? If every key hashes to the same bucket the table behaves as a single list, so a search compares every record.

3. Distinguish the dictionary ADT from the hash table. Dictionary is the ADT, the promise of storing and retrieving pairs by key. A hash table is one implementation of it; a balanced binary search tree is another.

4. What order does keys() return, and why does it matter? No specified order. The chapter showed the same seven keys coming out differently from 7, 11 and 13 bucket tables, matching neither insertion order nor sorted order, so any program depending on the order is relying on an accident.

5. Why must a key be immutable? Give the failure. The key's hash chooses its bucket. The chapter mutated a list key after insertion; the record stayed in the old bucket while the hash pointed to a new one, so the record was present in the table and unreachable by search.

6. Why should a missing key not be reported as None? Because None may be a legitimate stored value, and then absent and present cannot be told apart. A distinct sentinel object is needed.

7. Name three decisions the ADT leaves to the implementation. The hash function, the collision handling strategy, and the number of buckets and when to change it.

8. Which questions can a balanced tree answer that a hash table cannot? The smallest key, the largest key, all keys in a range, and all keys in sorted order, each in O(log n) or in output-proportional time.