Hashing with collision resolution

[May Amor]

Helu gurus!!! I have a code below about hashing method with collision resolution...My problem is how to use the collsion resolution again if the hash index though has already a value. Please kinda help me with this..I want to determine also if the table now is full so as to stop user from entering a key.
size of the table=19,
Thanx a lot..GodBless
_______________ _______________ _______________ ___

#include<iostream.h>
#include<conio.h>
 
//function prototypes
int input(int);
int process(int);
void output(int,int);
int collision(int,int);
 
//global variable
int arr[19]={0};
 
//start of main program
 main()
{
int key,hash_key,hash_index,m=0;
cout<<"Hash method: FOLD BOUNDARY";
cout<<"\nCollision resolution method: KEY OFFSET";
cout<<"\nEnter 6 digit numbers.";
cout<<"\nEnter 0 as sentinel.";
while(m<19){
 
 hash_key=input(key);
 if (hash_key==0) { return 0;}
 else
   {     hash_index=process(hash_key);
      output(hash_key,hash_index); }
 
  }  m++;
cout<<"\nEntered numbers execeeded!"; //end of loop
}//end of main program
 
//start of input function
int input(int x){
cout<<"\n\nEnter key:";
cin>>x;
return x;}
//end of input function
 
//start of process function
int process(int x){
  int a,b,c,d,e,f;
    a=x/100000;
    b=x%100000/10000;
      int v=(b*10)+a;
 
   c=x%10000/1000;
     d=x%1000/100;
     int q=(c*10)+d;
 
    e=x%10;
     f=x%100/10;
     int w=(e*10)+f ;
 
     return (w+v+q)%19+1;
}  //end of process function
 
//start of output function
void output(int key,int adres){
int b,z,index1=0,index2=0,index3=0,index4=0,u;
bool wer;
cout<<"\n\tList\tKey\n";
 
while (arr[adres-1]!=0)
    { index1=collision(key,adres);
       arr[index1-1]=key;break;
 
if (arr[index1-1]!=0)
 { index2=collision(key,index1);
   arr[index2-1]=key;
 
if(arr[index2-1]!=0)
     { index3=collision(key,index2);
       arr[index3-1]=key;
   }
 }
} 
 
   if (arr[adres-1]==0)
   { arr[adres-1]=key; }
 
for(u=0;u<19;u++){
      z=arr[u];
      cout<<"\t"<<(u+1)<<".\t"<<z<<endl; }
}
 
    //end of output function
 
