HashMap1.8原理解析，类比1.7差异分析
2019-12-17 本文已影响0人
酱爆大头菜
上一篇 懂LruCache？你必须先懂LinkedHashMap，顺带给LruCache提个建议中我们分析了LinkedHashMap原理。
其实LinkedHashMap继承于HashMap，如果想理解的彻底必须懂HashMap的底层原理。
本文主要针对HashMap的以下几个问题展开分析，由浅入深，由使用到原理，上下关联，融会贯通。
- 什么是HashMap？
- HashMap使用方式？
- HashMap的几个重要方法的源码是怎么实现的？
- HashMap 1.7 ~ 1.8 有什么不同？
1. 到底什么是HashMap？
- HashMap是一个继承于AbstractMap，实现Map和Serializable接口的 线程不安全 的 乱序 散列表，内部根据key的 hashCode 存储key - value键值对。
2. HashMap使用方式？
- HashMap的使用非常简单，如下：
public class HashMapActivity extends AppCompatActivity {
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_hash_map);
HashMap<String, String> hashMap = new HashMap();
hashMap.put("k", "v");
hashMap.put("k2", "v2");
hashMap.put("k3", "v3");
for (Map.Entry<String, String> entries : hashMap.entrySet()) {
Log.d("TAG", "key:" + entries.getKey() + " value:" + entries.getValue());
}
}
}
Log
2019-12-12 18:35:23.378 11510-11510/com.test D/TAG: key:k2 value:v2
2019-12-12 18:35:23.378 11510-11510/com.test D/TAG: key:k3 value:v3
2019-12-12 18:35:23.378 11510-11510/com.test D/TAG: key:k value:v
- 通过以上的日志输出可以看出HashMap数据存储的无序性。
3. HashMap的几个重要方法怎么实现的？
-
我们根据HashMap的使用的顺序逐一分析每个方法具体在干什么事。
- 3.1. HashMap使用前都需要借助构造方法进行实例化，那么HashMap的构造方法具体做了什么？
/**
* 创建一个默认的初始容量，负载因子为0.75的HashMap对象
*/
public HashMap() {
//默认为0.75，该变量主要用于扩容触发，当HashMap存储超过设定容容量75%时触发扩容。
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
*创建一个初始容量为initialCapacity，负载因子为默认0.75的HashMap对象
* @param initialCapacity 初始化容量，
* @throws IllegalArgumentException 如果传入的初始化容量是负数则报这个异常
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 创建一个初始容量为initialCapacity，负载因子为loadFactor 的HashMap对象。
*
* @param initialCapacity 初始容量
* @param loadFactor 负载因子
* @throws IllegalArgumentException 如果初始容量或loadFactor有一个为负数则抛该异常。
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//如果初始容量 > 2^30则设定initialCapacity = 2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//如果loadFactor是负数或者非数字值则抛异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
//这个逻辑是一个将initialCapacity转换为2的n次方的一个过程，具体细节我们后续详细分析
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 构造一个和指定Map有相同mappings的HashMap，初始容量能充足的容下指定的Map,负载因子为0.75
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
- 以上构造方法已经逐行写了注释，针对 tableSizeFor(int cap) 我们展开分析下。
/**
* 直接翻译英文注释的意是
* 返回给定目标容量的两个大小的幂
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
- 在看这个方法之前首先你得懂 移位运算 和 或运算，我先简单普及下这俩运算
- 首先计算机只认识二进制数字，它认为所有的数据都是0101010组成的。
- 比如十进制 24 转为2进制为11000
- 移位运算则将2进制数据移动位置并补0，比如11000>>> 1后为01100，01100 >>> 2后为00010
- 或运算是有一个1则为1，全是0则为0.
- ok,普及完了，我们研究下上边的代码。
- 非常简单首先进行了cap-1，该操作是为了防止当前入参已是2的幂了，结果最后返回的却是入参的2倍。
- 后续都是或运算和移位预算。按照我上述的逻辑会发现到最后会将入参的最高位后均会变成1。
- 比如入参是25，25-1 =24， 二进制为11000，最后会变成11111，最后return 在将11111+1，最后返回32。
- 其实上述方法只是返回了离入参的最近的2的n次幂，比如入参是3则返回4，入参是5则返回8。
我们写个demo验证下
public class HashMapActivity extends AppCompatActivity {
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_hash_map);
Log.d("TAG", "tableSizeFor->:" + tableSizeFor(0));
Log.d("TAG", "tableSizeFor->:" + tableSizeFor(1));
Log.d("TAG", "tableSizeFor->:" + tableSizeFor(2));
Log.d("TAG", "tableSizeFor->:" + tableSizeFor(3));
Log.d("TAG", "tableSizeFor->:" + tableSizeFor(4));
Log.d("TAG", "tableSizeFor->:" + tableSizeFor(5));
}
final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= 1 << 30) ? 1 << 30 : n + 1;
}
}
Log
2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: tableSizeFor->:1
2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: tableSizeFor->:1
2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: tableSizeFor->:2
2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: tableSizeFor->:4
2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: tableSizeFor->:4
2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: tableSizeFor->:8
-
HashMap构造方法小结，我们梳理下new HashMap()后干了啥事
- a. new HashMap()进行了局部变量赋默认值 this.loadFactor = DEFAULT_LOAD_FACTOR;
- b. new HashMap(1)调用了this.HashMap(1, DEFAULT_LOAD_FACTOR)
- c. new HashMap(1, 0.8)进行了初始容量大小判断，负载因子合规判断，以及调用了tableSizeFor(initialCapacity)进行了初始容量转2^n转化。
- 3.2. HashMap添加数据通过put方法，我们看下put方法
/**
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return 如果当前key下之前没有数据则返回null，否则返回之前的老数据。
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 存放数据
* @param hash 通过key计算的hashCode
* @param key 键
* @param value 值
* @param onlyIfAbsent 如果是true并且该key下原来有值，则不替换原来的值
* @param evict 如果是false则代表table处于创建模式。
* @return 如果之前有值则返回，如果之前没值则返回null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果tab为null或者长度为0则通过resize()方法创建一个 Node<K,V>[]赋值给tab。
//resize()方法后续单独分析
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果当前key的位置没有数据，则直接存入当前数据。
if ((p = tab[i = (n - 1) & hash]) == null)
//通过newNode()方法创建并存入数据。
tab[i] = newNode(hash, key, value, null);
else {
//如果当前key位置有数据，说明发生的hash冲突。
Node<K,V> e; K k;
//判断当前的key和之前老数据的key是否相同，如果相同则把老数据赋值给局部变量e。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断该位置的结构是否为红黑树，如果是红黑树则启用putTreeVal()方法处理数据，如果有key相同的则将老数据赋值给局部变量e
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//当前位置的结构是链表，则在循环在链表后添加当前数据。
for (int binCount = 0; ; ++binCount) {
//循环到最后一个元素，没有key重复则在链表尾添加Node<K,V>对象，此时e为null
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//添加后判断当前链表的长度，如果长度>=8则转换为红黑树。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果本次循环的key和当前key相同则退出循环，并在下边逻辑中进行替换操作。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//如果本次循环的key不相同的，且当前不是链表尾，则继续下次循环
p = e;
}
}
//替换值操作
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//LinkedHashMap预留的方法。
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判断扩容
if (++size > threshold)
resize();
//LinkedHashMap预留的方法。
afterNodeInsertion(evict);
return null;
}
/**
* 向红黑树插入/更新数据
* 遍历红黑树判断该节点的key是否与需插入的key相同，相同则返回老数据，不同则插入并返回null
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
-
HashMap put()方法小结，我们梳理下调用put()后干了啥事？主要分为以下7步
- 首先将全局变量table赋值给局部tab，并判断tab是否为null，如果为null则调用resize()方法初始化，创建table。
- 通过 tab[i = (n - 1) & hash]获取当前key的hashCode值位置的数据，如果为null，则说明该位置之前未存放数据，直接通过newNode()创建 Node<K,V>对象存储。
- 如果key hashCode对应的位置不为null则发生了hash碰撞，判断带插入key和碰撞的key是否相同，相同则直接替换对象。
- 如果碰撞位置的数据结构是否为红黑树，如果是则通过putTreeVal()方法处理数据，如果发现有key相同则返回老数据并赋值给局部变量e。
- 如果碰撞位置的数据结果为链表，则循环判断是否有和当前key相同的，如果有则返回老的数据，并赋值给e，如果没有则循环到链表尾，插入新数据。然后判断链表长度，如果>=8则通过treeifyBin()转换为红黑树。
- 判断局部变量e，如果!=null,则通过入参onlyIfAbsent 判断是否替换旧的值，然后调用afterNodeAccess()，该方法默认实现为空，LinkedHashMap有用到。
- 判断数据个数是否大于扩容阀值，如果大于则调用resize()扩容。并调用afterNodeInsertion()，该方法默认实现为空，LinkedHashMap有用到。
- 3.3. HashMap.put()中用到resize()方法，这个方法主要是干啥的？
/**
* 该函数有两个功能
* 1. 初始化hash表
* 2. 扩容
*
* @return the table
*/
final Node<K,V>[] resize() {
// 保存之前的table；
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;// 保存之前的table的容量。
int oldThr = threshold;// 保存之前的阀值（threshold值为oldTab.length*load_factor）
int newCap, newThr = 0;
//如果oldCap > 0说明之前的table不为空
if (oldCap > 0) {
//如果老table的长度已经>=最大整型值则将阀值设置为Integer.MAX_VALUE，后续也不在进行扩容。
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果容量翻倍后<最大整型值，且老容量>=16,则将新阀值也翻倍。（<<1可代表翻倍）
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//此时说明oldTab 为 null，oldCap 为0,如果oldThr > 0说明，HashMap被调用以下三构造方法之一。
//HashMap(int initialCapacity, float loadFactor)
//HashMap(int initialCapacity)
//HashMap(Map<? extends K, ? extends V> m)
//oldThr 为用户指定的 HashMap的初始容量（initialCapacity）。
else if (oldThr > 0) // initial capacity was placed in threshold
//table未初始化时oldThr为初始容量initialCapacity
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// oldCap <= 0 且 oldThr =0，说明通过HashMap()创建的HashMap，所有值均采用默认值，oldTab（Table）表为空，oldCap为0，oldThr等于0，直接设置新容量为16，新阀值为16*0.75
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新阈值为0
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"})
//初始化table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果老table!=null则将旧数据移值到新table中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果是单个节点则直接放到newTab的指定位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果是红黑树则进行红黑树的rehash操作
((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;
// 将同一桶中的元素根据(e.hash & oldCap)是否为0分成2个不同的链表，完成rehash
//索引不变得链表
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);
//索引不变的链表尾指针!=null则将尾指针.next制空
if (loTail != null) {
loTail.next = null;
//将头指针放在桶的第一个位置
newTab[j] = loHead;
}
//索引改变的链表尾指针!=null,则将尾指针.next制空
if (hiTail != null) {
hiTail.next = null;
//新的位置为原位置+oldCap
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
-
HashMap.resize()方法小结，我们梳理下调用resize()后干了啥事？主要分为以下7步
- 首先resize()有两个功能，一个是初始化table，一个是扩容。
- 如果之前table!=null 则判断 if( table.lenth>=整型最大值 ) { 则将扩容阀值设置为整型最大值，并停止扩容。} else if ( table.lenth*2<整型最大值 ) {则扩容为原来2倍，且阀值扩大为原来2倍}
- 如果通过构造函数创建了HashMap则赋值容量变量和阀值变量，如果没有设置容量和负载因子则用默认的赋值。
- 如果table未初始化则通过new Node[newCap]初始化，如果进行了扩容则通过new Node[newCap]创建新的容器。
- 如果老table!=null则将老数据移值到新容器中，存储位置为原位置/原位置+原容量，移值过程采用尾插法，转移数据时统一计算存储位置。
-
JDK1.7 ~ JDK1.8在resize()的区别有哪些？
- 扩容时机：1.7是先判断>阀值扩容后再插入数据，1.8是先插入数据然后判断>阀值扩容。
- 存储位置计算：1.7 重新hashCode，扰动处理然后取模运算，并且每一个数据单独计算，1.8 原位置/原位置+旧容量，在转移数据时统一计算。
- 扩容后转移数据：1.7使用头插法，原位置数据往后移动，会出现逆序/环形链表死循环问题，1.8使用尾插法，防止出现死循环，逆序，环形链表等问题。
- 3.4. HashMap.get()方法主要做了什么？这个方法主要是干啥的？
//返回key对应的值，如果返回为null，可能是值为空也可能是key不存在，如需判断是哪种情况可用containsKey()判断
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)
//如果是红黑树则通过getTreeNode获取
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;
}
至此HashMap1.8的核心方法已经分析结束了，接下来我们针对1.7和1.8的差异进行针对性对比。
4. HashMap 1.7 / 1.8差异分析
| 差异种类 | HashMap 1.7 | HashMap 1.8 |
|---|---|---|
| 数据结构 | 数组+链表 | 数组+链表+红黑树，当链表lenth>8则转换为红黑树，在resize()后，所有数据位置会重新计算，如果红黑树的元素个数<=6则转回链表 |
| 初始化方式 | inflateTable() | resize() |
| hash计算方式 | hashCode() , 扰动处理（4次位运算+5次异或运算） | hashCode() , 扰动处理（1次位运算+1次异或运算） |
| 数据存放方式 | 无冲突时存放数组，有冲突时存放单链表 | 无冲突时存放数组，有冲突存放链表（长度<8）或红黑树(长度>=8) |
| 数据插入方式 | 头插法（将原有数据后移一位） | 尾插法（直接插入链表或红黑树尾部） |
| 扩容后存储位置的计算方式 | 全部重新计算（hashCode()>扰动处理>&(lenth-1)） | 原位置/原位置+老table.lenth |
| 扩容后转移老数据的方式 | 头插法（原数据后移一位，会出现逆序，环形链表，死循环等问题） | 尾插法（不会出现逆序，环形列表，死循环等问题） |
| 扩容时机 | 先判断>阀值扩容后再插入 | 先插入数据然后判断>阀值扩容 |
| 旧数据转移时的位置计算时机 | 单独计算 | 转移时统一计算 |
补充一点小知识
-
哈希表如何解决Hash冲突？
哈希表如何解决Hash冲突.jpg
-
为什么HashMap具备下述特点：键-值（key-value）都允许为空、线程不安全、不保证有序、存储位置随时间变化？
1.jpg
-
为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键
1.jpg
-
HashMap 中的 key若 Object类型， 则需实现哪些方法？
1.jpg
