Practical 7: a Hash Table with Separate Chaining

Chapter Thirty-One

Syllabus topic Module 2, practical 7, "Hash Table: Write a program to: Implement a hash table with separate chaining for collision handling. Store and retrieve data from the hash table."

Pages 212 to 223 of 297

Aim

To implement a hash table with separate chaining for collision handling, and to store data in it and retrieve it.

The idea

An array finds item n in one step, by arithmetic on the index. A hash table finds the item for a key in one step, by arithmetic on the key.

key "Aarti"  --hash-->  1234567  --% 7-->  bucket 4

buckets:
  0:
  1:  ("Divya", 55)
  2:
  3:
  4:  ("Aarti", 78) -> ("Eshan", 67)      <- two keys, one bucket: a CHAIN
  5:  ("Chetan", 90)
  6:

Three parts, and each has its own job:

Part	What it does
the hash function	turns a key of any kind into a whole number
the bucket index	that number modulo the number of buckets
collision handling	what to do when two keys land in the same bucket

MU names separate chaining as the collision handling, which means each bucket holds a list of the pairs that landed there.

A hash function, written out

def simple_hash(key):
    """Add the character codes. Simple, and bad, which the next section shows."""
    total = 0
    for character in str(key):
        total += ord(character)
    return total


def polynomial_hash(key, base=31):
    """Multiply by a base at each step, so POSITION matters."""
    total = 0
    for character in str(key):
        total = total * base + ord(character)
    return total


for name in ["Aarti", "Divya", "Chetan", "abc", "cba", "bca"]:
    print(f"  {name:<8} sum of codes {simple_hash(name):>8}   "
          f"polynomial {polynomial_hash(name):>14}")

print()
print("look at abc, cba and bca: the sum is the SAME for all three,")
print("because addition does not care about order. The polynomial differs.")

  Aarti    sum of codes      497   polynomial       63031847
  Divya    sum of codes      509   polynomial       66044729
  Chetan   sum of codes      595   polynomial     2017322785
  abc      sum of codes      294   polynomial          96354
  cba      sum of codes      294   polynomial          98274
  bca      sum of codes      294   polynomial          97344

look at abc, cba and bca: the sum is the SAME for all three,
because addition does not care about order. The polynomial differs.

There is the difference between a bad hash function and a good one. Adding the character codes gives the same number for any anagram, so abc, cba and bca all collide, and in real data anagrams and rearrangements are common. Multiplying by a base at each step makes the position of each character matter.

The 31 is a small odd prime, and the choice matters less than people think; what matters is that the multiplication mixes the bits.

The class

"""A hash table with separate chaining, for Major Practical 3, Module 2."""


def string_hash(key, base=31):
    """A polynomial hash, written out so the bucket numbers are reproducible.

    NOTE: Python's built in hash() of a str is salted per process, so it gives
    a different number in every run. A textbook example needs a stable one.
    """
    total = 0
    for character in str(key):
        total = total * base + ord(character)
    return total


