美文网首页
Concerning Hash Tables Part II

Concerning Hash Tables Part II

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

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

相关文章

网友评论

      本文标题:Concerning Hash Tables Part II

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