Hash Table Exercises

   < Previous  Next >

Hash Table Basics

  1. Describe how hashing works (including what is the underlying data structure for a hash table and what is a hash function)
  2. What would the hash function look like if a string is used as the key?
  3. What are the requirements for a good hash function?
  4. Identify multiple scenarios when it is appropriate to use a hash table

Handling Collisions

  1. Using the following strategies, and given a hash table with 7 entries, draw the hash table and it's contents after inserting the following numbers: 7, 11, 71, 42, 13, 49:
    1. Separate chaining
    2. Linear probing
    3. Quadratic probing
    4. Double hashing
  2. Calculate the load factor α for each of the previous strategies in the exercise above.

Rehashing

  1. What is rehashing and what are the major steps of rehashing?
  2. Why do we rehash?
  3. When do we rehash?

Hashing Efficiency

  1. Discuss the advantages and disadvantages of the following implementations for hash tables (use efficiency as evidence to support your claims):
    1. Separate chaining
    2. Linear probing
    3. Quadratic probing
    4. Double hashing

    Last Modified: