- 01.了解散列思想
- 02.什么是散列函数
- 03.解决散列冲突
- 散列表的英文叫“Hash Table”，我们平常也叫它“哈希表”或者“Hash 表”。它是用数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
- 【举例1】
- 假设有89名运动员参加校运动会。每个运动选手都会有自己的参赛编号，假设参赛编号就是1~89。那么如何存储数据，实现通过编号快速查找到对应选手的信息呢？
- 将这89名选手的信息放在数组里，编号为1的选手放在数组下标为1的位置，编号为k的选手放在下标为k的位置。因为参赛编号和数组下标一一对应，当我们要查询参赛编号为x的选手信息时，只需要将下标为x的数组元素取出来即可，时间复杂度是O(1)。
- 【举例2】
- 假设89名运动员的编号是一个6位数，例如051167，其中05表示年级，11表示班级，67表示1~89中的第67号。那么针对这样的编号，如何存储选手信息，才能够支持通过编号来快速查找选手信息呢？
- 想法就是截取编号的最后两位作为数组下标，这样编号跟数组下标仍然是一一对应，能够达到查找目的。
- 总结：
- 上面两个例子中体现的就是典型的散列思想。参赛选手的编号叫作键（key）或者是关键字，用以来标识一个选手。把参赛编号转化为数组下标的映射方法叫作散列函数（或者“Hash函数”“哈希函数”），而散列函数计算得到的值叫作散列值（“Hash值”“哈希值”）。下图对上述概念做了直观的图形展示。
image- 散列表用的就是数组支持按下标随机访问的时候，时间复杂度是O(1)的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，用同样的散列函数，将键值转化为数组的下标，从数组中取出对应的数据。
- 散列
- 散列使用一个散列函数，将一个键映射到一个索引上。先回顾一下映射表(map)又称字典(dictionary)、散列表(hash table)或者关联数组(associate array)，是一种使用散列实现的数据结构，用来存取条目的容器对象。
- Java合集框架定义了java.util.Map接口来对映射表建模，三个具体实现类为java.util.HashMap(散列实现)、java.util.LinkedHashMap(使用LinkedList)、java.util.TreeMap(使用红黑树)。
- 存储了值的数组称为散列表(hash table)，将键映射到散列表中的索引上的函数称为散列函数(hash function)。散列(hashing)是一种无需进行搜素，即可通过从键得到的索引来获取值的技术。
- 从上面的例子，可以看出，散列函数在散列表中起着非常关键的作用。
- 可以把它定义与hash(key)，其中key表示元素的键值，hash(key)的值表示经过散列函数计算后得到的散列值。
- 如何构造散列函数呢？总结了三点基本要求：
- 散列函数计算得到的散列值是一个非负整数
- 如果 key1 = key2，那么 hash(key1) == hash(key2);
- 如果 key1 ≠ key2，那么 hash(key1) ≠ hash(key2);
- 第三点理解起来可能会有问题，这个要求看起来合情合理，但在真实的情况下，几乎是不可能的。即便是业界著名的 MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。而且，因为数组有存储空间有限，也会加入散列冲突的概率。
- 所以几乎无法找到一个完美的无冲突的散列函数，即便能找到，付出的时间成本、计算成本也是很大的，针对散列冲突问题，我们需要通过其他途径来解决。
- 再好的散列函数也无法避免散列冲突。常用的两种解决散列冲突的方法是：开放寻址法（open addressing）和链表法（chaining）。
- 开放寻址法包含三种比较经典的探测方法。
- 线性探测（hash(key)+0，hash(key)+1，.....）
- 二次探测（hash(key)+0，hash(key)+，hash(key)+，.....）
- 双重探测（hash1(key)，hash2(key)，......）
- 以线性探测为例，进行详细说明。
- 线性探测：当我们往散列表中插入数据时，如果某个数据经过散列函数散列以后，存储位置已经被占用了，就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。举个例子说明如下：
image- 如图的散列表是大小为10，已经有6个元素（橙色表示已插入数据）插入到散列表当中。x经过散列函数，被散列到下标为7的位置，但是下标为7的位置已经被占用，然后就从7依次往后查找空闲位置，遍历到结尾还是没找到，就从表头开始寻找，直到找到空闲位置2，将其插入。
- 【查找操作】：在散列表中查找元素与上述的插入操作很类似。首先是通过散列函数找到对应查找元素的散列值，然后对比数组中下标为散列值的元素与要查找的元素。如果相等，说明就是要查找的元素；如果不等，就顺序往后依次查找，如果遍历到数组中的空闲位置还没有找到，说明要查找的元素并没有在散列表当中。
image
- 【删除操作】：对于线性探测法解决散列冲突的散列表，删除操作不能简单地把要删除的元素设置为空，因为这样的操作会影响到查找操作的结果。查找操作中如果找到空闲位置，就会认为要查找的元素不存在，如果这个空闲位置是后来删除导致的，会导致原来的算法失效。
image- 解决办法：将要删除的元素给一个特殊的标记为deleted。当线性探测查找的时候，遇到标记为deleted的空间，并不是停下来，而是继续往下探测。
- 【线性探测的缺点】：当散列表中插入的数据越来越多，会导致散列冲突的概率增大，空闲位置越来越少，线性探测的时间就越来越久。最坏情况下，需要探测整张散列表，时间复杂度是O(n)。
- 【二次探测】：二次探测就是将线性探测的步长，变成了原来的“二次方”。
- 【双重探测】：双重探测就是用一组散列函数hash1(key)，hash2(key)...... 来探测空闲位置。
- 不管哪种探测方法，最后当散列表空闲不多的时候，散列冲突的概率就会增大。为了保证散列表的操作效率，会尽量保证散列表中有一定比例的空闲槽位。用装载因子（load factor）来表示空位的多少。散列表的装载因子 = 填入表中的元素个数 / 散列表的长度
- 链表法是一种更加常用散列冲突解决办法，相比开放寻址法，它要简单很多。如下图，在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。
image
- 当插入的时候，我只需要通过散列函数计算出对应散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度O(1)。当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或是删除。
- 实际上，这两个操作的时间复杂度跟链表的长度k成正比，也就是O(k)。对于散列比较均匀的散列函数来说，理论上讲， k=n/m,其中n 表示散列中数据的个数，m表散列表中“槽”的个数。
