数据结构与算法(二)

上一节讲了数组、链表、栈、队列的数据结构，详情请见数据结构与算法(一)。这一节要讲的是散列表。我举个例子，假设我们班有54个学生，现在要对这些学生进行编号，编号规则为4位数组，比如0236，其中02为班级号，36为学生编号。那我们怎么做呢？

我们可以截取编号的后两位，即1-54。把编号为 1 的学生放到数组中下标为 1 的位置；编号为 2 的学生放到数组中下标为 2 的位置。以此类推，编号为 k 的学生放到数组中下标为 k 的位置。这样编号与下标一一对应，当我们要获取编号为x的学生，只需要将数组下标为x的数据取出来就好啦，根据之前学习的知识，可知时间复杂度为O(1)。

散列表

上例中将编号截取后两位存放在数组中，就是运用了散列表的思想。学生的编号叫做键(key)或关键字，用来标示一名学生。将编号转换为下标的映射方法叫做散列函数，而经散列函数得到的值叫做散列值或Hash值。

散列表用的就是数组支持按照下标随机访问时，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

散列函数

散列函数是散列的关键，它是一个函数，定义为hash(key)，其中key表示元素键值，hash(key) 的值表示经过散列函数计算得到的散列值。

那么上例中，写成散列函数比较简单，应该是这样：

int hash(String key) {
  // 获取后两位字符
  string lastTwoChars = key.substr(length-2, length);
  // 将后两位字符转换为整数
  int hashValue = Integer.parseInt(lastTwoChars);
  return hashValue;
}

那么一个散列函数应该满足什么样的基本要求呢？

• 散列函数计算得到的散列值是一个非负整数：因为数组下标是从 0 开始的，所以散列函数生成的散列值也要是非负整数
• 如果 key1 = key2，那 hash(key1) == hash(key2)：相同的 key，经过散列函数得到的散列值也应该是相同的。
• 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)：存在在理想状态下，真实的情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的。因为数组容量有限，所以存在不同的 key 对应的散列值一样，这就是散列冲突

如何解决散列冲突

开放寻执法

如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。那如何重新探测新的位置呢？这里讲3种方法

线性探测

当往散列表中插入数据时，如果该数据经过散列函数散列之后，散列值的位置已经被占用了，我们就从当前位置开始，依次往后查找，直到找到空闲位置为止。

插入

从图中可以看出，散列表的大小为 10，在元素 x 插入散列表之前，已经 6 个元素插入到散列表中。x 经过 Hash 算法之后，被散列到位置下标为 7 的位置，但是这个位置已经有数据了，所以就产生了冲突。于是我们就顺序地往后一个一个找，看有没有空闲的位置，遍历到尾部都没有找到空闲的位置，于是我们再从表头开始找，直到找到空闲位置 2，于是将其插入到这个位置。

查找

通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。

删除

将删除的元素，特殊标记为 deleted，而不能单纯地把要删除的元素设置为空。当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。

这是因为在查找的时候，如果通过线性探测方法，找到一个空闲位置，就认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。

二次探测

和线性探测很像，而二次探测探测的步长变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0，hash(key)+12，hash(key)+22……

双重散列

使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

不管采用哪种探测方法，当散列表中插入的数据越来越多，散列冲突的概率就会越来越大。我们可以用装载因子（load factor）来尽可能的地保证散列表的操作效率。装载因子越大，空闲位置越少，产生冲突的可能性越大。

装载因子 = 元素个数 / 散列表的长度

链表法

链表法相对更加简单，在散列表中，每个数组位置，或者叫做桶，对应一条链表，所有Hash值相同的元素就放在对应桶的链表中。

不难看出，当插入时，只需通过散列函数计算出对散列值，将其插入到对应散列值的链表中，所以插入的时间复杂度是 O(1)；当查找、删除一个元素时，我们同样通过散列函数计算出散列值，然后遍历链表查找或者删除。两个操作的时间复杂度跟链表的长度 k 成正比，也就是 O(k)。

如何设计散列表

根据以上的内容，我们知道理想状态下，没有散列冲突时，散列表的查询时间复杂度是 O(1)。但是在实际工作中，由于散列函数和装载因子设计得不好，散列冲突的可能性大大增加，导致查询效率降低。甚至有些恶意攻击者设计好数据，使得散列后，都散列在同一个桶中，这样散列表就退化为链表，查询时间复杂度变为O(n)。那么如何设计一个好的散列表，能够在散列冲突的情况下，来避免查询效率的降低呢？可以从以下几点考虑。

设计一个合适的散列函数

• 散列函数设计不能太复杂：如果太复杂，计算会消耗时间，间接影响性能
• 散列函数生成的值要尽可能随机并且均匀分布：避免或最小化散列冲突，即使冲突，每个桶的数据也会尽可能平均。

常见的一些设计方法有直接寻址法、平方取中法、折叠法、随机数法等。

定义装载因子阈值，并且设计动态扩容策略

对于频繁插入和删除的数据集合来说，事先无法确定要插入的数据个数，所以无法事先申请一个固定大小的散列表，随着插入数据越来越多，装载因子慢慢变大，散列表的空闲位置越来越少，发生散列冲突的概率就越大。那这种情况该如何处理呢？

考虑动态扩容，当装载因子过大时，我们也可以进行动态扩容，重新申请一个更大的散列表，通过散列函数重新计算每个数据的存储位置，将数据搬移到这个新散列表中。

插入一个数据，最好情况下，不需要扩容，最好时间复杂度是 O(1)。最坏情况下，启动扩容，重新申请内存空间，重新计算哈希位置，并且搬移数据，所以时间复杂度是 O(n)。均摊时间复杂度接近最好情况是 O(1)。

