Develop a symbol-table implementation that maintains two hash tables and two has

Question

Develop a symbol-table implementation that maintains two
hash tables and two hash functions. Any given key is in one of the tables, but not both.
When inserting a new key, hash to one of the tables; if the table position is occupied,
replace that key with the new key and hash the old key into the other table (again kicking
out a key that might reside there). If this process cycles, restart. Keep the tables less
than half full. This method uses a constant number of equality tests in the worst case
for search (trivial) and amortized constant time for insert. Please give solution in java as soon as possible.

Explanation / Answer

Hello,

Hope the below code helps.

** Creating a new hashtable.
hashtable_t *ht_create( int size ) {

   hashtable_t *hashtable = NULL;
   int i;

   if( size < 1 ) return NULL;

   /* Allocate the table itself. */
   if( ( hashtable = malloc( sizeof( hashtable_t ) ) ) == NULL ) {
       return NULL;
   }

   /* Allocate pointers to the head nodes. */
   if( ( hashtable->table = malloc( sizeof( entry_t * ) * size ) ) == NULL ) {
       return NULL;
   }
   for( i = 0; i < size; i++ ) {
       hashtable->table[i] = NULL;
   }

   hashtable->size = size;

   return hashtable;  
}

*** Hash a string for a particular hash table.
int ht_hash( hashtable_t *hashtable, char *key ) {

   unsigned long int hashval;
   int i = 0;

   /* Convert our string to an integer */
   while( hashval < ULONG_MAX && i < strlen( key ) ) {
       hashval = hashval << 8;
       hashval += key[ i ];
       i++;
   }

   return hashval % hashtable->size;
}

** Create a key-value pair.
entry_t *ht_newpair( char *key, char *value ) {
   entry_t *newpair;

   if( ( newpair = malloc( sizeof( entry_t ) ) ) == NULL ) {
       return NULL;
   }

   if( ( newpair->key = strdup( key ) ) == NULL ) {
       return NULL;
   }

   if( ( newpair->value = strdup( value ) ) == NULL ) {
       return NULL;
   }

   newpair->next = NULL;

   return newpair;
}

** Insert a key-value pair into a hash table.
void ht_set( hashtable_t *hashtable, char *key, char *value ) {
   int bin = 0;
   entry_t *newpair = NULL;
   entry_t *next = NULL;
   entry_t *last = NULL;

   bin = ht_hash( hashtable, key );

   next = hashtable->table[ bin ];

   while( next != NULL && next->key != NULL && strcmp( key, next->key ) > 0 ) {
       last = next;
       next = next->next;
   }

   /* There's already a pair. Let's replace that string. */
   if( next != NULL && next->key != NULL && strcmp( key, next->key ) == 0 ) {

       free( next->value );
       next->value = strdup( value );

   /* Nope, could't find it. Time to grow a pair. */
   } else {
       newpair = ht_newpair( key, value );

       /* We're at the start of the linked list in this bin. */
       if( next == hashtable->table[ bin ] ) {
           newpair->next = next;
           hashtable->table[ bin ] = newpair;
  
       /* We're at the end of the linked list in this bin. */
       } else if ( next == NULL ) {
           last->next = newpair;
  
       /* We're in the middle of the list. */
       } else {
           newpair->next = next;
           last->next = newpair;
       }
   }
}

/* Retrieve a key-value pair from a hash table. */
char *ht_get( hashtable_t *hashtable, char *key ) {
   int bin = 0;
   entry_t *pair;

   bin = ht_hash( hashtable, key );

   /* Step through the bin, looking for our value. */
   pair = hashtable->table[ bin ];
   while( pair != NULL && pair->key != NULL && strcmp( key, pair->key ) > 0 ) {
       pair = pair->next;
   }

   /* Did we actually find anything? */
   if( pair == NULL || pair->key == NULL || strcmp( key, pair->key ) != 0 ) {
       return NULL;

   } else {
       return pair->value;
   }
  
}

int main( int argc, char **argv ) {

   hashtable_t *hashtable = ht_create( 65536 );

   ht_set( hashtable, "key1", "inky" );
   ht_set( hashtable, "key2", "pinky" );
   ht_set( hashtable, "key3", "blinky" );
   ht_set( hashtable, "key4", "floyd" );

   printf( "%s ", ht_get( hashtable, "key1" ) );
   printf( "%s ", ht_get( hashtable, "key2" ) );
   printf( "%s ", ht_get( hashtable, "key3" ) );
   printf( "%s ", ht_get( hashtable, "key4" ) );

   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.