CSC161 2010F, Class 45: Hash Tables, Continued

Overview:
* Review.
* Collisions.
* A Hash Function.
* Building Code.
  * Header - Data type and functions
  * Tests - Interactive and unit
  * Implementation(s).

Admin:
* Food.
* A Kington story.
* Assignment 9 is now ready.
* Soda experiment!

Dictionaries and Hash Tables
* A dictionary associates things with other things
  We call one value the key and the other the value
  Both are traditinally strings
  * Effectively, "an array indexed by strings rather than integers"
* Hash tables are one implementation of dictionaries
  * As long as we want the behavior of an array, use an array
  * Use a hash function to turn strings (keys) into integers (index in
    the array)

Hash Function (see code)

Problem: We have collisions!
* That is, multiple keys can hash to the same number
* Multiple mechanisms for dealing with collisions
  * Linear Probing
    If you can't put it in slot N, try N+K mod table size, N+2K mod table size, N+3K mod table size, ...
  * Progressive Probing
    If you can't put it in slot N, try N+f(K) mod table size
      f is often K^2
  * Don't store key/value pairs in each place, store lists of key value pairs

Traditionally: The hash table should have size 2x#elements

Steps:
* Define the type
* Describe the functions (document)
* Unit tests
* Write the code for the functions