CSC 207 Grinnell College Fall, 2014 Algorithms and Object-Oriented Design

# Hash Tables

## Summary

This lab provides practice with several basic algorithms related to hash tables.

## Insertion into 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).

1. 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.

1. Closed, unbucketed hash table, using linear probing
2. Closed, unbucketed hash table, using quadratic probing
3. Open, bucketed hash table (with chaining)

Show the resulting structure by filling in the following tables:

Closed, unbucketed hash table
using linear probing
Closed, unbucketed hash table
```http://www.walker.cs.grinnell.edu/courses/207.sp012/labs/lab-hashtables.shtml