算法原理系列：散列表
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434848
散列表
在刷题的时候散列表用的蛮多，刚好在《算法》查找章节中有它的介绍，就拿过来梳理梳理。之前讲的二分查找也好，二叉搜索树也好都是基于key值的有序性来搜索答案的，而散列表则是一个无序的数据结构。令人神奇的事，无序结构的查找性能能够维持在常数级别。
结构缘由
在理解散列之前，先来看看最快的键值对查找结构是什么？最原始的数据结构我能想到的就是数组，如int[] nums = {1,2,3,4,5,6};，根据下标，我们能直接找出任何想要的数nums[i]，而此时键值对是<i,nums[i]>，这很容易理解，下标当作nums[i]的唯一键，但在实际很多的应用场景中的key是什么样的？
如按照学号，查找学生的姓名<1631577 lisi>,<1631437 zhangsan>，很大的问题在于key的值并无规律可循，key也不一定是整数吧，可以是字符串，甚至可以由多个key组成一个唯一主键。那么问题来了，这能否想办法映射到一个连续的内存空间中去，并加快查找呢？
像这种情况，假如内存足够大，我们完全可以用一个String[] map = new String[2000000]来把它们存进来，所以有：
map[1631577] = "lisi;"
map[1631437] = "zhangsan;"
你能很快发现问题，当我们只有两个值需要存时，却需要开辟2000000的内存空间，这是相当不划算的，所以假如我们能找到一个映射使得，
1631577 - > 0
1631437 - > 1
如果你能找到它，那么事情就变得很容易了。所以我们可以简单的构建一种函数如：
f(x)={0,x>16315001,x≤1631500
f(x)= \begin{cases} 0, x \gt 1631500 \ 1, x \le 1631500 \ \end{cases}
所以，我们只要定义一个映射函数，把它们的键值映射过去就完事了。
public int hashCode(int key){
if ( key > 1631500) return 0;
else{
return 1;
}
}但又发现问题了，如果我再加入一个键值对时，如<1631588,wangwu>，此时它们都同时映射到了0，那就意味着必须针对这种情况做冲突处理。所以，从以上两点，你能总结出两个性质：
- 第一，散列表是典型的用空间来换时间的数据结构，如果内存无限大，有时你甚至可以不用对键做映射处理，只需要一次查找就能找到对应的value。
- 第二，映射函数是为了寻找键与数组下标的关系，使得查找转换成在该数组范围内的索引0,M-1，可分配的数组大小为M。
存在两个问题，映射函数怎么找，以及对应的键求得的映射值相同时，该如何处理。
映射函数的寻找
为什么说散列表是空间换时间？现在给你10000条数据，我要让你映射到数组大小为10000的索引当中去，最理想的情况就是每个键经过映射都能唯一的对应一个下标。那么，每次查找，只要我们的映射函数算法性能和数据大小无关，一次查找操作就能完成。
继续给你10000条数据，把数组开辟的大小改一改，映射到数组大小为500的索引当中去，此时你会发现，为了让查找的平均性能最好，不管怎么塞这些数据，每个位置塞20条数据是最理想的，而此时你需要的查找次数为20次，查找时间明显比之前多了20倍。
所以说，散列表是空间换时间的典型数据结构，它为了性能最佳，需权衡空间的分配。
在上面的分析中，引出了一个性能最优的假设，这为我们衡量映射函数的好坏提供了标准。
假设J：我们使用的散列函数能够均匀并独立地将所有的键分布于0到M-1之间。
关于映射函数有很多种做法，参考博文【散列表的基本概念及其运算】
- 直接定址法 取关键字或关键字的某个线性函数值为散列地址，如
h(key) = key;
h(key) = a * key + b; 其中a和b为常数- 数字分析法（针对具体场景具体分析）
- 平方取值法 取关键字平方后的中间几位为散列地址。
- 折叠法 将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列地址。
- 除留余数法 取关键字被某个不大于散列表长m的数p除后所得的余数为散列地址，即：
h(key) = key mod p, p <= m- 随机数法 选取一个随机函数，取关键字的随机函数值为它的散列地址，即：
h(key) = random(key);在实际操作中，我们不需要为每个类定义一个hash函数，在Java中，Object中有一个hashCode()的方法，使得所有的子类能够继承它。所以，当我们定义一个key类时，我们只需要重写它的hashCode()方法即可。
冲突检测拉链法
冲突检测常用的手段有两种，一种是拉链法，一种是线性探测法。拉链法是数组与链表的结合，简单来说，当存在相同的hash值时，它们就会被存在相同的链表中，而链表的键值对插入可以拿之前实现过的SequentialSearchST来存储，所以它的一个基本代码形式为：
private SequentialSearchST<Key, Value>[] st = new SequentialSearchST<Key, Value>[capacity];
所以我们有了如下初始化代码：
public class SeparateChainingHashST<Key, Value> {
private static final int INIT_CAPACITY = 4;
private int n; //number of key-value pair
private int m; // hash table size
private SequentialSearchST<Key, Value>[] st;
public SeparateChainingHashST() {
this(INIT_CAPACITY);
}
public SeparateChainingHashST(int m){
this. m = m;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[m];
for (int i = 0; i < m; i++)
st[i] = new SequentialSearchST<Key, Value>();
}
}put操作
public void put(Key key, Value val) {
if (key == null) throw new IllegalArgumentException("first argument to put() is null");
if (val == null) {
delete(key);
return;
}
// double table size if average length of list >= 10
if (n >= 10*m) resize(2*m);
int i = hash(key);
if (!st[i].contains(key)) n++;
st[i].put(key, val);
} get操作
public Value get(Key key) {
if (key == null) throw new IllegalArgumentException("argument to get() is null");
int i = hash(key);
return st[i].get(key);
}很清楚，也很简单没什么好说的，直接跳过。在实现基于拉链法的散列表时，我们的目标是选择适当的数组大小M，既不会因为空链表而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。而拉链法的一个好处就是这并不是关键性的选择。
冲突检测线性探测法
开放地址散列表中最简单的方法叫做线性探测法：当碰撞发生时（当一个键的散列值已经被另一个不同的键占用），我们直接检查散列表中的下一个位置（将索引值加1）。
初始化
public class LinearProbingHashST<Key, Value> {
private static final int INIT_CAPACITY = 4;
private int n; // number of key-value pairs in the symbol table
private int m; // size of linear probing table
private Key[] keys; // the keys
private Value[] vals; // the values
/**
* Initializes an empty symbol table.
*/
public LinearProbingHashST() {
this(INIT_CAPACITY);
}
/**
* Initializes an empty symbol table with the specified initial capacity.
*
* @param capacity the initial capacity
*/
public LinearProbingHashST(int capacity) {
m = capacity;
n = 0;
keys = (Key[]) new Object[m];
vals = (Value[]) new Object[m];
}
}put操作
public void put(Key key, Value val) {
if (key == null) throw new IllegalArgumentException("first argument to put() is null");
if (val == null) {
delete(key);
return;
}
// double table size if 50% full
if (n >= m/2) resize(2*m);
int i;
for (i = hash(key); keys[i] != null; i = (i + 1) % m) {
if (keys[i].equals(key)) {
vals[i] = val;
return;
}
}
keys[i] = key;
vals[i] = val;
n++;
}put操作，直接找到第一个非空元素，把键值对存入到平行数组当中去即可。
get操作
public Value get(Key key) {
if (key == null) throw new IllegalArgumentException("argument to get() is null");
for (int i = hash(key); keys[i] != null; i = (i + 1) % m)
if (keys[i].equals(key))
return vals[i];
return null;
}
内存使用情况：
拉链法和线性探测法的详细比较取决去实现的细节和用例对空间和时间的要求。即时基于性能考虑，选择拉链法而非线性探测法也不一定是合理的。在实践中，两种方法的性能差别主要是因为拉链法为每个键值对都分配了一小块内存而线性探测法则为整张表使用了两个很大的数组。对于非常大的散列表，这些做法对内存管理系统的要求也很不相同。在现代系统中，在性能优先的情景下，最好由专家去把握这种平衡。