CS211: Hash Tables

Sometimes when programming, it can be convenient to think of collections of data in the form of pairs. For example, if you're implementing a benchmarking suite which will run multiple different applications and store their behavioral data it's natural to want some sort of data structure which attaches an application's name with that information. It would be convenient to have a singular source that can be quickly indexed by sending in the target application's name. Python provides exactly that natively with dictionaries:

1: benchmarks = ["sunflow", "jython", "h2"]
2: behavior_stats = dict()
3: for b in benchmarks:
4:     behavior_stats[b] = run(b)
5: # ...
6: print(f"sunflow took {behavior_stats['sunflow'].wall_time}s to run!")

Python's dictionary, or dict, class is implemented under the hood as a hash table.

A hash table "is a generalization of the simpler notion of an ordinary array"¹. The idea is to be able to approximate the immediacy of an array while also abstracting the indexing mechanism to fit for any datatype the user defines. This is what the example in Listing 1 is showing: we can index into the hash table, behavior_stats, with a string! This is a major upgrade for thinking through certain programming challenges where sets of data need to sync up with a common non-integer identifier. A hash table is essentially just an array with an extra step for determining the desired index—the extra step is called a hash function.

We can define a simple hash table API as follows:

• init
  • Initializes a hash table
• insert
  • Inserts an element with the desired key into the hash table
• get
  • Retrieves the element with the desired key from the hash table
• delete
  • Removes the element with the desired key from the hash table
• free
  • Frees the hash table

A hash function is any function which takes some "key" input and maps it to an index.

One way to handle collisions is through a strategy called chaining. The "chain" in chaining refers to using a linked list for every index in the hash table array. When an element maps to an index, then that element is stored within the linked list associated with that index. We can visualize this below:

index    array

       +-------+   +-------+    +-------+
 [0]   |   A   | → |   B   | →  |   C   | → NULL
       +-------+   +-------+    +-------+
 [1]   |   D   | → NULL
       +-------+
 [2]   |  NULL |
       +-------+   +-------+	     
 [3]   |   E   | → |   F   | → NULL 
       +-------+   +-------+	      
 [4]   |  NULL |    
       +-------+

Although the above works well to handle collisions, it can detract from the initial incentive of the quick retrieval of elements when using hash tables.

There are some heuristic hashing function methods that are often employed in real-world hash maps such as the division method, multiplication method, mid square method, and the digit folding method

• Division method
  • h(k) = k mod m
  • m should not be a power of 2
  • a prime not too close to a power of 2 yields good results
• Multiplication method
  • h(k) = ⌊m (k A mod 1)⌋ where A in range 0 < A < 1
  • m is often a power of 2
  • Donald Knuth suggests A = (5^(1/2) - 1)/2
• Mid square method
  • h(k) = k^(2) and extract middle r digits
• Digit folding method
  • Subdivide k into groups of digits
  • Add those digits together

I have included a Python script, hash_benchmark.py, which can be used to see how these collision functions work in practice with different distributions of data.

Closed hashing, sometimes called open addressing, refers to a hash table strategy where chaining is eschewed for other clever workarounds to collisions. Instead of having each index mapped to a linked list, an empty index will be found to map the element to. We'll look at three types of closed hashing strategies: linear probing, quadratic probing, and double hashing.

Recall our discussion of vectors. When a vector got too full, a categorization dependent on the implementation, it would need to be "stretched out" with the contents copied over to another, larger array. Rehashing works in the exact same way, although the major difference is that elements can no longer be naively copied over---they must be hashed again.

1. Using the hash function f(x) = x % 7 and the input [14, 27, 3, 56, 91, 42], compute the index for each element by hand and draw the resulting hash table array. Does any collision occur? If so, identify which elements collide and at which index.
2. Run hash_benchmark.py --summary with the default distributions and record the collision counts for each method. Then run it with --graph and compare the growth curves. Which method performs best on each distribution and why? Write a short paragraph summarizing your findings.
3. Implement a hash table in C using the chaining strategy shown in the lecture. Your implementation should use an array of linked list heads as the underlying structure. Implement insert, get, and delete operations. Test it by inserting [10, 22, 31, 4, 15, 28, 17, 88, 59] with the hash function h(k) = k % 7 and printing the contents of each bucket.
4. The lecture states that chaining "can detract from the initial incentive of quick retrieval." Explain in your own words why this is the case. What is the worst case number of comparisons needed to find an element in a hash table using chaining when all elements hash to the same index?
5. Implement linear probing in C. Using the hash function h(k) = k % 8 and the sequence [10, 17, 432, 1, 100, 133, 31], insert each element and print the final state of the array. How many probing steps were required in total across all insertions?
6. Using the quadratic probing formula h(k, i) = (h(k) + (a × i) + (b × i²)) mod m with a = b = 1 and m = 8, manually compute the insertion index for 100 given that h(100) = 0 and indices 0 and 2 are already occupied. Show each step of the calculation. Then implement quadratic probing in C and verify your result.
7. The double hashing example in the lecture uses h(k) = k mod 13 and g(k) = 1 + (k mod 11) to insert 14. Verify each step of the calculation by hand: confirm that index 1 collides, that index 5 collides, and that index 9 is empty. Then use the same two hash functions to insert the value 27 into the same table and show each probing step.
8. The lecture compares rehashing to the resizing of vectors. Implement a hash table in C that tracks its load factor (number of elements divided by table size) and automatically rehashes into a table twice the size when the load factor exceeds 0.7. Verify by inserting enough elements to trigger a rehash and printing the table before and after.