进行扩容时的装载因子应当设置一个阈值，当装载因子超过这个阈值时，就应该启动扩容，但是需要设置得当。如果太大，会导致冲突过多；如果太小，会导致内存浪费严重。实际工作中，要权衡时间、空间复杂度来设置装载因子的值。

选择合适的散列冲突解决方法

开放寻执法

优点

• 所有数据存储在数组中，查询速度快
• 易于序列化

缺点

• 删除数据麻烦，需要特殊标记已经删除掉的数据
• 数据都在数组中，冲突代码更高

链表法

优点

• 内存利用率更高：因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好
• 链表法对大装载因子的容忍度更高，开放寻址法只能适用装载因子小于 1 的情况；对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成 10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多

缺点

• 对于比较小的对象的存储，比较消耗内存，因为链表需要存储指针。但是存储的是大对象，那链表中指针的内存（4 个字节或者 8 个字节）消耗在大对象面前就可以忽略了。

实际上，可以链表法改造，可以实现一个更加高效的散列表。那就是，我们将链表法中的链表改造为其他高效的动态数据结构，比如跳表、红黑树。这样时间复杂度是 O(logn)，正如HashMap的实现。

总结

当数据量比较小、装载因子小的时候，适合采用开放寻址法：
当存储大对象、大数据量的散列表，因为它更加灵活，支持更多的优化策略，比如用红黑树代替链表

哈希算法

定义

将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法

优秀的哈希算法的基本要求

• 从哈希值不能反推原始数据
• 对输入数据敏感，原始数据微小变动，哈希值也不同
• 散列冲突的概率要很小
• 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值

哈希算法的应用

安全加密

哈希算法最常用的应用就是安全加密了，最常用于加密的哈希算法是MD5（MD5 消息摘要算法）和 SHA（安全散列算法）。除此之外，还有DES（数据加密标准）、AES（高级加密标准）。

MD5的哈希值是固定的 128 位二进制串，能表示的数据是有限的，最多能表示 2^128 个数据，而我们要哈希的数据是无穷的。基于鸽巢原理，如果有 2^128+1 个数据求哈希值，就必然会出现散列冲突。即便哈希算法存在散列冲突的情况，但是因为哈希值的范围很大，冲突的概率极低，在有限的时间和资源下，哈希算法相对来说还是很难破解的。

唯一标示

如果要在文件夹中，搜索某个文件是否存在，我们一般用文件名来比对搜索。但是如果文件的量很大呢？就可能存在名称相同但图片内容不同，此时不能简单地用文件名称来搜索了，那我们该怎么做呢？

任何文件在计算中都可以表示成二进制码串，我们给每一个文件取一个唯一标识，比如，我们可以从文件的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为文件的唯一标识。

我们把每个文件的唯一标识，和相应的文件在计算机中的路径信息，都存储在散列表中。当要查看某个文件是不是在库中的时候，我们先通过哈希算法对这个文件取唯一标识，然后在散列表中查找是否存在这个唯一标识。

如果不存在，那就说明这个文件不存在；如果存在，我们再通过散列表中存储的文件路径，获取到这个已经存在的文件，跟现在要插入的文件做全量的比对，看是否完全一样。如果一样，就说明已经存在；如果不一样，说明两份文件尽管唯一标识相同，但是并不是相同的文件。

数据校验

比如BT下载，通过哈希算法，对 100 个文件块分别取哈希值，并且保存在种子文件中。哈希算法对数据很敏感，只要文件块的内容有一丁点儿的改变，最后计算出的哈希值就会完全不同。所以，当文件块下载完成之后，我们可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要重新下载。

散列函数

散列函数关注散列后的值是否能平均分布，散列函数执行的快慢，也会影响散列表的性能，所以，散列函数用的散列算法一般都比较简单，比较追求效率。

负载均衡

我们如何在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上呢？
最直接的方法：维护一张映射关系表，表明了客户端IP和服务端编号的映射关系，每次请求时，从映射关系表中找到对应的服务器编号，然后再去对应的服务器请求。但这个方法有两个弊端：1.如果客户端很多，那么映射表会很大，浪费内存；2.客户端的上下线，服务器的扩容缩容都会导致映射失效，维护成本变大。

借助Hash算法：对客户端IP或者会话ID计算哈希值，然后与服务器数量取模，得到的值就是请求的服务器编号。这样，同一次会话中的所有请求都路由到同一个服务器上啦。

数据分片

取唯一标示中的例子，如果文件数很大，达到1个亿，那很显然单机系统内存有限，其上构建散列表不太可能。那就需要对数据分片，在多台机器上处理。我们准备 n 台机器，让每台机器只维护某一部分文件对应的散列表。我们每次读取一个文件，计算唯一标识，然后与机器个数 n 求余取模，得到的值就对应要分配的机器编号，然后将这个文件的唯一标识和文件路径发往对应的机器构建散列表。

当我们要判断一个文件是否存在，通过同样的哈希算法，计算这个文件的唯一标识，然后与机器个数 n 求余取模。假设得到的值是 k，那就去编号 k 的机器构建的散列表中查找。

分布式存储

为了提高数据的读取、写入能力，一般都采用分布式的方式来存储数据，将数据分布在多台机器上。通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。
如果某台机器崩溃或者要增加机器时，需要用到一致性Hash算法。

以上就是数据结构与算法散列表与哈希算法的相关内容啦，喜欢的小伙伴可以关注收藏我的私人博客，这里有你想要的一切哦，兄弟，还等啥呢？