Aug 12 16:57 1996 hashfunc.c Page 1 /* Here are some of the hash functions */ /* for strings that are in the text */ typedef unsigned int Index; /* START: fig5_3.txt */ Index Hash1( const char *Key, int TableSize ) { unsigned int HashVal = 0; /* 1*/ while( *Key != '\0' ) /* 2*/ HashVal += *Key++; /* 3*/ return HashVal % TableSize; } /* END */ /* START: fig5_4.txt */ Index Hash2( const char *Key, int TableSize ) { return ( Key[ 0 ] + 27 * Key[ 1 ] + 729 * Key[ 2 ] ) % TableSize; } /* END */ /* START: fig5_5.txt */ Index Hash3( const char *Key, int TableSize ) { unsigned int HashVal = 0; /* 1*/ while( *Key != '\0' ) /* 2*/ HashVal = ( HashVal << 5 ) + *Key++; /* 3*/ return HashVal % TableSize; } /* END */ Nov 4 20:36 1997 hashsep.h Page 1 /* Interface for separate chaining hash table */ typedef int ElementType; /* START: fig5_2.txt */ typedef unsigned int Index; /* END */ /* START: fig5_7.txt */ #ifndef _HashSep_H #define _HashSep_H struct ListNode; typedef struct ListNode *Position; struct HashTbl; typedef struct HashTbl *HashTable; HashTable InitializeTable( int TableSize ); void DestroyTable( HashTable H ); Position Find( ElementType Key, HashTable H ); void Insert( ElementType Key, HashTable H ); ElementType Retrieve( Position P ); /* Routines such as Delete are MakeEmpty are omitted */ #endif /* _HashSep_H */ /* END */ Aug 12 15:27 1996 hashsep.c Page 1 #include "fatal.h" #include "hashsep.h" #include #define MinTableSize (10) struct ListNode { ElementType Element; Position Next; }; typedef Position List; /* List *TheList will be an array of lists, allocated later */ /* The lists use headers (for simplicity), */ /* though this wastes space */ struct HashTbl { int TableSize; List *TheLists; }; /* Return next prime; assume N >= 10 */ static int NextPrime( int N ) { int i; if( N % 2 == 0 ) N++; for( ; ; N += 2 ) { for( i = 3; i * i <= N; i += 2 ) if( N % i == 0 ) goto ContOuter; /* Sorry about this! */ return N; ContOuter: ; } } /* Hash function for ints */ Index Hash( ElementType Key, int TableSize ) { return Key % TableSize; } /* START: fig5_8.txt */ HashTable InitializeTable( int TableSize ) { HashTable H; int i; /* 1*/ if( TableSize < MinTableSize ) Aug 12 15:27 1996 hashsep.c Page 2 { /* 2*/ Error( "Table size too small" ); /* 3*/ return NULL; } /* Allocate table */ /* 4*/ H = malloc( sizeof( struct HashTbl ) ); /* 5*/ if( H == NULL ) /* 6*/ FatalError( "Out of space!!!" ); /* 7*/ H->TableSize = NextPrime( TableSize ); /* Allocate array of lists */ /* 8*/ H->TheLists = malloc( sizeof( List ) * H->TableSize ); /* 9*/ if( H->TheLists == NULL ) /*10*/ FatalError( "Out of space!!!" ); /* Allocate list headers */ /*11*/ for( i = 0; i < H->TableSize; i++ ) { /*12*/ H->TheLists[ i ] = malloc( sizeof( struct ListNode ) ); /*13*/ if( H->TheLists[ i ] == NULL ) /*14*/ FatalError( "Out of space!!!" ); else /*15*/ H->TheLists[ i ]->Next = NULL; } /*16*/ return H; } /* END */ /* START: fig5_9.txt */ Position Find( ElementType Key, HashTable H ) { Position P; List L; /* 1*/ L = H->TheLists[ Hash( Key, H->TableSize ) ]; /* 2*/ P = L->Next; /* 3*/ while( P != NULL && P->Element != Key ) /* Probably need strcmp!! */ /* 4*/ P = P->Next; /* 5*/ return P; } /* END */ /* START: fig5_10.txt */ void Insert( ElementType Key, HashTable H ) { Position Pos, NewCell; List L; /* 1*/ Pos = Find( Key, H ); /* 2*/ if( Pos == NULL ) /* Key is not found */ Aug 12 15:27 1996 hashsep.c Page 3 { /* 3*/ NewCell = malloc( sizeof( struct ListNode ) ); /* 4*/ if( NewCell == NULL ) /* 5*/ FatalError( "Out of space!!!" ); else { /* 6*/ L = H->TheLists[ Hash( Key, H->TableSize ) ]; /* 7*/ NewCell->Next = L->Next; /* 8*/ NewCell->Element = Key; /* Probably need strcpy! */ /* 9*/ L->Next = NewCell; } } } /* END */ ElementType Retrieve( Position P ) { return P->Element; } void DestroyTable( HashTable H ) { int i; for( i = 0; i < H->TableSize; i++ ) { Position P = H->TheLists[ i ]; Position Tmp; while( P != NULL ) { Tmp = P->Next; free( P ); P = Tmp; } } free( H->TheLists ); free( H ); } Nov 4 20:35 1997 hashquad.h Page 1 /* Interface for quadratic probing hash table */ typedef int ElementType; /* START: fig5_14.txt */ #ifndef _HashQuad_H #define _HashQuad_H typedef unsigned int Index; typedef Index Position; struct HashTbl; typedef struct HashTbl *HashTable; HashTable InitializeTable( int TableSize ); void DestroyTable( HashTable H ); Position Find( ElementType Key, HashTable H ); void Insert( ElementType Key, HashTable H ); ElementType Retrieve( Position P, HashTable H ); HashTable Rehash( HashTable H ); /* Routines such as Delete are MakeEmpty are omitted */ #endif /* _HashQuad_H */ /* END */ Aug 12 15:27 1996 hashquad.c Page 1 #include "fatal.h" #include "hashquad.h" #include #define MinTableSize (10) enum KindOfEntry { Legitimate, Empty, Deleted }; struct HashEntry { ElementType Element; enum KindOfEntry Info; }; typedef struct HashEntry Cell; /* Cell *TheCells will be an array of */ /* HashEntry cells, allocated later */ struct HashTbl { int TableSize; Cell *TheCells; }; /* Return next prime; assume N >= 10 */ static int NextPrime( int N ) { int i; if( N % 2 == 0 ) N++; for( ; ; N += 2 ) { for( i = 3; i * i <= N; i += 2 ) if( N % i == 0 ) goto ContOuter; /* Sorry about this! */ return N; ContOuter: ; } } /* Hash function for ints */ Index Hash( ElementType Key, int TableSize ) { return Key % TableSize; } /* START: fig5_15.txt */ HashTable InitializeTable( int TableSize ) { HashTable H; int i; Aug 12 15:27 1996 hashquad.c Page 2 /* 1*/ if( TableSize < MinTableSize ) { /* 2*/ Error( "Table size too small" ); /* 3*/ return NULL; } /* Allocate table */ /* 4*/ H = malloc( sizeof( struct HashTbl ) ); /* 5*/ if( H == NULL ) /* 6*/ FatalError( "Out of space!!!" ); /* 7*/ H->TableSize = NextPrime( TableSize ); /* Allocate array of Cells */ /* 8*/ H->TheCells = malloc( sizeof( Cell ) * H->TableSize ); /* 9*/ if( H->TheCells == NULL ) /*10*/ FatalError( "Out of space!!!" ); /*11*/ for( i = 0; i < H->TableSize; i++ ) /*12*/ H->TheCells[ i ].Info = Empty; /*13*/ return H; } /* END */ /* START: fig5_16.txt */ Position Find( ElementType Key, HashTable H ) { Position CurrentPos; int CollisionNum; /* 1*/ CollisionNum = 0; /* 2*/ CurrentPos = Hash( Key, H->TableSize ); /* 3*/ while( H->TheCells[ CurrentPos ].Info != Empty && H->TheCells[ CurrentPos ].Element != Key ) /* Probably need strcmp!! */ { /* 4*/ CurrentPos += 2 * ++CollisionNum - 1; /* 5*/ if( CurrentPos >= H->TableSize ) /* 6*/ CurrentPos -= H->TableSize; } /* 7*/ return CurrentPos; } /* END */ /* START: fig5_17.txt */ void Insert( ElementType Key, HashTable H ) { Position Pos; Pos = Find( Key, H ); if( H->TheCells[ Pos ].Info != Legitimate ) { Aug 12 15:27 1996 hashquad.c Page 3 /* OK to insert here */ H->TheCells[ Pos ].Info = Legitimate; H->TheCells[ Pos ].Element = Key; /* Probably need strcpy! */ } } /* END */ /* START: fig5_22.txt */ HashTable Rehash( HashTable H ) { int i, OldSize; Cell *OldCells; /* 1*/ OldCells = H->TheCells; /* 2*/ OldSize = H->TableSize; /* Get a new, empty table */ /* 3*/ H = InitializeTable( 2 * OldSize ); /* Scan through old table, reinserting into new */ /* 4*/ for( i = 0; i < OldSize; i++ ) /* 5*/ if( OldCells[ i ].Info == Legitimate ) /* 6*/ Insert( OldCells[ i ].Element, H ); /* 7*/ free( OldCells ); /* 8*/ return H; } /* END */ ElementType Retrieve( Position P, HashTable H ) { return H->TheCells[ P ].Element; } void DestroyTable( HashTable H ) { free( H->TheCells ); free( H ); } Aug 12 15:27 1996 testhash.c Page 1 #define SepChain /* Define the appropriate hash algorithm */ #ifdef SepChain #include "hashsep.h" #endif #ifdef QuadProb #include "hashquad.h" #endif #include #define NumItems 400 main( ) { HashTable H; Position P; int i; int j = 0; int CurrentSize; H = InitializeTable( CurrentSize = 13 ); for( i = 0; i < NumItems; i++, j += 71 ) { #ifdef QuadProb if( i > CurrentSize / 2 ) { H = Rehash( H ); printf( "Rehashing...\n" ); CurrentSize *= 2; } #endif Insert( j, H ); } for( i = 0, j = 0; i < NumItems; i++, j += 71 ) #ifdef SepChain if( ( P = Find( j, H ) ) == NULL || Retrieve( P ) != j ) #endif #ifdef QuadProb if( Retrieve( ( P = Find( j, H ) ), H ) != j ) #endif printf( "Error at %d\n", j ); printf( "End of program.\n" ); return 0; }