本文共 811 字，大约阅读时间需要 2 分钟。

普通hash

定义 Hash函数：一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。 碰撞（冲突）：如果两个关键字通过hash函数得到的值是一样的，就是碰撞或冲突。 Hash表（散列表）：根据散列函数和冲突处理将一组关键字分配在连续的地址空间内，并以散列值记录在表中的存储位置，这种表成为散列表。

常用算法

直接寻址法：即取关键字或关键字的线性函数为散列地址：H(key)=key或H(key)=a*key+b; 数字分析法：即分析一组数据后采用的方法：如人的出生年月为92-09-03则前三位重复的几率比较大，容易产生碰撞，所以应该采用后三位作为hash值好点 平方取中法：取关键字平方的后几位。 折叠法：把关键字分割成位数相同的几部分，最后一部分可以位数不同，然后取这几部分的叠加值 随机数法：以关键值作为生成随机数的种子生成散列地址，通常适用于关键字长度不同的场合。 除留余数法：取关键字被某个不大于散列表长度m的数p除后所得的余数为散列地址:H(key)=key%p(p<=m);不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生碰撞。

一致性hash

hash算法被普遍用在很多地方，但是普通hash用在分布式环境中会有一些问题，比如用在membercache中时，假设有四个结点，如果初始算法为hash%4,则如果其中一台机器宕机的话，就需要改成hash%3算法，则所有的数据都要重新计算存储的位置，所以开销比较大。 一致性hash：首先对四个结点求hash值，然后分布在一个圆环上，然后对关键字也用同样hash算法求出hash值，并也分布在圆环上，其中数据存储在距离最近的结点，这样当其中一个结点宕机的时候只需要移动这个结点的部分数据到下个结点就行。  

转载地址：http://ilwad.baihongyu.com/