Chapter 12: Maps and Hash Tables

12.1Maps and the idea of hashing

So far we have reached items by position (cell 5 of an array) or in order (from the head of a list). In everyday life we look things up by name: the registrar finds a student by ID, a dictionary lists a meaning under the word, a compiler finds a variable's type from its name. The map ADT describes such lookups, and hashing makes them fast.

12.1.1Maps

Each line of a phone book holds a name, which identifies the line, and a number attached to it. Asking for Ayşe Demir's number, we have the name and want the number. The name is the key, the number the value.

Uniqueness is the heart of the definition. If a name appeared twice, "this person's number" would have no single answer. So inserting with an existing key creates no new pair but changes the existing pair's value. Values carry no such restriction: two people may share a number, two students a grade.

Figure 12.1 shows a phone book as a map. Three names pass through a function that sends them to slots 02, 01, and 14 of a table, where their numbers are stored. That function, which turns a name into a slot number, is the hash function — the real subject of this chapter.

As an abstract data type, a map says what a structure does — which operations exist and what each changes — not how. It can be implemented with an unsorted array, a sorted array, a search tree, or a hash table; all answer the same questions, at different speeds.

The hash table is the most common choice because insertion, search, and deletion take O(1) time on average: a key's value is reached as fast among a million items as among a thousand, while even binary search on a sorted array needs O(log n) comparisons. The rest of the chapter explains where this average constant time comes from and when it breaks down.

12.1.2The map ADT's operations

The map ADT has four operations: insertion, search, deletion, and update. Java's java.util.Map calls them put, get, and remove; a put with an existing key is the update.

The snippet below uses them in turn; the comments give each result.

Map<Integer, String> m = new HashMap<>();
m.put(105, "Murat");   m.put(21, "Leyla");
m.put(21, "Ali");      // update: "Leyla" → "Ali"
m.get(21);             // "Ali"
m.remove(105);         // "Murat"
m.get(88);             // null: no such key

Line 1 creates an empty map from Integer keys to String values. The declared type is the Map interface and new HashMap<>() its hash table implementation — a good habit, since switching to TreeMap later changes only this line.

Line 2 adds (105, "Murat") and (21, "Leyla"). Line 3 adds nothing: key 21 exists, so its value changes from "Leyla" to "Ali" and the map still holds two pairs. m.get(21) now returns "Ali", m.remove(105) removes that pair and returns "Murat", and m.get(88) returns null because 88 was never a key.

put also returns a value, ignored above: null for a new key, the old value after an update. This is the easiest way for code to tell the two apart.

12.1.3Constant-time access in an array

Can an array be searched in O(1) time? Not by comparing items. In an unsorted array the target could be anywhere, and linear search may check every cell, in O(n). In a sorted array binary search halves the range each step, in O(log n), and no comparison-based method does better in general.

But if we know an item's position — its index — access takes one step:

int[] sortedArr = {1, 3, 5, 7, 9};
int idx = 2;                   // index of the item we want
int item = sortedArr[idx];      // O(1): item = 5

sortedArr[idx] scans nothing: it adds index × cell size to the array's start address and goes straight there, in the same time for five items or five million. Indexed access is O(1).

Hence the idea behind the hash table: if a key can be turned directly into an array index, we reach the right cell in one step, with no comparisons. The rest of the chapter shows how, and what gets in the way.

12.1.4Indexing: the key is the index

Take the simplest case, integer keys from 0 to 9. Key k goes in cell k — 3 in A[3], 7 in A[7] — and to find a key we look only at its cell. This is indexing.

Figure 12.2 shows the key space {1, 3, 5, 6, 7, 9}: each key sits in the cell with its own number, and cells 0, 2, 4, and 8 are empty.

A successful and an unsuccessful search cost the same: each looks at a single cell. Insertion and deletion likewise change one cell.

12.1.5Direct addressing and its limits

Generalizing indexing gives direct addressing: one cell for every possible key, with key k in A[k]. Search, insertion, and deletion are O(1), with no comparisons at all.

Figure 12.3 shows the catch. Ali, Beyza, Deniz, and Onur occupy cells 0, 2, 5, and 29 of a 30-cell array: four cells used, thirty allocated, 26 empty but still taking memory.

Direct addressing has two serious limits:

• Wasted memory. A large key space needs a large array. Nine-digit student IDs need 10⁹ cells — about 4 GB even at 4 bytes per int — for a department of a few hundred students, using less than one cell in a million.
• Keys need not be integers. A string such as "Ali" or "Beyza" cannot index an array; there is no A["Ali"].

The way out is a function that compresses the large, possibly non-integer key space into a small array, mapping every key to an index from 0 to N − 1, where the array size N is proportional to the number of items stored. Such a function is a hash function.

12.1.6The hashing technique

Hashing stores items so they can be reached quickly. The key step is to find an item's position in the array fast; that position is a bucket, or under open addressing a slot. Once it is known, inserting, removing, or updating the item touches only that cell.

In Figure 12.4, the key "Ali" goes into the hash function, which produces 8, and the item is placed in bucket 8. Looking "Ali" up later repeats the calculation, gets 8 again, and goes straight to bucket 8.

Where does the 8 come from? Every Java object has a hashCode() method; for "Ali" it returns 65918. With 13 buckets we take the remainder: 65918 mod 13 = 8. A "hash function" is thus two steps — key to integer, integer to the table's range — both examined in the next section, along with how 65918 is computed.

12.2Hash functions

The hash function takes a key and produces the item's position, and the table's speed depends largely on its quality. A good one spreads keys evenly, so every operation takes a step or two; a bad one piles keys into a few buckets, and the table is no better than a list.

12.2.1What makes a good hash function

A good hash function has four properties:

• It is deterministic. The same key always gives the same index. If "Ali" goes into bucket 8 but is later sought in bucket 3, it is lost. So the function cannot depend on random numbers, the clock, or anything outside the key.
• It is fast. A slow hash throws away the table's whole advantage. We treat its cost as O(1): hashing a string takes time proportional to its length, but key length does not grow with the number of items.
• It distributes keys uniformly. When buckets fill evenly, each holds few items and fewer keys share a bucket — that is, there are fewer collisions.
• It uses the whole key. A function that sees only the first letter sends "Ali", "Ayşe", and "Ahmet" to the same bucket. If some part of the key is ignored, keys that agree elsewhere always collide.

Numbers show why the last point matters. Put "Ali", "Ayşe", and "Ahmet" into 13 buckets. Using only the first letter's code (A = 65) sends all three to bucket 65 mod 13 = 0; Java's String.hashCode(), which uses every character, puts them in buckets 8, 6, and 5. Changing only the function takes us from three collisions to none.

The worst function returns the same index for every key. Then all items share one bucket, a search walks through them in O(n), and the hash table has become a complicated linked list.

The capacity, the number of buckets N, matters too: too many buckets waste memory, too few crowd up and collide. In practice N is kept proportional to the number of items, and the table grows as items arrive (12.5.2).

12.2.2Hash codes and compression

A hash function works in two stages, shown for "Ali" in Figure 12.5.

1. Hash code: the key becomes an integer, independently of the table. In Java this is each object's hashCode(). The code knows nothing of the table's size and can be huge or negative.
2. Compression function: the hash code is reduced to an index from 0 to N − 1. This step depends on the table's size; if the table grows, the same code compresses to a different index.

