数据结构与算法——散列表

1. 什么是散列表？

散列表（Hash Table）又叫做哈希表，是一种很常用的数据结构。散列表其实是基于数组实现的，可以说，没有数组就没有散列表。先来举一个简单的例子，来认识一下什么是散列表。

假如在学校的运动会上，每个运动员的胸前都会标识自己的号码，编号是1，2，3……，这样的话，我们可以很容易的将运动员信息存储在数组当中，运动员的编号就是数组的下标。但是会存在这样一种情况，假如运动员的编号不是顺序排列的，而是需要加上更多的信息，比如年级，班级，例如一个运动员的编号是15030711，15是年级，03是专业，07是班级，11是顺序号，这样的话我们该怎么存储运动员信息呢？

其实也不难，我们只需要截取运动员编号的最后两位，作为数组的下标存储在数组中，当需要根据编号查询信息的时候，我们也同样截取编号最后两位来进行查询。这就是很典型的散列思想。

选手的编号叫做 键 ， 把运动员编号转换为数组下标的方法叫做 散列函数（或哈希函数）， 通过散列函数计算得到的值叫做 散列值（或哈希值） 。

根据下图你更能理解散列表：

2. 哈希函数

结合上面的理解，你应该可以想到，其实散列表的关键就在于哈希函数的实现。哈希函数，顾名思义，其实就是一个函数，key 就是键值，经过 hash(key) 得到的值就是哈希值。

哈希函数的设计有三个原则：

• 通过哈希函数计算得到的哈希值是一个非负的整数。
• 如果 key1 = key2，那么 hash(key1) = hash(key2)。
• 如果 key1 != key2，那么 hash(key1) != hash(key2)。

前面两点其实很好理解，第一点，要求是一个非负的整数，这是因为数组的下标是从 0 开始的，第二点，如果 key 相同，那么通过哈希函数得到的哈希值也相同。

第三点稍微有点不好理解，key1 不等于 key2，那么哈希值也是不相等的，这只是一种理想的状况，但是在实际情况中，无法避免这种哈希冲突 。

3. 哈希冲突

哈希冲突，又叫哈希碰撞，是哈希函数可能会遇到的问题，即不同的 key 值经过哈希函数计算之后，可能得到相同的哈希值，那么这种状况该怎么解决呢？一般是通过两种方式：

1. 开放寻址法
2. 链表法

开放寻址法可以通过线性探测这种方式来实现，比如我们的一个 key 经过哈希函数得到哈希值之后，相应的存储位置已经被占用，那么我们遍历散列表，找到一个空闲的位置，将数据插入。

例如下图，标记为黄色的是已经有数据，标记为红色的是空闲空间，一个 key 经过 hash 哈希函数之后的存储位置为 2，但是下标为 2 的的地方已经有数据了，所以就重新探测一个空的位置。

第二种方式是链表法，这种方式会更加简单，也更加适用。例如下图，在每一存储位置，都会有相应的链表，如果哈希值相同，我们直接将数据存放在存储位置对应的链表中。

但是这种方式也可能会存在问题，比如说哈希函数设计的不合理，导致大量的数据都集中在一条链表中，这样的话，数据的插入和查找速度就会急剧退化为O(n)。针对这种情况，我们可以使用更加优秀的动态数据结构代替链表，例如红黑树、跳表等。这样，就算数据全都集中在一个节点上，数据的查询效率也不会下降得太厉害。

4. 散列表的具体应用

其实，散列表和链表在很多时候都是结合在一起使用的，接下来就看看散列表的两个具体应用：LRU（最近最少使用策略，Least Recently Used）缓存淘汰算法和 Java 的 LinkedHashMap。

1.LRU 缓存淘汰算法

首先，该怎么理解 LRU，即最近最少使用策略呢？举个简单的例子，比如你买了很多书，书架上渐渐放满了，当你有新的书的时候，需要将原来的书拿掉一些，腾出新的位置来。这样的话，你肯定会拿掉那些最近很少使用到的那些书，这就是一种最近最少使用策略。

其实可以用单链表实现一个LRU缓存淘汰算法，具体可以这样做：我们维护一个有限的缓存空间，如果空间不够，需要淘汰缓存的话，我们直接将链表头部的数据删除即可。当要缓存某个数据的时候，我们需要查找这个数据，如果找到了，将其放置在链表尾部，如果没找到，则将数据插入到链表尾部。因为涉及到的查找操作需要遍历链表，时间复杂度是O(n)，所以我们可以用散列表加上双向链表来实现，将时间复杂度降为O(1)。具体该怎么实现呢？

先来看看下面实现的图：

首先，如果空间不够，我们直接将双向链表头部的元素删除；查找一个元素，我们可以在接近 O(1) 的时间复杂度找到该元素，并且将其插入到链表的尾部；删除一个元素，由于双向链表保存了上一个链表的指针，所以能够在O(1) 的时间内删除；添加一个元素，如果此元素已经在链表中，则直接将该元素插入到链表尾部，如果不在链表中，直接将元素插入到链表尾部，如果缓存满了，则删除链表头部元素之后才添加。

2.LinkedHashMap

如果熟悉 Java 的话，肯定会经常用到 LinkedHashMap 这个容器，它与 HashMap 唯一的区别就是，LinkedHashMap 能够按照插入次序依次遍历得到数据，这个功能是怎么实现的呢？其实和上面的结构图很类似，插入到 HashMap 中的数据用双向链表连接起来，然后按照遍历链表的方法依次得到数据，这样就能够实现有序输出数据了。

好了，散列表就基本上讲完了。