ICOM 4035 – Data Structures

Fall 2007

 

Laboratory 9: Hash Tables

 

1.    Objectives

 

  1. Introduce the Hash Table data structure.
  2. Compare the HashTables to trees, lists, stacks and queues.
  3. Partial implement a HashTable and use it on an application.

 

2.    Overview

 

The data structures you have seen until now are perfect for dynamic allocation of unknown amount of data. However when it comes to a large amount of data the structures start to behave slowly and getting the desired information takes a lot of time. To solve this issue two alternatives exist, the first one is creating a search tree to speed up the process; this will be done in the next laboratory. For now you will focus in the other technique which is creating a new data structure called the hash table. A hash table is a structure composed of arrays of all sorts of things. In this laboratory you will have an array of DLList. The index where the data is to be stored is calculated using a mathematical function referred as a hash function which receives an object and associates an index (hash code) to it. Collisions occur when two different objects have the same hash code, you won’t have to worry for this because the problem will be taken care of by using the DLLists which will allow infinite objects with the same hash code to be stored in the same index. There are several other techniques to deal with these collisions, such as adding a number to the index until no collision is found or rehashing the object among others.

 

3.    Practice

 

In this laboratory you are asked to implement two functions inside of the hash table.

put(E item) :- will add the item according to its key and hash code in the appropriate index.

hashCode(E item) :- returns the index to store or search the item. The hash code will go as follows.

 

Download the source code here.