哈希，哈希函数，散列表，你知多少？

哈希，哈希函数，散列表，他们之间有密切的关系，但是很多不懂的小白会搞混他们分别是干什么的，下面分别说一下他们的作用和特点

首先说的是哈希，哈希是密码学的基础，理解哈希是理解数字签名和加密通信等技术的必要前提。
哈希，英文是 hash ，本来意思是”切碎并搅拌“，有一种食物就叫 Hash ，就是把食材切碎并搅拌一下做成的。哈希函数的运算结果就是哈希值，通常简称为哈希。哈希函数有时候也翻译做散列函数。
用图来画一下哈希与哈希函数的关系

那现在你大概的了解了哈希与哈希函数的关系，那么，哈希函数到底是做了什么处理之后生成的哈希呢？

哈希函数要做的事情是给一个任意大小的数据生成出一个固定长度的数据，作为它的映射。所谓映射就是一一对应。

哈希的独一无二性，保证了如果数据在存储或者传输过程中有丝毫损坏，那么它的哈希就会变。哈希函数的最常见的一个作用就是进行完整性校验（ Integrity Check ），完整的意思是数据无损坏。哈希有很多不同的称呼，有时候叫 Digest 摘要，有时候叫 Checksum 校验值，有时候叫 Fingerprint 指纹，其实说的意思差不多，也就是说哈希可以用来代表数据本身。

知道了哈希函数，那我们就想到了，这样的函数，到底会采用什么样的算法去计算呢？

首先计算哈希函数的算法叫哈希算法。
一个可靠的哈希算法要满足三点：
第一是安全，给定数据 M 容易算出哈希值 X ，而给定 X 不能算出 M ，或者说哈希算法应该是一个单向算法。
第二是独一无二，两个不同的数据，要拥有不相同的哈希。
第三是长度固定，给定一种哈希算法，不管输入是多大的数据，输出长度都是固定的。

下一步我们更细致的聊聊哈希算法的特点。

首先说哈希算法有很多种，例如 md5 ，sha256 等等，但是它们总体上可以分为两大类，一类是普通哈希，另外一类是加密哈希，cryptographic hash function 。
业界可以找到的哈希算法是有很多种的。我们可以大致按照输出的哈希的长度来聊，虽然哈希算法的安全性也不单单是跟哈希长度有关，但是一般哈希值越长也就是越安全。

例如 CRC-32 的输出是32 bit，也就是32位的二进制数，表示成十六进制就是8位。
MD5 算法的哈希是32位16进制数，比较常见。
SHA-256是256个 Bit ，十六进制表示就是64位。

那我们怎么区分一个哈希算法是普通哈希还是加密哈希呢？

两种算法之间没有特别明显的区别。
例如本来 MD5 就是设计出来做加密哈希的，但是后来由于计算机的发展 MD5 出现碰撞的可能性就很大了，所以目前 MD5 只能当普通哈希用，用来做数据校验。

加密哈希跟普通哈希的区别就是安全性，一般原则是只要一种哈希算法出现过碰撞，就会不被推荐成为加密哈希了，只有安全度高的哈希算法才能用作加密哈希。

这里提到了碰撞，顺便我们就在来说一下什么是哈希碰撞

我们仔细想一下，之前我们说过哈希函数计算出来的哈希值长度是固定，如果哈希的长度是固定的，也就是取值范围是有限的，而输入数据的取值范围是无限的，所以总会找到两个不同的输入拥有相同的哈希。所以，哈希函数的安全性肯定是个相对概念。如果出现了两个不同输入有相同输出的情况，就叫碰撞，collision 。不同的哈希算法，哈希位数越多，也就基本意味着安全级别越高，或者说它的”抗碰撞性“就越好。

那么一个是不是计算出位数越长的哈希算法，是不是越好呢？

