浅谈hash实现原理
哈希表(散列表)通过将关键码映射到表中的某个位置上来存储元素，然后根据关键码来访问元素。
常用的hash函数有除留余数法，线性探测，二次探测，开链法，在大部分情况下基本就是用开链法：
1、直接定址法
取关键字的某个线性函数作为散列函数，Hash(key)=A*key+B;
但是这种方法有很大的缺陷，就是当关键码比较分散时，hash表的所浪费的空间是非常大的。
2、除留余数法
设散列表中允许出现的地址数为m，取一个不大于m但是最接近或等于m的素数p，作为除数(素数作为除数能够减少哈希冲突)。
hash(key)=key%p; p<=m;
解决冲突的方法：
一、闭散列法(开地址法)：
1、线性探测法
在线性探测中，冲突时通过顺序扫描数组(可以往回找)，直到找到空的位置。查找算法也使用了探测法。
hash(key)+0,hash(key)+1,hash(key)+2, .... hash(key)+i,
但是这种方法有可能引发原始集聚话问题，即导致局部范围大规模发生冲突。
2、二次探测法
hash(key)+0^2,hash(key)+1^2,hash(key)+2^2, .... hash(key)+i^2。
二次探测法检查了远离原始探测点的单元，这样的话就降低了原始集聚化问题。
二、开散列法(链地址法):
数组查找容易，插入删除难，链表插删容易，查找困难，拉链法：可以理解为数组中存放链表，相同关键码放在数据同一下标
的链表里。
元素个数/hash表长度 一般控制在0.7 -0. 8 如果超过就要扩容
hash表扩容
Hash表中每次发现loadFactor到一定程度时（比如大于0.8），就开辟一个原来桶数组的两倍空间（称为新桶数组），然后把原来的桶数组中元素所有转移过来到新的桶数组中。注意这里转移是须要元素一个个又一次哈希到新桶中。
这样的方法的缺点是，容量扩张是一次完毕的，期间要花非常长时间一次转移hash表中的全部元素
Memcached的扩容条件是当表中元素个数超过Hash容量的1.5倍时就进行扩容，扩容过程由独立的线程来完成，扩容过程中会采用2个Hash表，将老表中的数据通过Hash算法映射到新表中，每次移动的桶的数目可以配置，默认是每次移动老表中的1个桶。
这样的策略就把第一个hash表全部元素的转移分摊为多次转移，并且每次转移的期望时间复杂度为O(1)。
如何提高hash查找的效率
- 设置好的hash函数，冲突尽量少
- 空间换时间，增大表长
- hash桶挂红黑树