-
9.0 HashMap底层原理及部分源码分析
0.序言
HashMap 在JDK1.7版本时底层数据结构是数组+链表，但是1.7时HashMap的并发扩容会导致死循环；JDK1.8时底层的数据结构变成数组+链表+红黑树，修改了并发扩容逻辑，并且提升了HashMap的性能。
0.1HashMap 重要属性
DEFAULT_INITIAL_CAPACITY = 1 << 4; Hash 表默认初始容量 8
MAXIMUM_CAPACITY = 1 << 30; 最大 Hash 表容量
DEFAULT_LOAD_FACTOR = 0.75f；默认扩容阈值比率(计算扩容阈值=阈值比率*HashMap容量)
TREEIFY_THRESHOLD = 8；链表转红黑树阈值
UNTREEIFY_THRESHOLD = 6；红黑树转链表阈值
MIN_TREEIFY_CAPACITY = 64；链表转红黑树时 hash 表最小容量阈值，达不到优先扩容1.0 JKD1.7HashMap组成结构及源码分析
HashMap 底层数据结构是数组+链表：数组就是存放Map 键值对的位置，当Map 中出现相同的Hashcode值时，称作hash碰撞，这时相同位置的值会形成一个链表放在数组的特定位置。如下图
1.1如何确定key在数组的位置
源码如下：
public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); // 获取 key 对应的整型 hash值 int hash = hash(key); // 再将这个hash值转换为小于这个数组的整型值 i，然后将节点插入数组i位置 int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
中的 hash 方法源码如下：
final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
不需要看懂，知道返回一个int 类型的hash值就可以了；怎么一个数值 中获取一个小于数组长度的int值呢？我们可能会想到直接对那个数值求余% (hash值%数组长度)，有实验可知求余运算效率低，HashMap是不会用的，我看下它到底是怎么计算的呢？源码如下用了&运算。
/** * Returns index for hash code h. * */ static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
1.2 HashMap的容量
为了保HashMap的数组长度必须是2的N次方，HashMap在初始化时的长度为11，数组的长度就是11吗？不是11是16，为什么呢？看以下源码
public V put(K key, V value) { // 如果数组为空，初始化数组，而不是在HashMap的构造方法中进行的的 if (table == EMPTY_TABLE) { //初始化数组方法 inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
初始化方法源码：
private void inflateTable(int toSize) { // 找到第一个大于等于初始化传入的HashMap长度 toSize 的 2的 N次方的值 int capacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; initHashSeedAsNeeded(capacity); } private static int roundUpToPowerOf2(int number) { // assert number >= 0 : "number must be non-negative"; return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; } // 巧妙的通过或运算和位移运算得出第一个大于i的 2 的 N 的数值 public static int highestOneBit(int i) { // HD, Figure 3-1 i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i - (i >>> 1); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
1.3 HashMap 扩容
当存入的数据长度 大于 数组长度*阈值率，HashMap自动扩容，扩容后数据的迁移逻辑如下：
/** * Transfers all entries from current table to newTable. */ void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; // 遍历旧数组 for (Entry<K,V> e : table) { // 遍历链表 while(null != e) { Entry<K,V> next = e.next; //第一行 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } // 重新计算当前节点在新数组中的位置 int i = indexFor(e.hash, newCapacity);//第二行 // 修改节点的指向 e.next = newTable[i];//第三行 newTable[i] = e;// 第四行 // 下一次循环 e = next; //第五行 } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
重点看注释写第N行的代码，这样逻辑更加清晰了。
第一行:记录oldhash表中e.next；
第二行:rehash计算出数组的位置(hash表中链表的位置)
第三行:e要插入链表的头部，所以要先将e.next指向newhash表中的第一个元素；
第四行:将e放入到newhash表的头部
第五行:转移e到下一个节点，继续循环下去；1.3.1 单线程扩容
假设:hash算法就是简单的key与lenath(数组长度)求余。hash表长度为2，如果不扩容，那么元素kev为3.5.7按照计算(key%table.length)的话都应该碰撞到table[1]上。
扩容:hash表长度会扩容为4重新hash，key=3会落到table[3]上(3%4=3)，当前e.next为key(7)，继续while循环重新hash，key=7会落到table[3上(7%4=3)，产生碰撞，这里采用的是头插入法，所以key=7的Entry会排在key=3前面(这里可以具体看while语句中代码)当前e.next为key(5),继续 while循环重新hash，kev=5会落到table[1]上(5%4=3)，当前e.next为null，跳出while循环，resize结束。途中竖着是数组，横着的是链表
1.3.2多线程扩容
多线程同时put的情况，然后同时进入transfer方法中：假设这里的两个线程同时执行了put操作，并进入了transfer如下环节。
while(null != e) { Entry<K,V> next = e.next; //第一行，线程1执行到此被任务调度挂起 // 重新计算当前节点在新数组中的位置 int i = indexFor(e.hash, newCapacity);//第二行 // 修改节点的指向 e.next = newTable[i];//第三行 newTable[i] = e;// 第四行 e = next; //第五行 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
从上面的图我们可以看到，因为线程1的e指向了key(3)，而next指向了key(7)，在线程2rehash后，就指向了线程2 rehash后的链表。然后线程1被唤醒了:
1.执行e.next=newTablelil，干是kev(3)的next指向了线程1的新Hash表，因为新Hash表为空，所以e.next=null
2.执行newTable[i]=e，所以线程1的新Hash表第一个元素指向了线程2新Hash表的key(3)。好了，e处理完毕。
3.执行e=next，将e指向next，所以新的e是key(7)然后该执行key(3)的next节点key(7)了:
1.现在的e节点是key(7)，首先执行Entry
2.执行enext=newTable]，于是key(7)的next就成了key(3)
3.执行newTable[]=e，那么线程1的新Hash表第一个元素变成了key(7)
4.执行e=next，将e指向next，所以新的e是key(3)此时状态为:
然后又该执行key(7)的next节点key(3)了:
1.现在的e节点是kev(3)，首先执行Entrynext=enext那么next就是null
2.执行enext=newTable[i]，于是key(3)的next就成了key(7)
3.执行newTable[i]=e，那么线程1的新Hash表第一个元素变成了kev(3)
4.执行e=next，将e指向next，所以新的e是key(7)
很明显，出现了环形的死循环。
1.4 Jdk1.8 HashMap的优化
优化了扩容逻辑，避免了死循环；添加红黑树，在链表数据量大时查询速度提升。
1.4.1 扩容优化
扩容的关键代码：
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; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } 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); } 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; if (oldTab != null) { 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 { // preserve order // 定义了四个指针 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; // 开始扩容 do { next = e.next; // 节点的hash值与 旧数组的容量相与，oldCap 是2的N次方 // 一个数和 2的N次方相与时，结果只能是0或 oldCap 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; } // 高位节点下标增加 oldCap if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
这里定义了四个指针，将某个链表分为两部分，链表节点和数组长度相与的结果作为分隔，等于0的放在以loHead为头节点的链表中，等1的放在以hiHead为头节点的链表中。如下图:
这种移动方式没有改变节点关系的方向，所以并发之下也没有问题 。
-
相关阅读:
（六）Vue之MVVC
C++ - 封装 unordered_set 和 unordered_map - 哈希桶的迭代器实现
【JAVAEE框架】Mybatis常用操作（CRUD）
MySQL 数据库 JDBC编程
Live800:三点自测，你的客服系统该升级了吗？
十一黄金周12306 抢票开源脚本登上热榜！探寻Python自动化与数据交互的无限可能！
GDB调试简单介绍
如何做架构设计？
初识Python
SpringCloud学习（七）----- 使用Feign调用别的微服务的方法
- 原文地址：https://blog.csdn.net/Mao_yafeng/article/details/127433153
