W
wkevin
Hi,
I tried to look for as much as simple implementation of a hash table in "c".
The performance and quality of the hash function do not interest me for this
task.
I found quite a lot of such example. When I reviewed the code, I always found
that something seems to be more complex than needed, and some logic which seems
that can be simplified, some redundant code, etc.
So I tried writing my own.
I tried it on some test cases and it was ok.
I would appreciate if you could review it correctness; I mean, are there
inputs where it will not work correctly?
Here is the code:
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
struct entry {
char *key;
char *val;
struct entry *next;
};
typedef struct entry entry_t;
struct hashtable {
struct entry **table;
int size;
};
typedef struct hashtable hashtable_t;
int hashfn(char *key, hashtable_t *htable)
{
int sum=0, i;
for (i=0; i<strlen(key);i++)
sum+=key;
return sum%htable->size;
}
void insert(hashtable_t *htable, char *key, char *val)
{
int hash;
hash = hashfn(key,htable);
entry_t *entry = htable->table[hash];
entry_t *last;
entry_t *new_entry;
while (entry != NULL) {
// replace
if (strcmp(entry->key,key) == 0) {
entry->val = val;
return;
}
last = entry;
entry = entry->next;
}
new_entry = malloc(sizeof(entry_t));
if (!new_entry) {
printf("could not allocate memory for new_entry\n");
return;
}
new_entry->key = key;
new_entry->val = val;
new_entry->next = NULL;
if (htable->table[hash] == NULL)
htable->table[hash] = new_entry;
else
{
// first
if (entry == htable->table[hash])
htable->table[hash] = new_entry;
else
last->next = new_entry;
}
}
char *get(hashtable_t *htable, char *key)
{
int hash = hashfn(key, htable);
entry_t *entry = htable->table[hash];
while (entry != NULL) {
if (strcmp(entry->key,key) == 0)
return entry->val;
entry = entry->next;
}
return NULL;
}
hashtable_t *ht_create(int size)
{
int i;
hashtable_t *htable = malloc(sizeof(hashtable_t));
if (!htable)
return NULL;
htable->table = malloc(size * sizeof(entry_t *));
if (!htable->table)
return NULL;
for (i=0; i<size; i++)
htable->table = NULL;
htable->size = size;
return htable;
}
int main()
{
hashtable_t *htable = ht_create(10);
if (!htable)
return;
insert(htable,"aba","111");
insert(htable,"bbb","222");
insert(htable,"aab","333");
printf("get(aba)=%s\n", get(htable,"aba"));
printf("get(bbb)=%s\n", get(htable,"bbb"));
printf("get(aab)=%s\n", get(htable,"aab"));
}
rgs,
Kevin
I tried to look for as much as simple implementation of a hash table in "c".
The performance and quality of the hash function do not interest me for this
task.
I found quite a lot of such example. When I reviewed the code, I always found
that something seems to be more complex than needed, and some logic which seems
that can be simplified, some redundant code, etc.
So I tried writing my own.
I tried it on some test cases and it was ok.
I would appreciate if you could review it correctness; I mean, are there
inputs where it will not work correctly?
Here is the code:
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
struct entry {
char *key;
char *val;
struct entry *next;
};
typedef struct entry entry_t;
struct hashtable {
struct entry **table;
int size;
};
typedef struct hashtable hashtable_t;
int hashfn(char *key, hashtable_t *htable)
{
int sum=0, i;
for (i=0; i<strlen(key);i++)
sum+=key;
return sum%htable->size;
}
void insert(hashtable_t *htable, char *key, char *val)
{
int hash;
hash = hashfn(key,htable);
entry_t *entry = htable->table[hash];
entry_t *last;
entry_t *new_entry;
while (entry != NULL) {
// replace
if (strcmp(entry->key,key) == 0) {
entry->val = val;
return;
}
last = entry;
entry = entry->next;
}
new_entry = malloc(sizeof(entry_t));
if (!new_entry) {
printf("could not allocate memory for new_entry\n");
return;
}
new_entry->key = key;
new_entry->val = val;
new_entry->next = NULL;
if (htable->table[hash] == NULL)
htable->table[hash] = new_entry;
else
{
// first
if (entry == htable->table[hash])
htable->table[hash] = new_entry;
else
last->next = new_entry;
}
}
char *get(hashtable_t *htable, char *key)
{
int hash = hashfn(key, htable);
entry_t *entry = htable->table[hash];
while (entry != NULL) {
if (strcmp(entry->key,key) == 0)
return entry->val;
entry = entry->next;
}
return NULL;
}
hashtable_t *ht_create(int size)
{
int i;
hashtable_t *htable = malloc(sizeof(hashtable_t));
if (!htable)
return NULL;
htable->table = malloc(size * sizeof(entry_t *));
if (!htable->table)
return NULL;
for (i=0; i<size; i++)
htable->table = NULL;
htable->size = size;
return htable;
}
int main()
{
hashtable_t *htable = ht_create(10);
if (!htable)
return;
insert(htable,"aba","111");
insert(htable,"bbb","222");
insert(htable,"aab","333");
printf("get(aba)=%s\n", get(htable,"aba"));
printf("get(bbb)=%s\n", get(htable,"bbb"));
printf("get(aab)=%s\n", get(htable,"aab"));
}
rgs,
Kevin