Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Simple open-addressed hashtable
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>
// no actual pointer should have this value, due to alignment
static void* DELETED = (void*)1;
static int TABLE_SIZE = 701;
static int hash(int key) {
return key % TABLE_SIZE;
}
static int hash2(int key) {
return 1 + key % (TABLE_SIZE - 1);
}
typedef struct {
int key;
void* value;
} entry;
entry** ht_create() {
entry** table = malloc(sizeof(entry*) * TABLE_SIZE);
memset(table, 0, sizeof(entry*) * TABLE_SIZE);
return table;
}
bool ht_put(entry** table, int key, void* value) {
int start = hash(key);
int idx = start;
int second_hash = hash2(key);
int i = 0;
do {
if (table[idx] == NULL) {
table[idx] = malloc(sizeof(entry));
table[idx]->key = key;
table[idx]->value = value;
return true;
}
else if (table[idx] != DELETED && table[idx]->key == key) {
table[idx]->value = value;
return true;
}
}
while((idx = (start + second_hash * ++i) % TABLE_SIZE) != start);
return false;
}
bool ht_get(entry** table, int key, void** value) {
int start = hash(key);
int idx = start;
int second_hash = hash2(key);
int i = 0;
do {
if (table[idx] == NULL) {
return false;
}
else if (table[idx] != DELETED && table[idx]->key == key) {
*value = table[idx]->value;
return true;
}
}
while((idx = (start + second_hash * ++i) % TABLE_SIZE) != start);
return false;
}
bool ht_del(entry** table, int key) {
int start = hash(key);
int idx = start;
int second_hash = hash2(key);
int i = 0;
do {
if (table[idx]->key == key) {
free(table[idx]);
table[idx] = DELETED;
return true;
}
}
while((idx = (start + second_hash * ++i) % TABLE_SIZE) != start);
return false;
}
int main() {
entry** table = ht_create();
assert(ht_put(table, 1234, (void*)5));
assert(ht_put(table, 1234, (void*)5));
assert(ht_put(table, 1234 + 701, (void*)6));
long result;
assert(ht_get(table, 1234, (void*)&result));
assert(result == 5);
assert(ht_get(table, 1234 + 701, (void*)&result));
assert(result == 6);
assert(ht_del(table, 1234));
assert(ht_get(table, 1234, (void*)&result) != true);
assert(ht_get(table, 1234 + 701, (void*)&result));
assert(result == 6);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.