- 1Vue+element-plus展开/收回功能_elementplus作业书控制全部展开和全部关闭
- 2kafka如何保证消息的顺序性_kafka消息顺序性
- 3Git不同分支代码合并_git不同版本代码合并
- 4mumu配置_mumu模拟器如何安装ca证书
- 5【NLP】模型压缩与蒸馏！BERT的忒修斯船
- 6centos 中使用 kubekey 安装 k8s v1.22.12 支持 GPU 调用
- 7三大深度学习生成模型：VAE、GAN及其变种_vae gan transformer
- 8优雅的使用 Dockerfile 定制镜像_dockerfile指定镜像名称
- 9基于javaweb+mysql的ssm网上果蔬商城水果蔬菜商城系统(java+ssm+mysql+tomcat+jsp)
- 10通过城市名，实现按照A,B,C,D...排序
Java 8 HashMap 详解_java8 hashmap
赞
踩
1. HashMap 存储结构
1.1 HashMap 底层结构
JDK 1.8 的 HashMap 底层数据结构与 JDK1.7 时大致相同，主要为 数组+链表。它采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体。但在1.8 版本中如果链表元素数量达到 8 ， 就会尝试进行树化操作（如果数组长度小于 64， 则进行扩容操作，而不是树化操作），将链表转化为 红黑树结构。故 HashMap 数据结构可作如下总结：
- JDK 1.7： 数组+链表
- JDK 1.8： 数组+链表+红黑树
static final int MIN_TREEIFY_CAPACITY = 64; final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); // 如果数组长度小于 64， 则进行扩容操作，而不是树化操作 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
1.2 HashMap 为什么采用数组 + 链表
- 数组结构简单，利用元素 key的hash值对数组长度取模可以快速定位到数组下标 index，效率极高
- 链表是用来解决hash冲突问题，当出现 hashCode 值一样的情形，就在数组相应下标位置形成一条链表。这是解决hash冲突的链地址法
Reference: 解决hash冲突的四种方法：
- 链地址法
基本思想是将所有哈希地址为 i 的元素构成一个单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在链表中进行。链地址法适用于经常进行插入和删除情况。- 开放定址法
也称再散列法，基本思想是当关键字key的哈希地址p=H（key）出现冲突时，以p为基础产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。- 再哈希法
同时构造多个不同的哈希函数，当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key），直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。- 公共溢出区域法
将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
1.2 HashMap 数组结构可否被替代
能否用LinkedList 代替
- 答案是可以，但是用数组效率最高。 在HashMap中定位数组下标利用元素的key的哈希值对数组长度取模就可以，显然数组的查找效率比LinkedList高。
ArrayList底层是数组查找也快，能否用ArrayList
- 采用基本数组结构扩容机制可以自己定义，HashMap中数组扩容刚好是2的次幂，在做取模运算的效率高。而ArrayList的扩容机制是1.5倍扩容，默认容量为10，不利于高效定位。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍扩容，默认为10
......
}
- 1
- 2
- 3
- 4
- 5
- 6
1.3 HashMap 为何不直接使用红黑树
- 当元素小于8个时，做查询操作链表结构已经能保证查询性能。
- 当元素大于8个的时候，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。因为红黑树需要进行左旋，右旋，变色操作来保持平衡，这些都是性能损耗。
因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑是浪费性能。
1.4 HashMap 红黑树什么时候退化为链表
从源码看，节点数量为6的时候退转为链表,中间有个差值7可以防止链表和树之间频繁的转换。如果设计成链表个数超过8则链表转换成树结构，小于8则树结构转换成链表，如果一个HashMap不停插入删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率很低。
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
......
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map); // 解除树化
......
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
2. HashMap 存取过程
2.1 HashMap put()方法
存储元素的过程如下：
-
对key 做hash() 运算，获取其hashCode 值, 可看到有对 key==null 返回 0 的处理，这就是HashMap允许 null 键的原因。 另外
hash()中 将 hashCode 与 hashCode 无符号右移16位的值进行异或处理，是出于减少哈希冲突的目的，因为这个操作把原 hashCode 中没有使用到的高位数据也利用起来参与到运算中了。Hash函数是指把一个大范围映射到一个小范围，目的是节省空间，使得数据容易保存。比较出名的有MurmurHash、MD4、MD5等等。
static final int hash(Object key) { int h; // 此处 h与其低16位 异或 操作，目的是减少index定位时的 hash碰撞 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }- 1
- 2
- 3
- 4
- 5
-
懒加载策略，如果当前 Entry[] 数组尚未初始化，则调用 resize（）方法初始化。
-
使用 hash（）运算后的值与【数组长度-1】与运算 后定位到数组 index，如果该位置上没有元素则插入。
-
如果碰撞了，【1】首先通过 equals（）比较 key，如相同则使用新的 value 覆盖旧 value，从此可知 HashMap 只允许一个Key为null的键值对；【2】不符合前一条则首先判断碰撞的元素是否是树节点，即该位置链表是否已经转化成红黑树，如是则将新元素转化为 树节点插入；【3】不符合前两条，遍历该数组下标的链表，将新元素添加到链表尾部后判断链表长度是否达到 8，达到 8 则将链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作，遍历过程中若发现 key 已经存在直接覆盖 value 即可。
-
插入成功后，判断数组实际存在的键值对数量size是否超过了最大容量threshold，如果超过则进行扩容。
public V put(K key, V value) { 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; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { 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; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); 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
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
2.2 HashMap get()方法
获取value的过程也很简单：
-
对key 做hash() 运算,获取用于定位数组下标的值。
-
使用 hash（）运算后的值与【数组长度-1】与运算 后定位到数组下标index，取该位置上第一个节点 first，如其直接命中则直接返回。
-
如果有冲突，则通过key.equals(k)去查找对应的Entry：若为树，则在树中通过key.equals(k)查找，O(logn)；如果是链表，则在链表中通过key.equals(k)查找，O(n)。
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } 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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
3. HashMap 容量相关
3.1 HashMap 初始化容量
HashMap默认容量为 16，最大容量为 1<<30 。扩容负载因子为 0.75，也就是默认容量下数组中实际存储的元素数量达到 16 * 0.75 = 12，就会触发扩容。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
- 1
- 2
- 3
一般建议使用 HashMap 的时候指定初始容量大小，因为随着元素的不断增加，如果实际容量与初始容量相差太大，HashMap会发生多次扩容，而其扩容机制决定了每次扩容都需要重建hash表，非常影响性能。
另外即便通过 HashMap(int initialCapacity) 设置初始容量的时候，HashMap也不一定会直接采用传入的数值，而是经过计算，得到一个新值，目的是提高hash的效率。 从以下代码看，经过无符号右移和按位或运算, HashMap的容量最终会被设置成 大于传入参数的最小的2的次幂（7–>8, 10–>16）。
static final int tableSizeFor(int cap) {
int n = cap - 1; // 参数值 -1 是为了处理传入参数值恰好是 2 的次幂的情况
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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
3.2 HashMap 扩容为什么是2的次幂
HashMap为了存取高效就要尽量减少碰撞，也就是尽量把数据分配均匀，每个index下标上的链表(也可能是红黑树)长度需要大致相同, 这个算法实际就是取模，hash%length。
但是取模运算不如位移运算快。因此源码中优化为 hash()&(length-1),也就是hash%length 等价于 hash()&(length-1).
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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) { // 注意，此处即为取模定位 index
......
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
之所以取数组长度为 2 的n 次方,是因为2的n次方用二进制表示实际就是1后面n个0，而2的n次方-1，实际就是n个1。
- 例如长度为8时候，3&(8-1)–>(11 & 111)=3, 2&(8-1)–>(10 & 111)=2 ，下标不同，不碰撞。
- 而长度为5的时候，3&(5-1)=0, 2&(5-1)=0，都在0上，出现碰撞了。
所以，保证容积是2的n次方，是为了保证在做 hash&(length-1)的时候，每一位都能&1 ，也就是和1111……1111111进行与运算, 尽量减少哈希冲突.
3.3 HashMap 扩容机制
HashMap 扩容为原来2倍，所以链表中节点的位置要么是在数组原位置，要么是在数组原位置再移动2次幂的数组位置，且链表元素的顺序不变。
- JDK1.7中 HashMap旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置。1.8的优化解决了 1.7 版本 HashMap多线程扩容出现链表中两个节点 next 指针互相指向对方的 死循环（HashMap Infinite Loop）问题。
以下代码中已经添加了注释，JDK1.8中HashMap 不需要像JDK1.7的实现那样重新计算hash值，而是复用原 hash 值，将其与原容量进行与操作，进而确定其数组下标是否需要改变。
- 例如原容量 oldCap = 16，二进制表示为： 00001 0000
则 key1=0001 1001, key2 = 0000 1001, 扩容前两个 key&(oldCap-1) 都在下标 9 位置
扩容时 key1&oldCap = 0001 0000=16 下标变化, key2&oldCap=0 下标不变
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; } // 没超过最大值，扩充为原来的2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } ...... threshold = newThr; @SuppressWarnings({"rawtypes"，"unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { // 把每个bucket都移动到新的buckets中 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { ...... else { // 重点，重新处理链表节点位置代码块 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // 复用原 hash 值与 原容量与操作，若原容量为oldCap = 16 = 00001 0000 // 则 key1=0001 1001, key2 = 0000 1001, 扩容前两个[key&(oldCap-1)]都 // 在下标 9 位置 // 扩容时 key1&oldCap = 0001 0000=16 下标变化, key2&oldCap=0 下标不变 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); // 放到new bucket里 位置与原索引相同 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 放到new bucket里，下标位置为 原索引 + 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
4. HashMap 使用指南
4.1 使用不可变类作为HashMap的Key
一般用Integer、String这种不可变类当HashMap当key，最常用String。
- 因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。
- HashMap 存取值的时候要用到 equals()和 hashCode()方法，键对象正确地重写这两个方法是非常重要的，通常不可变类已经很规范的覆写了hashCode()以及equals()方法。
使用可变类（如List）作为 HashMap 的key 的问题
- 例如把List 作为键，那么当这个 List 对象添加删除元素的时候 hashcode可能发生改变， 这样可能会导致其在HashMap中数组 index下标定位不准，也就无法取出存储的value。
4.2 实现自定义类作为HashMap的Key
主要涉及两个关键点：
- 重写 hashcode 和 equals 方法
- 设计一个不变类
4.2.1 重写 hashcode 和 equals 方法
需要遵守以下四个原则：
-
两个对象相等，hashcode一定相等
-
两个对象不等，hashcode不一定不等
-
hashcode相等，两个对象不一定相等
-
hashcode不等，两个对象一定不等
4.2.2 如何设计一个不变类
-
类添加final修饰符，保证类不被继承
如果类可被继承就会破坏类的不可变性机制，只要子类覆盖父类的方法（如equals 和 hashCode）并且子类可以改变成员变量值，那么一旦子类以父类的形式出现时，不能保证当前类是否可变。 -
所有成员变量必须私有，并且加上final修饰
通过这种方式保证成员变量不可改变。但只做到这一步还不够，因为对象成员变量有可能在外部改变其值，所以第5点弥补这个不足。 -
不提供改变成员变量的方法，包括setter
避免通过其他接口改变成员变量的值，破坏不可变特性。 -
在getter方法中，不要直接返回对象本身，而是克隆对象并返回对象的拷贝
这种做法也是防止对象外泄，防止通过getter获得内部可变成员对象后对成员变量直接操作，导致成员变量发生改变。 -
通过构造器初始化所有成员，进行深拷贝(deep copy)
如果构造器传入的对象直接赋值给成员变量，还是可以通过对传入对象的修改达到改变内部变量的效果。例如：
public final class Table {
private final int[] myArray;
public Table (int[] array) {
this.myArray = array; // myArray和array指向同一块内存地址
//修改传入的array对象的值可改变myArray内部的值
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
为了保证内部的值不被修改，可采用深度copy来创建一个新内存保存传入的值。正确做法：
public final class Table {
private final int[] myArray;
public Table (int[] array) {
this.myArray = array.clone();
}
}
- 1
- 2
- 3
- 4
- 5
- 6
