哈希表定义
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数（哈希函数），存放记录的数组叫做散列表。
优缺点
哈希表可以提供快速的操作。第一次接触哈希表时，它的优点多得让人难以置信。不论哈希表中有多少数据，插入和删除只需要接近0(1）的时间级（由于碰撞冲突的存在，实际时间大于这个值）。在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)。哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。
当然，哈希表也有一些缺点。它通常是基于数组的，数组创建后难于扩展。所以哈希表被基本填满时，性能下降得非常严重，所以必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。而且，也没有一种简便的方法可以以任何一种顺序〔例如从小到大）遍历表中的数据项。
综上，如果不需要有序遍历数据，井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。
哈希查找
使用哈希查找有两个步骤:
1. 使用哈希函数将被查找的键转换为数组的索引。在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突。
2. 处理哈希碰撞冲突。有很多处理哈希碰撞冲突的方法，下文介绍。
哈希表是一个在时间和空间上作出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要根据实际情况，调整哈希函数即可在时间和空间上做出取舍。
哈希函数
在哈希表中，记录在表中的位置和其关键字之间存在着一种确定的关系。这样我们就能知道所查关键字在表中的位置，从而直接通过下标找到记录。
1.哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；
2.由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1！=key2，而 f (key1) = f(key2)。
3.只能尽量减少冲突而不能完全避免冲突，这是因为通常关键字集合比较大，其元素包括所有可能的关键字， 而地址集合的元素仅为哈希表中的地址值。在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一 种“处理冲突” 的方法。
哈希函数构造方法
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。一个好的散列函数一般应该考虑下列因素：
1.计算简单，以便提高转换速度。
2.关键词对应的地址空间分布均匀，以尽量减少冲突。
（当然也要考虑空间限制）
常见的哈希函数：
1. 直接寻址法
取关键字或者关键字的某个线性函数值作为哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b为整数),这种散列函数也叫做自身函数.如果H(Key)的哈希地址上已经有值了,那么就往下一个位置找,直到找到H(Key)的位置没有值了就把元素放进去。
例：有一个人口统计表，记录了从不同年龄的人口数目，其中年龄作为关键字，哈希函数取关键字本身。很显然，当需要查找某一年龄的人数时，直接查找相应的项即可。稍微复杂一点，如果我们要统计的是1990后出生的人口数，那么我们对出生年份这个关键字可以用年份减去1990来作为地址。这种哈希函数简单，并且对于不同的关键字不会产生冲突，但可以看出这是一种较为特殊的哈希函数，实际生活中，关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费，因此这种方法适应性并不强。
2. 数字分析法
分析一组数据,比如一组员工的出生年月,这时我们发现出生年月的前几位数字一般都相同,因此,出现冲突的概率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果利用后面的几位数字来构造散列地址,则冲突的几率则会明显降低.因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。这就要求能预先估计出全体关键字的每一位上各种数字出现的频度。
3. 平方取中法
取关键字平方后的中间几位作为散列地址。因为这种方法的原理是通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。该方法适用于关键字中的每一位都有某些数字重复出现频度很高的现象。
4. 折叠法
折叠法是将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(注意:叠加和时去除进位)作为散列地址.数位叠加可以有移位叠加和间界叠加两种方法.移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。该方法适用于关键字特别多的情况。
5. 随机数法
选择一个随机数,作为散列地址,通常用于关键字长度不同的场合。此时，H(key)=random(key)。
6. 除留余数法
取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址.即H(Key)=Key MOD p,p<=m.不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选得不好，则很容易产生冲突。
实际造表时，采用何种构造哈希函数的方法取决于很多因素。另外，哈希函数也远远不止上面的这几种，只要合理考虑下面这几个因素的，理论上都可以作为哈希函数：
l 计算哈希函数所需时间 （简单）。
l 关键字的长度。
l 哈希表大小。
l 关键分布情况。
l 记录查找频率
哈希冲突通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。
1.开放定址法
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H(key)出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi=(H(key)+di)%m i=1，2，…，m-1,其中H（key）为哈希函数，m 为表长，di称为增量序列，i为碰撞次数。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下几种：
(1) 线性探测再散列
di=1，2，3，…，m-1
这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
(2)二次探测再散列
di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )
这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
(3)伪随机探测再散列
di=伪随机数序列。
在实际程序中应预先用随机数发生器产生一个随机序列，将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次序，从而可以避免或减少聚集。
线性探测再散列的优点是：只要哈希表不满，就一定能找到一个不冲突的哈希地址，而二次探测再散列和伪随机探测再散列则不一定。线性探测再散列容易产生“二次聚集”，即在处理同义词的冲突时又导致非同义词的冲突。
其实除了上面的几种方法，开放定址法还有很多变种，不过都是对di有不同的表示方法。（如双散列探测法：di=i*h2(k)）
2.再哈希法
这种方法是同时构造多个不同的哈希函数：Hi=RHi（key），i=1，2,3，…,n。
当哈希地址H1=RH1（key）发生冲突时，再计算H2=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
3.链地址法(拉链法)
这种方法的基本思想是将所有哈希地址相同的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表中，因而查找、插入和删除主要在同义词链中进行。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。链地址法适用于经常进行插入和删除的情况。
拉链法的优点
与开放定址法相比，拉链法有如下几个优点：
(1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
(3)开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中理论上可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；（散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度）
注：HashMap默认装填因子是0.75。
(4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放定址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径。这是因为各种开放定址法中，空地址单元都被理解没有查找到元素。 因此在用开放定址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
拉链法的缺点
拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，此时将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
4、建立公共溢出区
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表(在这个方法里面是把元素分开两个表来存储)。
Java中的equals和hashCode
首先，Java中equals方法和hashCode方法都是Object类中就有的，所以每个对象都是有这两个方法的，有时候我们需要实现特定需求，可能要重写这两个方法。Object类中，equals其实就是比较地址是否相等，而hashCode就是散列函数的实现，是native方法，实现逻辑与JVM有关，有些JVM是直接返回对象的存储地址，但是大多时候并不是这样，只能说可能和存储地址有一定关联。equals和hashCode共同作用，有效支撑了基于哈希机制的集合类。
由于两者经常被重写，这里说一些重写的原则。
equals重写约定
自反性: x.equals(x) 一定是true。
对null: x.equals(null) 一定是false。
对称性: x.equals(y)和y.equals(x)结果一致。
传递性：x.equals(y), 并且y.equals(z)，那么x.equals(z)。
一致性：对于任何非null的引用值x和y，只要equals的比较操作在对象中所用的信息没有被修改，多次调用x.equals(y)返回结果一致;因此，equals方法里面不应该依赖任何不可靠的资源。
hashCode重写约定
注：关于hashCode的约定，参考哈希表的定义，就变得很好理解。因为要同时兼顾时间空间，所以允许一定的哈希冲突，但必须保证等价对象的哈希值相等（当然哈希函数还是要尽量减少冲突的）。
哈希加密算法
现代通常所说的哈希算法，应该区别于哈希表的构造函数算法（因为哈希算法在此基础上增加了额外的含义），并广泛用于密码学等领域。
密码学里面有一类算法叫做哈希哈希算法，也称作散列算法、摘要算法，通常用于对一段信息的取样。当你给它一段信息（message）时，可以用特定算法生成一段信息摘要（message digest），通常摘要的长度更短。摘要（digest）可以表示这段信息的某种特征——就如同指纹一样，所以这个特征也叫做指纹（fingerprint）、校验。
理想情况下，哈希算法应该有四个重要特性（这里是密码学中的哈希算法）：
不可逆：不能从摘要生成其原始信息
无冲突：不同的信息具备不同的摘要
易计算：对任意信息容易计算其摘要
特征化：信息修改后其摘要一定变化
实际上，前两个特性基本无法绝对实现。以流行的MD5举例，既无法避免彩虹表的存在，也早在2004年就实现了碰撞。截至2015年，这些算法的生存状况如图：一致性哈希
一致性哈希算法(consistent hashing) ，主要用于发布式缓存中。在一些高速发展的web系统中，传统的哈希函数，如hash取模法，存在明显缺陷。随着系统访问压力的增长，缓存系统不得不通过增加机器节点的方式提高集群的相应速度和数据承载量。增加机器意味着，如果按照hash取模的方式，在增加机器节点的这一时刻，大量的缓存不能命中，缓存数据需要重新建立，甚至是整体迁移，这一瞬间会给DB带来极高的系统负载。
判定哈希算法好坏的四个定义：
1、平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
2、单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
3、分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
4、负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。
在分布式集群中，对机器的添加删除，或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash取模算法，那么在有机器添加或者删除后，很多原有的数据就无法找到了，这样严重的违反了单调性原则。接下来主要说明一下一致性哈希算法是如何设计的。
以SpyMemcached的ketama算法来说，思路是这样的：
使用虚拟节点的思想，为每个物理节点（服务器）在分配100～200个虚拟节点。这样就能抑制分布不均匀，最大限度地减小服务器增减时的缓存重新分布。用户数据映射在虚拟节点上，就表示用户数据真正存储位置是在该虚拟节点代表的实际物理服务器上。
下图描述了需要为每台物理服务器增加的虚拟节点。x轴表示的是需要为每台物理服务器扩展的虚拟节点倍数，y轴是实际物理服务器数。可以看出，当物理服务器的数量很小时，需要更大的虚拟节点，反之则需要更少的节点，从图上可以看出，在物理服务器有10台时，差不多需要为每台服务器增加100~200个虚拟节点才能达到真正的负载均衡。
参考地址：http://baike.baidu.com/
参考地址：http://blog.csdn.net/tanggao1314/article/details/51457585
参考地址：http://blog.csdn.net/qq_21688757/article/details/53861896
参考地址：http://www.linuxidc.com/Linux/2016-01/127239.htm
参考地址：http://blog.csdn.net/cywosp/article/details/23397179
参考地址：http://blog.csdn.net/kongqz/article/details/6695417
