转载请注明出处！https://www.jianshu.com/p/e325578eb512
如果你需要一个简单而不失优雅的无序数据表，那么散列表一定是你的首选。
在我们分布较好（近似均摊）的散列表内，查找、插入等操作一般在常数级别。
所有的数据结构都是在时间与空间上作出了平衡选择，而散列表则非常好的找到了平衡点。
散列表的难度比较简单，核心难度在于如何设计出一个优秀的散列函数，可以使我们均匀的分布每个键值。幸运的是，Java已经为我们准备好了不少常用的数据类型（Integer, String, Double, File, URL等）的散列函数——hashCode()。
散列函数
对于散列表而言，所有存储的键值，不论是什么类型的数据，都要通过散列函数转化为数组中的索引实现存储。而如何设计优秀散列函数，一直是算法专家和数学专家的问题。我们在这里仅提供一种简单思路。
- 假设散列表大小为M长度的整数数组，则每个存储的键值都应该分布在 0~M-1的数组区间。
假设键值的散列值为正整数k，则我们可以将
k % M，那么我们得到的就是分布在0~M-1的某个值了。
-
hashCode()返回的是一个32位比特整数，一般为内存地址经算法产生。
private int hash(Key key) {
if (key == null) throw new IllegalArgumentException();
return ((key.hashCode() & 0x7fffffff) % M);
}
上述代码是一个简单的散列函数，其中0x7fffffff是最大的正整数（无符号32位 0111 1111 1111 1111 1111 1111 1111 1111），通过&0x7fffffff，可以得到一个去符号的31位整数，然后再与M取余即可得到键的hash索引。
- 有时候hash索引会产生重复，处理好小整数M内的重复情况是关键。
软缓存
对于有些散列函数，在处理过程中比较耗时，我们可以采用临时变量存储计算后的hashCode()，Java中的String就是如此处理的。
散列表实现——链表
链表实现即为每个键所转化的索引放入一个M大小的数组中，再将索引重复的键值以链表的方式存储在每个数组内。（数组嵌套链表）
假设我们这里有一个顺序存放数据的链表SequentialSearchST，拥有get(key), put(key,value), delete(key)几个常用的方法，具体代码参见我的Github源码。
构造 constructor：
public class SeparateChainingHashST<Key, Value> {
private int N;//键值总对数
private int M;//散列表大小
private SequentialSearchST<Key, Value>[] st;//存放链表
public SeparateChainingHashST() {
this(997);//默认构造器
}
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();
}
private int hash(Key key) {
if (key == null) throw new IllegalArgumentException();
return ((key.hashCode() & 0x7fffffff) % M);
}
}
查找 get：
public Value get(Key key) {
if (key == null) throw new IllegalArgumentException();
if (isEmpty()) throw new NoSuchElementException();
return (Value) st[hash(key)].get(key);
}
插入 put：
public void put(Key key, Value value) {
if (key == null) throw new IllegalArgumentException();
if (value == null) {
delete(key);
} else {
//动态调整散列表的大小
if (N >= 10 * M) resize(2 * M);
if (!st[hash(key)].contains(key)) N++;
st[hash(key)].put(key, value);
}
}
动态调整散列表的大小，这里的调整临界值非固定，这里达到1/10就调整只是为了较为均衡的分布利用空间。
动态调整 resize：
动态调整散列表的大小不是必须的，但如同数组的动态变换大小一样，这样可以优化内存的空间利用，减少重复copy次数带来的开销。
private void resize(int chains) {
SeparateChainingHashST<Key, Value> temp = new SeparateChainingHashST(chains);
for (int i = 0; i < M; i++) {
Iterator<Key> iterator = st[i].keys().iterator();
while (iterator.hasNext()) {
Key key = iterator.next();
Value value = st[i].get(key);
temp.put(key, value);
}
}
M = temp.M;
N = temp.N;
st = temp.st;
}
删除 delete：
public void delete(Key key) {
if (key == null) throw new IllegalArgumentException();
if (isEmpty()) throw new NoSuchElementException();
if (get(key) == null) throw new NoSuchElementException();
if (st[hash(key)].contains(key))
N--;
st[hash(key)].delete(key);
if (M > 4 && N <= 2 * M) resize(M / 2);
}
散列表实现——数组
实现散列表的另一种方式是通过数组来完成，用大小为M 的数组和N 的键值对（M > N）来存储。其中当键值对重复时，我们需要使用数组中的空位来解决冲突。这种方法也被称为开放地址散列表。
当碰撞发生时（某键的散列值已被使用），则我们直接向下寻找位置：
- 命中，键值相同。
- 未命中，键值为空（没有键），此时可执行插入。
- 继续向下，该键与当前键不同。
开放地址散列表的核心思想是与其将内存用作链表（与链表实现对比），不如将他们作为散列表中的空元素，这些空元素可以作为查找结束的标志。
我们在维护键对应的值的时候，采用并行数组来解决，一条保存键，一条保存值。
public class LinearProbingHashST<Key, Value> {
private int N; //total number of item
private int M; //Size of map , M > N
private Key[] keys;
private Value[] values;
public LinearProbingHashST() {
this(16);//default construct
}
public LinearProbingHashST(int cap) {
this.M = cap;
this.N = 0;
keys = (Key[]) new Object[M];
values = (Value[]) new Object[M];
}
private int hash(Key key) {
if (key == null) throw new IllegalArgumentException();
return ((key.hashCode() & 0x7fffffff) % M);
}
...
}
查找 get：
public Value get(Key key) {
if (key == null) throw new IllegalArgumentException();
if (isEmpty()) throw new NoSuchElementException();
for (int i = hash(key); keys[i] != null; i = (i + 1) % M) {
if (keys[i].equals(key)) {
return values[i];
}
}
return null;
}
由于是使用数组实现，所以查找比较简单，开销很小，最差情况也能在 O(logN) 内能完成。
插入 put：
public void put(Key key, Value value) {
if (key == null) throw new IllegalArgumentException();
if (N >= M / 2) resize(2 * M);
if (value == null) delete(key);
int i;
for (i = hash(key); keys[i] != null; i = (i + 1) % M) {
if (keys[i].equals(key)) {
values[i] = value;
return;
}
}
keys[i] = key;
values[i] = value;
N++;
}
插入的时候，要注意散列表大小最好需要动态变化。这里为了保证使用的内存量和键值对数量的比例在某一范围内，采用1/2。
删除 delete：
- 先查找到键的位置
- 将键赋空删除
- 如果删除的键后面没有键（不连续），则删除操作结束。
- 如果删除的键后面连续还有键，则需要将后面的连续键向前移动一格位置。
前三步不难理解，那么第四步这么做的原因，主要是因为如果不将后面的键向前移动位置使之保持连续，那么在之后的查找过程中会出现错误。
比如（见上图）我们查找H，此时C已被删除。若我们不向前移动H，那么查找操作将会返回不存在H，因为H实际存储在7的位置（散列值为4）。
public void delete(Key key) {
if (key == null) return;
if (isEmpty() || !contains(key)) throw new NoSuchElementException();
int i = hash(key);
while (!key.equals(keys[i])) {
i = (i + 1) % M;
}
keys[i] = null;
values[i] = null;
i = (i + 1) % M;
while (keys[i] != null) {
Key keyToRedo = keys[i];
Value valueToRedo = values[i];
keys[i] = null;
values[i] = null;
N--;
put(keyToRedo, valueToRedo);
i = (i + 1) % M;
}
N--;
if (N > 0 && N <= M / 8) resize(M / 2);
}
键簇：
上面删除操作中提到连续的键值，这里引入一个概念——键簇来表示连续的键。数组实现的散列表操作平均开销是与键簇的分布直接相关的。
显然只有短小的键簇才能保证较高的效率。
因为当键簇长了后，每次查找（例如查找H）的遍历次数会越来越多，导致耗时增加。我们希望散列表中键簇的分布均匀且长度大部分合适。
对于不断的插入键，散列表会越填越满，直至连成大的键簇。这样性能会变的很差，为了保证性能，我们只能牺牲内存开销，动态的调整散列表的大小。
调整数组大小 resize：
private void resize(int cap) {//must be needed
LinearProbingHashST<Key, Value> t;
t = new LinearProbingHashST<>(cap);
for (int i = 0; i < M; i++)
if (keys[i] != null)
t.put(keys[i], values[i]);
keys = t.keys;
values = t.values;
M = t.M;
}
实现比较简单，直接赋值一个新的大小的数组即可。
性能：
对于各种常见的符号表而言，这里做一个性能汇总：
| 算法 | 最坏情况 | 平均情况 | 内存使用 |
|---|---|---|---|
| 顺序查找（无序链表） | N | N | 48N |
| 二分查找（有序数组） | logN | logN | 16N |
| 二叉树查找（二叉树） | N | 1.39logN | 64N |
| 红黑树查找（红黑树） | 2logN | logN | 64N |
| 散列表（数组） | logN | N/M | 48N+32M |
| 散列表（链表） | logN | 1.5(get) 2.5(put) | 32N~128N |
根据经验而言，一般会优先选用散列表，实现简单并且性能优秀。除非是其他因素，才会选择红黑树来实现，因为红黑树在logN内支持的操作更多。
谢谢观看。
参考文献：《算法导论》 《Algorithms, 4th Edition》
