Data Structures Program #13

CS 153 Data Structures I

Assignment #13

Due: 4/26/01

Purpose: to learn about using HASH tables (with overflow chaining)

Task: Build a Hash capability that attempts to store a new value in the PRIMARY array. If the 'home' slot for the new value is already occupied in the PRIMARY array, store the new value in the OVERFLOW array. Each HOME slot should be the head of a potential link/chain to the synonyms of that slot. The PRIMARY and OVERFLOW arrays should hold struct Node(s)

struct Node
{ int data;
int next;};

Assume that you only need to store 15- 20 values. Since you need to demonstrate the correctly handling of collisions, make PRIMARY size 10 using mod 10 as your hash function. This will make it easy to create collisions. Make OVERFLOW size 50 to avoid any size problems.

class Hash contains:

Hash::Hash();
Hash::~Hash();
void Hash::Insert(int);
bool Hash::Find(int);
void Hash::Remove(int);
Node PRIMARY[10];
Node OVERFLOW[50];

Detail:

Hash::Hash(); - Initialize the private data arrays
Hash::~Hash(); - Nothing to do since there is no dynamic data
void Hash::Insert(int); Put a new value into either PRIMARY or OVERFLOW as appropriate
bool Hash::Find(int); Return true or false
void Hash::Remove(int arg); Locate and remove. Several possibilities exist
1. arg is in PRIMARY and no synonyms exit
2. arg is in PRIMARY and synonymns do exit
3. arg is in OVERFLOW

GUI Interface

Buttons
- Insert
- Find
- Remove
EditBox