The split pays off: the hash code is the key's job (String and Integer each compute their own), compression is the table's. So one table works with keys of any type, and one key fits a table of any size.

Two compression methods are common.

The division method. h(k) = k mod N: the remainder of the hash code divided by N, always from 0 to N − 1 (for negative codes see 12.3.4). It is simple and fast but sensitive to N: with a prime N, regular patterns in the keys — say, all multiples of 10 — do not pile up in the same buckets.

Why? With N = 10, k mod 10 sees only the last digit, which is 0 for every key, so the other digits have no effect — a breach of the "whole key" rule. 11 shares no factor with 10, so the remainders run 10, 9, 8, … across the buckets. In general, if the keys are multiples of d and g is the greatest common divisor of d and N, the keys can reach only 1/g of the buckets. With a prime N, g exceeds 1 only if d is a multiple of N.

The MAD method (Multiply-Add-and-Divide). h(k) = ((a·k + b) mod p) mod N, where p is a prime larger than N, and a ≠ 0 and b are chosen at random when the table is created. Multiplying and adding scramble patterns in the keys, so the spread is good even when N is not prime.

12.2.3The equals and hashCode contract

A Java hash table relies on two methods: hashCode() picks a key's bucket, and equals() tells whether a key found there really is the one sought. The two must agree, and Java states the agreement as a contract.

Four consequences follow:

• Equal objects have the same hash code. Otherwise equal keys land in different buckets, and a value inserted under a cannot be found under b.
• Equal hash codes do not imply equal objects: "Aa" and "BB" both hash to 2112. That is why the table, having reached a bucket, still compares keys with equals.
• Override both. A class that redefines (overrides) equals must override hashCode on the same fields; overriding only one breaks the contract.
• Mutable keys. If a key's equals/hashCode fields change after insertion, its new hash code points to another bucket while the item stays in the old one.

Java 16's record types get both methods right automatically:

record Student(int id, String name) {}
Map<Student, Double> grades = new HashMap<>();
grades.put(new Student(42, "Ada"), 87.5); // record: equals/hashCode built in (Java 16+)

record Student(int id, String name) {} defines an immutable class whose generated equals compares both fields and whose hashCode is computed from both. A grade inserted under new Student(42, "Ada") is found with a different new Student(42, "Ada") object, and since record fields cannot change, the mutable-key problem cannot arise.

12.2.4Forgetting hashCode

The contract is most often broken by overriding equals and forgetting hashCode. The Point class below treats points with equal coordinates as equal but has no hashCode().

class Point {
  int x, y;
  Point(int x, int y) { this.x = x; this.y = y; }
  public boolean equals(Object o) {
    return o instanceof Point p
        && x == p.x && y == p.y;
  }
  // no hashCode() -> Object's is used
}
Map<Point, String> m = new HashMap<>();
m.put(new Point(1, 2), "A");
m.get(new Point(1, 2));  // most likely null (!)

o instanceof Point p asks whether o is a Point and, if so, binds it to p; then the coordinates are compared. By this method, two new Point(1, 2) objects are equal.

Without an override, Java uses Object's hashCode(), which is based on the object's identity and usually differs for every new object. So two points with the same coordinates almost always have different identity hashes, with the result shown in Figure 12.6.

Buckets 3 and 6 are only examples; identity hashes can vary from run to run. The outcome almost never does: get looks in the wrong bucket and returns null. "Almost" matters — if two identity hashes happen to share a bucket, get succeeds and the bug hides. Bugs that make a program fail only sometimes are among the hardest to find.

Moreover, HashMap compares hash codes before calling equals on a node, so even when two such points share a bucket, differing identity hashes mean equals is never called. Without a hashCode override, however correct equals is, the map never sees the equality.

The fix is to override hashCode on the fields equals uses:

public int hashCode() {
  return Objects.hash(x, y);
}

Objects.hash(x, y) combines the fields much as String.hashCode() does: 31 · (31 · 1 + x) + y, which is 31 · 32 + 2 = 994 for (1, 2). Equal points give equal values and share a bucket, so the contract holds. Point(2, 1) gives 31 · 33 + 1 = 1024: order matters.

12.2.5Some hash functions

Here are four hash functions in common use, each with a short Java version.

Modulus (division remainder). The simplest function for integer keys:

int modulusHash(int key, int arraySize) {
  return Math.floorMod(key, arraySize);
}

Java's % takes the sign of the dividend, so a negative key can give a negative remainder; Math.floorMod always returns 0 … arraySize − 1 for a positive divisor (12.3.4).

CRC32. The cyclic redundancy check is a checksum designed to detect corrupted data in transmission; it mixes bits well enough to serve as a hash function. Java provides it in java.util.zip:

long crc32Hash(String key) {
  CRC32 crc = new CRC32();  // java.util.zip
  crc.update(key.getBytes());
  return crc.getValue();
}

The method feeds the string's bytes to a CRC32 object and returns the 32-bit result, from 0 to 2³² − 1, as a long; it still needs compressing. For "Ali" it returns 1933558706.

DJB2. A short, fast string hash by Daniel J. Bernstein:

int djb2Hash(String s) {
  int h = 5381;
  for (int i = 0; i < s.length(); i++)
    h = (h * 33) ^ s.charAt(i);
  return h;
}

Starting at 5381, each character multiplies the result by 33 and combines it with the character's code. Classic DJB2 adds (h * 33 + c); this common variant uses XOR (^, bitwise exclusive or). The multiplication soon overflows int, so results may be negative: "Ali" gives 193442657, but long strings often go negative, and a safe compression is again needed.

Java's String.hashCode(). The function Java uses for strings:

// Σ s[i] · 31^(n−1−i)
"abc".hashCode()  // 96354

For n characters it computes s[0] · 31ⁿ⁻¹ + s[1] · 31ⁿ⁻² + … + s[n−1], weighting each character by a power of 31 that depends on its position. For "abc", 97 · 31² + 98 · 31 + 99 = 93217 + 3038 + 99 = 96354. Thanks to the positional weights, "abc" and "cba" differ; simply adding the codes could not tell them apart.

Why 31? It is odd and prime. An odd multiplier does not wipe out the information in overflowing bits, whereas an even one would zero the lowest bit at every step. And 31 · h is fast to compute as (h << 5) − h, a shift and a subtraction.

12.2.6Code trace: "Ali".hashCode()

The hash method below does String.hashCode()'s calculation with an explicit loop; main applies it to "Ali" and compresses the result for 13 buckets.

// same calculation as String.hashCode():
int hash(String s) {
  int h = 0;
  for (int i = 0; i < s.length(); i++)
    h = 31 * h + s.charAt(i);
  return h;
}

// main:
int code = hash("Ali");               // 65918
int index = Math.floorMod(code, 13);  // 8

Starting from h = 0, each iteration multiplies h by 31 and adds the next character's code; Java converts the char from s.charAt(i) to its Unicode code, an integer, in the addition. In "Ali", A = 65, l = 108, i = 105. Table 12.4 lists each iteration.

The formula agrees: 65 · 31² + 108 · 31 + 105 = 62465 + 3348 + 105 = 65918. The loop never computes powers; multiplying the running total by 31 raises every earlier character's coefficient by one power. This is Horner's method for evaluating polynomials: n multiplications and n additions, O(n) time, O(1) extra space.

Finally, Math.floorMod(65918, 13): 13 · 5070 = 65910 and 65918 − 65910 = 8, so "Ali" lands in bucket 8 (Figure 12.7).

