数据结构（三）——散列（上）
松鼠的窝 2018-01-23
为什么要设计散列这种数据结构呢？在现实世界中，实体之间可能存在着映射关系（key-value），比如一个订单可能对应多个商品，对应一个配送站点。散列正是对这种映射关系的逻辑结构的表达，但同时，作为一种数据结构，在计算机中该如何实现存储呢？
本节将重点从散列的逻辑结构和存储结构出发，对上述涉及的散列原理及应用场景作出说明：
- 散列函数与散列表
- Java中的散列实例
- 保证最坏情况时间复杂度
一、散列函数与散列表
1.1 散列函数
散列函数（Hash Function）是一种从任何一种数据中创建小的数字“指纹”的方法。一般来讲，散列函数的输入包含较多的信息（比如SHA-2最高接受(264-1)/8长度的字节字符串），经过散列算法后，映射为一个更小空间的散列值（通常为格式固定的字母和数字组成的字符串），其过程如下图所示。
散列函数在加密、校验等安全领域有广泛的应用，比如，SHA（Secure Hash Algorithm）家族在TLS和SSL、PGP、SSH、S/MIME和IPsec等安全协议中的广泛应用，MD5（Message-Digest Algorithm 5）在文件下载中校验的应用，此外，散列表是散列函数的一个主要应用。
1.2 散列表
散列表的核心优势是能够按照关键字快速存取数据记录，其插入、查找和删除的平均时间复杂度为O(1)。在实现上，将关键字通过散列函数映射为一个数组的地址，而将数据记录存储在该数组单元中。对同一散列函数，要求两个散列值如果是不相同的，那么这两个散列值的原始输入也是不相同的；但两个散列值如果是相同的，却并不能确定两个输入值是相同的，如果不同的输入得到的相同的散列值，这种情况就是“散列冲突”。一种常用的散列表结构如下图所示。
从图中可以看出，散列表的核心结构为：数组+链表。直接存储散列数据的结构称为节点，节点包含散列值、关键字、数据域和指针域（指向下一个节点）。如图中的节点13，其关键字经过散列函数得出在数组中的下标为0，数据域为13，指针域指向下一个节点6。节点在数组中存储的地址称为槽位，比如散列冲突时，37、62、52和92经过散列函数计算得出的槽位均为14。
那么，为了减少散列冲突，使数据元素在数组中均匀分布，在散列表的实现中，选择合适的散列函数至关重要，常见的散列函数包括直接寻址法、数字分析法、平方取中法、折叠法、随机数法及除留余数法等，其中，直接寻址法通过取key值或者key值的某个线性函数值作为散列地址，即hash(k)=k或者hash(k)=a*k+b；除留余数法通过取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 hash(k)= k mod p, p < m。在JDK中常用除留余数法作为散列函数。
1.3 解决散列冲突
一个好的散列函数要求尽量减少散列冲突且计算简单，但冲突总是无法避免的，遇到冲突有哪些解决办法呢？
- 链地址法。上图中解决散列冲突的方法就是链地址法，即将散列到同一槽位的元素通过链表进行保存。JDK中就是使用这种方法来解决散列冲突的。
- 开放定址法。假定散列函数为H，经过散列函数运算H(key)后得到散列值为Hi，过程如下：
Hi =(H(key) + di) % m，其中i = 1，2，…，n.
常用的开放定址法包括线性探测法和平方探测法。其区别在于di：
线程探测法：di = 1，2，3，…，m-1.
平方探测法：di =12，-12，22，-22，…，k2，-k2 ( k<=m/2 ). - 再散列。顾名思义，在散列冲突发生后，采用新的散列函数对key进行重新散列。假定散列函数分别为RH1，RH2……，散列过程如下：
Hi=RH1（key）， 其中 i=1，2，…，k
当散列值Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到不冲突为止。
二、Java中的散列实例
Java中的散列实例包括HashSet、HashMap、LinkedHashSet、LinkedHashMap以及HashTable等，其中，HashSet和LinkedHashSet是基于HashMap和LinkedHashMap封装实现的，HashTable相比于HashMap仅增加了对同步操作的支持，并且在Java 5以后建议使用ConcurrentHashMap代替HashTable（第三章会讲到ConcurrentHashMap），因此本节将重点对HashMap和LinkedHashMap的实现原理进行说明。
2.1 HashMap实现原理
2.1.1 HashMap的散列函数
《Effective Java》中指出：覆盖equals时必须覆盖hashCode，hashCode在基于散列的集合中有重要的作用，因为HashMap的hash方法需要根据Key对象的hashCode来计算散列值的。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}上文提到，Java中采用除留余数法作为散列函数，假定n为数组的长度，则槽位的计算方法为hash % n。但计算hash值属于高频操作，而取余运算较为耗时，因此在Java中采用另外一种实现：(n - 1) & hash。使得hash % n 等于 (n - 1) & hash的前提是n = 2 m（m 为任意正整数），HashMap中数组长度要求必须为2的m次幂，扩容时也是按照2的倍数进行扩展，初始长度为1 << 4 == 2 4 == 16，最大值为 1 << 30 == 2 30 == 1073741824。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始值 static final int MAXIMUM_CAPACITY = 1 << 30; // 最大值
下面以Key='A'为例说明HashMap中散列的计算过程：
首先，'A'作为字符串，String的hashcode方法如下：
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}String计算hashcode的算法是遍历String串中的每个字符，应用公式 h = 31 * h + val[i] （val[i]表示第i个字符的ASCII码值）进行计算。计算hashcode是一个比较耗时的操作，因此，String采用了闪存散列代码的方法，hashcode计算完成后会保存在hash域中，由于String是final类型的，所以再次调用时判断如果hash值不为0则直接返回保存的hash值。
HashMap的hash方法将hashcode与hashcode>>>16进行异或，即将hashcode的高16位与低16位进行异或，然后与(n-1)进行位与操作得到该Key值在数组中的下标。在HashMap中，数组长度n始终为2的次方，比如初始长度16，n-1=15(0000 1111)，那么在计算数组下标时，实际上只有低四位是有用的，这可能会使得散列冲突加剧，所以HashMap的设计者在综合权衡速度、作用和质量的基础上，选择了将hashcode的高16位与低16位进行异或得到一个综合的信息。
2.1.2 链表和红黑树在解决散列冲突时的应用
在JDK1.8之前，Java仅采用链表解决散列冲突，因此，在最坏情况下，假定所有节点关键字的hash值都相等，则所有节点插入同一槽位，导致HashMap退化为该槽位的链表，查找节点的时间复杂度为O(n)。JDK1.8在解决散列冲突时引入了红黑树，在某槽位的链表长度超过限额之后，则将链表转换为红黑树。通过上一节的描述，我们知道红黑树能够保证最坏情况的操作时间复杂度为O(Log(n))，因此，使得HashMap在散列冲突时的性能有较大程度的提升。（下文中无特殊说明时，HashMap均表示JDK1.8中的实现）
下面以HashMap插入和删除元素为例，说明链表和红黑树在解决散列冲突时的应用。HashMap中采用Node和TreeNode来分别表示链表和红黑树中存储的节点，其定义如下：
// 链表节点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
// 红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
boolean red;
}
// 将链表节点转换为红黑树节点
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}在HashMap中插入节点的流程，主要包括以下几步：
- 根据数组是否为空（长度为0）确定是否初始化数组；
- 根据hash值计算Node在数组中的下标，根据下标判断是否散列冲突，如果不冲突，则新建节点插入数组；
- 如果冲突并且不是同一节点，通过链表存储新的节点；
- 如果冲突导致链表过长，就把链表转换为红黑树；
- 判断节点是否已经存在，如果存在就替换该节点对应的旧值，自增HashMap的修改数modCount；
- 判断是否需要扩容（超过加载因子loadFactor * 数组容量），如果需要就调用resize方法扩容。
用流程图表示如下：
可以看出，链表和红黑树的转换发生在插入节点导致链表过长时，下面是HashMap中putVal方法的部分实现。
Node<K,V> e; K k;
// 待插入节点已存在
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 需要插入红黑树节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 遍历链表插入节点
else {
for (int binCount = 0; ; ++binCount) {
// 当前节点的下一个节点为空
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 判断是否需要将链表转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 待插入节点已存在
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}上述代码中，p初始为tab[i = (n - 1) & hash]，即待插入节点对应槽位处链表的首节点，e表示已存在的待插入节点。首先判断待插入节点是否已存在，其次判断是否已经需要插入红黑树节点，最后遍历该链表，找到合适的插入位置，完成后判断链表长度，如果超过TREEIFY_THRESHOLD（8），则调用treeifyBin方法。在treeifyBin方法中，会判断HashMap数组长度，如果小于MIN_TREEIFY_CAPACITY（64），则先进行扩容。否则将Node链转换为TreeNode链，最后调用TreeNode的treeify方法生产红黑树。
TreeNode继承自LinkedHashMap.Entry，而LinkedHashMap.Entry又继承自HashMap.Node，所以TreeNode具有Node的所有属性。TreeNode是HashMap的静态内部类，其内部定义一系列方法用于保证红黑树的性质，包括转换树（treeify）、左旋（rotateLeft）、右旋（rotateRight），删除后平衡（balanceDeletion）、插入后平衡（balanceInsertion）等。
同样，在HashMap中删除元素也涉及到链表和红黑树的转换，HashMap的remove方法主要分为两步：1）找到待删除的节点；2）删除节点。
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 待删除节点为该槽位首节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 继续查找该槽位所连接的链表
else if ((e = p.next) != null) {
// 待删除节点为红黑树节点，调用红黑树的遍历方法
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
// 遍历链表，找到待删除节点
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 删除节点
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 如果待删除节点为红黑树节点，则调用TreeNode的删除节点方法
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 删除该槽位的首节点
else if (node == p)
tab[index] = node.next;
// 删除链表中的节点
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}值得关注的是删除红黑树节点的removeTreeNode方法中，当红黑树规模较小时，则会调用untreeify方法将红黑树退化为链表，该过程与插入时链表转换为红黑树的过程刚好相反。
2.1.3 扩容
HashMap中有三个关键参数控制着扩容的时机，分别是threshold、loadFactor和size，其中，threshold = loadFactor * size。threshold表示当前HashMap所能容纳的节点的最大数量，超过threshold就会触发扩容；loadFactor为加载因子，初始值为0.75f；size表示HashMap存储节点的数组的容量，初始值为16。
扩容的实现主要分为两步：1）根据新的容量初始化节点数组；2）将原数组中的元素重新散列至新数组。新容量总是在现有容量的两倍，因此HashMap的容量总等于2的幂（比如初始容量16扩容后为32）。同时，新的扩容上限也增加为现有上限的两倍。
根据新的容量初始化节点数组
// 初始引用oldTab、oldCap和oldThr
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
// 初始newCap、newThr
int newCap, newThr = 0;
// 原容量大于0情况的扩容
if (oldCap > 0) {
// 超过HashMap的容量上限就不再继续扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新容量为原容量的2倍，新的上线为原上线的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
// 设置初始容量为16、初始限度为12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算resize的上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 初始化新容量数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;将原数组中的元素重新散列至新数组
HashMap计算插入节点槽位的方法为：(n - 1) & hash，由于HashMap的容量总是以2的倍数递增，所以，扩容后的容量相比于原容量在二进制表达上，只是最高位前面增加了一位，并且为1。举个例子，容量为16，n - 1为15（0000 1111），扩容后的容量为32，n - 1为31（0001 1111），0001 1111 相比于 0000 1111 只是多了最高位的 1。因此在于hash值做位与运算时，如果hash值该位为1，则新槽位 = 原槽位 + 原容量，否则槽位不变。
// 遍历原数组中的所有槽位
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 原数组不再对节点持有引用
oldTab[j] = null;
// 若该节点不存在散列冲突，计算在新数组中的槽位，直接插入
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 插入红黑树节点
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 按照原顺序插入链表节点
else {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 保持原槽位
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原槽位+原容量
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原槽位插入新数组中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原槽位+原容量插入新数组中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}2.2 LinkedHashMap实现原理
在上节已经讲过，LinkedHashMap支持按照插入顺序对节点排序。实际上，LinkedHashMap还支持按照访问顺序排序。排序方式是由accessOrder字段决定的，如果accessOrder为true，则按照访问顺序排序，否则按照插入顺序排序。LinkedHashMap按照访问顺序排序的特征为很多算法实现提供了支持，比如Android中的LruCache（缓存策略为最近最少使用最先删除）就是基于LinkedHashMap的访问顺序实现的，其构造方法如下：
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
// accessOrder字段为true，表示按照访问顺序排序，实现最近最少访问最先删除
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}因此，在探讨LinkedHashMap的实现原理时，将重点关注LinkedHashMap是如何实现插入顺序和访问顺序的？支持LinkedHashMap保持顺序的基础在于其节点Entry类自包含了before和after域，分别指向当前节点的前节点和后节点，这类似于LinkedList实现双向链表的方法。
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}Entry继承自HashMap.Node，因此具有HashMap节点类的所有特性。比如，LinkedHashMap插入节点是通过调用HashMap的put方法实现的。而put方法又调用了newNode和afterNodeInsertion等方法，而这些方法正好是HashMap预留给LinkedHashMap用来保持顺序的方法，主要包括节点的初始化等、插入节点后的调整等。
// 新建节点
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
// 用链表节点替代红黑树节点
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
// 创建红黑树节点
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
return new TreeNode<>(hash, key, value, next);
}
// 用红黑树节点替代链表节点
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
// 重新初始化
void reinitialize() {
// ……
}
// 节点操作后的调整
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }LinkedHashMap初始化节点是通过重写HashMap的newNode方法实现的，首先创建LinkedHashMap.Entry节点对象，其次将该节点对象链接到LinkedHashMap当前尾节点的后面（after域），成为新的尾节点。通过节点之间的链接来保证插入节点的有序性。
// LinkedHashMap的新建节点实现
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
// 将当前节点链接到尾节点的后面
linkNodeLast(p);
return p;
}
// 链接到尾节点的后面
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}需要注意的是，LinkedHashMap并未改变节点存储的顺序，换句话说，在HashMap存储节点的数组Node
// LinkedHashMap的LinkedHashIterator实现
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
// next指向当前节点的after节点
next = e.after;
return e;
}
// HashMap的HashIterator实现
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
// next指向当前槽位的下一个节点或者下一个槽位的首节点
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}可以看出，LinkedHashMap的顺序是在迭代器层面实现的。那LinkedHashMap的访问顺序又是如何实现的呢？也是通过迭代器吗？LinkedHashMap在插入、查找以及替换元素之后都会调用afterNodeAccess方法进行重排序，下面来看下afterNodeAccess的实现。
// 将指定节点移至尾部
void afterNodeAccess(Node<K,V> e) {
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 尾节点的after节点为null
p.after = null;
// 指定节点为首节点，则将其after节点置为首节点
if (b == null)
head = a;
// 否则将before节点的after节点置为指定节点的after节点
else
b.after = a;
// 如果指定节点的after节点不为空，则将其before节点置为指定节点的before节点
if (a != null)
a.before = b;
// 否则将其before节点置为last节点
else
last = b;
// 如果last节点为null，则指定节点为头结点
if (last == null)
head = p;
// 否则将指定节点绑定到尾节点
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}afterNodeAccess方法实现的核心功能是将指定节点移动到LinkedHashMap当前节点链的尾部，整个过程如下示意图所示。
由此可知，在访问元素后，总会将该元素移动到LinkedHashMap当前节点链的尾部，而tail尾节点也就是最年轻（youngest）的节点，head是最老（eldest）的节点，从而实现了访问顺序的排序。回到本节开始提到的Android中LruCache基于LinkedHashMap的实现最近最少访问最先删除算法的问题。LruCache指定了缓存的最大值maxSize，缓存元素超过maxSize后会触发删除eldest节点，Android中的LinkedHashMap实现新增了eldest方法，返回的正好就是节点链的头节点header（eldest），即最近最少访问的节点。
public Entry<K, V> eldest() {
LinkedEntry<K, V> eldest = header.nxt;
return eldest != header ? eldest : null;
}至此，我们分析了HashMap和LinkedHashMap的实现原理，相比于之前版本的实现，JDK 1.8中最坏情况下查找的时间复杂度已经由O(n)变为O(lgn)，大大提高了性能。但在某些需要严格确保性能的场合，比如路由表实现，需要保证最坏情况下的时间复杂度仍为O(1)，那么就需要重新设计散列算法，而不能使用标准Java库中的链地址法来解决散列冲突了。
