Hash Tables

• Vocabulary: hash, key, collision-resolution technique, clustering
• Hash algorithms - what are they, how are they used, what makes them good, and what makes them bad?
• Collision resolution techniques - linear probing, double hashing, linked-list collision resolution. What are they, and what are their advantages and disadvantages?
• Given a hash function and collision resolution technique, show the state of the hash table after a particular sequence of insertions.
• Universal hashing - how do we maintain constant time, on average, amortized over many operations?