目录

1 哈希表的含义与结构特点

1.1 哈希（Hash）即无序

1.2 从数组看哈希表的结构特点

2哈希函数（Hash Function）与哈希冲突（Hash Collision）

2.1 哈希函数及其设计方法

2.2 哈希冲突及其解决方案（含Java模拟）

2.2.1 开放地址法

2.2.2 链表法

1 哈希表的含义与结构特点

1.1 哈希（Hash）即无序

哈希表（Hash Table）更直观的中文名字是散列表，存储在里面的元素不是单个的，而是成对的，这就是我们熟悉的键值对（key-value pair）。Java中的Map（映射）、Python中的Dictionary（字典）以及NoSQL（非关系型数据库）采用的都是这种存储方式。

“数据结构学习笔记”系列的前6篇文章介绍的线性表型结构（链表、栈、队列）、数组型结构（数组、基于数组的字符串）和树型结构（二叉树）都有一个共同的特点，就是它们都要保证存储在里面的数据是有序的。哈希表则与之相反，存储在其中的元素是散列的，也就是无序的。

出于好奇，笔者去有道词典查了查hash这个单词的意思，《牛津词典》的解释是：“a hot dish of cooked meat and potatoes that are cut into small pieces and mixed together”，就是用切成碎末的肉和马铃薯做成的热菜，由此就引申除了“零碎、杂乱”的意思，到数据结构领域就成了“散列”。

顺便提一下，还有一个很有趣的短语：make a hash of sth，意思是把某事弄糟。

1.2 从数组看哈希表的结构特点

我们认为，数组型结构和树型结构都可以看成线性表型结构的推广，而哈希表的散列型结构又是数组型结构的推广。为什么这么说呢？

在线性表中，无论是链表、栈还是队列，每一个元素在空间位置上与其前后的元素构成关联；在数组中，每一个数据在空间位置上都与首元素构成关联，索引的本质含义是元素与首元素的偏移量；在树结构中，每一个数据在空间位置上都与其上下层的元素构成关联。

因此，与线性表相比，数组将所有元素相互依赖的递归结构转换为所有元素具有相同基准的结构，从而实现了基于索引的快速随机访问；树将元素间一对一的关系推广为一对多的关系，从而实现了数据结构的层级。

上述有序结构中，能够衍生出无序结构的只有数组。在本系列讲解数组的文章中，提到了我们会基于日常经验将“索引”理解为“编号”的问题，这实际上就是散列的思想。因为元素一旦具有唯一的“编号”，我们定位元素时的思考角度就不再是谁在谁的前面或后面，而是那个元素的“编号”是多少。

“编号”与元素之间是映射(Map)的关系，这很像字典(Dictionary)的检字法。正因为数组中索引与元素具有映射关系，所以把索引看成编号是没有毛病的。编号可以有序，也可以无序。比如下面的Python代码定义的列表（相当于数组）和字典（相当于哈希表）：

# 定义一个 列表（数组）list_1 = ['赵', '钱', '孙', '李']# 定义一个 字典（哈希表）， 键-值 为上述列表的 索引-元素dict_1 = {0:'赵', 1:'钱', 2:'孙', 3:'李'}# 再定义一个 字典（哈希表），键-值 为 拼音首字母-汉字dict_2 = {'z':'赵', 'q':'钱', 's':'孙', 'l':'李'}

2哈希函数（Hash Function）与哈希冲突（Hash Collision）

2.1 哈希函数及其设计方法

数组是顺序存储，可以顺序访问（即遍历），也可以随机访问；而哈希表则实现了随机存取，无论是存储还是取出数据都与数据所在的位置无关。实现随机存取依靠的是哈希函数（Hash Function）。

哈希函数的格式是：addr= f(key)。其中addr指的是数据的内存地址，key指的是数据值有关的关键字。存储时，通过关键字分配得一个内存空间；取出时，通过关键字定位到内存地址，从而得到数据值。

键值对为“索引-元素”的哈希表，哈希函数应写为：addr = f(index) = index。其实就是一个一元一次函数：y=x，这是一个线性函数，因此数组既能顺序访问，也能随机访问。但是数组的随机访问是有局限性的，访问元素只有基于顺序的索引这一个选择，不能根据数值本身包含的信息查找数据。我们来看下面的两个存储姓氏的哈希表，代码语言为Python：

family_name_1 = {1:'赵', 2:'钱', 3:'孙', 4:'李'}family_name_2 = {'z':'赵', 'q':'钱', 's':'孙', 'l':'李'}

第一个哈希表（字典）的关键字是姓氏在《百家姓》中的次序，第二个哈希表（字典）的关键字是姓氏的拼音首字母，如何定义关键字是根据需求来的。

哈希函数的设计是为了让“键值对”中的“键”具有唯一性，且符合数据检索的需求。设计哈希函数的常用方法包括：直接定制法、数字分析法、平方取中法、折叠法和除留取余法。