Short strings give positive results, but long ones exceed the int limit (2³¹ − 1 = 2,147,483,647). Java raises no error on overflow; the value silently wraps and may turn negative — "Sercan".hashCode() is −1821977712. Stranger still, "polygenelubricants" hashes to exactly Integer.MIN_VALUE, −2147483648, a value that exposes a trap in 12.3.4.

12.2.7Code trace: modulusHash()

Here is the division method on a 10-cell table: each of five keys gets a cell index and is written there.

int modulusHash(int key, int arraySize) {
  return Math.floorMod(key, arraySize);
}

// main:
Integer[] table = new Integer[10];
for (int k : new int[]{5, 1, 10, 26, 99}) {
  int j = modulusHash(k, table.length);
  table[j] = k;
}

Because table is an Integer array rather than int, every cell starts as null, keeping an empty cell distinct from 0. Each iteration writes the key into cell k mod 10.

No cell got two keys, but only by luck: a next key of 15 would go to cell 15 mod 10 = 5 and overwrite 5. This table ignores collisions and is for illustration only. Each insertion took O(1), the five together O(5), in a fixed space of 10 cells.

12.2.8Collisions

With 10 buckets and the division method, for example, h(5) = h(105) = 5. Two items cannot share a cell directly, so the table needs a strategy for this case.

Collisions are no accident: whenever the key space is larger than the table, a simple counting argument makes them unavoidable.

This limits what any hash function can do. For nine-digit IDs, U = 10⁹, and with 1000 buckets the fullest bucket receives at least a million possible IDs. A good function cannot prevent collisions; it can only spread the keys that actually arrive evenly. And collisions come early: 23 random keys in 365 buckets collide with probability about 0.507. This is the "birthday problem" — in a class of 23, two people probably share a birthday.

In Figure 12.9, six key-value pairs go into a 10-slot table by the division method. The first five find empty slots, but (105, Murat) wants slot 5, which holds (5, Ali).

There are two main strategies for resolving collisions:

• Separate chaining: each bucket keeps a linked list of the items that land in it, and a colliding item joins the list.
• Open addressing: all items live in the array itself, and an item arriving at an occupied slot looks for another empty one by a fixed rule.

The next two sections code and trace each strategy.

12.3Separate chaining

Separate chaining resolves collisions in the most direct way: a bucket holds every item that lands in it. Instead of one item, each bucket stores the head of a linked list called a chain; "separate" means each bucket has its own.

12.3.1The idea of chaining

Insert (5, "Ali"), (1, "Tuna"), (10, "Leyla"), (26, "Ceren"), (99, "Sena"), and (105, "Murat"), in that order, into 10 buckets with h(k) = k % 10:

• h(5) = 5: bucket 5 is empty; the node (5, "Ali") is attached to it.
• h(1) = 1: bucket 1 is empty; the node (1, "Tuna") is attached to it.
• h(10) = 0: bucket 0 is empty; the node (10, "Leyla") is attached to it.
• h(26) = 6: bucket 6 is empty; the node (26, "Ceren") is attached to it.
• h(99) = 9: bucket 9 is empty; the node (99, "Sena") is attached to it.
• h(105) = 5: bucket 5 already holds (5, "Ali") — a collision. The new node goes at the front: the bucket points to 105, and 105 to 5.

Why the front? The bucket knows only the first node, so appending means walking to the end, while prepending takes two reference assignments — new node to old head, bucket to new node — in O(1) regardless of length. But as 12.3.5 shows, insertion first checks whether the key is already in the chain, which walks the whole chain anyway; so some implementations, Java's HashMap among them, append. Both are correct.

A chained table never fills up; chains just grow. That flexibility is the method's strength, and its price is that longer chains mean slower searches, so we watch the average chain length — how full the table is.

12.3.2Hash table terminology

To ease reading the code, Figure 12.11 names the parts of the same six-pair table.

Capacity counts buckets; size counts pairs. In the figure, 5 of 10 buckets are occupied but there are 6 pairs, since one bucket holds two. Under chaining, size can exceed capacity: 10 buckets can hold 25 pairs.

12.3.3Code: the HashTable class

Here is the skeleton of a chained hash table with Integer keys and String values.

public class HashTable {
  private HashNode[] buckets;      // first nodes of the chains
  private int numBuckets, size;

  public HashTable(int capacity) {
    this.numBuckets = capacity;
    this.buckets = new HashNode[capacity];
    this.size = 0;
  }
  private class HashNode {
    private Integer key;
    private String value;
    private HashNode next;
    public HashNode(Integer key, String value) {
      this.key = key; this.value = value;
    }
  }
}

• buckets is an array of HashNode; each cell points to a chain's first node, or is null.
• numBuckets is the array's length, size the number of pairs.
• The constructor allocates the array. A new Java object array starts out all null, so no loop is needed: new HashTable(10) gives 10 empty buckets and size = 0.
• The inner class HashNode holds a key, a value, and a next reference — a singly linked list node with a key added.

The node must store the key, not just the value: a bucket can hold several pairs, and only the stored key tells which node is wanted. With values alone, we could not tell whether "Murat" or "Ali" in bucket 5 belongs to 105.

Space: N references in the array plus a key, a value, and a next per node, O(N + n) in all.

12.3.4Bucket indices and negative hash codes

getBucketIndex computes a key's bucket:

// Naive way: key % buckets.length → can be negative!
private int getBucketIndex(Integer key) {
  int h = key.hashCode();  // = key
  return Math.floorMod(h, buckets.length);
}

An Integer's hashCode() is the number itself (41 hashes to 41), which Math.floorMod compresses to the array length. The first line's comment is a warning: the naive key % buckets.length can be negative.

Java's % takes the sign of the dividend: 41 % 10 = 1, but −7 % 10 = −7, and a negative index throws ArrayIndexOutOfBoundsException. Math.floorMod always returns 0 to divisor − 1 for a positive divisor.

This matters even if keys are always positive integers: a table meant for any key type must handle keys like Strings, whose hash codes are often negative ("Sercan" hashes to −1821977712).

For a divisor n > 0, Math.floorMod behaves like this short method:

private int getBucketIndex(Integer key) {
  int h = key.hashCode();  // = key
  return Math.floorMod(h, buckets.length);
}

// equivalent of floorMod for n > 0:
static int floorMod(int x, int n) {
  int r = x % n;       // sign comes from x
  if (r < 0) r += n;   // if negative, add n
  return r;
}

Since x % n lies between −(n − 1) and n − 1, adding n to a negative result moves it into 1 … n − 1; positive results are untouched. Table 12.8 traces two calls.

Taking the absolute value, Math.abs(h) % N, almost always works, with one exception. An int spans −2147483648 to 2147483647, so the negation of Integer.MIN_VALUE = −2147483648 does not fit, and Math.abs(Integer.MIN_VALUE) overflows back to −2147483648.

12.3.5Code: put()

Insertion has three steps: find the bucket, scan the chain, and if needed add at the front.

public void put(Integer key,
                String value) {
  int bucketIndex = getBucketIndex(key);
  HashNode head = buckets[bucketIndex];
  while (head != null) {    // is the key there?
    if (head.key.equals(key)) {
      head.value = value;  // if so, update
      return;
    }
    head = head.next;
  }
  size++;
  HashNode node =
      new HashNode(key, value);
  node.next = buckets[bucketIndex];
  buckets[bucketIndex] = node;   // add at the front
}

