HashMap

发表于

重要概念

  • Capacity HashMap当前长度，为2的N次幂
  • LoadFactor 负载因子 一般为0.75
  • threshold Capacity * LoadFactor

JDK8的hashmap改进

采用了位桶+链表/红黑树的方式，当某个位桶长度超过8时，链表转红黑树

采用了head和tail来保证链表顺序和之前一致，之前采用的rehash会倒置链表元素。但是还是会有数据丢失（并发情况），所以并发情况还是推荐使用ConcurrentHashMap

何时需要扩容

HashMap.Size >= Capacity * LoadFactor，扩容为原先的2倍大小

hash值计算

扩容步骤Rehash(JDK8 之前)

通过单词意思可以知道这是个重新hash计算的过程

JDK8之后存在的并发问题

  • put的时候导致多线程数据不一样

假如A线程计算出要落到hash桶的索引i，然后进入了睡眠，这个时候B线程，计算出了和A线程同样的hash桶索引i，然后B线程插入了数据在索引i，此时A线程苏醒，它还以为索引i中并没有数据，所以插入了数据在索引i，这样就覆盖了B线程在索引i插入的数据

  • 触发fail-fast

线程A在迭代，线程B在插入删除操作，会抛出异常java.util.ConcurrentModificationException

类似于直接使用foreach迭代数组，边迭代边删除，一样会报错java.util.ConcurrentModificationException(并发修改异常)因为使用foreach时，会创建两个线程，一个用来迭代数组为线程A，一个用来新增删除为线程B，B每次检查A线程中元素个数是否和自己相同，不同则抛出异常

此时需要使用Iterator迭代器，即可解决边迭代边增删问题

1
2
3
4
5
6
7
8
Iterator it = list.iterator();
while(it.hasNext()){
    Object ele = it.next();
    if ("B".equals(ele)) {
        //list.remove(ele);//错误,不能使用
        it.remove();
    }
}
  • 并发扩容数据丢失

如果有多个线程同时发现需要扩容，但是最终只有一个线程扩容后的数组会赋给table

赏个🍗吧
0%