class HashTable:
    """Separate chaining: each bucket is a list of (key, value) pairs."""

    def __init__(self, buckets=7, load_limit=0.75):
        if buckets <= 0:
            raise ValueError("there must be at least one bucket")
        self.buckets = [[] for _ in range(buckets)]
        self.count = 0
        self.load_limit = load_limit
        self.comparisons = 0
        self.rehashes = 0

    # ---- the three parts -------------------------------------------------
    def bucket_of(self, key):
        """The index this key belongs in."""
        return string_hash(key) % len(self.buckets)

    def load_factor(self):
        """Items divided by buckets. The single number that predicts the cost."""
        return self.count / len(self.buckets)

    # ---- storing ---------------------------------------------------------
    def put(self, key, value):
        """Store or update. Returns the bucket used and whether it collided."""
        index = self.bucket_of(key)
        chain = self.buckets[index]
        collided = len(chain) > 0
        for position, (existing, _) in enumerate(chain):
            if existing == key:
                chain[position] = (key, value)      # an update, not a second entry
                return index, False
        chain.append((key, value))
        self.count += 1
        if self.load_factor() > self.load_limit:
            self._rehash()
        return index, collided

    def __setitem__(self, key, value):
        self.put(key, value)

    # ---- retrieving ------------------------------------------------------
    def get(self, key, default=None):
        """The value for a key. Counts the comparisons made inside the chain."""
        self.comparisons = 0
        chain = self.buckets[self.bucket_of(key)]
        for existing, value in chain:
            self.comparisons += 1
            if existing == key:
                return value
        return default

    def __getitem__(self, key):
        marker = object()
        value = self.get(key, marker)
        if value is marker:
            raise KeyError(key)
        return value

    def __contains__(self, key):
        marker = object()
        return self.get(key, marker) is not marker

    def __len__(self):
        return self.count

    # ---- removing --------------------------------------------------------
    def remove(self, key):
        """Delete a key. Raises KeyError if it is not there."""
        chain = self.buckets[self.bucket_of(key)]
        for position, (existing, _) in enumerate(chain):
            if existing == key:
                del chain[position]
                self.count -= 1
                return True
        raise KeyError(key)

    # ---- growing ---------------------------------------------------------
    def _rehash(self):
        """Double the buckets and put every pair back. Every index changes."""
        old = self.buckets
        self.buckets = [[] for _ in range(len(old) * 2)]
        self.count = 0
        self.rehashes += 1
        for chain in old:
            for key, value in chain:
                index = self.bucket_of(key)
                self.buckets[index].append((key, value))
                self.count += 1

    # ---- looking at it ---------------------------------------------------
    def show(self):
        lines = []
        for index, chain in enumerate(self.buckets):
            if chain:
                items = " -> ".join(f"({k!r}, {v!r})" for k, v in chain)
                lines.append(f"  {index:>3}: {items}")
            else:
                lines.append(f"  {index:>3}:")
        return "\n".join(lines)

    def chain_lengths(self):
        return [len(chain) for chain in self.buckets]

    def statistics(self):
        lengths = self.chain_lengths()
        used = sum(1 for n in lengths if n)
        return {
            "items": self.count,
            "buckets": len(self.buckets),
            "load factor": round(self.load_factor(), 3),
            "buckets used": used,
            "buckets empty": len(lengths) - used,
            "longest chain": max(lengths),
            "average non-empty chain": round(self.count / used, 3) if used else 0,
        }

Practical 7: a Hash Table with Separate Chaining

Storing and retrieving

from hashtable import HashTable

table = HashTable(buckets=7)

marks = [("Aarti", 78), ("Divya", 55), ("Chetan", 90),
         ("Eshan", 67), ("Farhan", 41), ("Gauri", 83)]

print("storing:")
for name, mark in marks:
    index, collided = table.put(name, mark)
    note = "  COLLISION, chained" if collided else ""
    print(f"  {name:<8} -> bucket {index}{note}")

print()
print("the table:")
print(table.show())

print()
print("retrieving:")
for name in ["Aarti", "Chetan", "Gauri", "Nobody"]:
    value = table.get(name)
    found = value if value is not None else "not found"
    print(f"  {name:<8} -> {str(found):<12} after {table.comparisons} "
          f"comparison(s) in its chain")

print()
print("the dictionary style operations work too:")
table["Hiral"] = 72
print("  table['Hiral'] =", table["Hiral"])
print("  'Aarti' in table:", "Aarti" in table)
print("  'Nobody' in table:", "Nobody" in table)
print("  len(table):", len(table))

Practical 7: a Hash Table with Separate Chaining

storing:
  Aarti    -> bucket 4
  Divya    -> bucket 2
  Chetan   -> bucket 2  COLLISION, chained
  Eshan    -> bucket 0
  Farhan   -> bucket 1
  Gauri    -> bucket 0  COLLISION, chained

the table:
    0: ('Gauri', 83)
    1:
    2:
    3:
    4:
    5:
    6:
    7: ('Eshan', 67)
    8: ('Farhan', 41)
    9: ('Divya', 55) -> ('Chetan', 90)
   10:
   11: ('Aarti', 78)
   12:
   13:

retrieving:
  Aarti    -> 78           after 1 comparison(s) in its chain
  Chetan   -> 90           after 2 comparison(s) in its chain
  Gauri    -> 83           after 1 comparison(s) in its chain
  Nobody   -> not found    after 1 comparison(s) in its chain

