哈希（Hash）相关---基本概念、hash函数构造方法、解决冲突的方法、解决分布式缓存的consistent hashing

----------------hash的基本概念------------
哈希方法在“键-值对”的存储位置与它的键之间建立一个确定的对应函数关系hash()，使得每一个键与结构中的一个唯一的存储位置相对于：存储位置=hash(键)
在搜索时，首先对键进行hash运算，把求得的值当做“键-值对”的存储位置，在结构中按照此位置取“键-值对”进行比较，若键相等，则搜索成功。

在存储“键-值对”的时候，依照相同的hash函数计算存储位置，并按此位置存放，这种方法叫做哈希方法（也叫做散列方法）。在哈希方法中使用的转换函数 hash被称为 哈希函数（或散列函数）。按照此算法构造出来的表叫做哈希表（或者散列表）。
哈希函数建立了从“键-值对”到哈希表地址集合的一个映射。使用这种方法由于不必进行多次键的比较，所以搜索速度非常快。
-----
哈希 就是以空间换时间（因为hash表也需要存储空间），不过，采用哈希函数的作用之一就是减少需要被处理的数组大小，（和直接寻址相比）存储空间的开销也相应减少。

---------------hash函数------------------
通常键的取值范围比哈希表地址集合大太多，因此有可能经过同一哈希函数的计算，把不同的键映射到了同一个地址上面，这就产生了冲突。
如果“键-值对”在加入哈希表的时候产生了冲突，就必须找另外一个地方来存储它，冲突太多会降低数据插入和查找的效率，因此希望找到一个不容易产生冲突的函数，即构造一个地址分布比较均匀的哈希函数。
常用的hash函数包括：
直接定址法（用于key值为数字或有一定次序规则的情况）、
数字分析法（对key中的数字规则进行分析）、
乘法散列法 将关键字key乘以一个常量A（0<A<1），并且提出key*A的小数部分；然后将这个值乘以m：
           h(key)=m*(key*A-(int)(key*A))
乘法散列的一个优势是对m的值没有特别的要求，对应m，一般指定为2的幂。因为这样容易在计算机中实现哈希函数的计算。对常量A，更好的选择是依赖于被散列的数据特征，一般用A等于黄金分割点0.618033.

陈留余数法（%取余法h(key)=key%m,）
其关键是m 的选取,一般选m 为小于某个区域长度n 的最大素数，一般地说，如果 m 的约数越多，那么冲突的几率就越大
简单的证明：假设m 是一个有较多约数的数，同时在数据中存在key 满足最大公约数gcd(m,key)=d >1 ，即 有m=a*d,key=b*d,则有以下等式：key% m= key – m*[key/m] =key – m*[b/a] 。其中，[b / a]的取值范围是不会超过[0，a-1]的正整数。也就是说，[b / a]的值只有a 种可能，而m 是一个预先确定的数。因此上式的值就只有a 种可能了（这显然缩小了余数分布的范围）。这样，取mod 运算之后的余数仍然在[0，m-1]内，但是它的取值仅限于等式可能取到的那些值。也就是说余数的分布变得不均匀了。容易看出，m 的约数越多，发生这种余数分布不均匀的情况就越频繁，冲突的几率越高。而素数的约数是最少的，因此我们选用大素数。所以“m应该最优选择素数”。

平方散列法 由于%包含了*和/的操作，而乘法的运算比除法省时，可以考虑把%变为乘和移位的组合操作对应平方散列法：

                    可以形如：index=(key*key)>>28

对与平方散列法其实有种改进，通过实验证明这种改进是有效的就是把key*key换成key*一个常数Q，这个常数就来自于斐波那契数列中的值，对于16位整数，Q为40503；32位整数，Q为2654435769；64位整数，Q为11400714819323198485
于是对于常见在32位整数来说，index=（key*2654435769）>>28

平方取中法（key平方后取中间的几位为hash地址）、
折叠法（将key分割成几个部分，叠加求和）、
随机数法（选择一个随机函数，取关键字的随机函数值为它的哈希地址）。

应该根据实际工作中关键码的特点选用适当的方法。

----------------hash冲突---------------
为了避免冲突，选择哈希函数h()的主导思想是使h(k)的出现是“随机”的，即每个关键字都可能散列到任一个地址中去，从而减少冲突的次数。虽然采用合适的哈希方法能够降低冲突的概率，但是冲突仍然是不可避免的:

解决冲突的方法：
(1).链地址法：将具有同一散列地址的记录存储在一条线性链表中。
(2).开放地址法：如果h(k)被占用，就按照如下序列探测：(h(k)+p(1))%TSize,(h(k)+p(2))%TSize,...,(h(k)+p(i))%TSize,...

                      其中，h(k)为哈希函数，TSize为哈希表的长度，p(i)为探测函数。在(h(k)+p(i))%TSize的基础上，若发现冲突，则使用

                      增量p(i+1)进行新的探测，直到无冲突为止。

                      其中，根据探测函数p(i)的不同，开发地址发又分为：

                                  线性探测法（p(i)=i:1,2,3,4,5,6,....）;   

                                  二次（或平方）探测法：（p(i)=((-1)^(i-1))(i)^2:1,-1,4,-4,9,-9,......）

                                  随机探测法（p(i):为随机数）

                                  双散列函数（双散列函数h(key)、hp(key)，如果h(key)出现冲突，则再使用hp(key)求取散列地址）

                                                     探测序列为：h(k),h(k)+hp(k), ... ,h(k)+i*hp(k),...     

(3). 桶地址法   
桶--一片较大的存储空间             
“桶”算法：假设哈希表有m个地址，就将其改为m个“桶”，其桶号和哈希地址一一对应，每个桶用来存放互为同义词的键，也就是如果两个不同的键用哈虚函数计算得到了同一个哈希地址，就将它们放到同一个桶中，检索的时候就在桶中进行顺序检索，如果当桶满时可以用开放地址法处理。  
-----
当某个bucket中存放的数据非常多时，也就是哈希表中的某个bucket冲突数据非常多时，采用哈希AVL树方式存放这些冲突数据对查找效率会有明显的提高。
-----------------解决分布式缓存的consistent hashing算法-----------------
consistent hashing算法：是一种hash算法，简单地说，在移除/添加一个cache（缓存）时，它能够尽可能小的改变已存在key映射关系，尽可能满足单调性（单调性是指：如果已经有一些内容通过哈希分配到了相应的缓存中，又有新的缓存加入到系统中。哈希的结果应该能够波安装原有已分配的内容可以被映射到新的缓存中去，而不会被映射到久的缓存集合中的其他缓冲区）的要求。
----------扩展 d-left-hashing------------

d-left-hashing,是对传统hash方法的优化和改进，以达到key位置的负载均衡。

其大概思想就是：整个哈希表被分成d个从左到右依次相邻子表，同时有d个相互独立的hash函数，当有key需要hash时，这d个hash函数同时计算，产生d个独立index，然后将key加入到负载最轻的位置中，如果负载最轻的位置有多个（比如同时为空或同时有n个），就把index指定为最左边负载最轻的子表中。

---------------

hash 在对海量数据的处理和密码学方面（如MD5算法）都有很好的应用。

------

后继还会对Hash进一步探索