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