Hash table implementation code

 C++代码中有unodered_map<>()可实现hash操作,But in code that pursues efficiency,Use will seriously affect the execution efficiency of the code.

Usually implemented manuallyhash tableEfficiency will be greatly improved,This is crucial for the pursuit of extreme efficiency.

通常的hashOperations have string hashes and hashes of larger data.

• 字符串哈希,Usually a shift operation is used.hval = hval << 5 + (str[i] - 'a' + 1),同时需要将 hval 进行缩放,Generally correct here13131（larger prime number,Experiments have found that hash collisions are small）或者2的次方（CPUFor when calculating division2The power of the speed is faster）取余.
• Hash for larger data,Generally correct13131或者2The square of the remainder.（这其实也就是hash table的范围）

#define HASHSIZE 10
#define ull unsigned long long
typedef unsigned int uint;
typedef struct Node {
    const char* key;
    const char* value;
    Node* next;
}Node;

struct HashTable {
    Node* node[HASHSIZE];

    void clear() {
        for (int i = 0; i < HASHSIZE; ++i)
            node[i] = nullptr;
    }

    uint hash(const char* key) {
        ull res(0);
        int i = 0;
        while (key[i] != '\0') {
            res = res << 5 + (key[i] - 'a' + 1);
            ++i;
        }
        return res % HASHSIZE;
    }

    Node* lookup(const char* key) {
        Node* np;
        uint index = hash(key);
        for (np = node[index]; np; np = np->next)
            if (!strcmp(key, np->key))
                return np;
        return nullptr;
    }

    bool install(const char* key, const char* value) {
        uint index;
        Node* np;
        if (!(np == lookup(key))) {
            index = hash(key);
            np = (Node*)malloc(sizeof(Node));
            if (!np) return false;
            np->key = key; np->next = node[index];
            node[index] = np;
        }
        np->value = value;
        return true;
    }
};