HashMap我们经常使用，那么它的数据结构和底层实现是怎么样的，我们来啃一下。
HashMap的数据结构
HashMap的数据结构是哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，在讨论哈希表之前，我们先大概了解下其他数据结构在新增，查找等基础操作执行性能。
1.数组
数组我们很熟悉，由于采用一段连续的存储单元来存储数据，故空间使用上处于劣势，对于数组的新增，删除等操作还有可能需要移动大量元素。但数组对于指定下标的查找时间复杂度为O(1)；数组的特点是：寻址容易，插入和删除困难；
2.链表
链表存储区间离散，占用内存比较宽松，故空间使用上占优势，对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)。链表的特点是：寻址困难，插入和删除容易。
3.哈希表
哈希表综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构。哈希表（(Hash table）既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。哈希表结构如下
2059840-8386849414328b14.png
从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组table，每个元素存储的是一个链表的头结点，每个元素都是一个Node<K,V>。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。
比如下图哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。
20131105152215718.png
HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解，一个线性的数组怎么实现按键值对来存取数据呢？我们继续看HashMap的重要属性。
HashMap的重要属性
源码
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
/**
* HashMap 的默认初始容量为 16，必须为 2 的 n 次方 (一定是合数)
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* HashMap 的最大容量为 2 的 30 次幂
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* HashMap 的默认负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 链表转成红黑树的阈值。即在哈希表扩容时，当链表的长度(桶中元素个数)超过这个值的时候，进行链表到红黑树的转变
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 红黑树转为链表的阈值。即在哈希表扩容时，如果发现链表长度(桶中元素个数)小于 6，则会由红黑树重新退化为链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* HashMap 的最小树形化容量。这个值的意义是：位桶（bin）处的数据要采用红黑树结构进行存储时，整个Table的最小容量（存储方式由链表转成红黑树的容量的最小阈值）
* 当哈希表中的容量大于这个值时，表中的桶才能进行树形化，否则桶内元素太多时会扩容，而不是树形化
* 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* Node 是 HashMap 的一个内部类，实现了 Map.Entry 接口，本质是就是一个映射 (键值对)
* Basic hash bin node, used for most entries.
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 用来定位数组索引位置
final K key;
V value;
Node<K,V> next; // 链表的下一个node
Node(int hash, K key, V value, Node<K,V> next) { ... }
public final K getKey() { ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
/**
* 哈希桶数组，分配的时候，table的长度总是2的幂
*/
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* HashMap 中实际存储的 key-value 键值对数量
*/
transient int size;
/**
* 用来记录 HashMap 内部结构发生变化的次数，主要用于迭代的快速失败机制
*/
transient int modCount;
/**
* HashMap 的门限阀值/扩容阈值，所能容纳的 key-value 键值对极限，当size>=threshold时，就会扩容
* 计算方法：容量capacity * 负载因子load factor
*/
int threshold;
/**
* HashMap 的负载因子
*/
final float loadFactor;
}
1.数组table
Node<K,V>[] table的初始化长度length由属性DEFAULT_INITIAL_CAPACITY决定，默认是16。
2.负载因子和最大容量
loadFactor为负载因子 (默认值DEFAULT_LOAD_FACTOR是 0.75)，threshold是最大容量（threshold=16*loadFactor），当HashMap的table长度为16，容量为16*loadFactor =12时，需要把数组扩容。threshold是 HashMap 所能容纳的最大数据量的 Node(键值对) 个数。
3.元素载体Node<K,V>
HashMap的主干是一个由Node元素组成的数组。Node是HashMap的基本组成单元。Node重要属性有 key , value, next，从属性key,value我们就能很明显的看出来Node就是HashMap键值对实现的一个基础bean，而next指向下一个Node，也就是数组位置相同的链表实现了。
4.红黑树阈值TREEIFY_THRESHOLD
即使负载因子和 Hash 算法设计的再合理，也免不了会出现链表过长的情况，这时会严重影响 HashMap 的性能。于是，在 JDK1.8 版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过 TREEIFY_THRESHOLD=8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高 HashMap 的性能，其中会用到红黑树的插入、删除、查找等算法。
新增put()方法
public V put(K key, V value) {
// 对key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步骤1:tab为空则调用resize()初始化创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤2:计算index,并对null做处理
//tab[i = (n - 1) & hash对应索引的第一个节点
if ((p = tab[i = (n - 1) & hash]) == null)
// 无哈希冲突的情况下,将value直接封装为Node并赋值
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步骤3:节点key存在,直接覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果key相同,p赋值给e
e = p;
// 步骤4:判断该链为红黑树
else if (p instanceof TreeNode)
// 若p是红黑树类型，则调用putTreeVal方式赋值
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步骤5:该链为链表
else {
// index 相同的情况下
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 如果p的next为空,将新的value值添加至链表后面
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 如果链表长度大于8,链表转化为红黑树,执行插入
treeifyBin(tab, hash);
break;
}
// key相同则跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//就是移动指针方便继续取 p.next
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
//根据规则选择是否覆盖value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 步骤6:超过最大容量,就扩容
if (++size > threshold)
// size大于加载因子,扩容
resize();
afterNodeInsertion(evict);
return null;
}
流程图如下：
4685968-0ccc069e89b40e4c.png
1.判断键值对数组table[i]是否为空或为null，执行resize()进行扩容
2.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向6，如果table[i]不为空，转向3
3.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals
4.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5
5.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可
6.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，执行resize()扩容
resize()扩容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// table已存在
if (oldCap >= MAXIMUM_CAPACITY) {
// oldCap大于MAXIMUM_CAPACITY,threshold设置为int的最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//newCap设置为oldCap的2倍并小于MAXIMUM_CAPACITY，且大于默认值, 新的threshold增加为原来的2倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// threshold>0, 将threshold设置为newCap,所以要用tableSizeFor方法保证threshold是2的幂次方
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 默认初始化，cap为16，threshold为12。
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// newThr为0，newThr = newCap * 0.75
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 新生成一个table数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// oldTab 复制到 newTab
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)
// e为红黑树的情况
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
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;
}
}
}
}
}
return newTab;
}
上面展示了resize方法的细节，可以看到扩容的实现时较为复杂的，但是我们知道所谓扩容，就是新申请一个较大容量的数组table，然后将原来的table中的内容都重新计算哈希落到新的数组table中来，然后将老的table释放掉。这里面有两个关键点，一个是新哈希数组的申请以及老哈希数组的释放，另外一个是重新计算记录的哈希值以将其插入到新的table中去。
1.第一个问题是，扩容会扩大到多少，通过观察上面的代码可以确定，每次扩容都会扩大table的容量为原来的两倍，当然有一个最大值，如果HashMap的容量已经达到最大值了，那么就不会再进行扩容操作了。
2.第二个问题是HashMap是如何在扩容之后将记录从老的table迁移到新的table中来的。上文中已经提到，table的长度确保是2的n次方，那么有意思的是，每次扩容容量变为原来的两倍，那么一个记录在新table中的位置要么就和原来一样，要么就需要迁移到(oldCap + index)的位置上。
下面简单来证明一下这个算法的正确性：
假设原来的table大小为4，那么扩容之后会变为8，那么对于一个元素A来说，如果他的hashCode值为3，那么他在原来的table
上的位置为(3 & 3) = 3,那么新位置呢？(3 & 7) = 3,这种情况下元素A的index和原来的index是一致的不用变。再来看一个
元素B，他的hashCode值为47，那么在原来table中的位置为(47 & 3) = 3，在新table中的位置为(47 & 7) = 7，也就
是（3 + 4），正好偏移了oldCap个单位。
那么如何快速确定一个记录迁移的位置呢？因为我们的计算方法为:(hashCode & (length - 1))，而扩容将导致(length - 1)会新增一个1，也就是说，hashCode将会多一位来做判断，如果这个需要新判断的位置上为0，那么index不变，否则变为需要迁移到(oldIndex + oldCap)这个位置上去，下面举个例子吧：
还是上面的两个元素A和B，哈希值分别为3和47，在table长度为4的情况下，因为(3) = (11)，所以A和B会有两位参与运算来
获得index，A和B的二进制分别为：
3 ： 11
47： 101111
在table的length为4的前提下：
3-> 11 & 11 = 3
47-> 000011 & 101111 = 3
在扩容后，length变为8：
3-> 011 & 111 = 3
47-> 10111 & 00111 = 7
对于3来说，新增的参与运算的位为0，所以index不变，而对于47来说，新增的参与运算的位为1，所以
index需要变为(index + oldCap)
获取操作get()方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
首先会获得当前table的一个快照，然后根据需要查找的记录的key的hashCode来定位到table中的index，如果该位置为null，说明没有没有记录落到该位置上，也就不存在我们查找的记录，直接返回null。如果该位置不为null，说明至少有一个记录落到该位置上来，那么就判断该位置的第一个记录是否使我们查找的记录，如果是则直接返回，否则，根据该index上是一条链表还是一棵红黑树来分别查找我们需要的记录，找到则返回记录，否则返回null。
可以看出，get方法的实现相对简单，key(hashcode)-->hash-->indexFor-->最终索引位置，找到对应位置table[i]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录。
网友评论