CSC 207  Grinnell College  Spring, 2012 
Algorithms and ObjectOriented Design  
This lab provides practice with several basic algorithms related to hash tables.
A hash function returns integers between 0 and 15 based on the first letter of a data item according to the following table.
A  B  C  D  E  F  G  H  I  J  K  L  M 
10  7  12  1  3  5  10  1  8  15  14  13  9 
N  O  P  Q  R  S  T  U  V  W  X  Y  Z 
6  11  3  12  2  5  13  9  15  6  3  0  7 
For example, according to this hash function, the string TM would hash to the value 13 (based on the initial letter T; the hash function does not look at the second letter M).
Consider the following sequence of 11 data items:
MQ GR GD WZ QS HW DT AX AL CY EM
Suppose the above sequence is to construct each of the following data structures 16 locations (labeled 0 through 15), based on the hash function given above.
Show the resulting structure by filling in the following tables:
Closed, unbucketed hash table using linear probing 
Closed, unbucketed hash table using quadratic probing  Open, bucketed hash table (with chaining)  



This document is available on the World Wide Web as
http://www.walker.cs.grinnell.edu/courses/207.sp012/labs/labhashtables.shtml
created 30 April by Henry M. Walker revised 7 May 2012 by Henry M. Walker 

For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. 