Name: ________________________________

CSE373 Spring Quarter
University of Washington
Miniquiz #10
May 6, 2005
Closed book, closed notes, closed neighbor; no calculators
1 point per part except as noted

 
. 
When two keys map to the same index in a hash map, we say there is a...
  1. collison
  2. collusion
  3. collapse
  4. conundrum
 
. 
If a hash function is guaranteed never to produce the same index for two different keys, we call it a _________ hash.
  1. profound          
  2. perfect
  3. party-time
  4. prismatic
 
. 
 
0 1 2 3 4 5 6 7 8 9
                                                 

 

At the Last National Bank, account numbers are 8 digit (decimal) integers, starting with a 1 or 2.  Suppose the account objects are kept in a hash table of size 10.    The account number is used as the key.

3. Suppose the hash function is computed by extracting the second digit (from the right) of the 8-digit account number.  Give an example of two (different) keys which hash to the same index.

 

4. Suppose the hash function is computed instead by adding up the 8 individual digits, then that number mod 10 is used as the index.  Give an example of two keys which hash to the same index.

 

 

 

 

 

 

 

2. Go back to the array representation.  Modify the array to show the results of adding the value 18 to the heap.  [Show this directly on the array above].