the dictionary style operations work too:
  table['Hiral'] = 72
  'Aarti' in table: True
  'Nobody' in table: False
  len(table): 7

Read the comparison counts. A retrieval compares only inside its own bucket, so it took one comparison where the bucket held one pair and more where a chain had formed. That is the whole reason a hash table is fast: the bucket is found by arithmetic and only its own short chain is searched.

An update is not a second entry

from hashtable import HashTable

table = HashTable(buckets=7)
table.put("Aarti", 78)
print("after storing 78:", table.get("Aarti"), " len", len(table))

table.put("Aarti", 91)
print("after storing 91:", table.get("Aarti"), " len", len(table),
      " <- still one item, the value was REPLACED")
print()
print(table.show())

after storing 78: 78  len 1
after storing 91: 91  len 1  <- still one item, the value was REPLACED

    0:
    1:
    2:
    3:
    4: ('Aarti', 91)
    5:
    6:

put searches the chain first and replaces the pair if the key is already there. Without that search, the same key would appear twice in the chain and get would return whichever came first, which is a real bug and an easy one to write.

A collision, and how likely it is

from hashtable import HashTable, string_hash

table = HashTable(buckets=7)
names = ["Aarti", "Divya", "Chetan", "Eshan", "Farhan", "Gauri", "Hiral",
         "Imran", "Jyoti"]

print(f"  {'key':<8} {'hash':>16} {'% 7':>5}")
for name in names:
    print(f"  {name:<8} {string_hash(name):>16} {string_hash(name) % 7:>5}")

print()
seen = {}
for name in names:
    index = string_hash(name) % 7
    seen.setdefault(index, []).append(name)

for index in sorted(seen):
    if len(seen[index]) > 1:
        print(f"  bucket {index} is shared by {', '.join(seen[index])}"
              f"  <- a COLLISION")

Practical 7: a Hash Table with Separate Chaining

  key                  hash   % 7
  Aarti            63031847     4
  Divya            66044729     2
  Chetan         2017322785     2
  Eshan            67251975     0
  Farhan         2097121342     1
  Gauri            68575794     0
  Hiral            69734236     5
  Imran            70776923     0
  Jyoti            72055637     3

  bucket 0 is shared by Eshan, Gauri, Imran  <- a COLLISION
  bucket 2 is shared by Divya, Chetan  <- a COLLISION

Collisions are not an accident. With more keys than buckets they are certain, by the pigeonhole principle, and long before that they are likely:

def collision_probability(keys, buckets):
    """The chance that at least two of `keys` keys share a bucket."""
    if keys > buckets:
        return 1.0
    no_collision = 1.0
    for i in range(keys):
        no_collision *= (buckets - i) / buckets
    return 1 - no_collision


print(f"  {'buckets':>8} {'keys':>6} {'chance of a collision':>23}")
for buckets, keys in [(7, 2), (7, 4), (23, 5), (23, 10), (100, 10),
                      (365, 23), (1000, 40)]:
    chance = collision_probability(keys, buckets)
    print(f"  {buckets:>8} {keys:>6} {chance * 100:>22.1f}%")

print()
print("the 365 and 23 row is the birthday problem: in a class of 23,")
print("it is more likely than not that two students share a birthday.")
print("a hash table meets the same arithmetic, which is why collision")
print("handling is part of the design and not an afterthought.")

   buckets   keys   chance of a collision
         7      2                   14.3%
         7      4                   65.0%
        23      5                   37.3%
        23     10                   90.0%
       100     10                   37.2%
       365     23                   50.7%
      1000     40                   54.6%

the 365 and 23 row is the birthday problem: in a class of 23,
it is more likely than not that two students share a birthday.
a hash table meets the same arithmetic, which is why collision
handling is part of the design and not an afterthought.

That is why MU's row says "for collision handling". A design without it is not a hash table.

A good hash function against a bad one, measured

from hashtable import HashTable


def bad_hash(key):
    """Only the first character. Deliberately terrible."""
    return ord(str(key)[0])


def sum_hash(key):
    """The sum of the character codes."""
    return sum(ord(c) for c in str(key))


