How to implement a hash table that support insert() and search() operations on i
ID: 3767946 • Letter: H
Question
How to implement a hash table that support insert() and search() operations on it. In particular, the program should prompt the user to enter initial size of the table and the load factor (a value between 0 and 1). The table must store integer key values and collision is resolved using quadratic probing. You can assume that the hash function is h(key) = key % tablesize. If a key cannot be inserted after 20 probing, then it is abandoned and the program returns “insert fails” message. When the table reaches the load factor the program creates a double-size table and rehashes all the items currently stored.
I need help I can not figure this out
Explanation / Answer
Program
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
struct entry_s
{
char *key;
char *value;
struct entry_s *next;
};
typedef struct entry_s entry_t;
struct hashtable_s
{
int size;
struct entry_s **table;
};
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;
}
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;
}
if( next != NULL && next->key != NULL && strcmp( key, next->key ) == 0 )
{
free( next->value );
next->value = strdup( value );
}
}
Else
{
newpair = ht_newpair( key, value );
if( next == hashtable->table[ bin ] )
{
newpair->next = next;
hashtable->table[ bin ] = newpair;
}
else if ( next == NULL )
{
last->next = newpair;
}
else
{
newpair->next = next;
last->next = newpair;
}
}
}
char *ht_get( hashtable_t *hashtable, char *key )
{
int bin = 0;
entry_t *pair;
bin = ht_hash( hashtable, key );
pair = hashtable->table[ bin ];
while( pair != NULL && pair->key != NULL && strcmp( key, pair->key ) > 0 )
{
pair = pair->next;
}
if( pair == NULL || pair->key == NULL || strcmp( key, pair->key ) != 0 )
{
return NULL;
}
else
{
return pair->value;
}
}
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
struct entry_s
{
char *key;
char *value;
struct entry_s *next;
};
typedef struct entry_s entry_t;
struct hashtable_s
{
int size;
struct entry_s **table;
};
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;
}
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;
}
if( next != NULL && next->key != NULL && strcmp( key, next->key ) == 0 )
{
free( next->value );
next->value = strdup( value );
}
}
Else
{
newpair = ht_newpair( key, value );
if( next == hashtable->table[ bin ] )
{
newpair->next = next;
hashtable->table[ bin ] = newpair;
}
else if ( next == NULL )
{
last->next = newpair;
}
else
{
newpair->next = next;
last->next = newpair;
}
}
}
char *ht_get( hashtable_t *hashtable, char *key )
{
int bin = 0;
entry_t *pair;
bin = ht_hash( hashtable, key );
pair = hashtable->table[ bin ];
while( pair != NULL && pair->key != NULL && strcmp( key, pair->key ) > 0 )
{
pair = pair->next;
}
if( pair == NULL || pair->key == NULL || strcmp( key, pair->key ) != 0 )
{
return NULL;
}
else
{
return pair->value;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.