- 一、为什么会有HashMap?
- 二、HashMap是什么?
- 1、为什么是 0.75 这个值呢？
- 追问1、加载因子什么时候适合减少，什么时候适合增加？【优化】
- 2、什么办法来解决因链表过长导致查询时间复杂度高的问题呢？
- 追问1：为什么红黑而非平衡树？
- 追问2：红黑树具体结构及实现，红黑树与查找树的区别体现
- 3、影响 HashMap 性能的因素？
- 4、HashMap 的 key 需要满足什么条件？
- 追问1：HashMap 允许 key/value 为 null， 但最多只有一个。 为什么？
- 追问2：如果重写了equals()，不重写hashCode()会发生什么？
- 三、HashMap怎么实现的?
- 1、HashMap的哈希函数怎么设计的？
- 追问1：初始容量为什么设置为 2 的整数次幂？【(n - 1) & hash 】
- 追问2：如果没使用 hash() 方法计算 hashCode，直接使用对象的 hashCode 值，会出现什么问题呢？
- 追问3：为什么获取下标时用按位与 &，而不是取模 %？
- 2、HashMap get和put源码，
- 3、JDK1.8后对HashMap的改进（*3）
- 追问1：为什么要做这几点优化？
- 追问2：1.8 中的 HashMap 是否线程安全？
- 追问3：什么时机执行 resize()？
- 追问4：resize() 如何实现的？
- 四、延申
- 1、HashMap 1.7 VS 1.8
- 追问1：为什么HashMap线程不安全？
- 2、你平常怎么解决这个线程不安全的问题？
- 3、那你知道ConcurrentHashMap的分段锁的实现原理吗？
- 四、参考
链表法查找时间是
O
(
1
+
n
)
O(1+n)
O(1+n) [n - 链表长度]，0.75是对时间和空间的平衡。
1）加载因子越大，空间利用就越充分，但链表长度越长，查找效率也就越低。
2）加载因子太小，数据过于稀疏，空间严重浪费，当然，时间查找会更高。
查询 *** 作频繁可适当地减少加载因子；内存利用率要求高可适当增加加载因子。
- 补充：若能预知存储数据量，设置初始容量 = 预知数据量 / 加载因子。可减少resize() *** 作，提高效率。
引入红黑树数据查询效率，当链表长度超过threshold（默认8）会将链表转换为红黑树，值得注意的是新增由于存在左旋、右旋效率会降低。
追问1：为什么红黑而非平衡树？不需要因为新增节点频繁调整二叉树。……
追问2：红黑树具体结构及实现，红黑树与查找树的区别体现……
3、影响 HashMap 性能的因素？- 1）负载因子与边界值。前者涉及时间与空间的平衡，后者可能会涉及resize()影响性能。
- 2）哈希值。理想情况是均匀散列。一般 HashMap 使用 String 类型作为 key，而 String 类重写了 hashCode 函数。
答：必须重写 hashCode 和 equals 方法， 常用的 String 类实现了这两个方法。
追问1：HashMap 允许 key/value 为 null， 但最多只有一个。 为什么？答： 如果 key 为 null 会放在第一个桶（即下标 0）位置， 而且是在链表最前面（即第一个位置）。
追问2：如果重写了equals()，不重写hashCode()会发生什么？默认的equals()与hashCode()比较的是内存地址，不重写会认为hashCode()不一样，就认为是不同对象，不需要再进行equals()比较，效率和正确性都会有问题。
HashMap()比较顺序： 1、hashCode()比较结果不相同，则说明是不同对象； 2、hashCode()比较结果相同，则需要再进行equals()比较，相等则说明相同，否则不同。三、HashMap怎么实现的? 1、HashMap的哈希函数怎么设计的？
先拿到 key 的hashCode（32位int值），然后让高16位和低16位进行异或 *** 作，然后 (n-1) & hash找到桶位置。
// 补充：源码分析键值对添加
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
// 【1】return code1 = key.hashCode()
// 【2】hash(code1) 计算出 hash 值
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //h>>>16：无符号右移16位
}
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 【3】putVal 方法中 (n - 1) & hash 决定 Node 存储位置。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
追问1：初始容量为什么设置为 2 的整数次幂？【(n - 1) & hash 】
为了服务hash到桶位置的算法 — (n - 1) & hash 。2的幂次方减1后每一位都是1，让数组每一个位置都能添加到元素。如果不是，那计算结果总有一位总0，对应下标位置总是空的。
如果初始化设置不是2的幂次方，HashMap也会调整到比初始化值大 & 最近的2的幂作为capacity。
追问2：如果没使用 hash() 方法计算 hashCode，直接使用对象的 hashCode 值，会出现什么问题呢？碰撞很严重，不是好的哈希算法。但若将 hashCode 二进制值对半切开，并且使用位异或运算，就能避免大量碰撞。简而言之，尽量打乱 hashCode 真正参与运算的低 16 位。
补充：没采用hash()的情况，直接用hashCode计算 假设添加两个对象 a 和 b，数组长度是16，公式(n - 1) & hash。 -> (16-1)＆a.hashCode 和 (16-1)＆b.hashCode， 0000000000000000000000000001111 [15的二进制] 1000010001110001000001111000000 [假设A] 0111011100111000101000010100000 [假设B] = 0。 哈希结果太让人失望了。追问3：为什么获取下标时用按位与 &，而不是取模 %？
& 效率更高。
如果
l
e
n
g
t
h
=
2
n
length = 2^n
length=2n，
那么
x
x
x %
l
e
n
g
t
h
=
length =
length=
x
x
x &
(
l
e
n
g
t
h
−
1
)
(length-1)
(length−1)
即：当长度为
2
n
2^n
2n 时，模运算% 可变换为按位与 & 运算。
……
3、JDK1.8后对HashMap的改进（*3）- 1）数据结构。从 数组+链表 改成 数组+链表或红黑树。
- 2）链表插入。从 头插法 改成 尾插法。
- 3）扩容优化。
- [1]-索引定位：1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；
- [2]-判断顺序：1.7先判断是否需要扩容，再插入；1.8先插入，再判断是否需要扩容。
-
1）数据结构。降低链表访问时间复杂度，从 O ( n ) O(n) O(n)降到 O ( l o g n ) O(logn) O(logn)。
-
2）链表插入。头插改变原本元素顺序，并发场景会导致链表成环，而尾插不会。
-
3）扩容优化。
[1]索引定位：新扩容算法效率更高。高1位为0，索引没变；是1，索引变成“原位置+旧容量”。
[2]判断顺序：JDK1.7 中先进行扩容后进行插入，而在 JDK1.8 中是先进行插入后进行扩容。
-
JDK1.7 中：先扩容后插入
当你发现你插入的桶是不是为空，如果不为空说明存在值就发生了hash冲突，那么就必须得扩容，但是如果不发生Hash冲突的话，说明当前桶是空的（后面并没有挂有链表），那就等到下一次发生Hash冲突的时候在进行扩容，但是当如果以后都没有发生hash冲突产生，那么就不会进行扩容了，减少了一次无用扩容，也减少了内存的使用 -
JDK1.8 中：先插入后扩容
主要是因为对链表转为红黑树进行的优化，因为你插入这个节点的时候有可能是普通链表节点，也有可能是红黑树节点
如果是链表节点，是否达到了 链表转化为红黑树的阈值是8，如果没有那么就还可以继续插入。
如果是红黑树节点，需要看插入红黑树节点是否还能满足当前是红黑树的特性，如果还能继续满足即还没有达到扩容的临界条件。
1.8虽然解决了链表成环，但还有其他并发问题，比如：上秒 put 的值，下秒 get 的时候却不是刚 put 的值；因为 *** 作都没有加锁，不是线程安全的。
追问3：什么时机执行 resize()？答：桶里Node 数量超过边界值，HashMap 会调用 resize() 方法重新分配 table 数组。
补充： 1、扩容2倍。 2、边界值[threshold] = 桶数量*负载因子[loadFactor]。不设置参数情况下，默认值为12。 3、resize()会导致HashMap数组复制，迁移到另一块内存，从而影响 HashMap 效率。追问4：resize() 如何实现的？
实现整体逻辑：若Node数量>threshold，就会扩容；扩容后判断高位是否为1，是1，则newPos=oldPos+oldCapacity；否则不变。
源码：……
4、HashMap的哈希函数怎么设计的？ - 追问1：初始容量为什么设置为 2 的整数次幂？【(n - 1) & hash 】 - 追问2：如果没使用 hash() 方法计算 hashCode，直接使用对象的 hashCode 值，会出现什么问题呢？ - 追问3：为什么获取下标时用按位与 &，而不是取模 %？ 6、HashMap get和put源码 5、JDK1.8后对HashMap的改进（*3） - 追问1：为什么要做这几点优化？ - 追问2：1.8 中的 HashMap 是否线程安全？ - 追问3：什么时机执行 resize()？ - 追问4：resize() 如何实现的？四、延申 1、HashMap 1.7 VS 1.8
追问1：HashMap/HashTable/ConcurrentHashMap数据结构，底层（*4），如何保证线程安全，怎么实现（*3）
……
1.7中transfer()链表使用头插法，多线程情况下，会成环；
1.8中putVal()若桶为空，多线程 *** 作，值会出现覆盖情况。
HashTable、Collections.synchronizedMap及ConcurrentHashMap都是实现线程安全的Map。
- 1）HashTable：直接在方法上加synchronized来锁住整个数组，粒度比较大。
- 2）Collections.synchronizedMap：Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现。
- 3）ConcurrentHashMap：使用分段锁，降低锁粒度，让并发度大大提高。
ConcurrentHashMap成员变量使用volatile修饰，免除指令重排序，同时保证内存可见性，另外使用CAS *** 作和synchronized结合实现赋值 *** 作，多线程 *** 作只会锁住当前 *** 作索引的节点。
如下图，线程A锁住A节点所在链表，线程B锁住B节点所在链表，互不干涉。
1、07 | 深入浅出HashMap的设计与优化
2、一个 HashMap 能跟面试官扯上半个小时
3、到底什么是 HashMap？
4、jdk 源码系列之 HashMap
5、HashMap 源码分析（JDK1.8）
6、由HashMap哈希算法引出的求余%和与运算&转换问题
7、【1】JDK8 HashMap扩容优化
8、HashMap 链表插入方式 → 头插为何改成尾插 ?
9、HashMap1.7 vs 1.8
- HashMap线程不安全
1、HashMap的transfer()方法（jdk1.7）
2、Hashmap头插法死循环
3、HashMap线程不安全的体现
4、深入解读HashMap线程安全性问题
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）