Sample Code

An Implemenation of a Hash Table Using Linear Probing to Resolve Collisions.

//-----------------------------------------------
// Demonstrate a hash table with linear probing.
//
// D. Searls
// Asbury University
// Jan 2012
//-----------------------------------------------

#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;

int const MAXSIZE = 211;  // Try 101, 211, and 997

struct shoeType
{
    int stockNum;
    string style;
    string color;
    int size;
    string width;
    
    void display()
    {
        cout << left << setw(10) << stockNum;
        cout << setw(10) << style;
        cout << setw(10) << color;
        cout << setw(7) << size;
        cout << setw(10) << width;
        cout << endl;
    }
};

//---------------------------------------------------------
// linearSearch
//
// Return the index at which the item with the specified
// stock number was found. If the item is not in the list,
// then return -1.
//
// In parameters: item, list, n
//---------------------------------------------------------
int linearSearch(int stockNum, const shoeType list[], int n)
{
    int pos = n-1;
    while (pos >= 0 && stockNum != list[pos].stockNum)
    {
        pos--;
    }
    return pos;
}

//---------------------------------------------------------
// hashInsert
//
// Insert the specified item into the hash table using
// linear probing to resolve collisions.
//
// Precondition: the table is not full.
//
// In Parameters: item, list
//---------------------------------------------------------
void hashInsert(shoeType item, shoeType list[])
{
    int pos = item.stockNum % MAXSIZE;
    while (list[pos].stockNum != 0)
    {
        pos++;
        if (pos == MAXSIZE)
        {
            pos = 0;
        }
    }
    list[pos] = item;
}
    
//---------------------------------------------------------
// hashSearch
//
// Return the index at which the item with the specified
// stock number was found. If the item is not in the list,
// then return -1.
//
// Precondition: the list is not full.
//
// In parameters: stockNum, list
//---------------------------------------------------------
int hashSearch(int stockNum, const shoeType list[])
{
    int pos = stockNum % MAXSIZE;
    while (list[pos].stockNum != stockNum && list[pos].stockNum != 0)
    {
        pos++;
        if (pos == MAXSIZE)
        {
            pos = 0;
        }
    }
    if (list[pos].stockNum == 0)
    {
        pos = -1;
    }
    return pos;
}

//*********************************************************
//*              M A I N   D R I V E R
//*********************************************************

int main()
{
    ifstream infile;
    shoeType shoe[MAXSIZE];
    shoeType myShoe;
    int pos;   // position of item in list
    int count; // number of items found
    int n;     // number of items in list
    
    // Read data into ordinary array and search for all possible
    // stock numbers.
    
    infile.open("ShoeData.txt");
    n = 0;
    infile >> myShoe.stockNum >> myShoe.style >> myShoe.color >> myShoe.size >> myShoe.width;
    while (!infile.fail())
    {
        shoe[n] = myShoe;
        n++;
        infile >> myShoe.stockNum >> myShoe.style >> myShoe.color >> myShoe.size >> myShoe.width;
    }
    infile.close();
    cout << n << " items in list" << endl << endl;
    
    count = 0;
    for(int stockNum = 1000000; stockNum < 10000000; stockNum++)
    {
        pos = linearSearch(stockNum, shoe, n);
        if (pos >= 0)
        {
            shoe[pos].display();
            count++;
        }
    }
    cout << count << " items were found" << endl << endl;
    
    //****************************************************************
    // Now, do it all over again using a hash table to store the data.
    //****************************************************************
    
    // Set up the table with invalid stock numbers.
    
    for (int i = 0; i < MAXSIZE; i++)
    {
        shoe[i].stockNum = 0;
    }
    
    // Read the data into the file.
    
    infile.open("ShoeData.txt");
    n = 0;
    infile >> myShoe.stockNum >> myShoe.style >> myShoe.color >> myShoe.size >> myShoe.width;
    while (!infile.fail())
    {
        hashInsert(myShoe, shoe);
        n++;
        infile >> myShoe.stockNum >> myShoe.style >> myShoe.color >> myShoe.size >> myShoe.width;
    }
    infile.close();
    cout << n << " items in list" << endl << endl;
    
    // Perform the searches
    
    count = 0;
    for(int stockNum = 1000000; stockNum < 10000000; stockNum++)
    {
        pos = hashSearch(stockNum, shoe);
        if (pos >= 0)
        {
            shoe[pos].display();
            count++;
        }
    }
    cout << count << " items were found " << endl << endl;
    
    

    
    return 0;
}