美文网首页
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