HashTable可以说是很多编程语言数据结构底层实现的基础，自己尝试实现一个简陋的能学到的东西还是相当多的。

hash加载因子

Hashtable 的加载因子确定元素与Hashtable 可拥有的元素数的最大比率。加载因子越小，平均查找速度越快，但消耗的内存也增加。默认的加载因子 0.72通常提供速度和大小之间的最佳平衡。当创建 Hashtable 时，也可以指定其他加载因子。 元素总量/ Hashtable 可拥有的元素数=加载因子。我最后参考JDK的实现选择了0.75为加载因子。

hash key的选择

使用字符串作为key和使用整形变量作为key是完全不一样的，首先字符串需要使用一种hash函数运算得到整形key, 其次字符串作为key需要占据更大的内存空间，本身char *占用8个字节，在加上字符串本身长度所分配的空间，而使用整形即便是long也只占用8个字节的大小。所以任何时候推荐大家使用如Php的数组，Python的字典能用整型做key就不用用字符串做key，整型key在时间和空间上都比字符串key节约。

hash算法

经过一番考察，返现time 33是比较好的hash算法，于是直接从php内核里面抠出了这个hash函数

inline unsigned long 
hash_func (const char *arKey)
{
    size_t nKeyLength = strlen(arKey);
    register unsigned long hash = 5381;

    /* variant with the hash unrolled eight times */
    for (; nKeyLength >= 8; nKeyLength -= 8) {
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
    }
    switch (nKeyLength) {
        case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 1: hash = ((hash << 5) + hash) + *arKey++; break;
        case 0: break;
    }

    return hash;
}

重建hash

重建hash是个非常耗时间和耗内存的操作，一次rehash需要重新计算key的hash，大多数的实现往往会缓存一个之前计算过一次的key，rehash的时候就不用进行重复计算了，但是大量的内存数据复制是不可避免的，因为需要把原先hash表里面的所有节点分配到新申请的内存中。所以最好的做好就是避免rehash这个操作，如果可以大概预测hash表的大小，在初始化hash表给定一个合适的范围可以提高效率，比如redis调优，自己在编程处理数据的时候也可以调优直接给hash表指定大小。

hash冲突解决方法

hash冲突的标准解决方法是使用链表，一旦使用了链表，在查找的时候，如果链表超长，hash就失去了意义，因为查找一个元素需要遍历这个链表（同时，插入和删除操作都会收到影响），从O(1)变成了O(n)，所以我们才需要固定hash加载因子，超过的时候进行rehash。这里推荐看看那linux内核中大量使用的hlist, 实现还是很牛逼的。因为我没有那个需求，所以我的链表的节点只有一个next指针，是个单链表。

后记

像Php内核的hash表实现会比较复杂，不管是hashtable结构体还是hashnode结构体都多了很多字段，原因是Php的数组（底层实现是个hashtable)承担了Php整个语言的数据结构，为了操作高效和方便，比如数组截取操作，看似简单，其实还是有点小复杂的，因为key经过hash之后的值分配到哪个Bucket是无法确定的，所以往hash表里面插入数据是无序的，为了保证有序，在每个hashnode上就会添加pre和next指针，用来保存插入时的顺序。所以所有的hashnode又是一个双向链表，所以会占用更多的内存，在计算机的世界里面，时间和空间永远是反比。

最后，Happy Hacking，代码地址