直接定制：比如上面姓氏哈希表的“键”就是根据某种规则直接定制的；数字分析：比如存储个人信息的表中，取身份证后六位，因为这几位不容易重复；平方取中：即取平方再取中间的若干位，适用于重复位较多的数据，平方为了扩大差异；分段叠加：比如将18位身份证号三等分，再将三个六位数值叠加（舍去进位）；除留取余：将关键字与长度短于关键字的数字做除法，取余数为地址；随机数法：比如快递柜的六位取件码就是随机生成的。

从以上方法中不难看不出，对原数据值哈希函数可以起到化长为短的作用。比如18位的身份证号经过数字分析法后就变成了6位。如果作为关键字的数据占空间很大，直接拿来用是很浪费内存的。

2.2 哈希冲突及其解决方案（含Java模拟）

任何一种哈希函数都很难保证得到的哈希值不会重复，一旦重复就会产生冲突。解决哈希冲突有两种常用的方法：开放地址法（openning addressing）和链表法（chaining）。

2.2.1 开放地址法

开放地址法的思路很好理解，如果出现哈希冲突，就采用某种探测方法从发生冲突的位置依照某种探测顺序依次查找，直到找到哈希表中的空位，将关键字存入。探测方法包括线性探测（Linear Probing）、二次探测（Quadratic Probing）、双重哈希（Double hashing）等。最常用的是线性探测。

比如我们要存入一组关键字{10,12,13,14,22,21}，哈希函数采用除留取余法，除数为7，余数分别是{3,5,6,0,1,0}，我们发现有两个0，存在冲突，先进入的14占据了0位置，21不能再用这个位置。线性探测的过程如下图所示：

可以用Java简单地模拟一下这个过程，数组模拟哈希表，数组的索引模拟地址。

package com.notes.data_structure7;public class LinearProbing {public static void main(String[] args) {// 模拟 哈希表 的数组int[] table = new int[7];// 要存入的关键字int[] keys = {10,12,13,14,22,21};for(int i=0;i<keys.length;i++) {int key = keys[i];int addr = get_addr(key);if(table[addr]==0) { // 无哈希冲突table[addr] = key;}else { // 有哈希冲突int current_addr = addr;a:for(int j=0;j<table.length;j++) {current_addr++;if(current_addr==table.length) {current_addr=0;}if(table[current_addr]==0) { // 无哈希冲突table[current_addr] = key;break a;}}}}// 打印表for(int i=0;i<table.length;i++) {System.out.println("addr:"+i+",key:"+table[i]);}}// 哈希函数static public int get_addr(int key) {return key%7;}}

打印结果下，key值为0表示位置为空。

addr:0,key:14addr:1,key:22addr:2,key:21addr:3,key:10addr:4,key:0addr:5,key:12addr:6,key:13

线性探测也是有局限性的，加入的值越多，发生哈希冲突的可能性就越大，哈希表的性能就越差。比如上面的关键字21因为哈希冲突被调到了地址2的位置，如果再加一个关键字为23，经哈希函数计算地址为2，又与21发生哈希冲突，不得不再次线性探测。

为了弥补上述缺陷，又出现了二次探测、双重哈希等改进方法。二次探测在线性探测基础上增加了地址跳转的跨度，那上面的代码来说，线性探测的次序是current_addr+1,+2,+3，二次探测次序是current_addr+1,+4,+9。双重哈希是预设多个的哈希函数，一个发生冲突，就换一个，直到不冲突为止。

2.2.2 链表法

链表法的思路是，哈希表的每一个槽(slot)都是一个链表，哈希函数计算的是槽位，将值根据相应的槽位存入对应的链表，这种解决方法比开放地址法要更加方便。

同样用Java模拟这个方法，该方法相比于开放地址法，省去判断是否有哈希冲突和遍历寻址的操作。链表的代码复用“数据结构学习笔记”系列的第一篇文章“链表”的代码，链接贴在下面：

/weixin_45370422/article/details/116573863

Java代码模拟的结果呈现方式是：由于链表里定义的打印结点的方法是不换行打印，因此不同的槽位用空行隔开，空位直接打印“空槽”两个字。

package com.notes.data_structure7;public class Chaining {public static void main(String[] args) {// 模拟 哈希表 的数组，表槽（slot）的数据类型是链表MyLink[] table = new MyLink[7];// 要存入的关键字int[] keys = {10,12,13,14,22,21};for(int i=0;i<keys.length;i++) {int key = keys[i];int addr = get_addr(key);if(table[addr]==null) {table[addr] = new MyLink();}table[addr].addNode(key);}// 打印表（链表的结点值打印不换行，不同的表槽用空行隔开，空位直接打印空槽）for(int i=0;i<table.length;i++) {MyLink link = table[i];try {link.printLink();System.out.println();} catch(NullPointerException e) {System.out.println("空槽");System.out.println();}}}// 哈希函数static public int get_addr(int key) {return key%7;}}

打印结果：

142122空槽10空槽1213