散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算出一个键值的函数，将所需查询的数据映射到表中一个位置来让人访问，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
从上面的定义中，我们得到两个关键信息：
- 散列表本质上是一个数组；
- 散列表的存储结果取决于散列函数；
散列函数（Hash Function）
散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字"指纹"的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。
一个好的散列函数应（近似地）满足简单均匀散列假设：每个关键字都被等可能地散列到 m 个槽位中的任何一个，并与其他关键字已散列到哪个槽位无关。
散列函数的五个特点
- 输入可以任意长度，输出是固定长度；
- 计算hash值的速度比较快（否则无法应用到实际生产的生产环境中）；
- 防碰撞特性（Collisionresistance）（保证上传和下载的数据是一样的）；
- 隐藏性（Hiding）或者叫做单向性（one-way）（即哈希函数的计算过程是单向不可逆的）；
- 谜题友好（puzzlefriendly）（即无法直观的从输入数据判断出输出数据是什么样子的）；
散列函数设计
基本要求
- 散列函数计算得到的散列值是一个非负整数；
- 如果 key1 = key2，那 hash(key1) == hash(key2)；
- 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。
几种设计方法
- 直接寻址法。取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）
- 数字分析法。分析一组数据，找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
- 平方取中法。取关键字平方后的中间几位作为散列地址。
- 折叠法。将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
- 随机数法。选择一随机函数，取关键字作为随机函数的种子生成随机值作为散列地址，通常用于关键字长度不同的场合。
- 除留余数法（除法散列法）。取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生碰撞。
常见的散列算法
- MD5: MD5消息摘要算法（英语：MD5 Message-Digest Algorithm），一种被广泛使用的密码散列函数，可以产生出一个128位（16个字符(BYTES)）的散列值（hash value），用于确保信息传输完整一致。MD5由美国密码学家罗纳德·李维斯特（Ronald Linn Rivest）设计，于1992年公开，用以取代 MD4 算法。这套算法的程序在 RFC 1321 中被加以规范。将数据（如一段文字）运算变为另一固定长度值，是散列算法的基础原理。1996年后被证实存在弱点，可以被加以破解，对于需要高度安全性的资料，专家一般建议改用其他算法，如SHA-2。2004年，证实MD5算法无法防止碰撞攻击，因此不适用于安全性认证，如SSL公开密钥认证或是数字签名等用途。
- SHA 家族：安全散列算法（英语：Secure Hash Algorithm，缩写为SHA）是一个密码散列函数家族，是 FIPS 所认证的安全散列算法。能计算出一个数字消息所对应到的，长度固定的字符串（又称消息摘要）的算法。且若输入的消息不同，它们对应到不同字符串的几率很高。
- RIPEMD：RIPEMD（RACE原始完整性校验讯息摘要）是一种加密哈希函数，由鲁汶大学 Hans Dobbertin,Antoon Bosselaers 和 Bart Prenee 组成的 COSIC 研究小组发布于1996年。 RIPEMD是以 MD4 为基础原则所设计的 ，而且其表现与更有名的SHA-1类似。
常见用途
- 安全加密
- 唯一标识
- 数据校验
- 散列函数
- 负载均衡
- 数据分片
- 分布式存储
- 网络协议中的 CRC 校验
- Git Commit ID
如何解决散列冲突
在使用散列函数时，两个不同的关键字可能映射到同一个槽中，我们称这种情形为冲突（Collision）。由于不存在完美的无冲突的散列函数，或者说完美的散列函数成本过高，我们需要考虑散列冲突时的解决方案。常用的解决方案有两类，分别是开放寻址法（open addressing）和链表法（chaining）。
开发寻址法
开放寻址法的核心思想是，如果出现了散列冲突，就重新探测一个空闲位置，将其插入。那如何重新探测新的位置呢？
- 线性探测（Linear Probing）：如果某个数据经过散列函数散列之后，存储位置已经被占用了，就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。这种方式的缺点是散列表的最坏情况下的时间复杂度为 O(n)。
- 二次探测（Quadratic probing）：二次探测和线性探测很像，只是二次探测探测的步长变成了原来的“二次方”，即探测的下标序列为 hash(key)+0，hash(key)+12，hash(key)+22……
- 双重散列（Double hashing）：所谓双重散列，意思就是不仅要使用一个散列函数。我们使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。
链表法
链表法的核心思想是在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素都会放到相同槽位对应的链表中。
还有一种解决散列冲突的方法和链表法类似，就是建立一个公共溢出区，用于保存散列冲突的值。
数据结构
- 数组（Array）：适用于数据量小，装载因子小的时候。
- 数组+链表（Array + Linked List）：适用于大数据量，存储大对象，装载因子大的时候。
- 数组+二叉树（Array + Binary Tree）：适用于存储大数据量，当存储的数据为小对象时，相对于链表更加节省内存。
操作
散列表的时间复杂度为 O(1)。
散列表的执行效率和三个因素有关：
- 散列函数是否均匀；
- 处理冲突的方法；
- 散列表的载荷因子（英语：load factor）。
给定一个能存放 n 个元素的、具有 m 个槽位的散列表 T，定义 T 的装载因子（load factor）a 为 n/m，即一个链的平均存储元素数。
- 对于一次不成功的查找，关键字 k 等可能地被散列到 m 个槽中的任何一个，查找的期望时间就是散列函数的执行时间和查找至链表 T[h(k)] 末尾的期望时间，这一时间的期望长度为 a，即一次不成功的查找平均检查 a 个元素。
- 对于一次成功的查找，查找的期望时间一定是小于 a 的，即一次成功的查找平均检查 a-1 个元素。
如果散列表中的槽数至少与表中的元素数成正比，则有 n=O(m)，从而 a=n/m=O(m)/m=O(1)。因此，查找操作平均需要常数时间。当链表采用双向链表时，插入操作在最坏情况下需要 O(1) 时间，删除操作最坏情况下也需要 O(1) 时间，因而，全部的字典操作平均情况下都可以在 O(1) 时间内完成。
动态扩容
为什么要进行扩容？
当散列表的装载因子过大或溢出桶（overflow bucket）过多时，执行效率就会变低，此时就需要扩容。
扩容的策略有哪些？
- 一次性扩容。需要扩容时申请一个 n 倍当前大小的空间，将原来散列表的所有数据全部重新计算散列值，加入到新表中，最后将要插入的新值加入到新表中。这种策略的优点是操作简单，缺点是扩容时效率较低，需要耗时等待。
- ”渐进式“扩容。将扩容过程穿插在插入、修改和删除的过程中。负载达到阈值后，新数据都插入新散列表中并且从原来的散列表取出一个数据插入新表，经过多次插入过程，原散列表中的内容就慢慢的转移到新表中了。这种方式的优点是扩容时无须耗时等待，缺点是扩容时会存在数据冗余（新表和旧表同时存在）。
- 等量扩容。这种情况的发生并不是装载因子过大造成的，而是溢出桶（overflow bucket）过多造成的，此时，装载因子并不大，只是由于插入散列表的 key 相同，导致所有的值落入一个 bucket 中，此时整个哈希表就退化成为一个链表了。这时的解决方案是将原有的 key/value 重新搬移到新的散列表中，重新计算 key 的值后，分配新的 bucket。
位图（BitMap）
一种数据结构，代表了有限域中的稠集（dense set），每一个元素至少出现一次，没有其他的数据和元素相关联。在索引，数据压缩等方面有广泛应用，比如 Linux 内核（如 inode，磁盘块）、Bloom Filter 算法等，其优势是可以在一个非常高的空间利用率下保存大量 0-1 状态。
BitMap 的基本原理就是用一个bit 位来存放某种状态，在特定场景下能够极大的节省存储空间，非常适合对海量数据的查找，判重，删除等问题的处理。
参考资料
- 维基百科
- 《算法导论》第三版 殷建平 等译
- 极客时间《数据结构与算法之美》王争
- Go 语言问题集
