← 返回目录

5、HashMap 有了解么,它的底层实现,为什么线程不安全?

第 5 / 10 卷日期:

int binarySearch(List<? extends Comparable<? super T>> list, T key) {

if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)

return Collections.indexedBinarySearch(list, key);

else

return Collections.iteratorBinarySearch(list, key);

}

ArrayList 实现了 RandomAccess 接口,而 LinkedList 没有实现。为什么呢?我觉得还是和底层数据结构有关! ArrayList 底层是数组,而 LinkedList 底层是链表。数组天然支持随机访问,时间复杂度为 O(1),所以称为

快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素,时间复杂度为 O(n),所以不支持快速随机访问。 ArrayList 实现了 RandomAccess 接口,就表明了他具有快速随机访问功能。 RandomAccess 接口只是标

识,并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的!

5、HashMap 有了解么,它的底层实现,为什么线程不安全?

HashMap 主要用来存放键值对,它基于哈希表的 Map 接口实现,是常用的 Java 集合之一,是非线程安全的。

HashMap 可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个

JDK1.8 之前 HashMap 由数组+链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于等于阈

值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。

HashMap 默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。并且, HashMap 总是使用 2 的幂作为哈希表的大小。

JDK1.7 及之前版本,在多线程环境下, HashMap 扩容时会造成死循环和数据丢失的问题。

数据丢失这个在 JDK1.7 和 JDK 1.8 中都存在,这里以 JDK 1.8 为例进行介绍。

JDK 1.8 后,在 HashMap 中,多个键值对可能会被分配到同一个桶(bucket),并以链表或红黑树的形式存储。

多个线程对 HashMap 的 put 操作会导致线程不安全,具体来说会有数据覆盖的风险。

举个例子:

两个线程 1,2 同时进行 put 操作,并且发生了哈希冲突(hash 函数计算出的插入下标是相同的)。

不同的线程可能在不同的时间片获得 CPU 执行的机会,当前线程 1 执行完哈希冲突判断后,由于时间片耗尽挂起。线程 2 先完成了插入操作。

随后,线程 1 获得时间片,由于之前已经进行过 hash 碰撞的判断,所有此时会直接进行插入,这就导致线

return putVal(hash(key), key, value, false, true);

}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) {

// ...

// 判断是否出现 hash 碰撞

// (n - 1) & hash 确定元素存放在哪个桶中,桶为空,新生成结点放入桶中(此时,这个结点是放在数组中)

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null);

// 桶中已经存在元素(处理hash冲突)

else {

// ...

}

还有一种情况是这两个线程同时 put 操作导致 size 的值不正确,进而导致数据覆盖的问题:

  1. 线程 1 执行 if(++size > threshold) 判断时,假设获得 size 的值为 10,由于时间片耗尽挂起。
  2. 线程 2 也执行 if(++size > threshold) 判断,获得 size 的值也为 10,并将元素插入到该桶位中,并将 size

的值更新为 11。

  1. 随后,线程 1 获得时间片,它也将元素放入桶位中,并将 size 的值更新为 11。
  2. 线程 1、2 都执行了一次 put 操作,但是 size 的值只增加了 1,也就导致实际上只有一个元素被添加到了

HashMap 中。

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) {

// ...

// 实际大小大于阈值则扩容

if (++size > threshold)

resize();

// 插入后回调

afterNodeInsertion(evict);

return null;

}

全站分卷索引 · 10 卷
  1. 11、Long 的长度和范围,为什么要减 1 ?
  2. 22、JAVA 异常的层次结构
  3. 33、JAVA 的集合类有了解么?
  4. 44、ArrayList 和 LinkedList 区别
  5. 55、HashMap 有了解么,它的底层实现,为什么线程不安全?
  6. 66、CoucurHashMap 和 HashTable
  7. 77、线程池有了解么,讲一下
  8. 89、MVCC 讲一下
  9. 911、Redis 有了解过么?zset 的底层数据结构?
  10. 10资料推荐