def polynomial_hash(key, base=31):
    total = 0
    for character in str(key):
        total = total * base + ord(character)
    return total


names = ["Aarti", "Anita", "Amit", "Ajay", "Divya", "Deepak", "Chetan",
         "Eshan", "Farhan", "Gauri", "Hiral", "Imran", "Jyoti", "Kiran",
         "Lata", "Manish", "Nisha", "Omkar", "Pooja", "Rahul"]
buckets = 7

print(f"  {'hash function':<14} {'chain lengths':<22} {'longest':>8} {'empty':>7}")
for label, function in [("first letter", bad_hash), ("sum of codes", sum_hash),
                        ("polynomial", polynomial_hash)]:
    lengths = [0] * buckets
    for name in names:
        lengths[function(name) % buckets] += 1
    print(f"  {label:<14} {str(lengths):<22} {max(lengths):>8} "
          f"{lengths.count(0):>7}")

print()
print(f"{len(names)} keys into {buckets} buckets, so a perfect spread is about "
      f"{len(names) / buckets:.1f} per bucket")
print("the longest chain is what a lookup costs in the worst case")

Practical 7: a Hash Table with Separate Chaining

  hash function  chain lengths           longest   empty
  first letter   [2, 2, 6, 2, 2, 4, 2]         6       0
  sum of codes   [3, 2, 3, 2, 4, 3, 3]         4       0
  polynomial     [5, 1, 3, 3, 1, 3, 4]         5       0

20 keys into 7 buckets, so a perfect spread is about 2.9 per bucket
the longest chain is what a lookup costs in the worst case

Read that honestly, because it does not say what a textbook would predict.

The first letter hash is the worst, at 6, and the reason is visible in the data: four of these names begin with A, so all four are forced into one bucket. That is a structural fault and it will show on any list of names.

The sum of codes came out best on this sample, at 4, and the polynomial second, at 5. Twenty keys in seven buckets is far too small a sample to rank two reasonable hash functions, and this run is a good reminder not to claim otherwise from one measurement.

So why is the sum of codes still the wrong choice? Because its fault is structural, not statistical, and the next listing makes it show.

def sum_hash(key):
    return sum(ord(c) for c in str(key))


def polynomial_hash(key, base=31):
    total = 0
    for character in str(key):
        total = total * base + ord(character)
    return total


groups = [["Anil", "Lina", "Nail", "Lani"],
          ["listen", "silent", "enlist", "tinsel"],
          ["MU101", "MU110", "MU011"]]

print("  keys that are rearrangements of each other:")
for group in groups:
    sums = {sum_hash(k) for k in group}
    polys = {polynomial_hash(k) for k in group}
    print(f"    {', '.join(group)}")
    print(f"      distinct sums       : {len(sums)} out of {len(group)}")
    print(f"      distinct polynomials: {len(polys)} out of {len(group)}")

print()
print("every rearrangement of the same characters gets the SAME sum, so they")
print("all collide, whatever the bucket count. The polynomial separates them.")

  keys that are rearrangements of each other:
    Anil, Lina, Nail, Lani
      distinct sums       : 1 out of 4
      distinct polynomials: 4 out of 4
    listen, silent, enlist, tinsel
      distinct sums       : 1 out of 4
      distinct polynomials: 4 out of 4
    MU101, MU110, MU011
      distinct sums       : 1 out of 3
      distinct polynomials: 3 out of 3

every rearrangement of the same characters gets the SAME sum, so they
all collide, whatever the bucket count. The polynomial separates them.

That is the disqualifying fault. Adding the codes gives every rearrangement of the same characters one number, so they collide in every table of every size, and no amount of rehashing helps. Real keys contain rearrangements all the time: names, product codes, roll numbers.

So the lesson for the journal is in two parts. Judge a hash function by the longest chain it produces on your own data, and, before that, reject one whose collisions are built into its arithmetic rather than left to chance.

Practical 7: a Hash Table with Separate Chaining

The load factor, and rehashing

The load factor is the number of items divided by the number of buckets. It is the one number that predicts the cost of a lookup.

from hashtable import HashTable

table = HashTable(buckets=4, load_limit=0.75)
names = ["Aarti", "Divya", "Chetan", "Eshan", "Farhan", "Gauri", "Hiral",
         "Imran", "Jyoti", "Kiran", "Lata", "Manish"]

