Homework: Hashes

   < Previous  Next >
Write your answers to the following questions in a flat text file hwkHashes.txt (not a Word document nor a Rich Text Format file):
  1. Define the following:
    1. Collision
    2. Perfect hash function
    3. Uniform hash function
    4. Open addressing
    5. Primary clustering
    6. Secondary clustering
    7. Load factor α
  2. Describe the major steps for the following operations on a hash table that uses separate chaining (feel free to use your answers as comments for your lab):
    1. Inserting an item
    2. Retrieving an item
    3. Deleting an item
    4. Displaying all items in the hash table
  3. If a hash table has a load factor α of 5/6, what is the approximate average number of comparisons that a (successful) search requires (for a successful search) for the following:
    1. Separate chaining
    2. Linear probing
    3. Quadratic probing
  4. When should each of the following collision resolution schemes be rehashed?
    1. Separate chaining
    2. Linear probing
  5. If h(x) = x mod 11 and separate chaining resolves collisions, what does the hash table look like after the following insertions occur into an empty hash table: 12, 10, 23, 16, 34, 2, 3?
    index  
    0  
    1  
    2  
    ...  
  6. If h(x) = x mod 11 and linear probing resolves collisions, what does the hash table look like after the following insertions occur into an empty hash table: 12, 10, 23, 16, 34, 2, 3?
    index value
    0  
    ...  
  7. If h(x) = x mod 11 and quadratic probing resolves collisions, what does the hash table look like after the following insertions occur into an empty hash table: 12, 10, 23, 16, 34, 2, 3?
    index value
    0  
    ...  
  8. If h(x) = x mod 11 and double hashing resolves collisions, what does the hash table look like after the following insertions occur into an empty hash table: 12, 10, 23, 16, 34, 2, 3?
    (Use f(i) = i*h2(x), h2(x) = R - (x mod R) where R is the prime number just smaller than the table size.)
    index value
    0  
    ...  
  9. What is the load factor α of the hash table in preceding problem?
  10. If h(x) = x mod hashTableSize and separate chaining resolves collisions, and using hwkHashes-table.txt as the hash table, write down just the affected list(s) after
    1. inserting 10007, 10008, 10009
    2. deleting 10010

Submission

Submit your txt file at https://3110.cs.mtsu.edu/. For further instructions, please see the Miscellaneous page.

Rubric:

Points        Question
-----------   --------------------------------------------------------------
_____ / 3.5   1
_____ /   2   2
_____ / 1.5   3
_____ /   1   4
_____ /   2   5
_____ /   2   6
_____ /   2   7
_____ /   2   8
_____ /   1   9
_____ /   1   10

_____ /  18   Total