Week8 Labs

Lab1.cpp

// TODO: Augment the hash table so all string characters are used in the hashing process
// Update3: Changed the array to be a three dimensional array which supports 2 slots for hash-data entry

#include <cstdlib>
#include <iostream>
#include <string.h>

using namespace std;

int hash_string(char str_name[]);

int main()
{
	int pass, slen, spos, hash_value;
	char hash_str[9];
	char hash_table[64][2][9];
  int collisionArray[64]; // stores the collisions in the table position
  int collisions = 0;

	// init hash table
	for ( pass = 0; pass < 64; pass++)
	{
    for (int innerpass = 0; innerpass < 2; innerpass++)
    {
		hash_table [ pass ][innerpass][0] = '\0';
    }
    collisionArray[ pass ] = 0; // init the collision table to 0
  }

	// produce 64 strings to be hashed
	for ( pass = 0; pass < 64; pass ++)
	{
		// generate random string of 5 to 8 chars
		slen = 5 + rand() % 4;
		spos = 0;
		do
		{
			hash_str[ spos ] = 'A' + rand() % 25;
			spos++;
			slen--;
		} while ( slen != 0 );
		hash_str[ spos ] = '\0';
		
    //display the string and its hash value
    if ( 0 == pass % 4 )
    {
      cout << endl;
    }
    cout << hash_str << ", " ;
		hash_value = hash_string ( hash_str );
    cout << hash_value << "\t";

    // check for collision
    if ( '\0' == hash_table[ hash_value ][0][0] )
    {
      strcpy( hash_table[ hash_value ][0], hash_str );
    } else if ('\0' == hash_table[ hash_value ][1][0]) {
      strcpy( hash_table[ hash_value ][1], hash_str );
    } else {
      collisions++;
      collisionArray[ pass ]++;
    }
	
  }
  cout << endl;
  cout << "There were " << collisions << " collisions. " << endl;

  cout << endl << endl;
  // second for loop to display the actual hash table
	for ( pass = 0; pass < 64; pass ++)
	{
    // do a repeat display of the actual hash table itself
   if ( 0 == pass % 4 )
   {
     cout << endl;
   }
   
   cout << pass << ":";
   if (hash_table[pass][0][0] == '\0')
   {
    cout << "______"; 
   } else {
    cout << hash_table[pass][0];
   }
    // print space between the 2 "cells" in table
   cout << " ";

    if (hash_table[pass][1][0] == '\0')
    {
    cout << "_____";
    } else {
    cout << hash_table[pass][1]; 
    } 
    cout << "," << collisionArray[pass] << "\t";
  
  }

  return EXIT_SUCCESS;
}

int hash_string(char str_name[])
{
  int hashval;

  hashval = str_name[ 0 ];
  hashval ^= str_name[ strlen( str_name ) / 2 ];
  hashval += str_name[ strlen( str_name ) - 1 ];
  return ( hashval & 0x3f );
}