This is the second of a 2-part series, which gives a brief introduction to the implementation of hash tables.
Warning: The problem of generics has not been addressed here & I'll see to it later...
/**
* Abstract: A hash table with linear probing
*/
#define PRIME 10007
typedef bool Value;
typedef struct LinearProbingHashSTStruct {
int capacity;//capacity of the table
int count;//number of key-value pairs
int *keys;
Value *vals;
int (*hash_func)(int);
}*LinearProbingHashST;
int Hash(int key) { return (key >= 0 ? key : -key) % PRIME; }
LinearProbingHashST CreateLinearProbingHashST() {
LinearProbingHashST st = (LinearProbingHashST)malloc(sizeof(*st));
st->capacity = PRIME;//initial capacity
st->count = 0;
st->keys = (int*)malloc(st->capacity * sizeof(*(st->keys)));
for (int i = 0; i < st->capacity; i++) { st->keys[i] = INT_MIN; }
st->vals = (Value*)malloc(st->capacity * sizeof(*(st->vals)));
st->hash_func = &Hash;
return st;
}
LinearProbingHashST CreateLinearProbingHashST_c(int capacity) {
LinearProbingHashST st = (LinearProbingHashST)malloc(sizeof(*st));
st->capacity = capacity;//initial capacity
st->count = 0;
st->keys = (int*)malloc(st->capacity * sizeof(*(st->keys)));
for (int i = 0; i < st->capacity; i++) { st->keys[i] = INT_MIN; }
st->vals = (Value*)malloc(st->capacity * sizeof(*(st->vals)));
st->hash_func = &Hash;
return st;
}
void SetLPHST(LinearProbingHashST st, int key, Value val);
void ResizeHST(LinearProbingHashST st) {
int half = st->capacity >> 1;
LinearProbingHashST tst = CreateLinearProbingHashST_c(st->count == half ? st->capacity << 1 : half);
for (int i = 0; i < st->capacity; i++) { if (st->keys[i] != INT_MIN) { SetLPHST(tst, st->keys[i], st->vals[i]); } }
free(st->keys);
st->keys = tst->keys;
free(st->vals);
st->vals = tst->vals;
st->capacity = tst->capacity;
free(tst);
}
void SetLPHST(LinearProbingHashST st, int key, Value val) {
if (st == NULL) return;
if (st->count == st->capacity >> 1) { ResizeHST(st); }
int i = st->hash_func(key);
while (st->keys[i] != INT_MIN) {
if (st->keys[i] == key) {
st->vals[i] = val;
st->count++;
return;
}
i = (i + 1) % st->capacity;
}
st->keys[i] = key;
st->vals[i] = val;
st->count++;
}
int GetLPHST(LinearProbingHashST st, int key) {
if (st == NULL) return 0;
int i = st->hash_func(key);
while (st->keys[i] != INT_MIN) {
if (st->keys[i] == key) { return st->vals[i]; }
i = (i + 1) % st->capacity;
}
return 0;
}
bool ContainsLPHST(LinearProbingHashST st, int key) {
if (st == NULL) return false;
int i = st->hash_func(key);
while (st->keys[i] != INT_MIN) {
if (st->keys[i] == key) return true;
i = (i + 1) % st->capacity;
}
return false;
}
void RemoveLPHST(LinearProbingHashST st, int key) {
if (st == NULL || !ContainsLPHST(st, key)) return;
int i = st->hash_func(key);
while (st->keys[i] != key) i = (i + 1) % st->capacity;
st->keys[i] = st->vals[i] = INT_MIN;
i = (i + 1) % st->capacity;
while (st->keys[i] != INT_MIN) {
int tk = st->keys[i];
Value tv = st->vals[i];
st->keys[i] = st->vals[i] = INT_MIN;
st->count--;
SetLPHST(st, tk, tv);
i = (i + 1) % st->capacity;
}
st->count--;
if (st->count > 0 && st->count == st->capacity / 8) { ResizeHST(st); }
}
网友评论