print(f"  {'after':<10} {'items':>6} {'buckets':>8} {'load':>6} "
      f"{'longest chain':>14} {'rehashes':>9}")
for name in names:
    table.put(name, len(name))
    stats = table.statistics()
    print(f"  {name:<10} {stats['items']:>6} {stats['buckets']:>8} "
          f"{stats['load factor']:>6} {stats['longest chain']:>14} "
          f"{table.rehashes:>9}")

print()
print("the buckets doubled whenever the load factor passed 0.75,")
print("which is what keeps the chains short and the lookup O(1)")
print()
for key, value in table.statistics().items():
    print(f"  {key:<24} {value}")

  after       items  buckets   load  longest chain  rehashes
  Aarti           1        4   0.25              1         0
  Divya           2        4    0.5              1         0
  Chetan          3        4   0.75              2         0
  Eshan           4        8    0.5              2         1
  Farhan          5        8  0.625              2         1
  Gauri           6        8   0.75              2         1
  Hiral           7       16  0.438              2         2
  Imran           8       16    0.5              2         2
  Jyoti           9       16  0.562              2         2
  Kiran          10       16  0.625              2         2
  Lata           11       16  0.688              2         2
  Manish         12       16   0.75              2         2

the buckets doubled whenever the load factor passed 0.75,
which is what keeps the chains short and the lookup O(1)

  items                    12
  buckets                  16
  load factor              0.75
  buckets used             9
  buckets empty            7
  longest chain            2
  average non-empty chain  1.333

Read the buckets column: it doubles whenever the load factor passes the limit. Rehashing is not optional in a hash table that grows, and the reason is in the cost table below.

Rehashing means every key has to be placed again, because the bucket index is the hash modulo the number of buckets, and that number has changed. A rehash is O(n), and it happens rarely enough that the average insertion is still O(1), which is what "amortised" means.

What it all costs

from hashtable import HashTable