当然不是，加密哈希其实也能当普通哈希来用，Git 版本控制工具就是用 SHA-1 这个加密哈希算法来做完整性校验的。一般来讲越安全的哈希算法，处理速度也就越慢，所以并不是所有的场合都适合用加密哈希来替代普通哈希。总之，哈希算法有很多种，长度越长的算法基本认为越安全。安全度低的哈希算法被认为是普通哈希算法，主要用来做完整性校验。安全度高的被称为加密哈希算***被用在加密算法中。所谓的高低都是相对概念，例如 MD5 曾经属于加密哈希，但是目前只能用来做安全校验了。而从2017年开始，SHA-1 算法生成的加密证书也会被各大浏览器拒绝了。目前最流行的加密算法是 SHA-2 ，但是跟 SHA-1 不同，SHA-2 不是一种算法，而是一系列算法的统称，其中就包括咱们之前提过的 SHA-256 。

说完了哈希函数，了解了哈希，我们下面来说一下散列表

散列表，又叫哈希表（Hash Table），是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。也就是说，把关键字映射到一个表中的位置来直接访问记录，以加快访问速度。一种散列存储结构，通过关键字快速定位。

通常，我们把这个关键字称为 Key，把对应的记录称为 Value，所以也可以说是通过 Key 访问一个映射表来得到 Value 的地址。而这个映射表，也叫作散列函数或者哈希函数，存放记录的数组叫作散列表。

散列表就像我们生活中的查字典，先查找到首字母，再去查拼音。

散列表既然是用的哈希函数，那必然就有一个哈希碰撞的问题

有时不同的 Key 通过哈希函数可能会得到相同的地址，这在我们操作时可能会对数据造成覆盖、丢失。之所以产生冲突是由于哈希函数有时对不同的 Key 计算之后获得了相同的地址。

解决对散列表函数产生冲突的处理方式也有很多，下面介绍几种。

开放地址法（也叫开放寻址法）：实际上就是当需要存储值时，对Key哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。
再哈希法：在产生冲突之后，使用关键字的其他部分继续计算地址，如果还是有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。
链地址法：链地址法其实就是对Key通过哈希之后落在同一个地址上的值，做一个链表。其实在很多高级语言的实现当中，也是使用这种方式处理冲突的，我们会在后面着重学习这种方式。
建立一个公共溢出区：这种方式是建立一个公共溢出区，当地址存在冲突时，把新的地址放在公共溢出区里。

那怎么样设计一个好的散列表呢

一个好的散列表设计，除了需要选择一个性能较好的哈希函数，否则冲突是无法避免的，所以通常还需要有一个好的冲突处理方式。这里我们选择除留取余法作为哈希函数，选择链地址法作为冲突处理方式。
具体的就是下图的存储结构

散列表有两种用法：一种是 Key 的值与 Value 的值一样，一般我们称这种情况的结构为 Set（集合）；而如果 Key 和 Value 所对应的内容不一样时，那么我们称这种情况为 Map，也就是人们俗称的键值对集合。（HashSet,HashMap）

根据散列表的存储结构，我们可以得出散列表的以下特点。

访问速度很快
由于散列表有散列函数，可以将指定的 Key 都映射到一个地址上，所以在访问一个 Key（键）对应的 Value（值）时，根本不需要一个一个地进行查找，可以直接跳到那个地址。所以我们在对散列表进行添加、删除、修改、查找等任何操作时，速度都很快。
需要额外的空间
首先，散列表实际上是存不满的，如果一个散列表刚好能够存满，那么肯定是个巧合。而且当散列表中元素的使用率越来越高时，性能会下降，所以一般会选择扩容来解决这个问题。另外，如果有冲突的话，则也是需要额外的空间去存储的，比如链地址法，不但需要额外的空间，甚至需要使用其他数据结构。这个特点有个很常用的词可以表达，叫作“空间换时间”，在大多数时候，对于算法的实现，为了能够有更好的性能，往往会考虑牺牲些空间，让算法能够更快些。
无序
散列表还有一个非常明显的特点，那就是无序。为了能够更快地访问元素，散列表是根据散列函数直接找到存储地址的，这样我们的访问速度就能够更快，但是对于有序访问却没有办法应对。
可能会产生碰撞
没有完美的散列函数，无论如何总会产生冲突，这时就需要采用冲突解决方案，这也使散列表更加复杂。通常在不同的高级语言的实现中，对于冲突的解决方案不一定一样。