美文网首页
Concerning Hash Tables Part I

Concerning Hash Tables Part I

作者: 刘煌旭 | 来源:发表于2020-12-18 23:46 被阅读0次

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);
}

相关文章

网友评论

      本文标题:Concerning Hash Tables Part I

      本文链接:https://www.haomeiwen.com/subject/tphqnktx.html