def chain_costs(items, buckets):
    """The average and worst comparisons for a successful lookup."""
    # load_limit must be BIGGER than any load factor reached here, or the
    # table rehashes and the "1 bucket" row is not one bucket at all.
    table = HashTable(buckets=buckets, load_limit=float("inf"))
    for n in range(items):
        table.put(f"key{n:05d}", n)
    lengths = table.chain_lengths()
    total = sum(length * (length + 1) // 2 for length in lengths)
    return total / items, max(lengths)


print(f"  {'items':>7} {'buckets':>8} {'load':>6} {'avg comparisons':>17} "
      f"{'worst':>7}")
for items, buckets in [(100, 1000), (500, 1000), (1000, 1000),
                       (2000, 1000), (10000, 1000), (10000, 1)]:
    average, worst = chain_costs(items, buckets)
    print(f"  {items:>7} {buckets:>8} {items / buckets:>6.1f} "
          f"{average:>17.2f} {worst:>7}")

print()
print("the average comparisons track the LOAD FACTOR, not the number of items.")
print("the last row is one bucket, which is a plain linked list: O(n).")

Practical 7: a Hash Table with Separate Chaining

    items  buckets   load   avg comparisons   worst
      100     1000    0.1              1.00       1
      500     1000    0.5              1.31       3
     1000     1000    1.0              1.59       4
     2000     1000    2.0              2.20       7
    10000     1000   10.0              5.74      16
    10000        1 10000.0           5000.50   10000

the average comparisons track the LOAD FACTOR, not the number of items.
the last row is one bucket, which is a plain linked list: O(n).

Situation	Lookup cost
load factor kept small, good hash	O(1)
load factor allowed to grow	O(load factor), so O(n / buckets)
a bad hash putting everything in one bucket	O(n), a linked list

So the honest statement is: a hash table is O(1) on average, given a good hash function and a load factor kept low by rehashing, and O(n) in the worst case. The last row of that output is the worst case, made to happen.

Separate chaining against the other way

MU names separate chaining. The alternative is open addressing, where a colliding key goes into another bucket rather than into a chain, and being able to compare them is worth a mark.

class LinearProbing:
    """Open addressing: on a collision, try the next slot, and the next."""

    EMPTY = object()
    DELETED = object()

    def __init__(self, size=11):
        self.slots = [self.EMPTY] * size
        self.count = 0

    def _hash(self, key):
        total = 0
        for character in str(key):
            total = total * 31 + ord(character)
        return total % len(self.slots)

    def put(self, key, value):
        index = self._hash(key)
        probes = 0
        while probes < len(self.slots):
            here = self.slots[index]
            if here is self.EMPTY or here is self.DELETED:
                self.slots[index] = (key, value)
                self.count += 1
                return probes + 1
            if here[0] == key:
                self.slots[index] = (key, value)
                return probes + 1
            index = (index + 1) % len(self.slots)
            probes += 1
        raise OverflowError("the table is full")

    def get(self, key):
        index = self._hash(key)
        probes = 0
        while probes < len(self.slots):
            here = self.slots[index]
            if here is self.EMPTY:
                return None, probes + 1
            if here is not self.DELETED and here[0] == key:
                return here[1], probes + 1
            index = (index + 1) % len(self.slots)
            probes += 1
        return None, probes

    def remove(self, key):
        """A removed slot becomes DELETED, not EMPTY. This is the TOMBSTONE."""
        index = self._hash(key)
        for _ in range(len(self.slots)):
            here = self.slots[index]
            if here is self.EMPTY:
                return False
            if here is not self.DELETED and here[0] == key:
                self.slots[index] = self.DELETED
                self.count -= 1
                return True
            index = (index + 1) % len(self.slots)
        return False

    def show(self):
        out = []
        for i, slot in enumerate(self.slots):
            if slot is self.EMPTY:
                out.append(f"  {i:>3}: .")
            elif slot is self.DELETED:
                out.append(f"  {i:>3}: TOMBSTONE")
            else:
                out.append(f"  {i:>3}: {slot[0]!r} = {slot[1]!r}")
        return "\n".join(out)


table = LinearProbing(size=11)
for name, mark in [("Aarti", 78), ("Divya", 55), ("Chetan", 90),
                   ("Eshan", 67), ("Farhan", 41)]:
    probes = table.put(name, mark)
    print(f"  put {name:<8} took {probes} probe(s)")

print()
print(table.show())
print()
for name in ["Aarti", "Farhan", "Nobody"]:
    value, probes = table.get(name)
    print(f"  get {name:<8} -> {str(value):<6} in {probes} probe(s)")

print()
print("now the reason a tombstone is needed:")
table.remove("Divya")
print("  removed Divya, and its slot is a TOMBSTONE, not empty")
for name in ["Aarti", "Chetan", "Farhan"]:
    value, probes = table.get(name)
    print(f"  get {name:<8} still works -> {value}")
print("  if the slot had been set to EMPTY, a search that probed past it")
print("  would stop there and report a key that is still present as missing.")

Practical 7: a Hash Table with Separate Chaining

  put Aarti    took 1 probe(s)
  put Divya    took 1 probe(s)
  put Chetan   took 1 probe(s)
  put Eshan    took 2 probe(s)
  put Farhan   took 1 probe(s)

    0: 'Eshan' = 67
    1: .
    2: .
    3: 'Divya' = 55
    4: .
    5: 'Chetan' = 90
    6: .
    7: .
    8: 'Farhan' = 41
    9: .
   10: 'Aarti' = 78

  get Aarti    -> 78     in 1 probe(s)
  get Farhan   -> 41     in 1 probe(s)
  get Nobody   -> None   in 2 probe(s)

now the reason a tombstone is needed:
  removed Divya, and its slot is a TOMBSTONE, not empty
  get Aarti    still works -> 78
  get Chetan   still works -> 90
  get Farhan   still works -> 41
  if the slot had been set to EMPTY, a search that probed past it
  would stop there and report a key that is still present as missing.

The tombstone is the point of that listing. In open addressing a search stops at the first empty slot, so emptying a slot in the middle of a probe sequence cuts the sequence in half and hides everything after it. Marking it DELETED keeps the search going while still allowing the slot to be reused.

	Separate chaining, MU's	Open addressing
A collision goes	into a list in the same bucket	into another slot
Load factor may exceed 1	yes	no, never
Deletion	remove from the list	needs a tombstone
Extra memory	a list per bucket	none
Cache behaviour	worse, the chain is scattered	better, the slots are contiguous
Simpler to write	yes	no

Separate chaining is simpler, allows a load factor above 1, and deletes cleanly. That is why it is what MU asks for, and why it is what you should write.

Where a hash table is the right answer

from hashtable import HashTable

print("a hash table gives, on average:")
print("  lookup by key      O(1)")
print("  insert             O(1)")
print("  delete             O(1)")
print("  keys in order      O(n log n), it has to sort them")
print("  the smallest key   O(n), it has to look at all of them")
print()
print("a binary search tree gives:")
print("  lookup by key      O(log n)")
print("  insert             O(log n)")
print("  keys in order      O(n), the in-order walk, FREE")
print("  the smallest key   O(log n), the leftmost node")
print()
print("so: a hash table when you look up by key and do not care about order;")
print("    a BST when you need the order as well.")

Practical 7: a Hash Table with Separate Chaining

a hash table gives, on average:
  lookup by key      O(1)
  insert             O(1)
  delete             O(1)
  keys in order      O(n log n), it has to sort them
  the smallest key   O(n), it has to look at all of them

a binary search tree gives:
  lookup by key      O(log n)
  insert             O(log n)
  keys in order      O(n), the in-order walk, FREE
  the smallest key   O(log n), the leftmost node

so: a hash table when you look up by key and do not care about order;
    a BST when you need the order as well.

That contrast is MU's Course Objective 8 in one page. And Python's own dict and set are hash tables, which is why x in some_dict is O(1) while x in some_list is O(n), as [Practical 7: a Common Member, and a Dictionary Sorted by Value] measured.

Procedure

Save hashtable.py with a hash function written out by hand, not Python's hash, and the

HashTable class with a list of lists as buckets.

Write bucket_of as the hash modulo the number of buckets.
Write put so that it searches the chain first and replaces an existing key rather than adding

a second entry.

Write get counting the comparisons it makes inside the chain, and remove raising KeyError.
Write show to print every bucket with its chain, including the empty ones.
Store at least six pairs, printing the bucket each one went to and marking the collisions.
Print the whole table and then retrieve several keys, printing the comparison count each time.
Store the same key twice with different values and show that the length does not change.
Compare three hash functions on the same twenty keys, tabulate the chain lengths and the longest

chain, then show separately that the sum of codes gives one number for every rearrangement.

Add rehashing at a load factor of 0.75 and print the load factor and the bucket count after each

insertion.

Result

Six pairs stored into seven buckets, with the bucket printed for each and the collisions marked. The whole table printed with its chains. Retrieval took one comparison in a bucket of one pair and more in a chain, confirming that only the key's own bucket is searched. Storing an existing key replaced its value and left the length unchanged. On twenty names into seven buckets the longest chains were 6 for the first-letter hash, 4 for the sum of codes and 5 for the polynomial, reported as measured rather than as predicted: twenty keys in seven buckets cannot rank two reasonable hash functions. The sum of codes was nevertheless shown to be disqualified, because every rearrangement of the same characters hashes to one number, so Anil, Lina, Nail and Lani collide in any table of any size. The collision probability table reproduced the birthday problem: 23 keys in 365 buckets collide more often than not. With a load limit of 0.75 the bucket count doubled whenever the load factor passed it, and the longest chain stayed short. Isolating the load factor showed the average comparisons tracking the load factor rather than the number of items: 1.00 at a load of 0.1, 1.59 at 1.0, 5.74 at 10, and 5000.50 with a single bucket, which is n over two and is exactly a linked list.

Practical 7: a Hash Table with Separate Chaining

Where marks are lost

Using Python's hash() on strings in an example whose bucket numbers are printed. It is salted

per process, so the output differs every run.

Not searching the chain in put, so the same key appears twice and get returns the older

value.

No collision in the test data. The exercise is collision handling; the entry must show one.
Calling a collision an error. It is expected, and with more keys than buckets it is certain.
Judging a hash function by how clever it looks instead of by the longest chain it produces.
Adding the character codes as the hash, which gives every anagram the same bucket.
No load factor and no rehashing, so the chains grow and the lookup quietly becomes O(n).
Saying a hash table is O(1) without "on average, with a good hash and a low load factor".
Confusing separate chaining with open addressing. MU asked for chaining.

For the journal

The aim in MU's words, both bullets. The bucket picture with one chain visible in it. The three part table: hash function, bucket index, collision handling. Then the hash function written out, with the abc, cba, bca run showing why adding the codes is wrong. Then the class, and the storing run with the bucket number and the collisions marked, and the whole table printed. Then the retrieval run with the comparison counts. Then the collision probability table with the birthday problem row, and one sentence: a collision is expected, not an accident. Then the three hash functions compared by longest chain, and the load factor run showing the buckets doubling. The conclusion: the hash gives the bucket by arithmetic and only that bucket's chain is searched, so a lookup costs the length of one chain, which the load factor keeps near one.

Practical 7: a Hash Table with Separate Chaining

Quick revision

Three parts: a hash function, the bucket index (hash modulo the bucket count), and

collision handling.

Separate chaining: each bucket holds a list of (key, value) pairs.
Write your own hash function for an example: Python's hash() of a string is salted per process.
Adding the character codes is a bad hash: every anagram collides. Multiply by a base each step so

position matters.

Judge a hash function by the longest chain on your own data, and reject outright any whose

collisions are built into the arithmetic: the sum of codes collides on every rearrangement, in every table of every size.

put must search the chain first and replace, or a key appears twice.
get searches only its own bucket's chain.
A collision is expected. With more keys than buckets it is certain (pigeonhole). 23 keys in 365

buckets collide more often than not, which is the birthday problem.

load factor = items / buckets. It is the number that predicts the lookup cost.
Rehashing: when the load factor passes a limit (0.75 is usual), double the buckets and place

every key again, because the index depends on the bucket count. O(n), rare, so insertion stays O(1) amortised.

Cost: O(1) average, O(n) worst, and the worst case is everything in one bucket.
Open addressing is the alternative: a colliding key goes to another slot, the load factor cannot

exceed 1, and deletion needs a tombstone or a probe sequence is cut short.

Python's dict and set are hash tables, which is why in on them is O(1).

Questions you should be able to answer

1. What are the three parts of a hash table? A hash function that turns a key into a number, the modulo that turns the number into a bucket index, and a way of handling two keys landing in the same bucket.

2. What is separate chaining? Each bucket holds a list of the pairs that hashed to it, and a lookup searches only that list.

3. Why is adding the character codes a bad hash function? Because addition ignores order, so every anagram gives the same number. abc, cba and bca all land in the same bucket.

4. How do you judge a hash function? By the longest chain it produces on your own data, because that is what a lookup costs in the worst case. But first reject any whose collisions are structural: measured here, the sum of codes gave the shortest chains on twenty names and is still wrong, because every rearrangement of the same characters hashes to one number.

Practical 7: a Hash Table with Separate Chaining

5. What is the load factor and why does it matter? Items divided by buckets. The average number of comparisons in a lookup tracks it, so keeping it near 1 keeps the lookup O(1).

6. What is rehashing and why is it needed? Doubling the bucket count and placing every key again. It is needed because the index is the hash modulo the bucket count, so every index changes when the count does, and it keeps the chains short.

7. Is a collision an error? No. It is expected, and once there are more keys than buckets it is certain by the pigeonhole principle. Long before that it is likely: 23 keys in 365 buckets collide more often than not.

8. What does a lookup cost? O(1) on average, given a good hash function and a load factor kept low. O(n) in the worst case, when every key lands in one bucket and the table is a linked list.

9. Why must put search the chain before appending? Otherwise storing an existing key adds a second pair with the same key, and get returns whichever it finds first.

10. What is a tombstone, and which method needs one? A marker left where a pair was deleted, needed by open addressing, because a search stops at the first empty slot and emptying a slot mid-sequence would hide every key after it. Separate chaining does not need one.

11. When would you choose a BST over a hash table? When the order of the keys matters. A BST gives the sorted order free in an in-order walk and the smallest key in O(log n); a hash table has to sort, at O(n log n), and scan for the smallest.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.

Syllabus for Major Practical 3

Report or request