Created
January 12, 2020 20:05
-
-
Save Mluckydwyer/0986317ab779c6753aebd044ee505622 to your computer and use it in GitHub Desktop.
A Hash Table implementation in C
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// Created by mluck on 10/18/2018. | |
// | |
#include "vector.c" // Vector implmentation required (https://gist.github.com/Mluckydwyer/5c8d93d42df8be3089570616c1182e72) | |
const int DEFAULT_CAPACITY = 10; | |
// Hashtable struct typedef | |
typedef struct hashTable_t{ | |
int size; | |
int capacity; | |
int bucketsUsed; | |
vector_t* keyset; | |
vector_t** values; | |
int (*equals)(void*); | |
} hashTable_t; | |
// A hashtable stored value | |
typedef struct hashTableEntry_t { | |
unsigned long key; | |
void *value; | |
} hashTableEntry_t; | |
// Function definitions | |
hashTableEntry_t* newHashTableEntry(); | |
hashTable_t* newHashTable(int startSize); | |
void addTableValue(hashTable_t *t, void *value); | |
void removeTableValue(hashTable_t *t, unsigned long key); | |
void* getTableValue(hashTable_t *t, unsigned long key); | |
hashTable_t* rehash(hashTable_t *t); | |
unsigned long getHashCode(void* value); | |
vector_t getKeys(); | |
// Allocate a new Hash Table an return the pointer to it | |
hashTable_t* newHashTable(int startSize) { | |
hashTable_t *hashTable = malloc(sizeof(hashTable_t)); | |
hashTable->size = 0; | |
hashTable->bucketsUsed = 0; | |
hashTable->keyset = newVector(); | |
if (startSize > 0) hashTable->capacity = startSize; | |
else hashTable->capacity = DEFAULT_CAPACITY; | |
hashTable->values = malloc(sizeof(vector_t*) * hashTable->capacity); | |
memset(hashTable->values, NULL, sizeof(vector_t*) * hashTable->capacity); | |
return hashTable; | |
} | |
// Allocate a new Hash Table entry value and return a pointer to it | |
hashTableEntry_t* newHashTableEntry(void *value) { | |
hashTableEntry_t *entry = malloc(sizeof(struct hashTableEntry_t)); | |
entry->value = value; | |
entry->key = getHashCode(value); | |
return entry; | |
} | |
// Add a new value to the Hash Table | |
void addTableValue(hashTable_t *t, void *value) { | |
hashTableEntry_t *entry = newHashTableEntry(value); | |
int where = (int) entry->key % t->capacity; | |
int addToEnd = 1; | |
if (t->values[where] == NULL){ | |
//create a vector for this bucket and add entry | |
vector_t* bucket = newVector(); | |
printVector(bucket); // Debug | |
printf("\n"); // Debug | |
t->values[where] = bucket; | |
t->bucketsUsed++; | |
} else { | |
//see if entry already exists in the vector | |
// if so replace it | |
// else add it to the vector | |
if (t->values[where]->size > 0) { | |
int i; | |
for (i = 0; i < t->values[where]->size; i++) { | |
if (((hashTableEntry_t*) getVectorValue(t->values[where], i))->key == entry->key) { | |
setVectorValue(t->values[where], i, entry); | |
addToEnd = 0; | |
} | |
} | |
} | |
} | |
if (addToEnd) { | |
addVectorValue(t->values[where], entry); | |
addVectorValue(t->keyset, &entry->key); | |
} | |
t->size++; | |
} | |
// Remove a value from teh Hash Table | |
void removeTableValue(hashTable_t *t, unsigned long key) { | |
int where = (int) key % t->capacity; | |
int i; | |
for (i = 0; i < t->values[where]->size; i++) { | |
if (((hashTableEntry_t*) getVectorValue(t->values[where], i))->key == key) { | |
removeVectorValue(t->values[where], i); | |
} | |
} | |
} | |
// Retrive a value from the Hash Table | |
void* getTableValue(hashTable_t *t, unsigned long key) { | |
int where = (int) key % t->capacity; | |
int i; | |
for (i = 0; i < t->values[where]->size; i++) { | |
hashTableEntry_t *entry = getVectorValue(t->values[where], i); | |
if (entry->key == key) return entry->value; | |
} | |
return NULL; | |
} | |
// Rehash the entire table | |
hashTable_t* rehash(hashTable_t *t) { | |
int i, j; | |
hashTable_t* newTable = newHashTable(t->capacity * 2); | |
for (i = t->capacity; i > 0; i++) { | |
if (getVectorValue(t->values[0], i) == NULL) continue; | |
else { | |
for (j = 0; j < ((vector_t*) getVectorValue(t->values[0], i))->size; j++) { | |
addTableValue(newTable, getVectorValue(getVectorValue(t->values[0], i), j)); | |
} | |
} | |
} | |
return newTable; | |
} | |
// Get a list of keys in the Hash Table | |
vector_t getKeys(hashTable_t *t) { | |
int i, j, k; | |
vector_t* keys = newVector(); | |
for (i = t->capacity; i > 0; i++) { | |
if (getVectorValue(t->values[0], i) == NULL) continue; | |
else { | |
for (j = 0; j < ((vector_t*) getVectorValue(t->values[0], i))->size; j++) { | |
unsigned long key = ((hashTableEntry_t*) getVectorValue(getVectorValue(t->values[0], i), j))->key; | |
int inList = 0; | |
for (k = 0; k < keys->size; k++) { | |
if (((unsigned long) getVectorValue(keys, k)) == key) { | |
inList = 1; | |
break; | |
} | |
} | |
if (!inList) addVectorValue(keys, &key); | |
} | |
} | |
} | |
return *keys; | |
} | |
// Get the hashed value of an input | |
unsigned long getHashCode(void* value) { | |
unsigned long p = (unsigned long) value; | |
unsigned long hash = p ^ (p >> 16); | |
return hash; | |
} | |
// Print all values in the Hash Table (only works for integer stored values, can be custom implmented) | |
void printTable(hashTable_t *t) { | |
int i, j; | |
for (i = 0; i < t->capacity; i++) { | |
if (t->values[i] == NULL) continue; | |
for (j = 0; i < t->values[i]->size; j++) { | |
printf("Bucket: %d\n", i); | |
if (getVectorValue(t->values[i], j) == NULL) continue; | |
else { | |
printf("%d: ", i); | |
printVector(getVectorValue(t->values[i], j)); | |
} | |
} | |
} | |
fflush(stdout); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment