This is the first 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 map, use separate chaining to resolve hash collisions.
* Reference: Algorithms, 4ed, by R. Sedgewick & Kevin Wayne
*/
typedef int Key;
typedef bool Value;
typedef struct Node {
Value val;
Key key;
struct Node *next;
}*NodePtr;
typedef NodePtr SequentialSearchST;
/**
* Support set key/value to a empty list(NULL), under which circumstance a new
* list's returned.
*/
SequentialSearchST SetSSST(SequentialSearchST st, Key key, Value val) {
struct Node *node = st;
while (node != NULL) {
if (node->key == key) {
node->val = val;
return st;
}
node = node->next;
}
node = (struct Node*)malloc(sizeof*node);
node->key = key;
node->val = val;
node->next = st;
return node;
}
/**
* Return 0 for empty list(NULL) and absent keys.
*/
int GetSSST(SequentialSearchST st, Key key) {
struct Node *node = st;
while (node != NULL) {
if (node->key == key) { return node->val; }
node = node->next;
}
return 0;
}
SequentialSearchST RemoveSSST(SequentialSearchST st, Key key) {
if (st == NULL) return NULL;
struct Node *node = st;
if (node->key == key) {
st = node->next;
free(node);
return st;
}
struct Node *next = st->next;
while (next != NULL) {
if (next->key == key) {
node->next = next->next;
free(next);
return st;
}
node = next;
next = node->next;
}
return st;
}
typedef struct SeparateChainingHashSTStruct {
int M;
SequentialSearchST *st;
}* SeparateChainingHashST;
int Hash(Key key, int M) { return key < 0 ? -key % M : key % M; }
SeparateChainingHashST CreateSeparateChainingHashST(int M) {
SeparateChainingHashST hst = (SeparateChainingHashST)malloc(sizeof(*hst));
hst->M = M;
hst->st = (SequentialSearchST*)malloc(M * sizeof(*(hst->st)));
for (int i = 0; i < M; i++) { hst->st[i] = NULL; }
return hst;
}
void SetSCHST(SeparateChainingHashST hst, Key key, Value val) {
int hash = Hash(key, hst->M);
hst->st[hash] = SetSSST(hst->st[hash], key, val);
}
int GetSCHST(SeparateChainingHashST hst, Key key) { return GetSSST(hst->st[Hash(key, hst->M)], key); }
void RemoveSCHST(SeparateChainingHashST hst, Key key) {
int hash = Hash(key, hst->M);
hst->st[hash] = RemoveSSST(hst->st[hash], key);
}
网友评论