HashMap 的数据结构
在 Java 中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址 容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。上面我们提到过， 常用的哈希函数的冲突解决办法中有一种方法叫做链地址法，其实就是将数组和链表组合在 一起，发挥了两者的优势，我们可以将其理解为链表的数组。
image.png
我们可以从上图看到，左边很明显是个数组，数组的每个成员是一个链表。该数据结构 所容纳的所有元素均包含一个指针，用于元素间的链接。我们根据元素的自身特征把元素分 配到不同的链表中去，反过来我们也正是通过这些特征找到正确的链表，再从链表中找出正 确的元素。其中，根据元素特征计算元素数组下标的方法就是哈希算法，即本文的主角 hash()函数（当然，还包括 indexOf()函数）。
哈希类集合的三个基本存储概念
- table
存储所有节点数据的数组 - slot
哈希槽。即table[i]这个位置 - bucket 哈希桶。
table[i]上所有元素形成的表或树的集合。
扩容 负载因子 0.75
length table 数组的长度
size 成功通过put方法添加到HashMap中的所有元素的个数
hashCode Object.hashCode()返回的int值，尽可能地离散均匀分布
hash Object.hashCode()与当前集合的table.length进行位运算的结果，以确定哈希槽的位置
HashMap 高并发，新增对象丢失
key value 允许为null
JDK1.7 数组+链表
JDK1.8 数组+链表+红黑树
JDK1.7 的死链问题
/**
* HashMap(JDK7) 死链.
* <p>
* 启动10万个线程，以System.nanoTime()返回的Long值为Key,自定义对象EasyCoding为Value,运行环境是JDK7。
*
* @author liusj
* @date 2020/12/11
*/
public class HashMashEndlessLoop {
private static HashMap<Long, EasyCoding> map = new HashMap<>();
public static void main(String[] args) {
for (int i = 0; i < 10000; i++) {
(new Thread() {
@Override
public void run() {
map.put(System.nanoTime(), new EasyCoding());
}
}).start();
}
}
}
class EasyCoding {
}
问题
1. HashMap 和 ConcurrentHashMap 的区别？
ConcurrentHashMap 和 HashMap 的实现方式不一样，虽然都是使用桶数组实现 的，但是还是有区别，ConcurrentHashMap 对桶数组进行了分段，而 HashMap 并没有。 ConcurrentHashMap 在每一个分段上都用锁进行了保护。HashMap 没有锁机制。 所以，前者线程安全的，后者不是线程安全的。
2. HashMap 的容量、扩容
主要成员变量：
* transient int size
记录了 Map 中 KV 对的个数
* loadFactor
装载因子，用来衡量 HashMap 满的程度。loadFactor 的默认值为 0.75f（static final float DEFAULT_LOAD_FACTOR = 0.75f;）
* threshold
临界值，当实际 KV 个数超过 threshold 时，HashMap 会将容量 扩容，threshold＝容量*装载因子
* capacity
容量，如果不指定，默认容量是 16(static final int DEFAULT_I NITIAL_CAPACITY = 1 << 4;)
size 和 capacity
HashMap 中的 size 和 capacity 之间的区别其实解释起来也挺简单的。我们知道， HashMap 就像一个“桶”，那么 capacity 就是这个桶“当前”最多可以装多少元素，而 size 表示这个桶已经装了多少元素。
loadFactor和threshold
前面我们提到过，HashMap 有扩容机制，就是当达到扩容条件时会进行扩容，从 16 扩容到 32、64、128... 那么，这个扩容条件指的是什么呢？
其实，HashMap 的扩容条件就是当 HashMap 中的元素个数（size）超过临界值（ threshold）时就会自动扩容。
在 HashMap 中，threshold = loadFactor * capacity。
loadFactor 是装载因子，表示 HashMap 满的程度，默认值为 0.75f，设置成 0.75 有一个好处，那就是 0.75 正好是 3/4，而 capacity 又是 2 的幂。所以，两个数的乘积都 是整数。
对于一个默认的 HashMap 来说，默认情况下，当其 size 大于 12(16*0.75)时就会触 发扩容。
总结
HashMap 中 size 表示当前共有多少个 KV 对，capacity 表示当前 HashMap 的容量是多少，默认值是 16，每次扩容都是成倍的。loadFactor 是装载因子，当 Map 中元素个数超过 loadFactor* capacity 的值时，会触发扩容。loadFactor* capacity 可以用 threshold 表示。
3. 为什么HashMap的默认容量设置成16
hash实现
具体实现上，由两个方法int hash(Object k)和int indexFor(int h,int length)来实现。
- hash: 该方法主要是将Object转换成一个整型
- indexFor: 该方法主要是将hash生成的整型转换成链表数组中的下标
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);
}
indexFor 方法其实主要是将 hashcode 换成链表数组中的下标。其中的两个参数 h 表示元素的 hashcode 值，length 表示 HashMap 的容量。那么 return h & (length-1) 是什么意思呢？
其实，他就是取模。Java 之所有使用位运算(&)来代替取模运算(%)，最主要的考虑就 是效率。
位运算(&)效率要比代替取模运算(%)高很多，主要原因是位运算直接对内存数据进行 操作，不需要转成十进制，因此处理速度非常快。
扩容
总结
HashMap 作为一种数据结构，元素在 put 的过程中需要进行 hash 运算，目的是计算出该元素存放在 hashMap 中的具体位置。
hash 运算的过程其实就是对目标元素的 Key 进行 hashcode，再对 Map 的容量进行 取模，而 JDK 的工程师为了提升取模的效率，使用位运算代替了取模运算，这就要求 Map 的容量一定得是 2 的幂。
而作为默认容量，太大和太小都不合适，所以 16 就作为一个比较合适的经验值被采用 了。
为了保证任何情况下 Map 的容量都是 2 的幂，HashMap 在两个地方都做了限制。
首先是，如果用户制定了初始容量，那么 HashMap 会计算出比该数大的第一个 2 的 幂作为初始容量。
另外，在扩容的时候，也是进行成倍的扩容，即 4 变成 8，8 变成 16。
4. 为什么建议设置 HashMap 的初始容量，设置多少合适
- 要设置HashMap的初始化容量
HashMap 有扩容机制，就是当达到扩容条件时会进行扩容。HashMap 的扩容条件 就是当 HashMap 中的元素个数（size）超过临界值（threshold）时就会自动扩容。在 HashMap 中，threshold = loadFactor * capacity。
所以，如果我们没有设置初始容量大小，随着元素的不断增加，HashMap 会发生多 次扩容，而 HashMap 中的扩容机制决定了每次扩容都需要重建 hash 表，是非常影响性能的。
- HashMap 初始化容量设置多少合适
这里我们可以参考 JDK8 中 putAll 方法中的实现的，这个实现在 guava（21.0 版本） 也被采用。
这个值的计算方法就是：
return (int) ((float) expectedSize / 0.75F + 1.0F);
比如我们计划向 HashMap 中放入 7 个元素的时候，我们通过 expectedSize / 0.75 F + 1.0F 计算，7/0.75 + 1 = 10 ,10 经过 JDK 处理之后，会被设置成 16，这就大大的 减少了扩容的几率。
Map<String, String> map = Maps.newHashMapWithExpectedSize(7);
参考书籍：《Java工程师成神之路》
网友评论