• getBucketIndex(key) finds the bucket in O(1); no other bucket is ever examined.
• head = buckets[bucketIndex] starts at the chain's first node and, despite its name, moves along the chain in the loop.
• The while loop asks head.key.equals(key) at each node. If the key is found, only its value changes and the method returns; this is an update, so size stays the same.
• If the loop ends with head == null, the key is absent: size grows by one and a new node is created.
• node.next = buckets[bucketIndex] links the node in front of the old chain, and buckets[bucketIndex] = node points the bucket to it. The order matters.

Keys are compared with equals, not ==, which asks whether two references point to the same object. Java caches Integer objects for −128 … 127, so == seems to work there; from 128 up, equal values are usually different objects and == returns false.

Cost. Finding the bucket and adding at the front are O(1), and the scan is proportional to chain length: O(1 + chain length), constant on average while chains stay short (12.3.10).

12.3.6Code trace: put()

A 10-bucket table holds only (105, "Murat"), so size = 1. We call put(21, "Leyla"), put(41, "Sena"), and put(21, "Ali") (Table 12.9).

In the first call bucket 1 is empty, so the loop never runs and the key is known to be absent. size becomes 2, and the node (21, "Leyla") gets next = buckets[1], which is null, before the bucket is pointed at it.

In the second, 41 also lands in bucket 1: a collision. The loop sees 21 ≠ 41, advances, and reaches null. size becomes 3, and the node (41, "Sena") points to the old head 21 while the bucket points to 41. The chain is now 41 → 21; the old chain sits behind the new node.

The third call is an update. The loop passes 41, then finds 21.equals(21) true, changes the value from "Leyla" to "Ali", and returns, after two comparisons. No node is added and size stays 3.

12.3.7Code and trace: get()

Lookup is the scanning part of put:

public String get(Integer key) {
  int bucketIndex = getBucketIndex(key);
  HashNode head = buckets[bucketIndex];
  while (head != null) {
    if (head.key.equals(key))
      return head.value;       // found
    head = head.next;
  }
  return null;                 // no such key
}

The method scans only the key's own chain, returning the value if the key is found and null if the chain runs out. The cost is O(1 + chain length), and the average chain length is n / N. Three searches on the table from the previous trace (bucket 5 → 105; bucket 1 → 41 → 21):

get(105) matches at the first node. get(21) first meets 41, a different key in the same bucket — the trace of a collision — and finds 21 at the second node. get(88) finds an empty bucket and returns null in one step. Had that bucket been occupied, the whole chain would have been scanned, since absence becomes certain only at the chain's end.

12.3.8Code: remove()

Removing a node from a chain is deletion from a singly linked list: we must change the next field of the node before it, so the scan tracks the previous node too.

public String remove(Integer key) {
  int bucketIndex = getBucketIndex(key);
  HashNode head = buckets[bucketIndex];
  HashNode prev = null;
  while (head != null &&
         !head.key.equals(key)) {
    prev = head;
    head = head.next;
  }
  if (head == null) return null;   // absent
  size--;
  if (prev != null)         // middle or end
    prev.next = head.next;
  else                      // front
    buckets[bucketIndex] = head.next;
  return head.value;
}

• prev starts as null: nothing precedes the first node.
• The loop advances while the chain continues and the key does not match. Java's && skips its second test when the first is false, so head.key is never read when head == null and no NullPointerException occurs.
• Each iteration sets prev = head and head = head.next, moving both references together.
• After the loop, head == null means the key is absent and the method returns null; otherwise head is the node to delete.
• In the middle or at the end (prev != null), the previous node skips it: prev.next = head.next. At the front (prev == null), the bucket itself changes: buckets[bucketIndex] = head.next.
• size has been decremented and the removed value is returned. Nothing references the unlinked node any more, so the garbage collector reclaims it.

The cost equals get's, O(1 + chain length); unlinking is a few assignments.

12.3.9Code trace: remove()

Start again from bucket 5 → (105, "Murat") and bucket 1 → (41, "Sena") → (21, "Ali"), size = 3, and call remove(21), remove(105), and remove(88).

remove(21) deletes from the middle. No match at 41, so both references advance: prev to 41, head to 21. 21 matches and the loop ends; since prev is not null, prev.next = head.next makes 41 skip 21 and point to null.

remove(105) deletes from the front. The condition fails at the first node, so the body never runs and prev stays null; the else branch sets buckets[5] = head.next, and with nothing after 105 the bucket empties.

remove(88) fails: the bucket is empty, the loop ends at once, and null is returned with the table and size unchanged.

12.3.10The cost of chaining

Every operation on a chained table takes O(1 + chain length). How long a chain gets depends on how full the table is.

An average is not a guarantee: one bucket may be empty and another crowded. The analysis usually assumes that the hash function sends each key to any bucket with equal probability, independently of the other keys — the assumption of simple uniform hashing.

The theorem's message: keep λ below a constant — say 0.75 — and every operation costs O(1) in expectation. This is done by enlarging the table as pairs arrive, called resizing (12.5.2). Under chaining λ may exceed 1; chains just get longer and operations slower.

The worst case is different. If every key lands in one bucket, a single chain of length n makes search O(n). This happens with a bad hash function or with keys chosen to collide; simple uniform hashing guarantees only the average.

12.4Open addressing

Separate chaining creates a node per collision, scattered through memory and each carrying an extra reference. Open addressing needs none of this: all pairs live in the array itself, at most one per slot, and a colliding key looks for another empty slot.

12.4.1Probe sequences

A key first tries its home slot, h(k). If it is empty, the key goes there; if not, a fixed rule picks a second slot, then a third, and so on. Checking a slot is called probing, and the order of slots tried is the key's probe sequence.

With at most one pair per slot, n ≤ N, so λ ≤ 1 — unlike chaining, λ cannot exceed 1. There are three common probing methods:

Open addressing needs no extra nodes or references, only the array, and a contiguous array suits the processor cache: probing consecutive slots beats hopping between scattered nodes in practice. In return, the load factor must stay low, since probe sequences lengthen quickly as the table fills, and deletion needs care (12.4.5).

All examples in this section insert the keys 18, 41, 22, 44, 59, 32, 31, and 73, in that order, into N = 13 slots with h(k) = k mod 13. Their home slots are 5, 2, 9, 5, 7, 6, 5, and 8. Running the same data through all three methods makes the differences plain.

12.4.2Linear probing

Linear probing is the simplest method: if the home slot is taken, try the next, then the next, wrapping around at the end:

// put(k): linear probing, N = 13
int h = k % 13;                // home slot
for (int i = 0; i < 13; i++) {
  int j = (h + i) % 13;          // h, h+1, h+2…
  if (table[j] == null) {      // empty?
    table[j] = k;
    break;
  }                            // occupied: i++
}

h is the home slot and i counts tries; j = (h + i) % 13 is the home slot, then the next, and so on, with % 13 wrapping from 12 to 0. At the first empty slot the key is written and break ends the loop, which runs at most 13 times — once per slot.

The first three keys go in on the first try: 18 → 5, 41 → 2, 22 → 9. Table 12.13 traces the rest.

44 finds its home slot 5 taken by 18 and settles next door in 6. 59 gets its home slot 7. 32's home slot 6 has just been taken by 44, and 59 holds 7, so 32 ends up in 8: though its home slot is not 5, it has fallen into the crowd that starts there.

