hash table 实现代码

 C++代码中有unodered_map<>()可实现hash操作，但是在追求效率的代码中，使用会严重影响代码的执行效率。

通常使用自己手动实现的hash table效率会有大幅度的提升，这对于追求极致效率的题目至关重要。

通常的hash操作有字符串哈希和较大数据的哈希。

• 字符串哈希，通常利用移位操作。hval = hval << 5 + (str[i] - 'a' + 1)，同时需要将 hval 进行缩放，这里一般可以对13131（较大的质数，实验发现哈希冲突较小）或者2的次方（CPU计算除法时对于2的次方速度较快）取余。
• 对较大的数据哈希，一般也是对13131或者2的次方取余。（这其实也就是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;
    }
};