C Program to implement Open Addressing Hash Table with Quadratic probing and rehashing

#include <stdio.h>
        #include <stdlib.h>
        #include <stdlib.h>
        #define NumItems 20
        #define MinTableSize (10)

        enum KindOfEntry { Legitimate, Empty, Deleted };

        struct HashEntry
        {
            int      Element;
            enum KindOfEntry Info;
        };
        typedef unsigned int Index;
        typedef Index Position;
        typedef struct HashEntry Cell;

        /* Cell *TheCells will be an array of */
        /* HashEntry cells, allocated later */
        struct HashTbl
        {
            int TableSize;
            Cell *TheCells;
        };
        typedef struct HashTbl *HashTable;
        /* Hash function for ints */
        Index
        Hash( int Key, int TableSize )
        {
            return Key % TableSize;
        }

 /* 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! */
                printf("\nnext prime%d\n",N);
                return N;
              ContOuter: ;
            }
        }
        HashTable
        InitializeTable( int TableSize )
        {
            HashTable H;
            int i;

/* 1*/      if( TableSize < MinTableSize )
            {
/* 2*/          printf( "Table size too small" );
/* 3*/          return NULL;
            }

            /* Allocate table */
/* 4*/      H = malloc( sizeof( struct HashTbl ) );
/* 5*/      if( H == NULL )
/* 6*/          printf( "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*/          printf( "Out of space!!!" );

/*11*/      for( i = 0; i < H->TableSize; i++ )
/*12*/          H->TheCells[ i ].Info = Empty;

/*13*/      return H;
        }

        Position
        Find( int Key, HashTable H )
        {
            Position CurrentPos;
            int CollisionNum;

/* 1*/      CollisionNum = 0;
/* 2*/      CurrentPos = Hash( Key, H->TableSize );
            //printf( "CurrentPos %d\n", CurrentPos );
/* 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;
        }

        void
        Insert( int Key, HashTable H )
        {
            Position Pos;

            Pos = Find( Key, H );
            if( H->TheCells[ Pos ].Info != Legitimate )
            {
                /* OK to insert here */
                H->TheCells[ Pos ].Info = Legitimate;
                H->TheCells[ Pos ].Element = Key;
                         /* Probably need strcpy! */
            }
        }

        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;
        }

        int
        Retrieve( Position P, HashTable H )
        {
            printf("\t%d",H->TheCells[ P ].Element);
            return H->TheCells[ P ].Element;
        }

        void
        DestroyTable( HashTable H )
        {
            free( H->TheCells );
            free( H );
        }
main( )
{
    HashTable H;
    Position P;
    int i;
    int CurrentSize;

    H = InitializeTable( CurrentSize = 11 );

    for( i = 0; i < NumItems; i++ )
    {
        if( i > CurrentSize / 2 )
        {
            H = Rehash( H );
            printf( "\nRehashing...\n" );
            CurrentSize *= 2;
        }
        Insert( i, H );
    }
    printf( "\nElements in Hash Table are...\n" );
    for( i = 0; i < NumItems; i++ )
        if( Retrieve( ( P = Find( i, H ) ), H ) != i )
            printf( "Error at %d\n", i );

    printf( "End of program.\n" );
    return 0;

}
Bhanu Namikaze

Bhanu Namikaze is an Ethical Hacker, Web Developer, Student and Mechanical Engineer. He Enjoys writing articles, Blogging, Solving Errors and Social Networking. Feel Free to let me know any of your concerns about hacking or let me know if you need any more methods on hacking anything. Enjoy Learning

No comments:

Post a Comment