31 fares worse. Slots 5 through 9 are all occupied, so it reaches 10 after six probes. 73, home slot 8, passes 8, 9, and 10 to reach 11. The seven slots from 5 to 11 now form one solid block.

Clustering feeds on itself: a key landing anywhere in a cluster walks to its end and extends it, and a longer cluster catches more keys. Neither 32 nor 73 has home slot 5, yet both joined the cluster starting there. And when the one empty slot between two clusters fills, they merge into a bigger one.

So the cost of linear probing depends on cluster length. In a sparse table almost every key goes in on the first try; as it fills, clusters lengthen and probes climb fast, as the numbers in 12.5.1 show.

12.4.3Quadratic probing

Primary clustering comes from probing neighboring slots. Quadratic probing escapes clusters with bigger jumps, trying slots 1, 4, 9, 16, … beyond the home slot.

// put(k): quadratic probing, N = 13
int h = k % 13;                // home slot
for (int i = 0; i < 13; i++) {
  int j = (h + i * i) % 13;      // h, h+1, h+4…
  if (table[j] == null) {      // empty?
    table[j] = k;
    break;
  }                            // occupied: i++
}

Only j changes: (h + i * i) % 13 offsets the home slot by 0, 1, 4, 9 for i = 0, 1, 2, 3. The same keys again:

The difference starts with 32, whose third try, 6 + 2² = 10, lands outside the cluster instead of extending it to 8. On its fourth try 31 jumps to 5 + 3² = 14, slot 14 mod 13 = 1. With slot 8 free, 73 goes home on the first try. Total probes fall from 19 to 14, the longest sequence from 6 to 4.

Quadratic probing reduces primary clustering but leaves another problem: keys with the same home slot follow the same sequence. 18, 44, and 31 all start at 5 and try 5, 6, 9, 1, …, blocking one another. This is secondary clustering, milder than primary clustering because it affects only keys that share a home slot.

Its second weakness is that it may not try every slot. For N = 13, h = 5, the tries i = 0, 1, …, 12 visit 5, 6, 9, 1, 8, 4, 2, 2, 4, 8, 1, 9, 6 — only seven distinct slots, {1, 2, 4, 5, 6, 8, 9}. If those are full, the key finds no room though six slots are empty. The following result avoids this.

For N = 13, the first seven tries (i = 0 … 6) are distinct — exactly the seven slots found above, after which they repeat. Hence tables using quadratic probing take a prime N and keep λ below 0.5.

12.4.4Double hashing

Secondary clustering arises because the step depends only on the home slot. Double hashing makes it depend on the key, through a second hash function h₂; the ith try is

h(k, i) = (h(k) + i · h₂(k)) mod 13, h₂(k) = 7 − (k mod 7)

Since k mod 7 runs from 0 to 6, h₂(k) runs from 1 to 7 and is never 0; a zero step would probe the home slot forever. In code:

// put(k): double hashing, N = 13
int h = k % 13;
int d = 7 - k % 7;             // step: 1…7
for (int i = 0; i < 13; i++) {
  int j = (h + i * d) % 13;
  if (table[j] == null) {      // empty?
    table[j] = k;
    break;
  }                            // occupied: i++
}

d = 7 - k % 7 is the step; % binds tighter than subtraction, so it means 7 − (k mod 7). Only j = (h + i * d) % 13 differs from the other methods.

Of the three keys with home slot 5, 18 goes in at once, 44 (step 5) jumps to 10, and 31 (step 4) tries 5, 9, then 5 + 8 = 13, slot 0. Starting from the same slot, they move by different steps and stay out of each other's way. With 44 no longer in slot 6, 32 also goes home at once, and the total drops to 11.

Double hashing does not abolish secondary clustering: keys with the same home slot and step still share a sequence. 59, 31, and 73 all have step 4 but different home slots, so they do not interfere. Both functions colliding at once is far less likely than one.

Why pair the step with a prime N?

Here N = 13 is prime and the steps are 1 to 7, so any key can reach every slot. With N = 12 and step 4, probing would visit only h, h + 4, h + 8 and could miss free slots.

12.4.5Deletion: the tombstone

Deletion under open addressing is subtler than it looks. Take the table left by linear probing — 41 in slot 2, and 18, 44, 59, 32, 22, 31, 73 in slots 5 to 11 — and delete 44.

Finding 44 is easy: h(44) = 5 holds 18, and slot 6 holds 44. Setting slot 6 to null seems natural but breaks the table. A search for 32 starts at h(32) = 6 and finds it empty, and under open addressing an empty slot means "the key is not further on," since had it been empty when 32 arrived, 32 would be there. The search reports 32 absent, yet 32 is in slot 8.

The deleted slot was a link in other keys' probe sequences: 32 went to 8 because 6 and 7 were taken, and emptying 6 cuts its path. So instead of emptying the slot, we mark it.

The last panel shows the tombstone during insertion. Inserting 57, the search notes the ✗ in slot 6 as the first available slot but keeps going, since 57 might be further on. Only on reaching a truly empty slot (12) is 57 known to be absent, and only then is it written into slot 6, so the deleted slot is not wasted.

Tombstones have a cost: they pile up, and searches must pass them like occupied slots, so after many deletions probe sequences stay long even with few real items. Tables therefore count tombstones too and, when needed, rebuild from scratch, which clears them.

12.4.6Code: findSlot()

Search and insertion probe the same way, so the shared work goes into one helper, findSlot, whose single integer result says whether the key was found and, if not, where it can go.

private int findSlot(int k) {      // probe for k
  int h = Math.floorMod(k, N), avail = -1;
  for (int i = 0; i < N; i++) {
    int j = (h + i) % N;           // linear
    if (table[j] == null ||
        table[j] == DEFUNCT) {
      if (avail == -1) avail = j;
      if (table[j] == null) break;
    } else if (table[j].key == k)
      return j;                    // found
  }
  return -(avail + 1);        // absent: encoded slot
}

• h is the home slot (Math.floorMod handles negative keys). avail holds the first empty or deleted slot seen, −1 until one appears.
• The loop probes linearly: j = (h + i) % N.
• An empty (null) or deleted (DEFUNCT) slot is noted in avail if none has been noted yet. A truly empty slot ends the loop, since the key cannot be further on; a deleted one does not.
• An occupied slot holding the key returns its index, 0 or more, meaning "found."
• If the loop ends without the key, -(avail + 1) is returned: always negative, meaning "not found," and encoding the insertion slot.

Why not -avail? If avail is 0, -avail is 0 too, indistinguishable from "found in slot 0." Adding 1 makes every "not found" strictly negative — slot 0 becomes −1, slot 6 becomes −7 — and the slot is recovered as −(j + 1). Java's Arrays.binarySearch reports a missing item's insertion point the same way.

Search and insertion then take a line each:

• get(k): with j = findSlot(k), return table[j].value if j ≥ 0, else null.
• put(k, v): if j ≥ 0, update that slot's value; otherwise write the pair into table[−(j + 1)].

For quadratic probing or double hashing only j changes, to (h + i*i) % N or (h + i*h2) % N.

The code assumes the table is never full: λ < 1 is maintained by growing the table, so the loop always meets an empty or deleted slot and avail never stays −1. In a full table it would, and the result -(−1 + 1) = 0 would be misread as "found in slot 0."

