定义
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。查找时，根据这个确定的对应关系找到给定key的映射f(key)，若查找集合中存在这个记录，则必定在f(key)的位置上。
这里我们把这种对应关系f称为散列函数，又称为哈希（Hash）函数。采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表或哈希表（Hash table）。关键字对应的记录的存储位置称之为散列地址。
散列技术最适合的场景是查找与给定值相等的记录，无法进行范围查询。对于查找来说，它简化了比较过程，效率比较高。
散列技术的记录之间不存在什么逻辑关系，它只与关键字有关联。
查找步骤
分为两步。
- 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。
- 查找记录时，通过相同的散列函数计算记录的散列地址，并按此散列地址访问该记录。
散列冲突
两个关键字key1≠key2，但是却有f(key1)=f(key2)，这种现象我们称为冲突，并把key1和key2称为这个散列函数的同义词。好的散列函数应该让冲突尽可能的少。
散列函数
不管做什么事要达到最优都不容易，既要付出尽可能的少，又要得到最大化的多。那么什么才算好的散列函数呢？这里有两个原则可以参考：
- 计算简单。如果你设计一个算法可以保证所有的关键字都不会产生冲突，但是这个算法需要很复杂的计算，会耗费很多时间，这对于频繁查找来说，就会大大降低查找的效率。因此散列函数的计算时间不应该超过其他查找技术与关键字比较的时间。
- 散列地址分布均匀。可以保证存储空间的有效利用，并减少为处理冲突而耗费的时间。
直接定址法
如果我们要将0~100岁的人口数字统计表存储到散列表，那么我们对年龄这个关键字可以直接用年龄数字作为地址。此时f(key)=key。
如果我们现在统计的是80后出生年份的人口数，那么我们对出生年份这个关键字可以用年份减去1980来作为地址。此时f(key)=key-1980。
也就是说，我们可以取关键字的某个线性函数值作为散列地址。即：
f(key)=a×key+b (a、b为常数)
这样的散列函数优点是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。
数字分析法
如果关键字是位数较多的数字，比如长度为11的手机号码，例如“151xxxx1234”。其中前三位是接入号，一般对应不同运营商公司的子品牌；中间四位是HLR识别号，表示用户号的归属地；后四位才是真正的用户号。
假设我们现在要存储某家公司的员工信息，用手机号码作为关键字。如果这家公司的员工都是同一个地区的（比如地方的小公司），中间4位大概率是相同的，那么极有可能前7位有大量重复。这种情况下抽取后面4位数字作为散列地址也许是个不错的选择。
如果这样抽取还是容易出现冲突，还可以对抽取出来的数字再进行反转（如1234改成4321）、右环位移（如1234改成4123）、左环位移、甚至前两位数与后两位数叠加（如1234改成12+34=46）等方法。总的目的就是为了提供一个散列函数，能够合理地将关键字分配到散列表的各位置。
使用关键字的一部分来计算散列存储位置，这在散列函数中是常常用到的手段。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。
平方取中法
假设关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227，用作散列地址。再比如关键字是4321，那么它的平方就是18671041，抽取中间的3位就可以是671，也可以是710，用作散列地址。平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。
折叠法
折叠法是将关键字从左到右分隔成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，取后几位作为散列地址。
比如关键字是9876543210，散列表表长为三位，我们将关键字分为四组987|654|321|0，然后将它们叠加求和987+654+321+0=1962，再求后3位得到散列表地址为962。
可能有时这还不能保证分布均匀，不妨从一端向另一端来回折叠后对齐相加。比如将987和321反转，再与654和0相加，变成789+654+123+0=1566，此时散列地址为566。
折叠法不需要事先了解关键字的分布，适合关键字位数较多的情况。
除留余数法
此方法最常用。对于散列表长为m，散列函数公式为：
f(key)=key mod p (p≤m)
mod是取模（求余数）的意思。事实上，这个方法不仅可以对关键字直接取模，也可以在折叠、平方取中后再取模。
很显然，本方法的关键就在于选择合适的p，p如果选得不好，就很容易产生同义词。
例如下表，我们对于有12个记录的关键字构造散列表时，就用了f(key)=key mod 12的方法。比如29 mod 12=5，所以它存储在下标为5的位置。
不过这也是存在冲突的可能的，因为12=2×6=3×4。如果关键字中有18（3×6）、30（5×6）、42（7×6）等数字，它们的余数都为6，这就和78所对应的下标位置冲突了；有像16（4×4）、28（7×4）、40（10×4）等数字，它们的余数都为4，这就和16对应的下标位置冲突了。
甚至极端一些，对于下表所示关键字，如果我们让p为12的话，就可能出现下面的情况，所有的关键字都得到了0这个地址数，这种情况就很糟糕了。
如果不选用p=12来做除留余数法，而选用p=11，结果如下表：
此时就只有12和144有冲突，相对来说，就要好很多。
随机数法
以关键字为种子，生成一个随机数作为它的散列地址。也就是f(key) = random(key)。这里random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。
那么问题来了，既然是随机数，那如何保证同一个关键字获取的地址是一样的？其实，计算机里的随机是伪随机，对于同一个种子，它生成的随机数序列是一样的。例如关键字是9，表长是21，运行下面的Java代码：
int key = 9, tableLength = 21, times = 6;
Random r1 = new Random(key);
System.out.print("[");
for (int i = 0; i < times; i++) {
// upper bound设置为tableLength，随机出来的数将会小于tableLength，可以直接作为地址
System.out.print(r1.nextInt(tableLength));
if (i != times - 1)
System.out.print(", ");
}
System.out.println("]");
System.out.print("[");
Random r2 = new Random(key);
for (int i = 0; i < times; i++) {
System.out.print(r2.nextInt(tableLength));
if (i != times - 1)
System.out.print(", ");
}
System.out.println("]");
输出结果：
[7, 4, 1, 7, 17, 12]
[7, 4, 1, 7, 17, 12]
就随机6次得到的结果来看，采用同一个关键字作为种子的随机函数，生成的随机数序列完全是一样的。既然这样，那么我们就可以每次都取序列的第一个值（随机一次）或第二个值（随机两次）作为散列地址（随机太多次会增加运算量，一次或两次就行了）。
可能有人会问，那如果关键字是字符串该如何处理？其实无论是英文字符，还是中文字符，也包括各种各样的符号，它们都可以转化为某种数字来对待，比如ASCII码或者Unicode码等，因此也就可以使用上面的这些方法。
总之，现实中，应该视不同的情况采用不同的散列函数。我们只能给出一些考虑的因素来提供参考：
- 计算散列地址所需的时间。
- 关键字的长度。
- 散列表的大小。
- 关键字的分布情况。
- 记录查找的频率。
综合这些因素，才能决策选择哪种散列函数更合适。
处理散列冲突的方法
设计的再好的散列函数也不可能完全避免冲突，那么该如何处理冲突呢？
开放定址法
一旦发生了冲突，就去寻找下一个空的散列地址，并将记录存入。只要散列表足够大，空的散列地址总能找到。它的公式是：
fi(key)=(f(key)+di) mod m (di=1,2,3,...,m-1)
比如说，关键字集合为[12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34]，表长为12。我们用散列函数f(key)=key mod 12。
前5个数都没有冲突，直接存入。
当计算key=37时，发现f(37)=1，此时就与25所在的位置冲突。于是我们应用上面的公式fi(37)=(f(37)+1) mod 12=2。于是将37存入下标为2的位置。如下图所示：
接下来22，29，15，47都没有冲突，正常的存入。
到了key=48，我们计算得到f(48)=0，与12所在的0位置冲突了，不要紧，我们fi(48)=(f(48)+1) mod 12=1，此时又与25所在的位置冲突了。于是fi(48)=(f(48)+2) mod 12=2，还是冲突…一直到fi(48)=(f(48)+6) mod 12=6时，才有空位。
我们把这种解决冲突的开放定址法称为线性探测法。
从这个例子我们也可以看到，在解决冲突的时候，还会碰到如48（48 mod 12=0）和37（37 mod 12=1）这种本来都不是同义词却需要争夺同一个地址的情况，我们称这种现象为堆积。很显然，堆积的出现，使得我们需要不断的处理冲突，无论是存入还是查找效率都会大大降低。
考虑深一步，如果发生这样的情况，当最后一个key=34，f(34)=10，与22所在的位置冲突，可是22后面没有空位置了，反而它的前面有一个空位置，尽管可以不断地求余数后得到结果，但效率很差。因此我们可以改进di=12，-12，22，-22，…，q2，-q2 （q≤m/2）， 注意，这里是平方后再取负，不是负数的平方，这样就等于是可以双向寻找到可能的空位置。对于34来说，我们取di=-1即可找到空位置了。另外增加平方运算的目的是为了不让关键字都聚集在某一块区域。我们称这种方法为二次探测法。
fi(key)=(f(key)+di) mod m (di=12，-12，22，-22，...，q2，-q2，q≤m/2)
还有一种方法是，在冲突时，对于位移量di采用随机函数计算得到，我们称之为随机探测法。
总之，开放定址法只要在散列表未填满时，总是能找到不发生冲突的地址，是我们常用的解决冲突的办法。
上面说的是存储流程，那该如何查询呢？查询的时候，也是用同样的散列函数，比如说关键字是key1，定位到地址后，还不能确定要找的就是这个地址存储的记录（因为冲突），还要拿关键字key1与该地址存储的关键字key2进行比较，如果key1=key2说明查找到了记录，此时直接返回记录；如果key1≠key2，那就继续寻找下一个地址存储的记录并比较关键字，同样是找到了就返回，没找到就继续查找下一个地址，直到所有可能出现的地址都没查到，那就说明记录不存在。
再散列函数法
每当发生散列地址冲突时，就换一个散列函数计算，相信总会有一个可以把冲突解决掉。
fi(key)=RHi(key) (i=1，2，...，k)
这里RHi就是不同的散列函数，你可以把我们前面说的什么除留余数、折叠、平方取中全部用上。这种方法能够使得关键字不产生聚集，当然，相应地也增加了计算的时间。
查询流程跟开放定址法差不多，都是定位到地址后还要比较关键字。
链地址法
思路还可以再换一换，为什么有冲突就要换地方呢？我们直接就在原地想办法不行吗？于是就有了链地址法。
将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。对于关键字集合[12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34]，我们用前面同样的12为除数，进行除留余数法，可得到如下图所示结构，此时，已经不存在什么冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。甚至当链表长度太长影响查询性能时，还可以将链表转换成红黑树，Java中的HashMap就是这么干的。
公共溢出区法
你不是冲突吗？好吧，凡是冲突的都跟我走，我给你们这些冲突的记录找个地方待着。就如同孤儿院收留所有无家可归的孩子一样，我们为所有冲突的关键字建立了一个公共的溢出区来存放。
就前面的例子而言，我们共有三个关键字37,48,34与之前的关键字位置有冲突，那么就将它们存储到溢出表中，如下图所示：
在查找时，对给定关键字通过散列函数计算出散列地址后，先与基本表的相应位置进行对比，如果相等，则查找成功；如果不等，再到溢出表进行顺序查找。如果有冲突的数据很少，公共溢出区的结构对查找性能来说还是不错的。
散列表查找性能分析
如果没有冲突，散列表查找性能很高，时间复杂度为O(1)。可惜，这只是“如果”，没有冲突的散列只是一种理想情况，在实际应用中，冲突是不可避免的。那么散列表查找的平均查找长度取决于哪些因素呢？
- 散列函数是否均匀。散列函数的好坏直接影响着出现冲突的频繁程度。
- 处理冲突的方法。相同的关键字、相同的散列函数，但处理冲突的方法不同，会使得平均查找长度不同。比如线性探测处理冲突可能会产生堆积，显然就没有二次探测法好。
- 散列表的装填因子。装填因子=填入表中的记录个数÷散列表长度。装填因子标志着散列表装满的程度。在散列表长度固定不变的情况下，当填入表中的记录越多，装填因子就越大，产生冲突的可能性就大。不管记录个数有多大，我们总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围内，此时散列表查找的时间复杂度就真的是O(1)了。为了做到这一点，通常都是将散列表的空间设置的比查找集合大，比如说控制装填因子的上限为0.75，此时虽然是浪费了一定的空间，但换来的是查找效率的大大提升，总的来说还是非常值得的。