深入浅出HashMap
2018-05-04 本文已影响169人
周小WA
Map
map是一种 key/value组织的数据结构。在Java中Map是一个接口类，其实现类比较常用的有：
HashMap, LinkedHashMap, TreeMap。
HashMap
HashMap在Map家族中用的最多的集合类，他是非线程安全的，允许key为null，可以插入相同的key值，但是会覆盖value值。内部数据结构有数组，单链表，红黑树。
什么是HashMap
HashMap是Map接口的实现类，其内部成员机构如下
image
- 其中table是个Node类型数组，是HashMap最重要的成员，用来存储每个节点数据。(其实Node是单链表数据结构)
- entrySet是用来缓存Node节点数据的，用来遍历访问的
- loadFactor是负载因子，用来表示table的填满程度 默认值为0.75
- threshold 值为capacity * loadFactor 当table节点个数大于threshold值的时候，就需要resize了
HashMap的工作原理
先从一段简单的代码说起
public static void main(String[] args) {
Map<Integer, String> integerStringMap = new HashMap<>();
integerStringMap.put(1, "a");
integerStringMap.put(2, "b");
integerStringMap.put(3, "h");
integerStringMap.put(6, "i");
integerStringMap.put(17, "j");
integerStringMap.put(49, "j");
integerStringMap.put(25, "c");
System.out.println(integerStringMap.toString());
}
该段代码简单的使用HashMap存储<Integer,String>值，下图为内部存储结构
HashMap
其中table只要插入一个值 其length(capacity)就会设置为16(该值可以自己设定，不设置则默认为16)，当table size值超过 capacity * loadFactor(16 * 0.75 = 12) 时 table就会开始resize，然后重新组织数据并插入新的节点。可以通过以下代码，验证以上说法是否正确
integerStringMap.put(4, "l");
integerStringMap.put(5, "l");
integerStringMap.put(7, "l");
integerStringMap.put(8, "l");
integerStringMap.put(9, "l");
integerStringMap.put(10, "l");
再观察table 数组的length，同时threshold的值也相应变了，至于为啥某些元素index变了 在下面内容会详细讲解。
image
HashMap put方法工作原理
先从JDK8源码说起。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 首次插入就将length初始化为16(DEFAULT_INITIAL_CAPACITY)
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// index 使用(n-1) & hash 取代模运算[hash % n] n为2的n次幂
if ((p = tab[i = (n - 1) & hash]) == null) // table对应的位置没有元素,则放入
tab[i] = newNode(hash, key, value, null);
else { // 冲突 开始解决冲突
Node<K,V> e; K k;
// 确定插入节点与当前idx相同节点是否"相等"
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 取代原来的node,value值之后设定
e = p;
// 使用红黑树组织node(冲突的第一个节点就是树节点(Hash table中的)
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);
// 如果单链表节点个数超过TREEIFY_THRESHOLD - 1则将单链表转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 遍历单链表过程中找到key相同的node 则break
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 判定是否需要替换value值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// LinkedHashMap中使用
afterNodeAccess(e);
return oldValue;
}
}
// table数组中元素个数
++modCount;
// 需要扩容
if (++size > threshold)
resize();
// LinkedHashMap回掉方法
afterNodeInsertion(evict);
return null;
}
上述方法就是HashMap插入节点的代码，主要有以下几个步骤
- 如果是第一个元素则 resize 初始化table
- 找到插入节点的index值，即bucket在table中的索引值
- 判断当前bucket节点是否有值，没有则直接插入，有则进行下面步骤，假设新节点为a，bucket处的原节点为b
- 首先判断a,b是否"相等",如果相等直接判断是否需要替换value值，如果不相等则进行下面步骤
- 如果index处节点是树TreeNode类型则插入到红黑树中，如果不是进行下面步骤
- 遍历以index处节点为头节点的单链表，遍历中如果遇到"相等"的节点，则停止遍历，然后判断是否需要替换value值
- 遍历到单链表结尾时(node->next == null)，判断是否需要将单链表转为树(单链表节点个数超过8则需要转位树存储)，若没有超过，则插入到单链表结尾
- 插入后判断
注意
以上说的“相等”是 hash值以及key的值或者equals都相等
e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))
当两个Key对象hashCode相同会发生什么
当两个key对象hashCode相同时，HashMap会将2个node放在同一个bucket里，新加的就插入到单链表后面(节点个数<8)或者红黑树中
两个相同hashCode的key怎么取value
当2个相同hashCode的key去获取values时，HashMap首先会根据hashCode值进行index获取node的bucket位置，即定位到bucket的首节点，然后：如果是红黑树，则遍历树根据key.equals来定位value值；如果是单链表，原理一致，只是遍历的是单链表。具体可以查看源码。
HashMap怎么resize
当table.size大于threshold值时，HashMap就会进行一次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) {
// 长度已经最大
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 双倍当前数组length
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold 扩大大小为原来的2倍
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 12
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // 设置新的 threshold
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 当前表指向新的空表 开始复制原先的数据 从oldTab
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// bucket只有一个节点直接将老节点插入到新的table中，注意要rehash的
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 { // preserve order
// 下面处理目的 将bucket中的节点转移到新的hash table上
// loHead, loTail用来构成(e.hash & oldCap == 0)低oldCap位的节点单链表, 结果为newTab[j] = loHead
// hiHead, hiTail用来构成(e.hash & oldCap != 0)高oldCap位的节点单链表, 结果为newTab[j + oldCap] = hiHead
// eg: oldCap为16, 则newCap为32, 假设index为1的bucket上有有1,17,49,65三个节点
// 则1. 1 & 16 = 0, 65 & 16 = 0则loHead -> 1 -> 65 <- loTail -> null, 结果为newTab[1] = loHead
// 2. 17 & 16 != 0, 49 & 16 != 0,则 hiHead -> 17 -> 49 <- hiTail -> null, 结果为newTab[17(1+16)] = hiHead
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;
}
就以文章中例子代码为例，下图为oldTable -> newTable节点的转移过程
image
参考文献