Cost. Each probe is O(1), so time is proportional to the number of probes: O(N) in the worst case, a small constant in expectation at a low load factor.

12.4.7Code trace: findSlot()

In the linear-probing table, 44 has been deleted, leaving ✗ in slot 6: 2 → 41, 5 → 18, 6 → ✗, 7 → 59, 8 → 32, 9 → 22, 10 → 31, 11 → 73, the rest empty. We call findSlot(32), then findSlot(57).

The search does not stop at the ✗; it notes slot 6 as "insert here if needed," moves on, and returns 8, so get returns table[8].value. The tombstone kept the path intact.

findSlot(57) makes eight probes. The ✗ in slot 6 becomes avail; slot 12 is empty too, but if (avail == -1) is false, so the first available slot is kept. A truly empty slot ends the loop — 57 cannot be further on — and the method returns −7. put sees j = −7 < 0 and sets table[−(j + 1)] = table[6] = 57, reusing the deleted slot.

Writing 57 into slot 12 instead would still be correct, but the ✗ in 6 would remain and cost every search through it an extra probe. Reusing the first available slot clears tombstones over time and keeps probe sequences short.

12.4.8The three probing methods compared

Table 12.18 sums up the three runs on the same eight keys.

This one example reflects the general trend. Linear probing clusters most; quadratic probing breaks primary clustering but keeps secondary; double hashing largely avoids both. Yet linear probing remains popular: consecutive slots are the cheapest access pattern for the cache, and at a low load factor clusters stay short, whereas double hashing needs a second hash per key and jumps far between slots.

To try the methods on other keys, use the sandbox in the slides or the open addressing simulator, which works on N = 11 slots with h(k) = k mod 11 and shows the slots tried, tombstones, and load factor for every insertion and search.

12.5Performance and applications

The promise of O(1) on average holds only if the table does not get too full. This section measures how fullness affects cost, then covers what happens as a table fills, how Java's HashMap handles it, and where hash tables are used.

12.5.1The load factor

The load factor λ = n / N is pairs per bucket, n being size in the code and N the number of buckets or slots. Its meaning depends on the strategy:

• Under chaining, λ is the average chain length. It may exceed 1, which only slows things down; the expected cost is O(1 + λ).
• Under open addressing, λ ≤ 1 by necessity. As λ nears 1, empty slots grow scarce and probes multiply.

Donald Knuth derived the expected number of probes for linear probing, for a large table and a good hash function:

successful search: ½ (1 + 1/(1 − λ)) unsuccessful search: ½ (1 + 1/(1 − λ)²)

An unsuccessful search runs until it reaches an empty slot, and an insertion follows the same path, so the two cost the same. The term 1 − λ is the fraction of empty slots: as it shrinks, the values grow, far faster for unsuccessful searches, where it is squared.

Two lessons stand out. Under open addressing the cost is low up to λ = 0.5 and then climbs steeply: going from 50% to 80% full raises an unsuccessful search from 2.5 to 13 probes, about five times as many, and at 90% it takes 50. Under chaining the cost grows only linearly and stays acceptable even at high load.

