CSE 214 Computer Science II (Spring 2015)

RECITATION 7 – Maps and Hash Tables

Objective:

1. To Study Map and Hash table

1. [20 min] Draw the 11-entry hash table to hash the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5. For the following

1. Results from using the hash function, h(i) =(3i+5) mod 11, assuming collisions are handled by chaining.
2. When collisions are handled by double hashing using the secondary hash function h′(k) = 7−(k mod 7).

2. [10 min][Open Addressing] Consider inserting the keys 7, 22, 35, 4, 15, 26, 48, 12 and 20 into a hash table of length m=13 using open addressing with the hash function h(k) =k mod13.  Illustrate the result of inserting these keys using quadratic probing.

3. [5 min] Show the effect of a series of operations on an given map {(7,B), (5,T),(3,Y),(9,H),(2,L)} storing enteries with integer keys and single character values.

1. Put(3,K)
2. Get(9)
3. Remove(2)
4. Size()
5. Put(4,I)

4. [10 min] What would be a good hash code for a vehicle identification number that is a string of numbers and letters of the form “9X9XX99X9XX999999,”where a “9” represents a digit and an “X” represents a letter?

5. [5 min] What is the worst-case time for putting n entries in an initially empty hash table, with collisions resolved by chaining? What is the best case?

6. [10 min]Consider lines of the given Code Fragment for the implementation of the class ChainHashMap. Here, we use the difference in the size of a secondary bucket before and after a call to bucket.remove(k) to update the variable n. If we replace [lines 31-33] with the following, does the class behave properly? Explain.

[Link: http://www3.cs.stonybrook.edu/~sael/teaching/cse214/rec/AbstractHashMap.java]

[Link: http://www3.cs.stonybrook.edu/~sael/teaching/cse214/rec/ ChainHashMap.java]

V answer = bucket.remove(k);

if (answer != null) // value of removed entry

• −; // size has decreased