Data Structures and Algorithms with C · Lecture Notes
Chapter 14: Hash Tables
Binary search in a sorted array and search in a balanced search tree proceed by comparing keys with one another. For this reason, in a structure of n items they cannot get below the order of lg n steps. A hash table takes a different route: it does not compare keys, it computes the position of the item in the array from the key. Because the computation takes only a few arithmetic operations, search, insertion and deletion finish in constant time on average. These notes first build the simplest form of this idea, direct addressing. They then work out, one by one, the hash functions that reduce a key to a small range of indices: division, multiplication, folding, mid-square, and the polynomial hash for strings. Two different keys may land in the same position; there are two main ways to resolve such a collision. In open addressing the item goes to another empty slot of the table; linear probing, quadratic probing and double hashing search for this slot in different orders. In chaining, every bucket is the head of a linked list. Each method is written in C and its code is traced step by step. The last sections treat the pitfall of deletion in open addressing, the effect of the load factor on cost, and growing the table.
Learning outcomes
- Explaining the idea
- Define a hash table, which searches in O(1) on average by computing the position from the key; state how it differs from direct addressing and what it costs.
- Choosing a function
- Compute division, multiplication, folding, mid-square and string hashes by hand; list the properties of a good hash function; show why the table size is chosen to be prime.
- Resolving collisions
- Apply linear probing, quadratic probing, double hashing and chaining step by step on a small table; distinguish primary from secondary clustering.
- Writing it in C
- Write the insertion, search and deletion routines with
malloc/free,NULLchecks and the full-table case; leave no memory leak. - Deleting correctly
- Show why a deleted slot cannot simply be left empty in open addressing and how a deleted marker protects search.
- Analyzing
- Explain the effect of the load factor on the expected number of probes with formulas and measurements; compute the amortized cost of doubling the table.
14.1The hashing idea
Consider a student records program. Given a student number, the program must find that student's record. The records are queried thousands of times a day; new students are added and graduates are deleted. Which data structure should be chosen for this job? The section begins with the costs of the familiar structures and shows why a hash table is different.
14.1.1Reducing the cost of search to a constant
If the records are kept in an unsorted array, insertion is very cheap: the new record is written at the end of the array. Search, however, is expensive. The number sought may be anywhere in the array, or not there at all. In the worst case, therefore, all n records are examined. Deletion also begins with a search, so it is O(n). If the array is kept sorted by number, search drops to O(lg n) with binary search. This time insertion and deletion become expensive: so that the order is not broken, all records after the new record's position are shifted by one slot. A balanced search tree does all three operations in O(lg n) and also allows traversing the records in sorted order. Table 14.1 compares the four structures.
| Structure | Search | Insert | Delete | Comment |
|---|---|---|---|---|
| Unsorted array | O(n) | O(1) | O(n) | append at the end, scan from the start |
| Sorted array | O(lg n) | O(n) | O(n) | binary search and shifting |
| Balanced search tree | O(lg n) | O(lg n) | O(lg n) | also gives sorted traversal |
| Hash table | O(1)* | O(1)* | O(1)* | * average; worst case O(n) |
The first three structures share a limit: all of them search by comparing keys. Each comparison gives two outcomes, “smaller” or “larger”. To choose one among n possible positions, at least lg n two-outcome decisions are needed. A comparison-based structure therefore cannot get below O(lg n). A hash table gets past this limit by giving up comparison. The position is computed directly from the key: position = h(key). The computation is a few arithmetic operations and does not depend on n.
The gain has a price. A hash table does not keep items in key order; positions are scattered according to the result of the computation. Some queries are therefore not cheap in a hash table: “print all records in order of number”, “find the smallest number”, or “list the records whose numbers lie between 1000 and 2000”. For these queries the whole table must be scanned and, if necessary, sorted separately. The second price is the worst case. If all keys fall into the same position, the table turns into a long list and search becomes O(n). That the average case stays constant depends on a good hash function and on keeping the table sufficiently empty. The rest of the notes examine these two conditions.
14.1.2Direct addressing
The simplest form of the hashing idea is to use the key itself as the array index. If the keys are integers between 0 and 9, an array of ten cells is enough: the record with key k is written in cell T[k]. To search, it is enough to look at T[k]; there is no loop and no comparison.
The set of all values that keys can take is called the key universe and is denoted U. When U = {0, 1, …, |U| − 1}, building an array T of |U| cells and keeping the item with key k in cell T[k] is called direct addressing. Each cell of the array either holds an item or is empty.
Figure 14.1 shows this arrangement. The universe consists of ten keys, and the keys in use are only 2, 3, 5 and 8. Each record is in the cell of its own number; the other six cells are empty.
T[k] holds the record with key k directly; cells with dashed outlines are empty.The C code in the slides represents each cell with a small structure. The field used says whether the cell is occupied, and the field name holds the record's data.
typedef struct { int used; char name[16]; } rec;
rec T[10]; /* key = index */
rec *da_search(int k) {
return T[k].used ? &T[k] : NULL;
}The code is short, but every line carries a decision. The first line defines a structure type named rec. The structure has two fields: used of type int, and the 16-character array name. Thanks to typedef, the type name is used without writing struct every time. The second line defines the ten-cell array T as a global. In C, global variables are filled with zeros when the program starts. So initially the used field of every cell is 0, that is, the table is empty. No separate initialization loop needs to be written.
The function da_search takes the key k and looks at the field T[k].used. If the field is nonzero, the cell is occupied and the function returns the address of that cell, &T[k]. If the field is zero, there is no record and NULL is returned. The conditional expression (? :) writes these two cases on one line. That the function returns the address of the record rather than a copy is a deliberate choice. The caller can read or modify the record through this address. The not-found case is also reported explicitly with NULL. Insertion and deletion are one-liners in the same way: insertion sets T[k].used = 1 and writes the data; deletion sets T[k].used = 0. All three operations are O(1).
In the test program, cells 2, 3, 5 and 8 were filled with the names Ali, Can, Ece and Naz. da_search returned the corresponding names for these four keys and NULL for the other six. On the same machine sizeof(rec) came out as 20 bytes (a 4-byte int and a 16-byte array), and the ten-cell array occupied 200 bytes.
An assumption is hidden in the code: k is always between 0 and 9. A k outside this range reads memory beyond the bounds of the array. C does not catch this error; the result is undefined behavior. In a real program a check such as if (k < 0 || k >= 10) return NULL; should be added at the start of the function.
The problem with direct addressing is the size of the universe. If student numbers have nine digits, |U| = 109. With 20-byte records this table takes 20 gigabytes. A university may have perhaps 20,000 students: only two hundred-thousandths of the table would be occupied, and the rest would sit empty. When the key is a string, for example a variable name or an e-mail address, the universe is practically infinite. In that case direct addressing cannot be built at all.
The solution is a function that reduces the key to a small range. The size of the table is chosen according to the number of keys in use, for example m = 40,000 cells. Every key is converted by this function to an index between 0 and m − 1. This function is called a hash function.
14.1.3The hash function and basic terms
A hash function is a function h: U → {0, 1, …, m − 1} from the key universe to the indices of the table. A structure consisting of an array of m cells and a hash function, which looks for the item with key k in the cell with index h(k), is called a hash table. Each cell of the table is called a bucket or a slot. The value h(k) is the home address of the key k.
The word “hash” in English means to chop up or mince. The function cuts the key into pieces, mixes them, and produces a small number. This course uses the word “hash” throughout.
A hash function maps |U| values to m indices, and m is much smaller than |U|. So some different keys are bound to land on the same index. This is called the pigeonhole principle: if eleven pigeons go into ten holes, at least one hole contains two pigeons. Figure 14.2 shows a function mapping four name keys to six buckets. Ali and Ece have the same home address, 3.
When k1 ≠ k2 but h(k1) = h(k2), this is called a collision. Keys that land on the same home address are called synonyms. If the table has n items and m buckets, the ratio α = n / m is called the load factor of the table.
Table 14.2 gives the terms together. The name “synonym” comes from linguistics: just as two words are spelled differently but carry the same meaning, two keys are different but arrive at the same address. The load factor measures how full the table is. α = 0.5 says that half of the table is full. In some collision-resolution schemes a bucket can hold more than one item, and α can exceed 1.
| Term | Meaning |
|---|---|
| bucket / slot | a position of the table, 0 … m − 1 |
| home address | h(k): the first place where the key is looked for |
| collision | k1 ≠ k2 but h(k1) = h(k2) |
| synonyms | keys that land on the same home address |
| load factor α | n / m, the fraction of the table that is full |
As long as m < |U|, collisions are unavoidable. Hash table design then comes down to two questions. The first is how to choose a good h: keys should be spread over the buckets as evenly as possible, with few collisions. The second is what to do when a collision occurs: where is the second item that lands on the same address put, and how is it found during search? Hash functions answer the first question; open addressing and chaining answer the second.
14.1.4The dictionary abstract data type
A hash table is an implementation. The abstract data type it implements is the dictionary. An abstract data type defines the values and operations of a structure independently of how those operations are written. A dictionary resembles an everyday dictionary: a word (the key) is given and its meaning (the value) is found.
A dictionary is a collection of key–value pairs in which every key occurs at most once. Its basic operations are insertion, search by key, and deletion by key.
typedef struct { int key; /* + value */ } item;
bool hash_insert(item x); /* update if found */
item *hash_search(int key); /* NULL if absent */
bool hash_delete(int key); /* false if absent */The interface in the slides gives the three operations as C declarations. The structure item holds the key; the “+ value” in the comment says that in a real application other fields would be added to the structure. hash_insert takes an item and returns a bool reporting whether the operation succeeded. If the key already exists, the new item is not added; the value of the existing one is updated. This preserves the rule “every key at most once”. hash_search returns the address of the item; if the key is absent it gives NULL. hash_delete returns true if it finds and deletes the key, and false if it cannot find it. bool, true and false are in the header <stdbool.h> introduced with C99; the code does not compile without including this header.
Dictionaries appear in many places. A compiler keeps every variable name in the source code in a symbol table: the name is the key, and its type and place in memory are the value. Horowitz's textbook opens hash tables with this example. The compiler looks up many names on every line; if lookup finishes in constant time, compilation speeds up. Web browser caches keep the address as the key and the page as the value. To find repeated items in a list, each item is added to a set; before it is added, the set is searched. A set is a dictionary without values.
Python's dict, Java's HashMap and C++'s unordered_map are all hash tables. C's standard library, however, has no ready-made hash table. The POSIX standard provides a limited routine called hsearch: only one table can be created at a time, and items cannot be deleted from it. A C programmer must therefore know how to write a hash table. The remaining sections of these notes do exactly that.
14.2Hash functions
The speed of a hash table depends on how evenly the keys are spread over the buckets. A function that throws all keys into the same bucket is also a valid function, but it turns the table into a single long list. This section first lists what is expected of a good function, and then works out the common methods for integer and string keys.
14.2.1Properties of a good hash function
Four properties are sought in a good hash function.
- It must be fast. The function runs on every search, insertion and deletion. The computation should finish in a few arithmetic operations. If the key is a string, each character should be processed at most once; that is, the cost should be linear in the key length.
- It must spread keys uniformly. Keys should fall into the m buckets in numbers as equal as possible. Theoretical analyses accept this as an assumption: each key falls into each of the m buckets with probability 1/m, independently of the other keys. This assumption is called the simple uniform hashing assumption.
- It must use all the bits of the key. Real data is usually patterned. Prices end in 5 or 0, memory addresses are multiples of 8, student numbers begin with the same year codes. A function that looks only at the last digit or the last few bits carries these patterns into the buckets and clusters the keys in a few buckets.
- It must be deterministic. The same key must go to the same bucket on every call. Otherwise an item that was inserted once could not be found later. Randomness can be used only when the function is chosen: when the program starts, one function is picked at random from a family of functions and used for the rest of the program.
Uniform distribution cannot be guaranteed without knowing the key set. For every fixed hash function, a key set can be found in which all keys fall into the same bucket. The aim of the methods is to behave well on the patterned data seen in real life.
14.2.2The division method
The simplest and most common method is to divide the key by the table size and take the remainder.
The division method: h(k) = k mod m. Because the remainder is always between 0 and m − 1, the result is directly an index.
unsigned h_div(unsigned k, unsigned m) { return k % m; }The function is a single % operation. It matters that the parameters are unsigned; the reason is given at the end of this subsection. All the subtlety of the method lies in the choice of m. Table 14.3 distributes eight keys with two different table sizes.
| k | 10 | 20 | 30 | 40 | 50 | 60 | 17 | 27 |
|---|---|---|---|---|---|---|---|---|
| k mod 10 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 7 |
| k mod 11 | 10 | 9 | 8 | 7 | 6 | 5 | 6 | 5 |
When m = 10, k mod 10 is the last decimal digit of k. The function never sees the other digits. The keys 10, 20, …, 60 all end in 0 and all fall into bucket 0; 17 and 27 also collide in bucket 7. Eight keys are spread over only two buckets. When m = 11, the same eight keys go to six different buckets. There are still two collisions (50 and 17 in bucket 6, 60 and 27 in bucket 5), but the multiples of 10 are now spread over consecutive buckets. The reason is that 11 has no common divisor with 10: 10j mod 11 takes ten different values for j = 1, …, 10.
The same problem is even more pronounced for powers of 2. If m = 2p, then k mod 2p is the lowest p bits of the binary representation of k. Because data in a computer is stored as binary numbers, patterns in the last bits are very common. The addresses of 8-byte structures are always multiples of 8, that is, their last three bits are 000. In a table with m = 16, these addresses fall only into buckets 0 and 8. For this reason the following rule is recommended (CLRS): m should be chosen as a prime number not close to a power of 2. For example, for about 2000 keys, 701 is a good choice: it is prime and far from 512 and 1024. In this table about three keys fall into each bucket on average.
The division method has one more trap in C. In C the result of the % operator carries the same sign as the dividend: the expression -7 % 11 is −7, not 4. If the key is of type int and can be negative, k % m gives a negative index. Memory before the start of the array is read or overwritten. The remedy is one of two ways. Either the key is kept unsigned from the start (h_div in the slides does this) or the remainder is made positive:
unsigned h_safe(int k, int m) {
int r = k % m; /* -m < r < m */
if (r < 0) r += m; /* same as ((k % m) + m) % m */
return (unsigned)r;
}In the test program -7 % 11 really gave −7; h_safe(-7, 11) returned 4 and h_safe(-22, 11) returned 0. Because the remainder lies between −m and m, adding m once moves it into the range 0 to m − 1. The expression ((k % m) + m) % m from the slides does the same job without a branch.
Thinking that the mathematical “mod” operation and the C operator % are the same. In mathematics −7 mod 11 = 4; in C -7 % 11 == -7. This bug produces no compiler warning; it shows up only when a negative key arrives, and it writes outside the array.
Cost. The division method is a single integer division: O(1). Division is a slower operation on a processor than addition and multiplication; still, since it is done once per key, it does not change the cost of the table.
14.2.3The multiplication method
The division method needs a good m. The multiplication method reduces this dependence: the mixing is done not by m but by a constant multiplier.
The multiplication method: for a constant 0 < A < 1, h(k) = ⌊m · (k·A mod 1)⌋. Here x mod 1 is the fractional part of x: x − ⌊x⌋.
The computation has two steps. First k is multiplied by A and the integer part of the result is discarded. A fraction between 0 and 1 remains. Then this fraction is multiplied by m and rounded down; the result is an integer between 0 and m − 1. The fractional part is affected by all the digits of k. So the choice of m is not critical, and m = 2p can be chosen freely. Knuth suggests the fractional part of the golden ratio for A: A ≈ (√5 − 1)/2 = 0.6180339887… This value spreads consecutive keys very evenly over the fractional interval.
Example (CLRS). Take k = 123456, p = 14, that is, m = 214 = 16384. The floating-point computation goes as follows:
k · A = 123456 · 0.6180339887 = 76300.0041151…
k · A mod 1 = 0.0041151…
m · 0.0041151… = 16384 · 0.0041151… = 67.42…
h(k) = ⌊67.42…⌋ = 67
On a computer, floating-point numbers carry rounding error and are slow. For this reason the method is usually written with integers. Let the word length be w = 32 bits and take s = ⌊A · 232⌋ = 2654435769. The low 32 bits of the product k · s equal 232 times the fractional part of k · A. The top p bits of these 32 bits are the integer part of 2p times the fractional part. That is exactly the value being sought.
/* w = 32 bit, m = 2^p; s = A * 2^32 */
uint32_t h_mul(uint32_t k, int p) {
const uint32_t s = 2654435769u;
return (uint32_t)(k * s) >> (32 - p);
}The code is three lines. uint32_t is the exact 32-bit unsigned integer type from the header <stdint.h>. The product k * s is computed between two uint32_t values, and if the result does not fit in 32 bits it overflows. Overflow of unsigned integers is defined in C: the result is the remainder modulo 232, that is, the upper bits are discarded. The discarded part corresponds to the integer part of the product, and the remaining 32 bits correspond to the fractional part. Finally the shift >> (32 - p) discards the low 32 − p bits and leaves the top p bits.
On the example: 123456 · 2654435769 = 327,706,022,297,664. The remainder of this number modulo 232 is 17,612,864. Shifting right by 18 bits means dividing by 218 = 262,144 and taking the integer part: 17,612,864 / 262,144 = 67.19…, so the result is 67. The test program got 67 from both the integer version and the floating-point version. The fractions of the two versions show small differences (67.42 and 67.19), because s is a rounded version of A · 232; their integer parts are the same.
The code has one limit: p must be between 1 and 32. If p = 0 is given, the shift amount becomes 32, and shifting a 32-bit number by 32 bits is undefined behavior in C. Since a table with m = 1 is meaningless anyway, this case causes no trouble in practice, but it should be written into the function's contract. Cost: one multiplication and one shift, O(1). Because multiplication is faster than division, the method is also advantageous in speed.
14.2.4Folding and mid-square
If the key is too long to fit in a processor word, for example a 14-digit identity number, it must first be shortened. The folding method does this.
Folding: the key is divided from left to right into parts of equal length and the parts are added. If the parts are added as they are, it is called shift folding; if the even-numbered parts are reversed before adding, it is called folding at the boundaries.
In Horowitz's example the key is x = 12320324111220. The three-digit parts are P1 = 123, P2 = 203, P3 = 241, P4 = 112 and P5 = 20; the last part has two digits. Figure 14.3 shows the two sums.
In shift folding the sum is 123 + 203 + 241 + 112 + 20 = 699. In folding at the boundaries, the key is folded back and forth at the part boundaries like a paper strip. When folded, every second part lands on top face down, and its digits are read in reverse. The sum is 123 + 302 + 241 + 211 + 20 = 897. If the result is larger than the table size, mod m is also taken; for example, for m = 11 both values give 6. The following function computes both kinds with a flag. The key is given as a string of digits, because a 14-digit number does not fit in a 32-bit integer.
/* x: digit string; parts of r digits, left to right */
unsigned fold(const char *x, int r, bool boundary) {
unsigned sum = 0;
int n = (int)strlen(x);
for (int start = 0, idx = 0; start < n; start += r, idx++) {
int end = start + r < n ? start + r : n; /* part: [start, end) */
unsigned part = 0;
if (boundary && idx % 2 == 1) /* even-numbered part: reversed */
for (int j = end - 1; j >= start; j--) part = part * 10 + (unsigned)(x[j] - '0');
else
for (int j = start; j < end; j++) part = part * 10 + (unsigned)(x[j] - '0');
sum += part;
}
return sum;
}The outer loop increases start by r each round and moves through the parts in turn; idx is the 0-based index of the part. end is one past the end of the part; since the last part may be short, the smaller of start + r and n is taken. The inner loops convert the digits of the part into a number: for each digit, part = part * 10 + digit. The expression x[j] - '0' converts a digit character to its numeric value; '7' - '0' is 7. In folding at the boundaries, the parts with odd idx (the second, fourth, …) are read from right to left. In the test program the function gave the values 699 and 897. Since every digit of the key is processed once, the cost is linear in the key length.
The mid-square method squares the key and uses the middle r bits of the result as the index; the table size is chosen as m = 2r. Why the middle? The lowest bits of a square depend only on the lowest bits of the number; the highest bits depend largely on the magnitude of the number. The middle bits, on the other hand, are formed in the product with contributions from nearly all bits of k. The idea is easy to see with a decimal example: for k = 1234, k2 = 1522756. The middle three of the seven digits are 227; in a table with m = 1000 the home address is 227. If any digit of 1234 changes, these three digits change too.
14.2.5String keys: the polynomial hash
In practice most keys are strings: variable names, user names, words. The first way that comes to mind to convert a string to an integer is to add up the character codes.
unsigned sum_hash(const char *s, unsigned m) { /* bad example */
unsigned h = 0;
for (; *s != '\0'; s++)
h += (unsigned char)*s;
return h % m;
}This function is bad. Addition forgets order: “abc” and “cba” consist of the same letters, their sums are 97 + 98 + 99 = 294, and both fall into the same bucket. Strings obtained by rearranging the letters of a string are called anagrams; the additive hash collides all anagrams. The second problem is the narrowness of the range. The sum of lowercase strings of 8 letters is at most 8 · 122 = 976. Even if the table has 10,000 buckets, the keys are squeezed into the first thousand buckets.
The solution is to take the position of each character into account as well. A string c0 c1 … cn−1 of n characters is read like a number in base 31:
h = c0 · 31n−1 + c1 · 31n−2 + … + cn−2 · 31 + cn−1
This expression is a polynomial. If computed directly, a separate power would be taken for each term. Horner's rule nests the polynomial: h = (…((c0 · 31 + c1) · 31 + c2) · 31 + …) + cn−1. One multiplication and one addition per character then suffice. The two functions in the slides use this rule.
unsigned str_hash(const char *s, unsigned m) {
unsigned h = 0;
for (; *s != '\0'; s++)
h = (h * 31 + (unsigned char)*s) % m;
return h;
}str_hash starts h at 0. The loop advances the pointer s over the characters of the string and stops at the '\0' terminator. At each step h is multiplied by 31, the code of the new character is added, and the result is taken mod m. The cast (unsigned char)*s is important: char is signed on many compilers, and non-ASCII bytes such as “ç” and “ğ” carry negative values. The cast reads the character as a number between 0 and 255.
Taking the mod at every step has two benefits. First, h always stays smaller than m and the product does not overflow (provided that 31 · m + 255 fits in an unsigned). Second, the result does not change: in modular arithmetic (a · 31 + c) mod m equals ((a mod m) · 31 + c) mod m. Taking the mod at intermediate steps gives the same result as taking it once at the end.
unsigned long djb2(const char *s) { /* Bernstein */
unsigned long h = 5381;
int c;
while ((c = (unsigned char)*s++) != 0)
h = h * 33 + c;
return h; /* then: h % m */
}The second function is Dan Bernstein's widely used djb2 hash. It starts with the initial value 5381 and computes h · 33 + c for each character. It takes no mod at intermediate steps; when the unsigned long overflows, the result automatically becomes the remainder modulo 2w (w is the number of bits of the type). Since unsigned overflow is defined in C, this is safe. For a table index, the caller takes the mod m of the result. The expression (c = (unsigned char)*s++) != 0 in the loop condition does three things: it reads the character, advances the pointer, and checks whether the character is zero. On Windows unsigned long is 32 bits and on Linux it is 64 bits; so djb2 may give different numbers for the same string on the two systems. On the test machine (Windows), djb2("kedi") came out as 2090432258.
Table 14.4 compares three functions on anagrams. The polynomial hash separates “abc” from “cba”, because “a” is multiplied by 312 in one and by 1 in the other.
| String | Sum | sum_hash | str_hash |
|---|---|---|---|
| "abc" | 294 | 8 | 5 |
| "cba" | 294 | 8 | 0 |
| "ab" | 195 | 8 | 3 |
| "ba" | 195 | 8 | 0 |
The choice of the number 31 is not random. The base should be odd: an even base fills the lowest bits with zeros during overflow, and the influence of the first characters is lost. The base should also be larger than the number of letters in the alphabet, so that different strings do not give the same “number”. Java's String.hashCode method also uses 31. Multiplying by 31 also has a cheap equivalent: 31 · h = 32 · h − h, that is, a shift and a subtraction.
Cost. All three string functions process each character once. For a key of L characters the time is O(L) and the memory is O(1). The “O(1)” cost of a hash table really means “O(L)” for string keys. Since the key length is independent of the table size, this is counted as a constant.
14.2.6Code trace: str_hash("kedi", 11)
The character codes of the string “kedi” in the ASCII table are k = 107, e = 101, d = 100 and i = 105. The table has 11 buckets. Table 14.5 shows each round of the loop.
| Round | *s | Code | Previous h | h * 31 + code | New h |
|---|---|---|---|---|---|
| 1 | 'k' | 107 | 0 | 0 · 31 + 107 = 107 | 107 mod 11 = 8 |
| 2 | 'e' | 101 | 8 | 8 · 31 + 101 = 349 | 349 mod 11 = 8 |
| 3 | 'd' | 100 | 8 | 8 · 31 + 100 = 348 | 348 mod 11 = 7 |
| 4 | 'i' | 105 | 7 | 7 · 31 + 105 = 322 | 322 mod 11 = 3 |
| 5 | '\0' | — | 3 | the loop condition is false; return 3 | |
In the first round h is zero, so the multiplication has no effect, and h becomes the remainder of 107 modulo 11: 107 = 9 · 11 + 8. In the second round the old value is multiplied by 31 and the code of “e” is added: 349 = 31 · 11 + 8. The third and fourth rounds give 7 and 3. At the fifth check *s is the terminator character, the loop ends, and the function returns 3. The home address of the key “kedi” is 3.
str_hash("kedi", 11). Above, the first character has been processed, h = 8. Below, the last character has been processed too, h = 3; the processed characters are shown faded.Let us also check the result without taking the mod at intermediate steps. The full polynomial is 107 · 313 + 101 · 312 + 100 · 31 + 105 = 3,187,637 + 97,061 + 3,100 + 105 = 3,287,903, and 3,287,903 mod 11 = 3. The two computations give the same result; that taking the mod at intermediate steps does not change the result can also be seen here with numbers. For a four-character string the loop runs four times and ends at the fifth check: the cost is linear in the string length.
14.3Open addressing
A good hash function reduces collisions but cannot eliminate them. This section first shows how early collisions begin, and then examines the methods that place the colliding item in another slot inside the table.
14.3.1Collisions are unavoidable
If the table is large and the number of keys is small, one might expect collisions to be rare. A probability computation refutes this intuition. The famous birthday paradox says: in a class of 23 people, the probability that two people share a birthday is about 50.7%. The computation is done through the complement. The probability that all 23 people were born on different days is
(365/365) · (364/365) · (363/365) · … · (343/365) ≈ 0.4927
The first person can be born on any day; the probability that the second is born on a different day is 364/365; the third must differ from the first two, and so on. The probability of at least one match is 1 − 0.4927 ≈ 0.507.
Let us translate this to a hash table: 23 keys, each landing in a random slot, are inserted into a table with m = 365 slots. Only 6% of the table is full, but the probability of at least one collision is more than half. When the number of keys reaches 57, this probability exceeds 99%. The general rule is this: in a table of m slots, the first collision is expected after about √m keys. In a table of a million slots this number is around a thousand. Collisions should therefore be treated not as an exceptional case but as the normal case.
There are two basic ways to resolve a collision. Figure 14.5 shows both on the same keys.
Open addressing: all items are kept in the slots of the table, and each slot holds at most one item. If the home address is occupied, other slots are examined according to a certain rule. Checking whether a slot is empty is called a probe, and the order of the slots examined is called the probe sequence. The probe sequence is written h(k, i): the slot examined at the i-th attempt (i = 0, 1, …, m − 1).
In open addressing every item occupies a slot, so n ≤ m, that is, α ≤ 1. When the table is full, no new item can be inserted. In chaining, by contrast, every bucket is the head of a linked list; items that fall into the same bucket are added to that list. Since the list can grow as long as needed, α > 1 is possible. Chaining is treated in detail in its own section. The rest of this section examines the three probing rules of open addressing: linear probing, quadratic probing and double hashing. All the examples use the same table: m = 11, h(k) = k mod 11, and the keys 22, 1, 13, 11, 24, 33 inserted in this order. The home addresses of these keys are 0, 1, 2, 0, 2, 0: 11 and 33 collide with 22, and 24 collides with 13.
14.3.2Linear probing
Linear probing: h(k, i) = (h(k) + i) mod m. If the home address is occupied, the next slot is examined; if that is occupied too, the one after it. When the end of the table is reached, probing wraps around to the start.
The rule is like someone looking for a seat in a cinema: if the numbered seat is taken, they sit next to it. The insertion of the six keys proceeds as follows.
- The home address of 22 is 22 mod 11 = 0. Slot 0 is empty; 22 is written there. One probe.
- The home address of 1 is 1 and that of 13 is 2. Both land in empty slots; one probe each.
- The home address of 11 is 0 and it is occupied by 22. Next slot 1 (occupied, 1), then slot 2 (occupied, 13), then slot 3 is examined. Slot 3 is empty. The probe sequence is 0, 1, 2, 3; four probes.
- The home address of 24 is 2 and it is occupied by 13. Slot 3 now holds 11. Slot 4 is empty. The probe sequence is 2, 3, 4; three probes.
- The home address of 33 is 0. Slots 0 through 4 are all occupied; slot 5 is empty. The probe sequence is 0, 1, 2, 3, 4, 5; six probes.
In the final state the first six slots of the table form a block of occupied slots (Figure 14.6). A new key whose home address falls on any slot inside this block walks to the end of the block and settles there; the block grows by one more slot. As the block grows, the chance of landing in it also grows: a block of 6 slots covers six of the 11 possible home addresses. Big blocks get bigger.
In linear probing, the tendency of occupied slots to form long consecutive blocks, and of these blocks to enlarge themselves, is called primary clustering.
Primary clustering does not affect only synonyms. In the example, the home address of 24 is 2 and it has nothing to do with 22 or 11. Yet because of 11 it had to walk one more slot. Keys with different home addresses share the same block and slow one another down. As the table approaches full, blocks merge and the average number of probes grows quickly. The numerical value of this growth is given in the load factor section.
14.3.3C implementation: slot state and insertion
In open addressing it is not enough for a slot to be just “full” or “empty”. For deletion to work correctly, a third state is needed. Why this state is needed is shown in detail in the deletion section; here only its definition is given.
#define M 11
typedef enum { EMPTY, USED, DELETED } state_t;
typedef struct {
int key; /* assumes key >= 0 */
state_t state;
} slot;
slot table[M]; /* global: all 0 = EMPTY */#define M 11 defines the table size as a macro constant. The preprocessor replaces every M in the code with 11 before compilation. enum defines three constants: EMPTY = 0, USED = 1 and DELETED = 2. If values are not given, C assigns 0 to the first constant and increments for each one after. state_t is the type name for these numbers; writing EMPTY instead of 0 in the code improves readability.
The structure slot has two fields: the key and the state. The assumption in the comment (key ≥ 0) removes the negative-remainder problem of the division method for this code. The array table is global and is filled with zeros when the program starts. Because EMPTY equals zero, all slots are empty at the start. The order of the enum constants therefore matters: if EMPTY were not written first, the table would not count as empty at the start.
In memory table is a single block of 11 structures laid out one after another. On the test machine each slot is 8 bytes (a 4-byte int and a 4-byte enum), and the table occupies 88 bytes. There are no pointers and no malloc. This is an important advantage of open addressing and is taken up again in the design comparison.
int insert(int k) {
int i = k % M; /* home addr */
for (int d = 0; d < M; d++, i = (i + 1) % M) {
if (table[i].state != USED) { /* free slot */
table[i].key = k;
table[i].state = USED;
return i;
}
}
return -1; /* table full */
}The function insert works line by line as follows.
- Line 2:
iis the home address of the key. The first probe will be made here. - Line 3: The
forloop manages two variables.dis the attempt counter and goes from 0 to M − 1.iis the slot being examined; at the end of every round it is incremented and taken mod M, so after 10 it returns to 0. The comma operator performs the two updates in one expression. - Lines 4–8: If the slot is not
USED, that is, it isEMPTYorDELETED, the key is written there, the state is set toUSED, and the index of the slot is returned. - Line 10: If the loop found occupied slots in all M attempts, the table is full; the function returns −1.
Limiting the number of attempts to M is important. The sequence of linear probing visits every slot once in M steps. Without the limit, the loop would run forever on a full table. In the test program, 5 was to be inserted into a table filled with the keys 0, 11, 22, …, 110; insert returned −1 after 11 attempts.
The function has a known shortcoming: it does not check whether the key is already in the table. If the same key is inserted a second time, a second copy is written into the first empty slot of the probe sequence. The dictionary rule “every key once” is the caller's responsibility in this code. Once DELETED slots come into play the problem becomes subtler; its solution is the function insert_unique in the deletion section.
Cost. Insertion takes as long as the number of probes. In the best case the home address is empty: Θ(1). In the worst case the whole table is traversed: O(m). The average case depends on the load factor; as long as α is kept constant it is O(1). No extra memory is used.
14.3.4Code trace: insert(33)
The table holds 22, 1, 13, 11 and 24; slots 0–4 are a block of occupied slots. Table 14.6 traces the call insert(33).
d | i | table[i] | Decision |
|---|---|---|---|
| — | 0 | — | home address 33 mod 11 = 0 |
| 0 | 0 | 22, USED | next: i = (0 + 1) mod 11 = 1 |
| 1 | 1 | 1, USED | next: i = 2 |
| 2 | 2 | 13, USED | next: i = 3 |
| 3 | 3 | 11, USED | next: i = 4 |
| 4 | 4 | 24, USED | next: i = 5 |
| 5 | 5 | EMPTY | table[5] = {33, USED}; return 5 |
The loop runs six rounds; the work in each round is the same: look at the state field and advance i. An empty slot is found at the sixth probe. 33 has landed five slots away from its home address. The cause is not 33's own synonyms but the whole block. Of the five keys in slots 0–4, only two (22 and 11) have the same home address as 33.
insert(33). Above, the 2nd attempt: slot 2 is occupied and i advances; the “home” marker shows the home address and “i” the slot being examined. Below, 33 has been written to slot 5.14.3.5Search and a code trace
Search follows exactly the probe sequence that insertion followed. If the key is in the table, it is somewhere in this sequence. But how does the search know when to say “absent”? Insertion writes to the first empty slot it meets in the probe sequence. So if the sought key were in the table, it would be found before the first EMPTY slot in the sequence. A search that meets an EMPTY slot can stop.
int search(int k) {
int i = k % M;
for (int d = 0; d < M; d++, i = (i + 1) % M) {
if (table[i].state == EMPTY) return -1;
if (table[i].state == USED &&
table[i].key == k) return i;
}
return -1;
}
bool erase(int k) {
int i = search(k);
if (i < 0) return false;
table[i].state = DELETED; /* tombstone */
return true;
}There are two functions in this code fragment; here search is explained, and erase is the subject of the deletion section. search uses the same loop skeleton as insert. At each slot it asks two questions. If the slot is EMPTY, the search ends and returns −1. If the slot is USED and its key is k, the sought key has been found; the index is returned. In the other cases, that is, if the slot is occupied by another key or is DELETED, the search moves to the next slot. The condition table[i].state == USED in the second if is necessary. In a DELETED slot the old key still stands in the key field; without this condition a deleted key would count as found. If the loop ends after M attempts without meeting any EMPTY slot, the table is full and the key is absent; the function again returns −1.
Table 14.7 traces two searches. The table holds 22, 1, 13, 11, 24 and 33 (slots 0–5).
| Call | Slots examined | Result | Probes |
|---|---|---|---|
search(24) | 2 (13) → 3 (11) → 4 (24) | found, return 4 | 3 |
search(44) | 0 (22) → 1 (1) → 2 (13) → 3 (11) → 4 (24) → 5 (33) → 6 (EMPTY) | absent, return -1 | 7 |
search(24) starts at home address 2. Slot 2 holds 13; the state is USED but the key is different, so it continues. Slot 3 holds 11, continue again. In slot 4 it finds 24 and returns 4. Three probes, the same as the three probes made when 24 was inserted. This is no coincidence: a successful search retraces the path the key took when it was inserted.
search(44) is longer. The home address of 44 is 0, and the whole block 0–5 is occupied by other keys. Slot 6 is EMPTY: if 44 were in the table, it would have been written at slot 6 at the latest, so it is absent. The unsuccessful search took seven probes. Unsuccessful searches are generally longer than successful ones, because they always walk to an empty slot. A search for a key that is not in the table and whose home address falls between 6 and 10, in contrast, ends in a single probe. In the test program search(5) was such a search and returned −1 at once.
search(44). The search starting at home address 0 walked through the block of occupied slots and met an empty slot at slot 6: 44 is not in the table.Cost. A successful search takes as many probes as the key took when it was inserted. An unsuccessful search takes as many as the distance from the home address to the first empty slot. Both are O(m) in the worst case and O(1) on average when α is constant.
14.3.6Quadratic probing
The cause of primary clustering is that the probe sequence passes through adjacent slots. Quadratic probing moves away from the home address in steadily growing steps.
Quadratic probing: h(k, i) = (h(k) + i2) mod m. The attempts look at slots 0, 1, 4, 9, 16, … away from the home address.
The same six keys settle as follows with quadratic probing. 22, 1 and 13 again land on their home addresses. The probe sequence of 11 is 0, 0 + 1 = 1, 0 + 4 = 4: slots 0 and 1 are occupied and slot 4 is empty. The sequence of 24 is 2, 2 + 1 = 3, and since slot 3 is empty it settles in two probes. The sequence of 33 is 0, 1, 4, 9: slots 0, 1 and 4 are occupied, and 33 is written in slot 9. For 33, linear probing needed six probes; quadratic probing needs only four.
The final table is 22, 1, 13, 24, 11 (slots 0–4) and 33 (slot 9). Quadratic probing removes primary clustering: 24 no longer waits behind 11 but settles in the first empty place on its own sequence. But keys with the same home address still follow the same sequence. 22, 11 and 33 all advance along the sequence 0, 1, 4, 9, … and cut each other off. This milder clustering is called secondary clustering.
A drawback of quadratic probing is that the probe sequence does not visit all slots. For m = 11 and home address 0, the attempts i = 0, 1, …, 10 look at slots 0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1 in turn. The sequence contains only six distinct slots: 0, 1, 3, 4, 5, 9. Slots 2, 6, 7, 8 and 10 are never probed. Insertion can fail even though the table has room. The following result draws the line on this problem.
If m is prime, the first ⌈m/2⌉ probes of quadratic probing look at distinct slots. Therefore, if the table is at most half full (α ≤ 1/2), an empty slot is always found for a new key.
Proof. Suppose two probes with 0 ≤ i < j < ⌈m/2⌉ look at the same slot. Then h + i2 ≡ h + j2 (mod m), that is, m divides the product j2 − i2 = (j − i)(j + i). Since m is prime, it must divide one of the factors. But 0 < j − i < m and 0 < j + i < m (the latter is the sum of two numbers smaller than m/2). So neither factor can be a multiple of m. Contradiction: the first ⌈m/2⌉ probes look at distinct slots. If the table has fewer than m/2 occupied slots, at least one of these distinct slots is empty. ∎
For m = 11, ⌈11/2⌉ = 6, and indeed the first six probes, 0, 1, 4, 9, 5, 3, look at distinct slots. The practical consequence of the theorem is simple: a table that uses quadratic probing is given a prime size and is not filled beyond half.
14.3.7Double hashing
The cause of secondary clustering is that the probe sequence depends only on the home address. Double hashing also computes the step size from the key.
Double hashing: with two hash functions h1 and h2, h(k, i) = (h1(k) + i · h2(k)) mod m. h1 gives the home address and h2 gives the step size.
In the example, h1(k) = k mod 11 and h2(k) = 1 + (k mod 10) are chosen. The step sizes are 2 for 11, 5 for 24 and 4 for 33. 22, 1 and 13 land on their home addresses. The sequence of 11 is 0, 2, 4: slots 0 and 2 are occupied and 11 is written in slot 4. The sequence of 24 is 2, 7; slot 7 is empty. The sequence of 33 is 0, 4, 8: slot 0 holds 22 and slot 4 holds 11; 33 is written in slot 8. Three probes sufficed for 33.
Here 22, 11 and 33 have the same home address but different step sizes (3, 2 and 4, respectively). The three follow different probe sequences and the chance that they cut each other's path is reduced. In linear and quadratic probing the probe sequence depends only on the home address; m different home addresses give m different sequences. In double hashing the sequence depends on the pair of home address and step size. The number of such pairs is of the order of the square of m.
h2 must satisfy two conditions. First, it must never be 0. If h2(k) = 0, all probes would look at the home address and the probing would never advance. That is why h2 begins with “1 +”. Second, h2(k) and m must be relatively prime. For example, if m = 10 and the step size were 6, the sequence starting at slot 5 would go around as 5, 1, 7, 3, 9, 5, …; only five of the ten slots would be probed. If m is chosen prime, every step size between 1 and m − 1 is relatively prime to m and the condition holds automatically. The m = 11 in the example is prime; since h2 takes values between 1 and 10, every sequence visits all 11 slots.
14.3.8Comparing the three probing schemes
The three methods can be written with a single function. The following code gives the function probe, which computes the slot of the i-th attempt according to the method, and a general insertion function that uses it. The definitions of table, slot and M are the same as in the open addressing section.
typedef enum { LINEAR, QUADRATIC, DOUBLE } method_t;
int probe(int k, int i, method_t m) { /* slot of attempt i */
int h1 = k % M;
switch (m) {
case LINEAR: return (h1 + i) % M;
case QUADRATIC: return (h1 + i * i) % M;
default: return (h1 + i * (1 + k % 10)) % M; /* h2 */
}
}
int insert_m(int k, method_t m) {
for (int d = 0; d < M; d++) {
int i = probe(k, d, m);
if (table[i].state != USED) {
table[i].key = k;
table[i].state = USED;
return i;
}
}
return -1;
}method_t names the three methods. The switch statement selects one of the formulas according to the method. In the double hashing branch the step size is 1 + k % 10. Because this code uses 10 rather than m, it suits only the table in the example. In a general table h2 is chosen to depend on m, for example 1 + (k mod (m − 2)). insert_m is the same as insert; the only difference is that it finds the slot with probe instead of i = (i + 1) % M. In quadratic probing the product i * i does not overflow as long as i < M. The test program inserted the six keys separately with each of the three methods; the results are exactly the same as Table 14.8.
| Method | Attempt i | Probe sequence of 33 | Probes | Final table (slot: key) |
|---|---|---|---|---|
| Linear | h + i | 0, 1, 2, 3, 4, 5 | 6 | 0: 22, 1: 1, 2: 13, 3: 11, 4: 24, 5: 33 |
| Quadratic | h + i2 | 0, 1, 4, 9 | 4 | 0: 22, 1: 1, 2: 13, 3: 24, 4: 11, 9: 33 |
| Double hashing | h1 + i · h2 | 0, 4, 8 | 3 | 0: 22, 1: 1, 2: 13, 4: 11, 7: 24, 8: 33 |
| Method | Clustering | Distinct probe sequences |
|---|---|---|
| Linear | primary (blocks) | m |
| Quadratic | secondary (same home address) | m |
| Double hashing | least | ≈ m2 |
Looking at these tables, one might think double hashing should always be chosen. On real computers the situation is more complicated. A processor brings memory into the cache not byte by byte but in blocks of 64 bytes. In linear probing, consecutive slots are in the same block: once the first probe brings the block in, the next few probes are almost free. The jumps of double hashing, in contrast, land in a different block at every probe. Linear probing is therefore cache-friendly and very fast when α is small (for example below 0.5). As α grows, the number of probes rises quickly because of clustering, and double hashing pulls ahead. The choice depends on how full the table will be kept.
14.4Chaining
In open addressing, a colliding item goes to another slot and occupies the place of other keys. Chaining does the opposite: the colliding item stays in its own bucket. So that a bucket can hold more than one item, every bucket becomes the head of a linked list.
14.4.1One linked list per bucket
Separate chaining, or simply chaining: every bucket of the table is the head pointer of a linked list. All keys whose home address is j are kept in the list of bucket j, that is, in its chain.
#define MZ 5
typedef struct node {
int key;
struct node *next;
} node;
node *bucket[MZ]; /* all NULL */The definitions are the usual node of a linked list. struct node has two fields: the key and the address of the next node. The structure holds a pointer of its own type, and this pointer is written before the typedef is complete. That is why the structure is given both a tag name (struct node) and a type name (node). The array bucket consists of five pointers. Because it is global, all pointers are NULL when the program starts: all five buckets are empty lists.
The picture in memory differs from open addressing. The array bucket itself is small and contiguous: five pointers, 40 bytes on a 64-bit machine. The nodes, however, are obtained one by one with malloc and scattered through random places in the heap. On the test machine sizeof(node) came out as 16 bytes: a 4-byte key, 4 bytes of padding to align the pointer on an 8-byte boundary, and an 8-byte pointer. For each item, 12 bytes of overhead are added to the 4-byte key. The bookkeeping information that malloc keeps for every block is not included in this count either.
bool chain_insert(int k) {
int i = k % MZ;
node *np = malloc(sizeof *np);
if (np == NULL) return false; /* no memory */
np->key = k;
np->next = bucket[i]; /* at the head */
bucket[i] = np;
return true;
}- Line 2:
iis the bucket of the key. - Line 3: Memory is obtained for the new node.
sizeof *npis the size of the type thatnppoints to, that is,sizeof(node). This spelling stays correct even if the type name changes.mallocis in the header<stdlib.h>. - Line 4: If
malloccannot find memory, it returnsNULL. If this check is skipped, the next line tries to write to addressNULLand the program crashes. The function reports the error to the caller by returningfalse. - Lines 5–7: The node is added at the head of the list. First the
nextfield of the new node points to the old head, then the bucket points to the new node. The order matters: ifbucket[i] = npwere done first, the old list would be lost.
Insertion at the head takes two pointer assignments however long the list is: O(1). Inserting at the end of the list would require walking the whole list. Since the order within a chain has no meaning, inserting at the head is the cheapest choice. This function too does not prevent the same key from being inserted twice. If duplicates are not wanted, chain_search must be called before insertion; then the cost of insertion equals the cost of search.
14.4.2Code trace: chain_insert
The table has five buckets and h(k) = k mod 5. Initially bucket 0 holds 10 and bucket 4 holds 4. Then 12, 7 and 22 are inserted in turn; all three have bucket 2. Table 14.10 traces each call.
| Call | i | np->next | bucket[2] afterwards | Chain 2 |
|---|---|---|---|---|
chain_insert(12) | 2 | NULL (old head) | node(12) | 12 |
chain_insert(7) | 2 | node(12) | node(7) | 7 → 12 |
chain_insert(22) | 2 | node(7) | node(22) | 22 → 7 → 12 |
In the first call bucket 2 is empty. The old head, that is, NULL, is written into the next field of the new node and the bucket points to the new node. Insertion into an empty list needs no special case; the same two assignments give the right result. In the second and third calls the new node goes in front of the old head each time. After the three insertions the chain is 22 → 7 → 12: the most recently inserted is at the head. Each call made one malloc.
chain_insert. Above, chain_insert(7): the next field of the new node points to the old head (12) and the bucket has not been updated yet. Below, after all three insertions: the chain of bucket 2 is 22 → 7 → 12. The Ø sign is NULL.14.4.3Code trace: chain_search
node *chain_search(int k) {
node *p = bucket[k % MZ];
while (p != NULL && p->key != k)
p = p->next;
return p; /* or NULL */
}Search walks the list of the bucket from the start. p starts at the head of the list. The while condition asks two things: is the list finished, has the key been found? If neither, p moves to the next node. The order of the condition matters. The && operator short-circuits: if p != NULL is false, the second condition is never evaluated. If the order were reversed, NULL->key would be read at the end of the list and the program would crash. When the loop ends, p points either to the node found or to NULL; the function returns both as they are.
| Call | Nodes p points to | Result | Nodes visited |
|---|---|---|---|
chain_search(12) | 22 (≠ 12) → 7 (≠ 12) → 12 (equal) | address of node(12) | 3 |
chain_search(17) | 22 (≠ 17) → 7 (≠ 17) → 12 (≠ 17) → NULL | NULL | 3 |
12 is at the end of the chain, because it was inserted first. The search looks at three nodes. The bucket of 17 is also 2 (17 mod 5 = 2). All three nodes of the chain differ from 17 and p ends up NULL. An unsuccessful search must walk the whole chain. An unsuccessful search for a key that falls into bucket 1 or 3, on the other hand, ends without looking at any node: the list is empty.
chain_search(17): p passed the three nodes of the chain and became NULL; 17 is not in the table.Cost. Search takes the cost of computing the home address plus the number of nodes visited in the chain. Under the simple uniform hashing assumption, the expected length of every chain is α = n/m. Because an unsuccessful search walks the whole chain, it looks at α nodes on average; together with the hash computation, Θ(1 + α). A successful search walks up to the node being sought. The items inserted into the same bucket after the sought item are in front of it, and their expected number is about α/2. A successful search therefore looks at 1 + α/2 nodes on average. In both cases, if α is kept constant the cost is O(1). In the worst case all keys fall into the same bucket and search becomes O(n).
14.4.4Code trace: chain_erase
To delete a node from a singly linked list, the predecessor of the node to be deleted must be known. The next field of the predecessor is changed so that it skips the deleted node and points to the one after it. The deletion routine therefore walks with two pointers.
bool chain_erase(int k) {
int i = k % MZ;
node *p = bucket[i], *prev = NULL;
while (p != NULL && p->key != k) {
prev = p;
p = p->next;
}
if (p == NULL) return false; /* absent */
if (prev == NULL) bucket[i] = p->next;
else prev->next = p->next;
free(p);
return true;
}- Line 3:
pis the node being examined andprevis its predecessor. The node at the head of the list has no predecessor;prevtherefore starts asNULL. - Lines 4–7: The search loop is the same as that of
chain_search. The only difference is that the old value ofpis written intoprevbeforepadvances. - Line 8: If
pisNULL, the key is absent andfalseis returned. - Lines 9–10: The node is removed from the chain. If
previsNULL, the deleted node is the head of the list; the bucket is updated to point to the next node. Otherwise thenextfield of the predecessor points to the successor ofp. - Line 11: The node's memory is given back with
free.
Table 14.12 traces the call chain_erase(7); 7 is in the middle of the chain.
| Step | prev | p | Event |
|---|---|---|---|
| 1 | NULL | node(22) | i = 7 mod 5 = 2; p at the head of the list |
| 2 | node(22) | node(7) | 22 ≠ 7: prev and p advance one step |
| 3 | node(22) | node(7) | p->key == 7: the loop ends |
| 4 | node(22) | node(7) | prev->next = p->next: 22 now points to 12 |
| 5 | node(22) | (freed) | free(p); return true; chain 22 → 12 |
chain_erase(7). Above, the node of 7 has been removed from the chain and is about to be freed; 22 points directly to 12. Below, the operation is finished: the chain of bucket 2 is 22 → 12.After step 4, no pointer from the chain reaches the node of 7. If free were not called at this moment, the node would remain in memory but could never be used again: a memory leak. After free(p), however, p still holds the old address. That address no longer belongs to the program; p is a dangling pointer. Reading p->key or following p->next is undefined behavior. Because the function returns right after free, this danger does not arise here. In the test program, a second call chain_erase(7) for the deleted 7 returned false. Deleting 22 at the head was also tried: prev stayed NULL and bucket[2] pointed to the node of 12.
Deletion in chaining needs no marker as in open addressing. The node is really removed from the list and the search path of no other key changes. Every key is searched only in the list of its own bucket; a deleted node cannot cut the search of another bucket. Cost: deletion walks the same path as search and does constant work after finding the node. On average O(1 + α), in the worst case O(n).
Forgetting the deletion of the head node. If the line prev->next = p->next runs while prev is NULL, it writes to address NULL and the program crashes. If the node to be deleted is at the head of the list, the pointer that must be updated is not a field of a node but bucket[i] itself.
14.4.5Releasing all the memory of the table
Because the nodes of a chained table are obtained with malloc, all of them must be given back before the program ends or when the table is no longer needed. The slides have no such routine; the following code completes it.
void chain_clear(void) {
for (int i = 0; i < MZ; i++) {
node *p = bucket[i];
while (p != NULL) {
node *after = p->next; /* save before free */
free(p);
p = after;
}
bucket[i] = NULL;
}
}The outer loop goes over the buckets and the inner loop over the chain of each bucket. The only subtlety of the code is the variable after. After free(p), p->next cannot be read, because the node's memory no longer belongs to the program. The address of the next node is therefore saved before free. At the end the bucket is set to NULL and the table becomes reusable. The cost is O(n + m): each node is handled once and each bucket once.
The memory leak was checked with a counting malloc/free wrapper, because AddressSanitizer cannot be used on Windows. The wrapper increments one counter on every successful allocation and another on every free. The test program inserted 10, 4, 12, 7 and 22, deleted 7 and 22, and then called chain_clear. The counters showed 5 allocations and 5 releases: there is no leak.
14.5Deletion, load factor and resizing
Insertion and search in open addressing were built; deletion was postponed. Why deletion needs a section of its own is seen in the first example. The second half of the section deals with how full the table should be kept and how the table is grown once a threshold is passed.
14.5.1The deletion trap in open addressing
A table with linear probing holds 22, 1, 13, 11, 24 and 33. 13 is to be deleted. The first solution that comes to mind is to set the slot of 13, slot 2, to EMPTY. Then let search(24) be called. The home address of 24 is 2; 24 had settled in slot 4 because slots 2 and 3 were occupied when it was inserted. The search looks at the home address, finds slot 2 EMPTY and returns −1 at once. Yet 24 is in the table.
EMPTY and search(24) saw an empty slot at the home address and stopped; 24 was not found. Below, the right way: slot 2 was marked with a deleted marker (✝); the search passed this slot, looked at 3 and 4, and found 24.The source of the problem is the stopping rule of the search. The search stops under the assumption “if the key were present, it would be found before the first EMPTY slot”. This assumption holds as long as slots only go from EMPTY to USED. When a USED slot becomes EMPTY again, the path of every key that settled by passing through that slot is cut. The keys beyond the deleted slot are in the table but cannot be found.
A tombstone is the special state put on a deleted slot in open addressing (DELETED in the code). Search does not count this slot as empty; it passes over it and continues. Insertion does count this slot as empty and may reuse it.
The name means a gravestone: no item lives in the slot any more, but it is recorded that an item once stood there. The tombstone obeys both rules. The path of a search is not cut, because a marked slot is full as far as search is concerned. Space is not wasted, because a marked slot is empty as far as insertion is concerned.
14.5.2Code trace: erase(13), then search(24)
The deletion routine is the second function of the code fragment given in the search section:
int search(int k) {
int i = k % M;
for (int d = 0; d < M; d++, i = (i + 1) % M) {
if (table[i].state == EMPTY) return -1;
if (table[i].state == USED &&
table[i].key == k) return i;
}
return -1;
}
bool erase(int k) {
int i = search(k);
if (i < 0) return false;
table[i].state = DELETED; /* tombstone */
return true;
}erase first finds the slot of the key with search. If the key is absent, it returns false. Otherwise it sets the state of the slot to DELETED. The key field is not touched; the old value stays in the slot. This causes no problem, because search accepts a key only if its state is USED. Table 14.13 traces the deletion and the search that follows it.
| Call | Step | Event |
|---|---|---|
erase(13) | 1 | search(13): home address 13 mod 11 = 2; slot 2 is USED with key 13 → returns 2 (1 probe) |
| 2 | i = 2 ≥ 0: there is an item to delete; table[2].state = DELETED | |
| 3 | return true | |
search(24) | 1 | home address 24 mod 11 = 2; slot 2 is DELETED: neither EMPTY nor USED, continue |
| 2 | slot 3: USED, key 11 ≠ 24, continue | |
| 3 | slot 4: USED, key 24 → return 4 (3 probes) |
search(24) does not stop at the tombstone in slot 2; both if conditions are false and the loop advances. The search finds 24 in three probes, as before the deletion. The test program ran the same sequence: erase(13) returned 1 (true), the following search(24) returned 4, search(13) returned −1, and a second erase(13) returned 0 (false). When slot 2 was set to EMPTY by hand, search(24) returned −1; the trap really occurred.
Insertion and a repeated key. insert reuses a DELETED slot. This creates a danger that the slides' exercise asks about. With 13 deleted and 24 standing in slot 4, let insert(24) be called. insert looks at home address 2, accepts the slot because it is not USED, and writes 24 there. The table now has two 24s: in slot 2 and in slot 4. In the test program this call really returned 2 and the table became 22, 1, 24, 11, 24, 33. Later erase(24) deletes only the first copy; the second copy stays in the table and search(24) goes on finding a deleted key. The solution is to search before inserting:
int insert_unique(int k) { /* does not reinsert an existing key */
int i = search(k);
if (i >= 0) return i; /* present: return its slot */
return insert(k); /* write to first EMPTY or DELETED slot */
}insert_unique scans the entire probe sequence of the key with search. If the key is present, it returns its position and writes no new copy. If not, insert writes to the first EMPTY or DELETED slot in the sequence. In the test program, after 13 was deleted, insert_unique(24) returned 4 and the table did not change; insert_unique(46) wrote 46 into the tombstone slot 2. This version reclaims the space of tombstones and does not allow repeated keys. The price is one search on every insertion.
Tombstones have a cost too. Because marked slots count as full for search, they lengthen searches. In a table with many insertions and deletions, most of the slots may become DELETED over time even if the actual number of items is small. In that case unsuccessful searches scan nearly the whole table. The remedy is to rebuild the table at certain intervals: all USED items are reinserted into a new, clean table and the markers are discarded. This operation is the same as resizing. In chaining this problem never arises.
14.5.3Load factor and the expected number of probes
In every collision-resolution scheme, cost rises with how full the table is. The load factor α = n/m measures this fullness. The theoretical analysis of hash tables gives the expected number of probes as a function of α under the simple uniform hashing assumption. Table 14.14 summarizes the results for four values of α.
| α | Chaining ✓ | Chaining ✗ | Linear ✓ | Linear ✗ | Uniform ✓ | Uniform ✗ |
|---|---|---|---|---|---|---|
| 0.25 | 1.13 | 1.25 | 1.2 | 1.4 | 1.15 | 1.3 |
| 0.5 | 1.25 | 1.50 | 1.5 | 2.5 | 1.39 | 2.0 |
| 0.75 | 1.38 | 1.75 | 2.5 | 8.5 | 1.85 | 4.0 |
| 0.9 | 1.45 | 1.90 | 5.5 | 50.5 | 2.56 | 10.0 |
The numbers in the table come from the following formulas:
- Chaining: successful search 1 + α/2, unsuccessful search 1 + α (the first 1 is the access to the bucket). Both are Θ(1 + α).
- Linear probing (Knuth): successful search ½ (1 + 1/(1 − α)), unsuccessful search ½ (1 + 1/(1 − α)2).
- Uniform open addressing (CLRS): successful search (1/α) · ln(1/(1 − α)), unsuccessful search 1/(1 − α). Double hashing behaves very close to this ideal.
There is a simple idea behind the formula 1/(1 − α) for an unsuccessful search. Each probe looks at a random slot, and this slot is occupied with probability α. The first probe is always made. The second probe is reached if the first slot is occupied: probability α. The third is reached if the first two slots are occupied: probability about α2. The expected total is the geometric sum 1 + α + α2 + … = 1/(1 − α). For α = 0.9 this is 10: one slot in ten is empty, and finding an empty slot takes ten tries on average.
The second lesson of the formulas is that cost grows not linearly in α but as 1/(1 − α). When α goes from 0.5 to 0.75, the unsuccessful search in linear probing goes from 2.5 to 8.5, and at 0.9 to 50.5. In chaining the increase is gentle: at α = 0.9 an unsuccessful search is 1.9 probes, and the table keeps working when α exceeds 1.
Because the formulas rest on an assumption, they were checked by measurement. Pseudo-random keys generated with a fixed seed were inserted into a table of 100,003 slots (a prime). For each α, the average number of probes in a successful search was computed over all inserted keys, and in an unsuccessful search over 20,000 keys that are not in the table. In double hashing, h2(k) = 1 + (k mod (m − 2)) was used. Table 14.15 gives the results next to the formulas. Since the keys were generated with a fixed seed, the numbers are independent of the machine; only time was not measured.
| α | Linear ✓ | Linear ✗ | Double hashing ✓ | Double hashing ✗ | Chaining ✓ | Chaining ✗ (nodes) |
|---|---|---|---|---|---|---|
| 0.25 | 1.170 (1.167) | 1.384 (1.389) | 1.154 (1.151) | 1.331 (1.333) | 1.128 (1.125) | 0.244 (0.25) |
| 0.5 | 1.500 (1.500) | 2.499 (2.500) | 1.389 (1.386) | 2.005 (2.000) | 1.248 (1.250) | 0.496 (0.50) |
| 0.75 | 2.521 (2.500) | 8.826 (8.500) | 1.855 (1.848) | 3.991 (4.000) | 1.374 (1.375) | 0.738 (0.75) |
| 0.9 | 5.636 (5.500) | 51.118 (50.500) | 2.551 (2.558) | 10.084 (10.000) | 1.450 (1.450) | 0.907 (0.90) |
The measurements agree with the formulas; the deviations are below 4%. The largest deviations are in linear probing, at α = 0.75 and 0.9 (2–4%). At high fullness a few long blocks affect the average noticeably. The values of double hashing match the uniform open addressing formula to three digits.
Under the simple uniform hashing assumption, if the load factor is kept bounded by a constant α0 less than 1 (α ≤ α0 < 1), the expected cost of search, insertion and deletion is O(1) in open addressing and in chaining. In chaining, it is enough for α to be bounded by any constant.
Proof. In chaining the expected cost is Θ(1 + α); if α is bounded by a constant, this is a constant too. In uniform open addressing, an unsuccessful search and insertion take at most 1/(1 − α) ≤ 1/(1 − α0), and a successful search takes even less. The right-hand side does not depend on n. Deletion is a search plus constant work, so it has the same bound. ∎
The thresholds used in practice are as follows: α ≤ 0.5–0.7 in open addressing and α ≤ 1 or so in chaining. In quadratic probing, by the theorem, the threshold must be at most 0.5. When the threshold is exceeded, the table is grown.
14.5.4Resizing
If the table size is given by a fixed macro, the load factor grows with the number of items. If the number of items is not known in advance, the table's array must be dynamic and must be grown when the threshold is exceeded.
typedef struct {
slot *a; /* dynamic array of m slots */
int m, n; /* size, used slots */
} Table;
/* after inserting: */
if (2 * t->n > t->m) /* α > 1/2 */
resize(t, next_prime(2 * t->m));The Table structure carries three fields: the address of the slot array, the number of slots m, and the number of occupied slots n. The array is now obtained with malloc or calloc and its size can change at run time. The second part of the code is the check that runs after every insertion. The condition 2 * t->n > t->m means α > 1/2; to avoid fractional numbers, both sides were multiplied by 2m. When the threshold is exceeded, the table is grown to the first prime that is not smaller than twice the old size. A prime size is needed for the division method and for quadratic probing.
The fragment in the slides assumes that two helper functions exist. The versions written for the test program are these:
int next_prime(int x) { /* first prime not smaller than x */
for (;; x++) {
int prime = x >= 2;
for (int d = 2; d * d <= x && prime; d++)
if (x % d == 0) prime = 0;
if (prime) return x;
}
}
int table_insert(Table *t, int k) { /* linear probing, m = t->m */
int i = k % t->m;
for (int d = 0; d < t->m; d++, i = (i + 1) % t->m) {
if (t->a[i].state != USED) {
t->a[i].key = k;
t->a[i].state = USED;
t->n++;
return i;
}
}
return -1;
}next_prime finds the first prime starting from x. It tests each candidate with divisors up to √x; the condition d * d <= x applies this bound without computing a square root. table_insert is the dynamic-table version of insert from open addressing. The only differences are that it takes the size from the field t->m rather than from the macro M, and that it increments the occupied-slot counter. The sequence of sizes that starts at 5 and takes the first prime at or above twice the size each time goes 5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, …
Why rehash? The first way that comes to mind to grow the table is to copy the old array to the beginning of the new one. This is wrong. The slot of an item depends on k mod m, and when m changes the home address changes too. 12 is at 12 mod 5 = 2 in a table of 5 slots; in a table of 11 slots its home address is 12 mod 11 = 1. A 12 copied to slot 2 cannot be found in the new table by search(12): the search looks at slot 1, finds it empty and stops. Every item must be inserted anew into the new table. This operation is called rehashing.
bool resize(Table *t, int new_m) {
slot *old = t->a;
int old_m = t->m;
slot *a = calloc(new_m, sizeof *a); /* EMPTY */
if (a == NULL) return false;
t->a = a; t->m = new_m; t->n = 0;
for (int i = 0; i < old_m; i++)
if (old[i].state == USED)
table_insert(t, old[i].key);
free(old);
return true;
}- Lines 2–3: The address and size of the old array are saved in local variables. Because the table structure will soon be attached to the new array, the old array can be read only through these copies.
- Lines 4–5: The new array is obtained with
calloc. Unlikemalloc,calloczeroes the memory; sinceEMPTY= 0, all slots start empty. If memory cannot be obtained, the function returnsfalse. In that case the table has not changed at all: the old array is in place; it just could not be grown. - Line 6: The table is attached to the new array and
nis reset;table_insertwill incrementnagain with each insertion. - Lines 7–9: Every slot of the old array is examined. Only
USEDslots are inserted into the new table.EMPTYandDELETEDslots are skipped; so the tombstones are also cleaned up. - Line 10: The old array is freed with
free. If this line is forgotten, every growth leaks the old array.
One subtlety of the function is its relationship with table_insert. If table_insert did the growth check itself, another growth could be triggered during rehashing. Because the new size is more than twice the old size and n starts from zero, the threshold is not exceeded in this code. Still, it is safer for the check to stay outside table_insert, on the caller's side. That is also the arrangement in the slides.
14.5.5Code trace: resize
7, 12 and 3 have been inserted into a table of 5 slots. With linear probing, 7 settled in slot 2, 12 in slot 3 (home address 2 is occupied), and 3 in slot 4 (home address 3 is occupied). n = 3, m = 5, α = 0.6 > 0.5: the table will be grown. The new size is next_prime(10) = 11. Table 14.16 gives the trace.
| Step | i | Event | t->n |
|---|---|---|---|
| 1 | — | old = old array, old_m = 5 | 3 |
| 2 | — | calloc(11, …): 11 slots, all EMPTY; t->a is the new array, t->m = 11 | 0 |
| 3 | 0, 1 | old[0], old[1] are EMPTY: skipped | 0 |
| 4 | 2 | 7 is USED: 7 mod 11 = 7 → slot 7 (old home address 7 mod 5 = 2) | 1 |
| 5 | 3 | 12 is USED: 12 mod 11 = 1 → slot 1 (old home address 2) | 2 |
| 6 | 4 | 3 is USED: 3 mod 11 = 3 → slot 3 (old home address 3) | 3 |
| 7 | — | free(old); return true; new α = 3/11 ≈ 0.27 | 3 |
resize(t, 11). Above, calloc has produced 11 empty slots; 7, 12 and 3 are in the old table. Below, the three items have settled at their new home addresses (12 → 1, 3 → 3, 7 → 7) and the old array has been freed.In the old table the three items formed a contiguous block, and 12 and 3 had slipped away from their home addresses. In the new table all three are at their own home addresses; there is no collision. Besides lowering the load factor, the growth has also dispersed the clusters. The test program got the same result in two ways: when resize was called directly, and when 7, 12, 3 were inserted in turn with the threshold check. In the second way the growth was triggered right after the third insertion. The counting wrapper showed four allocations (two initial arrays and two new arrays) and four releases.
Cost of a single growth. While calloc zeroes the new array it touches m' slots, the loop goes over the old m slots, and n items are reinserted. The total is O(n + m). A single insertion is therefore sometimes very expensive.
If the table is grown by doubling its size (or more) when the threshold is exceeded, then over n insertions into an empty table the total number of reinserted items is less than 2n. The amortized cost per insertion is O(1).
Proof. Let the last growth have taken place when the number of items was ns ≤ n, and let ns items be reinserted in this growth. The previous growth was triggered at the latest when the table size was half of this; at that moment there were at most ns/2 items. In the one before that, at most ns/4, and so on. The total number of reinsertions is at most ns + ns/2 + ns/4 + … < 2ns ≤ 2n. The calloc cost of each growth is also proportional to the table size, and since the sizes at least double each time, it is bounded by the same geometric sum. The total cost of n insertions is O(n) and O(1) per insertion. ∎
This kind of analysis is called amortized analysis: although some individual operations are expensive, the total cost of a sequence of operations is divided by the number of operations. The theorem was checked by a measurement. One million items were inserted into a table starting at 5 slots, and when α > 1/2 the table was grown to the next prime. There were 19 growths and the final size reached 3,292,489. The total number of reinsertions was 1,646,169, that is, 1.65 per item: below the 2 in the theorem. The total number of slots allocated in the growths came to 6.6 per item.
Growing the table by a fixed amount each time, for example 100 slots. Then n insertions cause about n/50 growths, and each moves as many items as there are at that moment, n. The total work reaches the order of n2 and the amortized cost per insertion becomes O(n). Growth must be multiplicative.
14.6Chaining or open addressing?
The two collision-resolution schemes offer the same dictionary operations, and both are O(1) on average when α is constant. The choice between them depends on the properties of the data and the application. Table 14.17 puts the differences side by side.
| Criterion | Chaining | Open addressing |
|---|---|---|
| Load factor | α > 1 is possible; the table does not fill up, it slows down | α ≤ 1; cost explodes as α → 1 |
| Deletion | simple; the node is removed from the list | needs a tombstone; tombstones accumulate |
| Bad hash function | more robust; only the affected chain grows | clusters affect neighboring keys too |
| Memory | a pointer per item and malloc overhead | no extra pointers; the whole table is contiguous |
| Cache | nodes scattered in the heap; not cache-friendly | contiguous array; linear probing in particular is cache-friendly |
| Choice of probing | not needed | a good probing scheme (double hashing) must be chosen against clustering |
The greatest strength of chaining is its flexibility. Even if the number of items is not known in advance, the table keeps working; only the chains grow. Deletion is as simple as removing a node from a linked list and does not affect the rest of the table. A bad hash function lengthens some chains, but the damage stays limited to those buckets. The price is memory and cache. On the test machine a 16-byte node was allocated for a 4-byte key. Because nodes are in different places of the heap, every step along a chain may require the processor to fetch a new block of memory.
Open addressing is superior on these two points. All items are in a single array, there are no pointers, and malloc is called only when the table is grown. The consecutive probes of linear probing fall into the same cache block. The price is sensitivity to the load factor and the complexity of deletion. If α is kept around 0.5, half of the table stays empty; compared with the node overhead of chaining, this is often still cheap.
A practical rule can be summarized as follows. If the number of items cannot be predicted, if there are many deletions, or if the quality of the hash function is uncertain, choose chaining. If memory and speed are critical, deletions are rare, and the load factor can be kept low, choose open addressing. Real libraries use both. Java's HashMap is based on chaining; Python's dict is based on open addressing.
14.7Complexity summary
Table 14.18 collects the cost of the hash table operations. The average column assumes that the load factor is kept constant and that the hash function spreads keys uniformly.
| Operation | Average (α constant) | Worst | Comment |
|---|---|---|---|
| search | O(1) | O(n) | if all keys fall into the same bucket |
| insert | O(1) | O(n) | insertion at the head of a chain is always O(1) |
| delete | O(1) | O(n) | tombstone in open addressing |
| resize | O(n + m) | O(n + m) | amortized O(1) per insertion |
| sorted traversal | O(m + n lg n) | O(m + n lg n) | a hash keeps no order; items are collected and sorted |
| minimum / maximum | O(n + m) | O(n + m) | the whole table is scanned |
The last two rows are where a hash table falls behind a balanced search tree. A search tree finds the smallest item in O(lg n) and traverses the items in sorted order in O(n). In a hash table the items are scattered over the buckets, so all buckets are examined to find the smallest item. For sorted traversal, all items are first collected into an array and then sorted.
The worst case does not come only through bad luck; it can also be produced deliberately. If the hash function is known to everyone, an attacker can prepare thousands of keys that all fall into the same bucket. For example, if a web server keeps request parameters in a hash table, a single request full of parameter names that fall into the same bucket puts the server to O(n2) work. This attack is called hash flooding. The remedy is to choose the hash function at random when the program starts. The function is chosen at random from a predefined family. Because the attacker does not know which function was selected, they cannot prepare colliding keys. If the probability that any two distinct keys collide is at most 1/m for the family, the family is called universal. This method is called universal hashing (CLRS, Section 11.3.3). The string hashes of languages such as Python and Rust therefore start with a random key on every run.
14.8Common mistakes
The six most frequent mistakes in hash table code are the following. Each is a situation encountered with an example in these notes.
k % mcoming out negative for a negative key. In C,-7 % 11is −7. A negative index writes outside the array. The key should be keptunsigned, or the remainder corrected as inh_safe.- Choosing m as 10 or a power of 2. With the division method, this choice looks only at the last digits or the last bits. Multiples of 10 collect in a single bucket at m = 10. m should be a prime far from powers of 2.
- Setting a deleted slot to
EMPTYin open addressing. Searches for keys that settled by passing through the deleted slot stop halfway. The slot must be markedDELETED. - Falling into an infinite loop when the table is full. If the probe loop runs until it finds an empty slot, it never stops in a full table. The number of attempts must be limited to m. In quadratic probing not all slots are probed even in m attempts; the table must not be filled beyond half.
- Not checking the result of
malloc; using a node afterfree. Writing to the result of amallocthat returnedNULLcrashes the program. Reading thenextfield of a deleted node afterfreeis undefined behavior; the address must be saved first. - Copying items with their old indices during resizing. The home address depends on m. An item copied to its old position cannot be found in the new table. Every item must be reinserted into the new table.
14.9Exercises and solutions
The solutions of the six exercises of the slides are given below with their intermediate steps. All results were recomputed with a verification script.
14.9.1A small table with linear probing
Question. With m = 7, h(k) = k mod 7 and linear probing, what does the table become when 10, 17, 24, 3 are inserted in turn?
Solution. The home addresses of the four keys are 10 mod 7 = 3, 17 mod 7 = 3, 24 mod 7 = 3 and 3 mod 7 = 3: all are synonyms. 10 is written in slot 3. For 17, slot 3 is occupied, so it is written in slot 4. For 24, slots 3 and 4 are occupied, so it is written in slot 5. For 3, slots 3, 4 and 5 are occupied, so it is written in slot 6. The final table: slots 3–6 = 10, 17, 24, 3. The numbers of probes are 1, 2, 3 and 4; 10 in total.
14.9.2The same keys with chaining
Question. If the same keys are placed with chaining (insertion at the head), how many nodes does the longest chain have?
Solution. All four keys fall into bucket 3. Since insertion at the head puts the last inserted at the front, the chain becomes 3 → 24 → 17 → 10: four nodes. The other six buckets are empty. The hash function has not spread these four keys at all; k mod 7 is a bad choice for numbers that are 3 more than a multiple of 7. Chaining confines this bad distribution to a single bucket, but a search in that bucket still takes four nodes.
14.9.3A quadratic probe sequence
Question. With m = 11, write the probe sequence of quadratic probing from 0, 1, 4, 9, 16, 25 (mod 11).
Solution. The first four values are smaller than 11 and stay as they are: 0, 1, 4, 9. 16 mod 11 = 5 and 25 mod 11 = 3. The sequence is 0, 1, 4, 9, 5, 3. All six values are distinct; this agrees with the bound ⌈11/2⌉ = 6 in the quadratic probing theorem. The seventh attempt is 36 mod 11 = 3, and it starts to repeat.
14.9.4A failed search in a full table
Question. In a table with linear probing and α = 0.9, how many probes does an unsuccessful search expect?
Solution. By Knuth's formula, ½ (1 + 1/(1 − 0.9)2) = ½ (1 + 1/0.01) = ½ · 101 = 50.5 probes. In the measurement 51.1 was found. For double hashing at the same fullness the expected value is 10, and for chaining 1.9. As α → 1, the cost of linear probing explodes.
14.9.5Additive and polynomial hashes
Question. Compute the additive hash and the base-31 polynomial hash (mod 11) for “ab” and “ba”.
Solution. “a” = 97, “b” = 98. Additive: 97 + 98 = 195 and 195 mod 11 = 8; both strings fall into bucket 8. Polynomial: for “ab”, 97 · 31 + 98 = 3105 and 3105 mod 11 = 3; for “ba”, 98 · 31 + 97 = 3135 and 3135 mod 11 = 0. The polynomial hash separates the two anagrams. str_hash gives the same values by taking the mod at intermediate steps: for “ab”, first 97 mod 11 = 9, then (9 · 31 + 98) mod 11 = 377 mod 11 = 3.
14.9.6Searching before inserting
Question. In open addressing, why must insert call search before writing into a DELETED slot?
Solution. The same key may already be present in a slot after the tombstone. In the example of the deletion section, after 13 is deleted, 24 stands in slot 4; the first slot in the probe sequence of 24 is the tombstone slot 2. An unchecked insert(24) writes 24 a second time into slot 2. If search is called first, 24 is found in slot 4 and no insertion is made. The function insert_unique does this.
14.10Summary
- A hash table does not compare keys; it computes the position from the key. Search, insertion and deletion are O(1) on average and O(n) in the worst case. The price is the loss of order information: sorted traversal, minimum/maximum and range queries are not cheap.
- Direct addressing uses the key as the index; it cannot be built if the universe is large. A hash function h: U → {0, …, m − 1} reduces the key to a small range. Because m < |U|, collisions are unavoidable; the birthday paradox shows that the first collision is expected after about √m keys.
- A good hash function is fast, spreads uniformly, uses all the bits and is deterministic. In the division method, m is chosen as a prime far from powers of 2. In the multiplication method, A ≈ 0.618 and m = 2p can be used. Long keys are folded; strings are computed with a base-31 polynomial hash by Horner's rule. In C, the negative result of
%must be watched for. - In open addressing all items are in the table and α ≤ 1. Linear probing creates primary clustering and quadratic probing creates secondary clustering; double hashing minimizes clustering with a key-specific step size. In quadratic probing m must be prime and α ≤ 1/2; in double hashing h2 must not be zero and must be relatively prime to m.
- In open addressing a deleted slot is not set to
EMPTYbut marked with a tombstone. Search passes over the marker, and insertion reuses the marked slot; to prevent repeated keys, a search is made before insertion. - In chaining every bucket is the head of a linked list. Insertion at the head is O(1) and search is Θ(1 + α). Deletion is removing a node from a linked list; the predecessor pointer and the head-node case need care. All nodes must finally be freed with
free. - The expected number of probes grows on the order of 1/(1 − α). When the threshold is exceeded, the table is grown to the first prime above twice its size and all items are rehashed; the amortized cost is O(1) per insertion.
- The worst case can be triggered by malicious input; universal hashing protects against this by choosing the function at random at run time.
14.11Key terms
- hash table
- hash function
- direct addressing
- bucket
- collision
- load factor
- dictionary
- abstract data type
- division method
- multiplication method
- folding
- open addressing
- probe
- linear probing
- quadratic probing
- double hashing
- primary clustering
- separate chaining
- tombstone
- rehashing
- amortized analysis
- cache
- dangling pointer
- memory leak
14.12Test Yourself
With m = 11, h(k) = k mod 11 and linear probing, 20, 31, 42, 9, 53 are inserted in turn. What is the final table? In how many probes does 53 settle?
Answer
All five keys have home address 9. 20 → 9, 31 → 10, 42 → 9, 10 occupied, wrap around → 0, 9 → 9, 10, 0 occupied → 1, 53 → 9, 10, 0, 1 occupied → 2. Table: slot 0 = 42, 1 = 9, 2 = 53, 9 = 20, 10 = 31. 53 settles in five probes.
The same keys are put into a chained table with m = 11 buckets, inserting at the head. What does the chain of bucket 9 look like? How many nodes does
chain_search(20)look at?Cevap
The chain is 53 → 9 → 42 → 31 → 20; the last inserted is at the head. Since 20 is at the end of the chain, the search looks at five nodes.
The keys 16, 32, 48 and 64 are put through the division method with m = 16 and m = 17. What are the home addresses? What does the result show?
Cevap
With m = 16 all four fall into 0, because k mod 16 takes only the last four bits and the last four bits of these keys are zero. With m = 17 the home addresses are 16, 15, 14 and 13; all four are different. A table size that is a power of 2 creates clustering on patterned data; a prime size does not.
What does
str_hash("ali", 7)return? (a = 97, l = 108, i = 105)Cevap
Round 1: 97 mod 7 = 6. Round 2: 6 · 31 + 108 = 294, 294 mod 7 = 0. Round 3: 0 · 31 + 105 = 105, 105 mod 7 = 0. The result is 0.
In a table with linear probing, slots 0–5 = 22, 1, 13, 11, 24, 33.
erase(22)is called. How many probes does the followingsearch(33)make? What would have happened if slot 0 had been set toEMPTY?Cevap
Slot 0 becomes
DELETED.search(33)passes over the marker in slot 0, finds different keys in 1, 2, 3 and 4, and finds 33 in slot 5: 6 probes. If slot 0 had been set toEMPTY, the search would have stopped at the first probe and returned −1; 33 would not have been found although it is in the table.In a chained table n = 2000, m = 1000; in an open-addressing table α = 0.8 and linear probing is used. How many probes does a successful and an unsuccessful search take on average in each?
Cevap
In chaining α = 2: successful 1 + α/2 = 2, unsuccessful 1 + α = 3. In linear probing, successful ½ (1 + 1/0.2) = 3, unsuccessful ½ (1 + 1/0.04) = 13. The chained table is faster although it is twice as full.
Keys are inserted in turn into an empty table of 11 slots; after each insertion, if
2 * n > m, the table is grown to sizenext_prime(2 * m). After which insertion do the first two growths happen, and what are the new sizes?Cevap
The first growth happens after the 6th insertion (12 > 11); the new size is
next_prime(22)= 23. The second happens after the 12th insertion (24 > 23); the new size isnext_prime(46)= 47.Double hashing is used with m = 10 and for one key h1 = 5, h2 = 6. What is the probe sequence and why is it problematic?
Cevap
The sequence is (5 + 6i) mod 10: 5, 1, 7, 3, 9, 5, 1, … Only five slots are probed, because 6 and 10 have a common divisor of 2. Even if the table has room, this key may fail to find it. If m is chosen prime, the problem disappears.
The chain of bucket 2 is 22 → 7 → 12 and
chain_erase(22)is called. How many rounds does the loop run, and which pointer is updated?Cevap
The loop does not run at all:
pis the first node and its key is 22.prevstaysNULL; thereforebucket[2] = p->nextis executed and the bucket now points to the node of 7. Then the node of 22 is freed; the chain becomes 7 → 12.The key is
int k = -15and m = 11. What isk % min C? What is the correct home address?Cevap
In C,
-15 % 11is −4; this index is outside the array. The correct home address is −4 + 11 = 7 (h_safe(-15, 11)).
14.13Further reading
- E. Horowitz, S. Sahni and S. Anderson-Freed, Fundamentals of Data Structures in C (2nd ed.), Chapter 8: the source followed in these notes for static and dynamic hashing, the division, mid-square and folding methods, and linear and quadratic probing with chaining.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms (3rd ed.), Chapter 11: gives direct addressing, the analysis of chaining, the division and multiplication methods, universal hashing and proofs of the expected number of probes in open addressing.
- R. Sedgewick, Algorithms in C, Parts 1–4 (3rd ed.), Chapter 14: treats hash functions, chaining, linear probing and double hashing with C code and experimental comparisons.
- D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.), Section 6.4: contains the original analysis of the formulas ½ (1 + 1/(1 − α)) and ½ (1 + 1/(1 − α)2) for linear probing and the rationale for the choice of the golden ratio in the multiplication method.
14.14References
- E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Chapter 8 (Hashing).
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, Chapter 11 (Hash Tables).
- R. Sedgewick, Algorithms in C, Parts 1–4, 3rd ed., Addison-Wesley, Chapter 14 (Hashing).
- D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998, Section 6.4.
Related pages: Chapter 14 slides · © Sercan Külcü. All rights reserved.