Hence two thresholds in practice: about 0.75 for chaining (Java's HashMap uses it) and about 0.5 for open addressing. Past the threshold, the table roughly doubles.

12.5.2Resizing

Past the threshold, the table grows. A Java array cannot change size, so growing means allocating a larger array and moving every pair into it — resizing. Each key is rehashed on the way, because its index h(k) mod N depends on N.

In Figure 12.22, 12, 7, 20, and 33 go into a chained table of 5 buckets; 12 and 7 share bucket 2. After the fourth insertion λ = 4/5 = 0.80 exceeds 0.75, so the table grows to 11 buckets and each key moves by k mod 11: 20 → 9, 7 → 7, 12 → 1, 33 → 0. Now 7 and 12 are apart, no collisions remain, and λ = 4/11 ≈ 0.36.

Why 11 and not 10? The division method spreads keys better with a prime N (12.2.2), so some implementations pick the first prime above double the old size. The code below uses the simpler 2N + 1, always odd: 11 for 5, a prime, though not always (7 gives 15).

A resize moves all n pairs, so by itself it costs O(n). But it is rare: since capacity roughly doubles, at least as many insertions pass before the next one, and spreading its cost over them leaves a constant share each.

Not every insertion is fast: the one that triggers a resize takes O(n). Most programs care only about average speed; real-time systems, where every operation must be quick, can resize incrementally over several insertions.

12.5.3Code trace: resize()

Here is the resize method for the chained HashTable class:

private void resize() {
  HashNode[] old = buckets;
  int newN = 2 * old.length + 1;
  buckets = new HashNode[newN];
  size = 0;  numBuckets = newN;
  for (HashNode head : old) {      // each bucket
    while (head != null) {
      put(head.key, head.value);
      head = head.next;
    }
  }
}

• old = buckets keeps the old array, the only way to reach the old chains once the new array exists.
• newN = 2 * old.length + 1 is odd and roughly double.
• buckets = new HashNode[newN] points the field at the new, empty array; since getBucketIndex uses buckets.length, all later indices use the new size.
• size = 0, because put increments size for each pair; otherwise pairs would be counted twice.
• The outer loop visits each old bucket, the inner loop walks its chain, and put(head.key, head.value) places each key in its new bucket.

put creates fresh nodes rather than reusing old ones; once unreferenced, the old array and nodes are garbage-collected. Moving nodes directly into the new chains would be more efficient, but this version is shorter and clearer.

Tracing the previous example: the old table has bucket 0 → 20, bucket 2 → 7 → 12 (7, inserted after 12, heads the chain), and bucket 3 → 33.

Old bucket 2's chain makes the inner loop run twice — 7, then 12 after head = head.next — and the two keys split into new buckets 7 and 1. All four pairs end up moved, size is 4 again, and λ = 4/11 ≈ 0.36.

Cost. The outer loop runs N_old times and the inner loops n times in all, each put O(1) on average: O(N + n), which is O(n) since the threshold keeps N proportional to n. Both arrays are in memory during the move.

12.5.4Complexity compared

The map ADT's implementations side by side:

On the starred cell: appending to an unsorted list is O(1), but map keys are unique, so we must first check whether the key exists, scanning the list in O(n). In a sorted array, binary search takes O(log n), but insertion and deletion shift items in O(n).

Three points about hash tables stand out:

• The worst case. If all keys land in one bucket, one long chain or one huge cluster makes operations O(n). The O(1) average needs a good hash function and a bounded load factor.
• Space. O(n + N) for the bucket array and the pairs, plus one reference per node under chaining. A bounded load factor gives N = O(n), so space is O(n).
• No order. Finding the smallest key, listing keys in order, or range queries such as "keys between 50 and 100" mean visiting the whole table, O(n) or more if sorting is needed. When order matters, search trees are the better choice.

12.5.5Inside Java's HashMap

Java's java.util.HashMap combines this chapter's ideas with a few clever details.

• Chaining with a power-of-two bucket count. The number of buckets n is always a power of 2 (16 by default), so the index comes from a fast bit operation instead of a division: h & (n − 1). For n = 16 = 2⁴, n − 1 = 15 is 1111 in binary, so & 15 keeps the last four bits — the same as h mod 16 for non-negative h, and still within 0 … 15 for negative codes.
• Bit mixing. The mask sees only low bits, so keys differing only in high bits would always collide. HashMap therefore first computes h ^ (h >>> 16): >>> 16 shifts the upper 16 bits down and ^ (XOR) mixes them into the low bits, so high bits affect the index too.
• The λ = 0.75 threshold. When items exceed 0.75 · n, the array doubles and nodes are redistributed; with 16 buckets, the 13th item triggers growth to 32. Because n is a power of 2, each node either stays put or moves to old index + old size, decided by a single bit.
• Treeification (Java 8+). A chain longer than 8 in a table of at least 64 buckets becomes a red-black tree, a balanced search tree, cutting that bucket's worst-case search from O(n) to O(log n). Smaller tables grow instead, since there a long chain more likely means too little capacity.

The figure's 16-bucket table is drawn to show everything at once; a real 16-bucket HashMap would grow rather than turn bucket 9's long chain into a tree, being below the 64-bucket limit.

Iteration order is a frequent question. Iterating with keySet() or a for loop follows bucket order, not insertion order, and resizing moves nodes, so the order can change. For insertion order use LinkedHashMap, for sorted keys TreeMap; for presence alone, HashSet uses the same hash table structure.

12.5.6Code trace: index(k, 16)

To see bit mixing at work, this short method imitates HashMap's index calculation, and main prints three keys' indices for 16 buckets.

static int index(Object key, int n) { // n = 2^k
  int h = key.hashCode();
  int m = h ^ (h >>> 16); // mix in the high bits
  return m & (n - 1); // low k bits
}
// main:
for (int k : new int[]{1, 65537, 131073})
  System.out.println(k + " -> " + index(k, 16));

For an Integer, key.hashCode() is the number itself. h >>> 16 shifts right 16 bits, filling with zeros, so the upper half drops into the lower; h ^ (h >>> 16) XORs it into the low 16 bits and leaves the high 16 unchanged; m & (n − 1) keeps the low 4 bits.

The keys were chosen on purpose: 1, 65537, and 131073 are 0x00000001, 0x00010001, and 0x00020001 in hexadecimal. Their low 16 bits agree (…0001) and only the high bits differ, so without mixing h & 15 would give 1 for all three.

Key 1's upper half is zero, so the XOR changes nothing and the index is 1. For 65537 the upper half is 1, and 0001 XOR 0001 leaves low bits 0000: m = 65536, index 0. For 131073 it is 2 (0010), and 0001 ^ 0010 = 0011: m = 131075, index 3. The program prints:

1 -> 1
65537 -> 0
131073 -> 3

Unmixed, all three keys would collide in bucket 1; mixed, they spread to 1, 0, and 3, for the price of one shift and one XOR. For keys with small hash codes (h < 65536) the upper half is zero and mixing changes nothing — the low bits already carry everything.

12.5.7Where hash tables are used

Hash tables appear wherever "is this key here, and what is its value?" needs a fast answer:

• Dictionaries and spell checkers. A word → meaning map lives in a hash table, and a spell checker asks of every word "is it in the dictionary?", in constant time on average.
• Databases. Hash indexes give fast access to records by key. A hash join, which combines two tables on a shared column, loads one table into an in-memory hash table and looks up each row of the other.
• In-memory caches. The result of an expensive computation or query is stored under a key such as a URL or the query text and returned directly when the request recurs. Redis and memcached are built on this idea.
• Browser history. Address → time of last visit; the browser colors links by whether they have been visited.
• Cookies and sessions. Cookie name → value, session ID → user data; the server finds the user by session ID on every request.
• Compilers. The symbol table maps names to type, address, and scope, and the compiler looks up every name it meets.

In Java, most of this uses HashMap and HashSet. Small tasks — counting occurrences, finding the common items of two lists, removing duplicates — also take O(n) expected time with a hash table. The next application is a typical case.

12.5.8Application: twoSum()

Given an integer array, find the indices of two items that sum to a target. Brute force tries every pair (i, j) with nested loops, in O(n²); a hash table needs a single pass.

static int[] twoSum(int[] a, int target) {
  Map<Integer, Integer> seen = new HashMap<>();
  for (int i = 0; i < a.length; i++) {
    int need = target - a[i]; // the partner we need
    if (seen.containsKey(need))
      return new int[]{seen.get(need), i};
    seen.put(a[i], i); // value -> index
  }
  return null; // no such pair
}

At a[i], the partner that completes the target is need = target − a[i]; if it has been seen, we are done. Seen values are kept in seen as value → index, and containsKey(need) takes O(1) on average. Otherwise a[i] joins the map, so later items can find it.

None of the first four partners (4, 9, 1, 7) has been seen, so each value is stored with its index. At step five, a[4] = 7 needs 5, seen at index 3, and the method returns [seen.get(5), 4] = [3, 4]: a[3] + a[4] = 5 + 7 = 12.

The check must come before the insertion; otherwise an item equal to half the target (6 for 12) would pair with itself. Duplicates still work: the first copy enters the map and the second finds it.

Cost. One pass, with an O(1)-average search and insertion per step: O(n) expected time and O(n) extra memory, against brute force's O(n²) time and no extra memory. Trading memory for time like this is the typical use of a hash table.

12.5.9Application: hashing student IDs

General-purpose hash functions must cope with any key; knowing the keys' structure allows a much better one. Here the goal is to spread student IDs over 1000 cells with no collisions.

IDs look like ab070c0de, for example 210707003:

• ab: year of enrollment, 20 to 24;
• c: department code, 6 or 7;
• de: enrollment number for that year and department, 00 to 99;
• the other digits ("070" and "0") never vary and carry no information.

This function spreads every such ID over 0–999:

hash(ab070c0de) = ((ab − 20) × 100 + (c − 6) × 500 + de) mod 1000

ab − 20, from 0 to 4, picks a block of 100 (2020 → 0–99, 2021 → 100–199); c − 6, 0 or 1, shifts department 7 by 500; and de, 0 to 99, is the position in the block.

There are 5 years × 2 departments × 100 numbers = 1000 possible IDs, each sent to its own index: department 6 fills 0–499, department 7 fills 500–999, each year its own block of 100. With no collisions at all, this is a perfect hash, possible only when the key set is known in advance — here, through the ID format.

In Java:

// s: student ID of the form "ab070c0de"
public int calculateHash(String s) {
  int ab = Integer.parseInt(s.substring(0, 2));
  int c  = Integer.parseInt(s.substring(5, 6));
  int de = Integer.parseInt(s.substring(7, 9));
  int year = (ab - 20) * 100;    // year block
  int dept = (c - 6) * 500;      // department: 0/500
  return (year + dept + de) % 1000;
}

substring(begin, end) includes begin and excludes end: s.substring(0, 2) is characters 0–1, the year; s.substring(5, 6) is character 5, the department; s.substring(7, 9) is characters 7–8, the enrollment number. Integer.parseInt converts each ("03" becomes 3), and the rest computes the formula.

The method does a fixed amount of work, O(1), but is correct only for IDs in the expected format. 250707001, with year 25, gives (500 + 500 + 1) mod 1000 = 1 and collides with 200706001; a department code of 8 overshoots 1000 and wraps onto another ID's index; a year below 20 can even give a negative result. A real program validates input first, rejecting malformed IDs or sending them to a general-purpose hash table.

12.6Common mistakes

The same mistakes recur in programs that use hash tables, and most pass the compiler and surface only on particular inputs. Table 12.26 collects those met in this chapter.

Mutable keys are especially insidious. Use an ArrayList as a key, then add to the list, and its hashCode() changes: [1, 2] hashes to 994, [1, 2, 3] to 30817. get then searches another bucket and returns null, though the pair is still there and size() is 1. The pair can be neither found nor removed — unreachable garbage inside the table.

Most of these share a root. A hash table assumes that a key's hash code does not change while it is stored and that equal keys hash alike. Break either and the table raises no error; it just answers wrongly. So in code using a hash table, check the key class's equals and hashCode first.

12.7Summary

• A map associates unique keys with values through put, get, and remove; put on an existing key updates it and returns the old value. A map is an ADT, most often implemented by a hash table.
• Direct addressing gives every possible key a cell and runs in O(1), but wastes memory on large key spaces and cannot take non-integer keys.
• A hash function turns a key into a hash code and, by compression, into an index in 0 … N − 1. A good one is deterministic, fast, and uniform, and uses the whole key. The division method wants a prime N; MAD is ((a·k + b) mod p) mod N. In Java, index with Math.floorMod(h, N).
• The equals/hashCode contract: equal objects must hash alike; equal hashes do not imply equality. hashCode picks the bucket, equals decides equality, and both are overridden together.
• Collisions are unavoidable whenever the key space exceeds the table (the pigeonhole principle).
• Separate chaining keeps a linked list per bucket, with new nodes possibly at the front. Operations take O(1 + chain length), O(1 + λ) expected, and λ > 1 is allowed. Deletion tracks the previous node.
• Open addressing stores pairs in the array, so λ ≤ 1. Linear probing suffers primary clustering, quadratic probing secondary clustering; the latter guarantees an empty slot with a prime N and λ < 1/2. Double hashing ties the step to the key, which must be nonzero and coprime with N. Deletion leaves a tombstone.
• The load factor is λ = n/N. An unsuccessful linear-probing search averages ½(1 + 1/(1 − λ)²) probes: 2.5 at λ = 0.5, 13 at 0.8. Past the threshold (≈ 0.75 for chaining, ≈ 0.5 for open addressing) the table roughly doubles and every key is rehashed — O(n) once, amortized O(1) per insertion.
• Insertion, search, and deletion are O(1) on average, O(n) in the worst case; space is O(n + N); there is no order.
• Java's HashMap: chaining, a power-of-two bucket count (16 by default), mixing with h ^ (h >>> 16) and the mask & (n − 1), doubling at 0.75, and red-black trees for chains longer than 8 (given at least 64 buckets).
• Known key structure allows a perfect hash: in the student ID example, 1000 possible IDs map to 1000 different indices.

12.8Key terms

Each term links to the course glossary, which gives its Turkish equivalent and its use in other chapters.

• map
• key
• value
• direct addressing
• hash table
• hash function
• hash code
• compression function
• bucket
• collision
• separate chaining
• open addressing
• probing
• linear probing
• quadratic probing
• double hashing
• primary clustering
• load factor
• resizing (rehashing)
• amortized analysis

12.9Test Yourself

1. 8, 13, 3, 21, and 6 are inserted in that order into a chained table of 5 buckets with h(k) = k mod 5, new nodes at the front. Give the final table and λ. How many key comparisons does get(8) make?

   Answer

   Buckets: 8 → 3, 13 → 3, 3 → 3, 21 → 1, 6 → 1. The latest key comes first: bucket 1 is 6 → 21, bucket 3 is 3 → 13 → 8, and buckets 0, 2, 4 are empty. λ = 5/5 = 1. get(8) examines 3, 13, and 8: 3 comparisons.

2. Compute "Can".hashCode() with the String.hashCode() formula (C = 67, a = 97, n = 110). Which of 13 buckets does it land in?

   Answer

   h = 67; 31 · 67 + 97 = 2174; 31 · 2174 + 110 = 67504. 13 · 5192 = 67496, remainder 8: bucket 8, where it collides with "Ali".

3. 4, 15, 26, and 5 are inserted in that order into an empty linear-probing table of 11 slots with h(k) = k mod 11. Where does each go, and with how many probes?

   Answer

   4 → 4 (1 probe). 15: home 4 taken, 5 free (2 probes). 26: home 4; 4, 5 taken, 6 free (3 probes). 5: home 5; 5, 6 taken, 7 free (3 probes). 9 probes in all; slots 4–7 form one cluster.

4. In that table, 15 is deleted by setting slot 5 to null. What does get(26) find? What if a tombstone is used instead?

   Answer

   With null: 4 (4 ≠ 26), then empty slot 5, so "26 absent," though 26 is in slot 6. With a tombstone: 4, 5 (✗, skipped), and 26 is found in 6 after 3 probes.

5. findSlot returned −1. What does it mean? With -avail instead of -(avail + 1), which cases would be confused?

   Answer

   Negative means "key absent," with insertion slot −(−1 + 1) = 0. With -avail, an available slot 0 would return 0, the same as "found in slot 0."

6. An 11-slot table uses double hashing with h(k) = k mod 11 and h₂(k) = 7 − (k mod 7). Where do 13, 24, and 35 go in an empty table? And under linear probing?

   Answer

   All three have home slot 2. 13 → 2. 24: step 7 − 3 = 4, so 2 + 4 = 6. 35: step 7 − 0 = 7, so 2 + 7 = 9. Linear probing would put them in 2, 3, 4, forming a cluster.

7. Keys are inserted one by one into a default Java HashMap. On which insertion does it first grow, and to how many buckets? When does it grow next?

   Answer

   16 buckets, threshold 0.75 · 16 = 12: the 13th insertion grows it to 32. The new threshold is 0.75 · 32 = 24, so the 25th insertion grows it to 64.

8. Compute ((ab − 20) × 100 + (c − 6) × 500 + de) mod 1000 for IDs 220706099 and 220707099.

   Answer

   Both have ab = 22, de = 99. 220706099: c = 6, 200 + 0 + 99 = 299. 220707099: c = 7, 200 + 500 + 99 = 799.

9. A linear-probing table has λ = 2/3. By Knuth's formulas, how many probes do successful and unsuccessful searches average?

   Answer

   1 − λ = 1/3. Successful: ½(1 + 3) = 2. Unsuccessful: ½(1 + 9) = 5.

10. A Point class's equals compares both coordinates, and its hashCode returns x + y. Is the contract met? After puts with keys new Point(1, 2) and new Point(2, 1) into an empty HashMap, what is size()?

    Answer

    Yes: equal points have equal coordinates, hence equal sums. (1, 2) and (2, 1) share hash code 3 but are unequal, so they share a bucket as separate pairs: size() is 2. The function is correct but weak, since all points with the same sum collide.

12.10Further reading

• M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data Structures and Algorithms in Java (6th ed., 2014), Chapter 10: the map ADT, hash codes versus compression, the MAD method, and Java implementations with chaining and linear probing, organized much like these notes.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapter 11: probabilistic proofs of the expected costs of chaining and open addressing, and universal hashing.
• R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Section 3.4: symbol tables with chaining and linear probing in Java, with experiments on the effect of the load factor.
• D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed., 1998), Section 6.4: the source of the linear-probing formulas, with a history of hashing.

12.11References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022.
2. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014.
3. D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998.
4. Oracle, Java SE 17 API Specification: documentation for java.util.Map, java.util.HashMap, and java.util.HashSet.
5. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.

Related pages: Chapter 12 slides · Study questions · Glossary · © Sercan Külcü. All rights reserved.