Skip to content

Instantly share code, notes, and snippets.

@padamupreti

padamupreti/hashtable.c

Last active February 3, 2023 04:45
Show Gist options
  • Save padamupreti/3d2fec4b4c9ab91192e8164f6c46955e to your computer and use it in GitHub Desktop.
Save padamupreti/3d2fec4b4c9ab91192e8164f6c46955e to your computer and use it in GitHub Desktop.
Download ZIP
hash table implementation
Raw
hashtable.c
// DSA - Hash Table implementation heavily derived from https://youtu.be/wg8hZxMRwcw
// and file from the repository (in video description)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10000
typedef struct entry {
char *key, *value;
struct entry *next;
} entry_t;
typedef struct {
entry_t **entries;
} ht_t;
ht_t* ht_create() {
ht_t *hashtable = (ht_t *) malloc(sizeof(ht_t));
hashtable->entries = (entry_t **) malloc(sizeof(entry_t *) * TABLE_SIZE);
int i;
for(i=0; i<TABLE_SIZE; i++)
hashtable->entries[i] = NULL;
return hashtable;
}
unsigned int hash(const char *key) {
unsigned int i;
unsigned long int result=0;
for(i=0; i<strlen(key); i++)
result = result * 35 + key[i];
result %= TABLE_SIZE;
return result;
}
entry_t* create_entry(const char *key, const char *value) {
entry_t *entry = (entry_t *) malloc(sizeof(entry_t));
entry->key = malloc((sizeof(char) * strlen(key)) + sizeof(char));
entry->value = malloc((sizeof(char) * strlen(value)) + sizeof(char));
strcpy(entry->key, key);
strcpy(entry->value, value);
entry->next = NULL;
return entry;
}
void ht_set(ht_t *hashtable, const char *key, const char *value) {
unsigned int slot = hash(key);
entry_t *entry = hashtable->entries[slot];
if(entry == NULL) {
hashtable->entries[slot] = create_entry(key, value);
return;
}
entry_t *prev;
while(entry != NULL) {
if(strcmp(entry->key, key) == 0) {
free(entry->value);
entry->value = malloc((sizeof(char) * strlen(value)) + sizeof(char));
strcpy(entry->value, value);
return;
}
prev = entry;
entry = entry->next;
}
prev->next = create_entry(key, value);
}
char* ht_get(ht_t *hashtable, const char *key) {
unsigned int slot = hash(key);
entry_t *entry = hashtable->entries[slot];
if(entry == NULL)
return NULL;
while(entry != NULL) {
if(strcmp(entry->key, key) == 0)
return entry->value;
entry = entry->next;
}
return NULL;
}
void ht_del(ht_t *hashtable, const char *key) {
unsigned int slot = hash(key);
entry_t *entry = hashtable->entries[slot], *prev;
if(entry == NULL)
return;
int i;
for(i=0; entry!=NULL; i++) {
if(strcmp(entry->key, key) == 0) {
if(i == 0 && entry->next == NULL)
hashtable->entries[slot] = NULL;
else if(i == 0 && entry->next != NULL)
hashtable->entries[slot] = entry->next;
else if(i != 0 && entry->next != NULL)
prev->next = entry->next;
else if(i != 0 && entry->next == NULL)
prev->next = NULL;
free(entry->key);
free(entry->value);
free(entry);
return;
}
prev = entry;
entry = entry->next;
}
}
// ONLY FOR VISUALIZATION OF HASH TABLE; NOT IDEAL FOR EFFICIENCY
void ht_print(ht_t *hashtable) {
unsigned int i;
for(i=0; i<TABLE_SIZE; i++) {
entry_t *entry = hashtable->entries[i];
if(entry != NULL) {
printf("hash_table[%4d]: ", i);
while(1) {
printf("%s=%s ", entry->key, entry->value);
if(entry->next == NULL)
break;
entry = entry->next;
}
printf("\n");
}
}
}
int main(int argc, char **argv) {
ht_t *ht = ht_create();
printf("Setting values ...\n");
ht_set(ht, "first", "first_value");
ht_set(ht, "second", "second_value");
ht_set(ht, "third", "third_value");
ht_set(ht, "fourth", "fourth_value");
ht_set(ht, "fifth", "fifth_value");
printf("\nBefore modification ::\n\n");
// ht_print(ht);
// printf("\n");
printf("%s = %s\n", "first", ht_get(ht, "first"));
printf("%s = %s\n", "third", ht_get(ht, "third"));
ht_del(ht, "first");
ht_set(ht, "third", "MODIFIED");
printf("\nAfter modification ::\n\n");
// ht_print(ht);
// printf("\n");
printf("%s = %s\n", "first", ht_get(ht, "first"));
printf("%s = %s\n", "third", ht_get(ht, "third"));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment