CSC 207 Grinnell College Spring, 2012
 
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
    using quadratic probing     		Open, bucketed hash table (with chaining)
    0     
    1     
    2     
    3     
    4     
    5     
    6     
    7     
    8     
    9     
    10     
    11     
    12     
    13     
    14     
    15     
    0     
    1     
    2     
    3     
    4     
    5     
    6     
    7     
    8     
    9     
    10     
    11     
    12     
    13     
    14     
    15     
    0 ⇒ 
    1 ⇒ 
    2 ⇒ 
    3 ⇒ 
    4 ⇒ 
    5 ⇒ 
    6 ⇒ 
    7 ⇒ 
    8 ⇒ 
    9 ⇒ 
    10 ⇒ 
    11 ⇒ 
    12 ⇒ 
    13 ⇒ 
    14 ⇒ 
    15 ⇒ 

This document is available on the World Wide Web as 

http://www.walker.cs.grinnell.edu/courses/207.sp012/labs/lab-hashtables.shtml
created 30 April by Henry M. Walker
revised 7 May 2012 by Henry M. Walker 		Valid HTML 4.01! Valid CSS!
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.

Copyright © 2009-2011 Jerod Weinman.
CC-BY-NC-SA
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License .