散列表（Hash Table）也叫哈希表，是一种在实际编程过程中被广泛使用的数据结构，但是你是否真的理解它呢？本篇文章将从原理对其进行分析。
散列思想
下面举一个例子，学校举报运动会，长跑项目总共有60名选手参加，对每个选手按照年级+班级+参赛序号的方法进行编号，我们希望利用编程对每个运动员的个人信息进行存储，并能通过编号进行快速查找。
我们采取的办法是，用数组来存储运动员的信息（数组支持时间复杂度为O(1)的随机访问），取每个运动员的编号后两位作为数组对应下标并一一对应，这样子就可以做到按照编号快速查找运动员信息了。比如2年级3班的一名运动员，他的参赛序号是40，所以他的编号就为020340，按照上面的方法，我们就可以在数组下标为40的位置查找到该运动员的信息了。
上面这个例子就是典型的散列思想，运动员的编号为键（key）或关键字，取后两位为数组下标的映射方法就是散列函数（“Hash 函数”或哈希函数），计算出来的值就是散列值（“Hash 值”或哈希值）。
什么是散列冲突
通过上面的介绍我们可以想到，散列函数必须是符合一定特点的，比如：
1、由散列函数计算的散列值应该为非负整数，这是因为数组下标的限制。
2、if k1 = k2，then Hash(k1) = Hash(k2)
3、if k1 ≠ k2，then Hash(k1) ≠ Hash(k2)
着重看一下第三条，在实际情况下，即使是著名的散列函数如（MD5，SHA，CRC）也无法确保不同的键产生相同的散列值，只能做到尽量减少，这种情况称为散列冲突。
如何解决散列冲突
既然散列冲突无法避免，那我们应该如何解决呢，常用的解决方法有两种：开放寻址法(open addressing)与链表法(chain)。
开放寻址法
开放寻址法的原理是当遇到冲突时，重新检测空闲位置，当检测到空位是就进行插入。检测的方法也有多种，这里先以线性探测为例。当冲突发生时，我们从当前位置开始依次往后每次一个单位进行寻找，当找到空闲位置时就进行插入，如果行进到尾部也没有空闲位置时，就从头开始继续寻找。
图1表示这种情况，当插入散列值为2的数据x时，图中橙色表示已被占用的位置。
我们可以思考一下当要对散列表进行查找操作的情况，通过计算出散列值进行查找，第一种情况是数据刚好就在对应位置中，对要查找的数据和“坑“内的数据进行比较，如果相等，那么找到数据。第二种情况，“坑”内的数据不与之相等的，考虑到散列冲突的情况，我们依次往后查找，在遇到空格前找到相等的数据，那么也是查找成功。第三种情况，在查找到对于数据前遍历到了数组的空闲位置，说明散列表中没有要找的数据。
另外我们还要考虑一种情况，当散列表查询之前进行了一次删除操作，留下了空格，我们可能就会在寻找过程中因此判定数据不在散列表中，因此我们需要在删除操作后在空格内进行delete标记，当查找操作时遇到标记过的空格时继续往后寻找。
另外还有两种检查的方法：二次探测（往后探测的步数为k²）和双重散列（往后探测的每一步使用不同的散列函数），这两种方法都能一定程度减少散列冲突。
优点：能通过CPU缓存加快查询速度（因数组在内存中为连续位置便于CPU缓存加载）。序列化较简单。
缺点：删除操作较麻烦，需要进行delete标记。冲突代价更高。
链表法
链表法比起开放寻址法理解起来就简单很多了，同时也更加常用。他的原理是在散列表对应的每个槽中，都对应一条链表，存储散列值相同的数据。
优点：因为采用的是链表，所以对内存利用率较高。对大装载因子（装载因子=填入表中的元素个数/散列表长度）容忍度较高。
缺点：使用链表，对cpu缓存不友好。
如何设计散列表
那么散列表的查询时间复杂度是多少呢？你可能会说，我们可以计算散列值直接找到对应的数据，因此为O(1)。其实不然，散列表的查询时间复杂度会受散列函数、散列冲突等影响，在极端情况下比如采取链表法解决冲突时，散列表会退化为链表，时间复杂度也退化为O(n)。跟着以下几个问题，我们一起来思考如何设计一个散列表。
设计散列函数的原则
1、散列函数不能太复杂。因为复杂度散列函数会使计算量增大，计算时间影响变大。
2、散列函数生成的散列值要尽量均匀分布。这样可以减少散列冲突的可能。
常用的设计方法有：直接寻址法、平方取中法、折叠法，随机数等，作了解即可。
装载因子过大时进行动态扩容的原则
上面我们提到装载因子=填入表中的元素个数/散列表长度。当装载因子过大也就是散列表将慢时，我们需要进行动态扩容。
散列表的扩容不同于数组，散列表的数据搬移需要重新计算散列值，元素在散列表中的位置会发生变化，因为散列表的大小变化可能会影响散列值（与散列函数有关）。进行一次动态扩容的时间复杂度为O(n)，因为我们需要对已有的n个元素进行搬移操作。而当一次扩容操作发生在插入操作过程中时（需要进行插入操作时散列表装载因子过高需要先进行扩容），这样的一次插入操作时间复杂度就从O(1)变为O(n)。
那么我们如何避免这种情况呢？我们采取将一次性搬移操作改为分次搬移的操作，每插入一个元素伴随着搬移一个元素的操作，这样子，我们就把时间复杂度为O(n)的插入操作进行分摊，避免了低效扩容。所以我们在进行查找元素时为了兼容两个新老散列表，先查找新的散列表，若未找到，再查找旧的散列表。
你可能会有一个问题：那到底何时进行动态扩容？这应该权衡时间与空间复杂度，当对查找效率要求较高时，我们应该降低装载因子到达动态扩容的阈值；当内存空间较紧张和对查找效率要求不高时，可以适当增加阈值。
如何选择冲突解决算法
上面在介绍冲突解决方法时已经分别分析了对应的优缺点，我们要权衡实际情况进行选择。
上面我们通过几个问题的引入介绍了散列表的原理以及设计原则，你可以结合熟悉的编程语言中对散列表的实现（如Java的HashMap）进行加深学习。本文是学习王争老师的《数据结构与算法之美》所作的学习笔记，如有错误请指出，谢谢！