//start of collision resolution method
int collision(int key,int hashed){
int offset,adrs;
offset=(key/19;
adrs=((offset + hashed) % 19 )+1;
return adrs;
}
//end of collision resolution method

[Flugeldorph]

May,

The following is rather lengthy, but is a complete system which contains a hashing algorithm that I cranked out in the past hour. Some code was borrowed from some previous software that I had written. At any rate, the code is written in C, as a console program, not in C++ but you should be able to use it directly from within C++.

This shows a method of hashing where you never have to worry about running out of space, and don't have to concern yourself with collisions as they will all be gracefully addressed.

What this does, is take a text file as input, parses out all ot the words (including non words, as I didn't spend the time to remove them), then adds the words to a hash table. If the word already exists in the table, only the count is incremented.

The hashing algorithm is taken directly from the Aho book on compiler design. It works extremely well with strings, but dosen't handle numbers without conversion to text. This is a small price to pay, because it is extremely fast as far as operation is concerned. I used to be able to process one million phone calls per minute on an HP9000 for a major phone company.

Once the file has been added to the hash table, you are allowed to enter words, which will be looked up in the hash table and displayed on the console, along with the number of times that it appears in the document.

The code will be in 8 small files. the only two that you will really need to look at are Hash.c, LoadHashTable.c and TryItOut.c the rest are part of the complete package.

If you have any questions at all, please ask.

Module name HashExample.h

#ifndef __HashExample__h
#define __HashExample__h
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
 
#define MASK                0xf0000000
#define SHIFT               24
#define HashTableNumItems   5003    // Needs to be a prime number for
                                    // best distribution. At least 10% of
                                    // estimated data size.
 
#define FileBuffSz          4096
#define Buff80              80
#define Buff256             256
 
#ifndef bool
#define bool                int
#endif
 
#ifndef True
#define True                1
#define False               0
#endif
 
typedef struct _wordused
{
   struct _wordused *Next;
   char *WordUsed;
   long NumberOfTimesUsed;
} wordused;
 
typedef struct
{
   long                     SysInfoSz;
   FILE                     *InFile;
   FILE                     *Trace;
   char                     *InFileName;
   char                     *InBuff;
   wordused                 *HashTable[HashTableNumItems];
   int                      argc;
   char                     **argv;
   long                     TotalNumberOfWords;
} sysinfo;
 
// Function prototypes
void main(int argc, char** argv);
void Initialize(sysinfo *SysInfo);
void TryItOut(sysinfo *SysInfo);
void FreeData(sysinfo *SysInfo);
void LoadHashTable(sysinfo *SysInfo);
unsigned int Hash(char *String, long TabLen);
void SysAbort(sysinfo *SysInfo, char *String, int NumArgs, ...);
#endif

Module Name: HashExample.c

/*
*
*  Example of Hashing which never runs out of space, and
*  handles collisions gracefully and painlessly
*
*  Usage for this Example HashExample -f FileName
8      where filename = the name of a local text file
*              or remote file (with full path)
*
*       What does it do? It will parse all of the words
*         In the input file, counting the number of
*         occurences of each word. After the input file
*         has been parsed, the user can query on a word
*         and the count will be returned.
*
*       Plese note that the hashing algorithm used expects
*         a string input, there fore integers, floats, etc.
*         must be converted to string before hashing. The
*         algorithm does, however, give extremely good
*         distribution, thus making it ideal for very large
*         amounts of entries. I used it while employed in the
*         telecommunications industry for looking up data in
*         indexed flat files (created using the hash) of over
*         4 million records. The original algorithm comes from
*         Compilers: Principles, Techniques, and Tools ...
*         By: Alfred V. Aho - fondly known as the Dragon book.
*
*        Enjoy !
*
*/
#include "HashExample.h"
 
void main(int argc, char** argv)
{
   sysinfo *SysInfo = NULL;
 
   SysInfo = (sysinfo *) calloc(1, sizeof(sysinfo));
   SysInfo->argc = argc;
   SysInfo->argv = argv;
 
   Initialize(SysInfo);
   LoadHashTable(SysInfo);
   TryItOut(SysInfo);
   FreeData(SysInfo);
   free(SysInfo);
}
 

Module Name: Initialize.c

#include "HashExample.h"
 
void Initialize(sysinfo *SysInfo)
{
   char        *ArgPtr       = NULL;
   char        Argid         = 0;
   int         i             = 0;
 
   SysInfo->SysInfoSz = sizeof(sysinfo);
   for(i = 1; i < SysInfo->argc; i++)
   {
      if(SysInfo->argv[i][0] == '-')
      {
         Argid = SysInfo->argv[i][1];
         if(!SysInfo->argv[i][2])
         {
            i++;
            ArgPtr = SysInfo->argv[i];
         }
         else
            ArgPtr = (char *)&SysInfo->argv[i][2];
         switch (Argid)
         {
            case 'f':
               SysInfo->InFileName = ArgPtr;
               break;
            default:
               SysAbort(SysInfo, "%c is not a valid option", 1, Argid);
         }
      }
   }
 
   if(SysInfo->InFileName == NULL)
      SysAbort(SysInfo, "Please Specify Input File Name with -f option", 0);
 
   SysInfo->InBuff = (char *)calloc(1, FileBuffSz);
   SysInfo->TotalNumberOfWords = 0;
}
 

Module Name: SysAbort.c

#include "HashExample.h"
 
void SysAbort(sysinfo *SysInfo, char *String, int NumArgs, ...)
{
   va_list       ap;
   va_start(ap, NumArgs);
 
   vfprintf(stderr, String, ap);
 
   va_end(ap);
 
   // Check if n\memory needs to be cleaned up
   FreeData(SysInfo);
 
   free(SysInfo);
   exit(1);
}

Module Name: FreeData.c

#include "HashExample.h"
 
void FreeData(sysinfo *SysInfo)
{
   int i = 0;
   wordused *CurrentNode = NULL;
   wordused *NextNode    = NULL;
 
   fclose(SysInfo->InFile);
 
   for(i = 0; i < HashTableNumItems; i++)
   {
      CurrentNode = SysInfo->HashTable[i];
      if(CurrentNode)
      {
         while(CurrentNode)
         {
            NextNode = CurrentNode->Next;
            free(CurrentNode->WordUsed);
            free(CurrentNode);
            CurrentNode = NextNode;
         }
      }
   }
 
   free(SysInfo->InBuff);
}
 

Module Name: Hash.c

#include "HashExample.h"
 
unsigned int Hash(char *String, long TabLen)
{
   unsigned long HashCode = 0;
   unsigned long g = 0;
   char *p;
 
   if(String) {
      for(p = String; *p; p++) {
         HashCode = (HashCode << 4) + *p;
         if(g = HashCode & MASK) {
            HashCode ^= g >> SHIFT;
            HashCode ^= g;
         }
      }
   }
   return(HashCode % TabLen);
}
 

Module Name: LoadHashTable.c

#include "HashExample.h"
 
void LoadHashTable(sysinfo *SysInfo)
{
   int           i            = 0;
   int           NodeSz       = sizeof(wordused);
   unsigned long HashCode     = 0L;
   wordused      *CurrentNode = NULL;
   int           IdxSz        = sizeof(wordused);
   char          *Word        = NULL;
   bool          FoundItem    = False;
 
   for(i = 0; i < HashTableNumItems; i++)
   {
      SysInfo->HashTable[i] = NULL;
   }
 
   SysInfo->InFile = fopen(SysInfo->InFileName, "r");
   if(SysInfo->InFile == NULL)
   {
      fprintf(stderr, "Unable to open InFile", SysInfo->InFileName);
   }
   else
   {
      while(True)
      {
         fread(SysInfo->InBuff, IdxSz, 1, SysInfo->InFile);
         if(feof(SysInfo->InFile))
            break;
         Word = strtok(SysInfo->InBuff, " \n\t");
         while(Word)
         {
            FoundItem = False;
            HashCode = Hash(Word, HashTableNumItems);
            CurrentNode = SysInfo->HashTable[HashCode];
            CurrentNode = SysInfo->HashTable[HashCode];
            if(CurrentNode)
            {
               while(CurrentNode)
               {
                  if(CurrentNode->WordUsed &&
                     (!(strcmp(CurrentNode->WordUsed, Word))))
                  {
                     CurrentNode->NumberOfTimesUsed += 1;
                     FoundItem = True;
                     break;
                  }
                  else if(CurrentNode->Next == NULL)
                  {
                     CurrentNode->Next = (wordused *)calloc(1, NodeSz);
                     break;
                  }
                  else
                     CurrentNode = CurrentNode->Next;
               }
            }
            if(!FoundItem)
            {
               SysInfo->TotalNumberOfWords += 1;
               if(!CurrentNode)
               {
                  CurrentNode = SysInfo->HashTable[HashCode] =
                     (wordused *)calloc(1, NodeSz);
               }
               CurrentNode->WordUsed = (char *)calloc(1, (strlen(Word)+1));
               strcpy(CurrentNode->WordUsed, Word);
               CurrentNode->NumberOfTimesUsed = 1;
            }
            Word = strtok(NULL, " \n\t");
         }
      }
   }
}

Module Name: TryItOut.c

#include "HashExample.h"
 
void TryItOut(sysinfo *SysInfo)
{
   wordused *CurrentNode   = NULL;
   unsigned long HashCode     = 0L;
   char     *Aword         = (char *)calloc(1, Buff256);
   bool     WordFound      = False;
 
   fprintf(stdout, "The document contained %ld words\n",
      SysInfo->TotalNumberOfWords);
   while(True)
   {
      gets(Aword);
      if(!(strcmp(Aword, "GoodByeYall")))
         break;
      HashCode = Hash(Aword, HashTableNumItems);
      CurrentNode = SysInfo->HashTable[HashCode];      WordFound = False;
      while(CurrentNode)
      {
         if(!strcmp(CurrentNode->WordUsed, Aword))
         {
            WordFound = True;
            break;
         }
         CurrentNode = CurrentNode->Next;
      }
 
      if(WordFound)
         fprintf(stdout, "%s was used in the document %d times\n",
            Aword, CurrentNode->NumberOfTimesUsed);
      else
         fprintf(stdout, "%s was not used in the document\n");
   }
}
 

Ti exit the program, type 'GoodByeYall' case sensitive.

Enjoy,

Larry