Hashing Exercises

Complete the following individually, then turn to a neighbor to confirm your answers.
  1. Hash Table Basics
    1. What is the underlying data structure for a hash table?
    2. A _______ determines the location to start to look in a hash table for a key.
    3. What would the hash function look like if a string is used as the key?
    4. Explain the pattern displayed when adding in each character using string folding: StringFoldingDemo.java
    5. What are the requirements for a good hash function?
    6. A hash function should be careful not to just use the high- or low-order bits of the key value. What are the high-order and low-order bits?
    7. Insert the following numbers into a hash table of size 7 and draw the resulting hash table:
      • 0
      • 1
      • 4
      • 9
      • 16
    8. Calculate the load factor α for the previous example.
  2. Hashing: Handling Collisions
    1. For each of the following strategies:
      1. Separate chaining
      2. Linear probing (f(i) = i, or p(K,i) = i)
      3. Quadratic probing (f(i) = i2, or p(K,i) = i2)
      4. Double hashing (f(i) = i * h2(x), or p(K,i) = i * h2(K)) and h2(x) = R - (x % R) (where R is the prime number just smaller than tableSize M)
      Do the following:
      1. Given a hash table with 7 entries, draw the hash table and its contents after inserting the following numbers: 7, 11, 71, 42, 13, 49
      2. Describe the major steps for:
        1. Inserting an item
        2. Retrieving an item
        3. Deleting an item
        4. Displaying all items in the hash table
      3. Calculate the load factor α
  3. Rehashing
    1. What is rehashing?
    2. What are the major steps of rehashing?
    3. Why do we rehash?
    4. When do we rehash?

Last Modified: