Java并发常见面试题总结(下)

Map(重要)

HashMap 和 Hashtable 的区别

  • 线程是否安全: HashMap 是非线程安全的,Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap 吧!);

  • 效率: 因为线程安全的问题,HashMap 要比 Hashtable 效率高一点。另外,Hashtable 基本被淘汰,不要在代码中使用它;

  • 对 Null key 和 Null value 的支持: HashMap 可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个;Hashtable 不允许有 null 键和 null 值,否则会抛出 NullPointerException

  • 初始容量大小和每次扩充容量大小的不同: ① 创建时如果不指定容量初始值,Hashtable 默认的初始大小为 11,之后每次扩充,容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。② 创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为 2 的幂次方大小(HashMap 中的tableSizeFor()方法保证,下面给出了源代码)。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。

  • 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)时,将链表转化为红黑树(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树),以减少搜索时间(后文中我会结合源码对这一过程进行分析)。Hashtable 没有这样的机制

  • 哈希函数的实现HashMap 对哈希值进行了高位和低位的混合扰动处理以减少冲突,而 Hashtable 直接使用键的 hashCode()

HashMap 中带有初始容量的构造函数:

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
     public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

下面这个方法保证了 HashMap 总是使用 2 的幂作为哈希表的大小

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    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;
}

HashMap 和 HashSet 区别

如果你看过 HashSet 源码的话就应该知道:HashSet 底层就是基于 HashMap 实现的。(HashSet 的源码非常非常少,因为除了 clone()writeObject()readObject()HashSet 自己不得不实现之外,其他方法都是直接调用 HashMap 中的方法

HashMapHashSet
实现了 Map 接口实现 Set 接口
存储键值对仅存储对象
调用 put()向 map 中添加元素调用 add()方法向 Set 中添加元素
HashMap 使用键(Key)计算 hashcodeHashSet 使用成员对象来计算 hashcode 值,对于两个对象来说 hashcode 可能相同,所以equals()方法用来判断对象的相等性

HashMap 和 TreeMap 区别

TreeMapHashMap 都继承自AbstractMap ,但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力

NavigableMap 接口提供了丰富的方法来探索和操作键值对:

  1. 定向搜索: ceilingEntry(), floorEntry(), higherEntry()lowerEntry() 等方法可以用于定位大于等于、小于等于、严格大于、严格小于给定键的最接近的键值对

  2. 子集操作: subMap(), headMap()tailMap() 方法可以高效地创建原集合的子集视图,而无需复制整个集合

  3. 逆序视图:descendingMap() 方法返回一个逆序的 NavigableMap 视图,使得可以反向迭代整个 TreeMap

  4. 边界操作: firstEntry(), lastEntry(), pollFirstEntry()pollLastEntry() 等方法可以方便地访问和移除元素

这些方法都是基于红黑树数据结构的属性实现的,红黑树保持平衡状态,从而保证了搜索操作的时间复杂度为 O(log n),这让 TreeMap 成为了处理有序集合搜索问题的强大工具

实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序,不过我们也可以指定排序的比较器。示例代码如下:

/**
 * @author shuang.kou
 * @createTime 2020年06月15日 17:02:00
 */
public class Person {
    private Integer age;
​
    public Person(Integer age) {
        this.age = age;
    }
​
    public Integer getAge() {
        return age;
    }
​
​
    public static void main(String[] args) {
        TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
            @Override
            public int compare(Person person1, Person person2) {
                int num = person1.getAge() - person2.getAge();
                return Integer.compare(num, 0);
            }
        });
        treeMap.put(new Person(3), "person1");
        treeMap.put(new Person(18), "person2");
        treeMap.put(new Person(35), "person3");
        treeMap.put(new Person(16), "person4");
        treeMap.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());
        });
    }
}

输出:

person1
person4
person2
person3

可以看出,TreeMap 中的元素已经是按照 Person 的 age 字段的升序来排列了

上面,我们是通过传入匿名内部类的方式实现的,你可以将代码替换成 Lambda 表达式实现的方式:

TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> {
  int num = person1.getAge() - person2.getAge();
  return Integer.compare(num, 0);
});

综上,相比于HashMap来说, TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力

HashSet 如何检查重复?

以下内容摘自我的 Java 启蒙书《Head first java》第二版:

当你把对象加入HashSet时,HashSet 会先计算对象的hashcode值来判断对象加入的位置,同时也会与其他加入的对象的 hashcode 值作比较,如果没有相符的 hashcodeHashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象,这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同,HashSet 就不会让加入操作成功

在 JDK1.8 中,HashSetadd()方法只是简单的调用了HashMapput()方法,并且判断了一下返回值以确保是否有重复元素。直接看一下HashSet中的源码:

// Returns: true if this set did not already contain the specified element
// 返回值:当 set 中没有包含 add 的元素时返回真
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

而在HashMapputVal()方法中也能看到如下说明:

// Returns : previous value, or null if none
// 返回值:如果插入位置没有元素返回null,否则返回上一个元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
...
}

也就是说,在 JDK1.8 中,实际上无论HashSet中是否已经存在了某元素,HashSet都会直接插入,只是会在add()方法的返回值处告诉我们插入前是否存在相同元素

HashMap 的底层实现

JDK1.8 之前

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值,然后通过 (n - 1) & hash 判断当前元素存放的位置(这里的 n 指的是数组的长度),如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash 值以及 key 是否相同,如果相同的话,直接覆盖,不相同就通过拉链法解决冲突

HashMap 中的扰动函数(hash 方法)是用来优化哈希值的分布。通过对原始的 hashCode() 进行额外处理,扰动函数可以减小由于糟糕的 hashCode() 实现导致的碰撞,从而提高数据的分布均匀性

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化,但是原理不变

static final int hash(Object key) {
      int h;
      // key.hashCode():返回散列值也就是hashcode
      // ^:按位异或
      // >>>:无符号右移,忽略符号位,空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

对比一下 JDK1.7 的 HashMap 的 hash 方法源码.

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
​
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法 ,JDK 1.7 的 hash 方法的性能会稍差一点点,因为毕竟扰动了 4 次

所谓 “拉链法” 就是:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可

JDK1.8 之后

相比于之前的版本, JDK1.8 之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构

我们来结合源码分析一下 HashMap 链表到红黑树的转换

1、 putVal 方法中执行链表转红黑树的判断逻辑。

链表的长度大于 8 的时候,就执行 treeifyBin (转换红黑树)的逻辑

// 遍历链表
for (int binCount = 0; ; ++binCount) {
    // 遍历到链表最后一个节点
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        // 如果链表元素个数大于TREEIFY_THRESHOLD(8)
        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;
}

2、treeifyBin 方法中判断是否真的转换为红黑树

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 判断当前数组的长度是否小于 64
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        // 如果当前数组的长度小于 64,那么会选择先进行数组扩容
        resize();
    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);
    }
}

将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树

HashMap 的长度为什么是 2 的幂次方

为了让 HashMap 存取高效并减少碰撞,我们需要确保数据尽量均匀分布。哈希值在 Java 中通常使用 int 表示,其范围是 -2147483648 ~ 2147483647前后加起来大概 40 亿的映射空间,只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。但是,问题是一个 40 亿长度的数组,内存是放不下的。所以,这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来要存放的位置也就是对应的数组下标

这个算法应该如何设计呢?

我们首先可能会想到采用 % 取余的操作来实现。但是,重点来了:“取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1) 的前提是 length 是 2 的 n 次方)。” 并且,采用二进制位操作 & 相对于 % 能够提高运算效率

除了上面所说的位运算比取余效率高之外,我觉得更重要的一个原因是:长度是 2 的幂次方,可以让 HashMap 在扩容的时候更均匀。例如:

  • length = 8 时,length - 1 = 7 的二进制位0111

  • length = 16 时,length - 1 = 15 的二进制位1111

这时候原本存在 HashMap 中的元素计算新的数组位置时 hash&(length-1),取决 hash 的第四个二进制位(从右数),会出现两种情况:

  1. 第四个二进制位为 0,数组位置不变,也就是说当前元素在新数组和旧数组的位置相同。

  2. 第四个二进制位为 1,数组位置在新数组扩容之后的那一部分。

这里列举一个例子:

假设有一个元素的哈希值为 10101100
​
旧数组元素位置计算:
hash        = 10101100
length - 1  = 00000111
& -----------------
index       = 00000100  (4)
​
新数组元素位置计算:
hash        = 10101100
length - 1  = 00001111
& -----------------
index       = 00001100  (12)
​
看第四位(从右数):
1.高位为 0:位置不变。
2.高位为 1:移动到新位置(原索引位置+原容量)。

⚠️注意:这里列举的场景看的是第四个二进制位,更准确点来说看的是高位(从右数),例如 length = 32 时,length - 1 = 31,二进制为 11111,这里看的就是第五个二进制位

也就是说扩容之后,在旧数组元素 hash 值比较均匀(至于 hash 值均不均匀,取决于前面讲的对象的 hashcode() 方法和扰动函数)的情况下,新数组元素也会被分配的比较均匀,最好的情况是会有一半在新数组的前半部分,一半在新数组后半部分

这样也使得扩容机制变得简单和高效,扩容后只需检查哈希值高位的变化来决定元素的新位置,要么位置不变(高位为 0),要么就是移动到新位置(高位为 1,原索引位置+原容量)

最后,简单总结一下 HashMap 的长度是 2 的幂次方的原因:

  1. 位运算效率更高:位运算(&)比取余运算(%)更高效。当长度为 2 的幂次方时,hash % length 等价于 hash & (length - 1)

  2. 可以更好地保证哈希值的均匀分布:扩容之后,在旧数组元素 hash 值比较均匀的情况下,新数组元素也会被分配的比较均匀,最好的情况是会有一半在新数组的前半部分,一半在新数组后半部分

  3. 扩容机制变得简单和高效:扩容后只需检查哈希值高位的变化来决定元素的新位置,要么位置不变(高位为 0),要么就是移动到新位置(高位为 1,原索引位置+原容量)

HashMap 多线程操作导致死循环问题

JDK1.7 及之前版本的 HashMap 在多线程环境下扩容操作可能存在死循环问题,这是由于当一个桶位中有多个元素需要进行扩容时,多个线程同时对链表进行操作,头插法可能会导致链表中的节点指向错误的位置,从而形成一个环形链表,进而使得查询元素的操作陷入死循环无法结束

为了解决这个问题,JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置,使得插入的节点永远都是放在链表的末尾,避免了链表中的环形结构。但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在数据覆盖的问题。并发环境下,推荐使用 ConcurrentHashMap

一般面试中这样介绍就差不多,不需要记各种细节,个人觉得也没必要记。如果想要详细了解 HashMap 扩容导致死循环问题,可以看看耗子叔的这篇文章:Java HashMap 的死循环。

HashMap 为什么线程不安全?

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

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

JDK 1.8 后,在 HashMap 中,多个键值对可能会被分配到同一个桶(bucket),并以链表或红黑树的形式存储。多个线程对 HashMapput 操作会导致线程不安全,具体来说会有数据覆盖的风险

举个例子:

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

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

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

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) {
    // ...
    // 判断是否出现 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 获得时间片,它也将元素放入桶位中,并将 size 的值更新为 11

  3. 线程 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;
}

HashMap 常见的遍历方式?

HashMap 的 7 种遍历方式与性能分析!

🐛 修正(参见:issue#1411)

这篇文章对于 parallelStream 遍历方式的性能分析有误,先说结论:存在阻塞时 parallelStream 性能最高, 非阻塞时 parallelStream 性能最低

当遍历不存在阻塞时, parallelStream 的性能是最低的:

Benchmark               Mode  Cnt     Score      Error  Units
Test.entrySet           avgt    5   288.651 ±   10.536  ns/op
Test.keySet             avgt    5   584.594 ±   21.431  ns/op
Test.lambda             avgt    5   221.791 ±   10.198  ns/op
Test.parallelStream     avgt    5  6919.163 ± 1116.139  ns/op

加入阻塞代码Thread.sleep(10)后, parallelStream 的性能才是最高的:

Benchmark               Mode  Cnt           Score          Error  Units
Test.entrySet           avgt    5  1554828440.000 ± 23657748.653  ns/op
Test.keySet             avgt    5  1550612500.000 ±  6474562.858  ns/op
Test.lambda             avgt    5  1551065180.000 ± 19164407.426  ns/op
Test.parallelStream     avgt    5   186345456.667 ±  3210435.590  ns/op

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMapHashtable 的区别主要体现在实现线程安全的方式上不同

  • 底层数据结构: JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的;

  • 实现线程安全的方式(重要):

    • 在 JDK1.7 的时候,ConcurrentHashMap 对整个桶数组进行了分割分段(Segment,分段锁),每一把锁只锁容器其中一部分数据(下面有示意图),多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率

    • 到了 JDK1.8 的时候,ConcurrentHashMap 已经摒弃了 Segment 的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6 以后 synchronized 锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在 JDK1.8 中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;

    • Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低

下面,我们再来看看两者底层数据结构的对比图

Hashtable :

JDK1.7 的 ConcurrentHashMap

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成

Segment 数组中的每个元素包含一个 HashEntry 数组,每个 HashEntry 数组属于链表结构

JDK1.8 的 ConcurrentHashMap

JDK1.8 的 ConcurrentHashMap 不再是 Segment 数组 + HashEntry 数组 + 链表,而是 Node 数组 + 链表 / 红黑树。不过,Node 只能用于链表的情况,红黑树的情况需要使用 TreeNode。当冲突链表达到一定长度时,链表会转换成红黑树

TreeNode是存储红黑树节点,被TreeBin包装。TreeBin通过root属性维护红黑树的根结点,因为红黑树在旋转的时候,根结点可能会被它原来的子节点替换掉,在这个时间点,如果有其他线程要写这棵红黑树就会发生线程不安全问题,所以在 ConcurrentHashMapTreeBin通过waiter属性维护当前使用这棵红黑树的线程,来防止其他线程的进入

static final class TreeBin<K,V> extends Node<K,V> {
        TreeNode<K,V> root;
        volatile TreeNode<K,V> first;
        volatile Thread waiter;
        volatile int lockState;
        // values for lockState
        static final int WRITER = 1; // set while holding write lock
        static final int WAITER = 2; // set when waiting for write lock
        static final int READER = 4; // increment value for setting read lock
...
}

ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

JDK1.8 之前

首先将数据分为一段一段(这个“段”就是 Segment)的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成

Segment 继承了 ReentrantLock,所以 Segment 是一种可重入锁,扮演锁的角色。HashEntry 用于存储键值对数据

static class Segment<K,V> extends ReentrantLock implements Serializable {
}

一个 ConcurrentHashMap 里包含一个 Segment 数组,Segment 的个数一旦初始化就不能改变Segment 数组的大小默认是 16,也就是说默认可以同时支持 16 个线程并发写

Segment 的结构和 HashMap 类似,是一种数组和链表结构,一个 Segment 包含一个 HashEntry 数组,每个 HashEntry 是一个链表结构的元素,每个 Segment 守护着一个 HashEntry 数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 的锁。也就是说,对同一 Segment 的并发写入会被阻塞,不同 Segment 的写入是可以并发执行的

JDK1.8 之后

Java 8 几乎完全重写了 ConcurrentHashMap,代码量从原来 Java 7 中的 1000 多行,变成了现在的 6000 多行

ConcurrentHashMap 取消了 Segment 分段锁,采用 Node + CAS + synchronized 来保证并发安全。数据结构跟 HashMap 1.8 的结构类似,数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值(8)时将链表(寻址时间复杂度为 O(N))转换为红黑树(寻址时间复杂度为 O(log(N)))

Java 8 中,锁粒度更细,synchronized 只锁定当前链表或红黑二叉树的首节点,这样只要 hash 不冲突,就不会产生并发,就不会影响其他 Node 的读写,效率大幅提升

JDK 1.7 和 JDK 1.8 的 ConcurrentHashMap 实现有什么不同?

  • 线程安全实现方式:JDK 1.7 采用 Segment 分段锁来保证安全, Segment 是继承自 ReentrantLock。JDK1.8 放弃了 Segment 分段锁的设计,采用 Node + CAS + synchronized 保证线程安全,锁粒度更细,synchronized 只锁定当前链表或红黑二叉树的首节点

  • Hash 碰撞解决方法 : JDK 1.7 采用拉链法,JDK1.8 采用拉链法结合红黑树(链表长度超过一定阈值时,将链表转换为红黑树)

  • 并发度:JDK 1.7 最大并发度是 Segment 的个数,默认是 16。JDK 1.8 最大并发度是 Node 数组的大小,并发度更大

ConcurrentHashMap 为什么 key 和 value 不能为 null?

ConcurrentHashMap 的 key 和 value 不能为 null 主要是为了避免二义性。null 是一个特殊的值,表示没有对象或没有引用。如果你用 null 作为键,那么你就无法区分这个键是否存在于 ConcurrentHashMap 中,还是根本没有这个键。同样,如果你用 null 作为值,那么你就无法区分这个值是否是真正存储在 ConcurrentHashMap 中的,还是因为找不到对应的键而返回的

拿 get 方法取值来说,返回的结果为 null 存在两种情况:

  • 值没有在集合中 ;

  • 值本身就是 null

这也就是二义性的由来

具体可以参考 ConcurrentHashMap 源码分析

多线程环境下,存在一个线程操作该 ConcurrentHashMap 时,其他的线程将该 ConcurrentHashMap 修改的情况,所以无法通过 containsKey(key) 来判断否存在这个键值对,也就没办法解决二义性问题了。

与此形成对比的是,HashMap 可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个。如果传入 null 作为参数,就会返回 hash 值为 0 的位置的值。单线程环境下,不存在一个线程操作该 HashMap 时,其他的线程将该 HashMap 修改的情况,所以可以通过 contains(key)来做判断是否存在这个键值对,从而做相应的处理,也就不存在二义性问题

也就是说,多线程下无法正确判定键值对是否存在(存在其他线程修改的情况),单线程是可以的(不存在其他程修改的情况)

如果你确实需要在 ConcurrentHashMap 中使用 null 的话,可以使用一个特殊的静态空对象来代替 null

public static final Object NULL = new Object();

最后,再分享一下 ConcurrentHashMap 作者本人 (Doug Lea)对于这个问题的回答:

The main reason that nulls aren't allowed in ConcurrentMaps (ConcurrentHashMaps, ConcurrentSkipListMaps) is that ambiguities that may be just barely tolerable in non-concurrent maps can't be accommodated. The main one is that if map.get(key) returns null, you can't detect whether the key explicitly maps to null vs the key isn't mapped. In a non-concurrent map, you can check this via map.contains(key), but in a concurrent one, the map might have changed between calls.

翻译过来之后的,大致意思还是单线程下可以容忍歧义,而多线程下无法容忍。

ConcurrentHashMap 能保证复合操作的原子性吗?

ConcurrentHashMap 是线程安全的,意味着它可以保证多个线程同时对它进行读写操作时,不会出现数据不一致的情况,也不会导致 JDK1.7 及之前版本的 HashMap 多线程操作导致死循环问题。但是,这并不意味着它可以保证所有的复合操作都是原子性的,一定不要搞混了!

复合操作是指由多个基本操作(如putgetremovecontainsKey等)组成的操作,例如先判断某个键是否存在containsKey(key),然后根据结果进行插入或更新put(key, value)。这种操作在执行过程中可能会被其他线程打断,导致结果不符合预期

例如,有两个线程 A 和 B 同时对 ConcurrentHashMap 进行复合操作,如下:

// 线程 A
if (!map.containsKey(key)) {
map.put(key, value);
}
// 线程 B
if (!map.containsKey(key)) {
map.put(key, anotherValue);
}

如果线程 A 和 B 的执行顺序是这样:

  1. 线程 A 判断 map 中不存在 key

  2. 线程 B 判断 map 中不存在 key

  3. 线程 B 将 (key, anotherValue) 插入 map

  4. 线程 A 将 (key, value) 插入 map

那么最终的结果是 (key, value),而不是预期的 (key, anotherValue)。这就是复合操作的非原子性导致的问题

那如何保证 ConcurrentHashMap 复合操作的原子性呢?

ConcurrentHashMap 提供了一些原子性的复合操作,如 putIfAbsentcomputecomputeIfAbsentcomputeIfPresentmerge等。这些方法都可以接受一个函数作为参数,根据给定的 key 和 value 来计算一个新的 value,并且将其更新到 map 中

上面的代码可以改写为:

// 线程 A
map.putIfAbsent(key, value);
// 线程 B
map.putIfAbsent(key, anotherValue);

或者:

// 线程 A
map.computeIfAbsent(key, k -> value);
// 线程 B
map.computeIfAbsent(key, k -> anotherValue);

很多同学可能会说了,这种情况也能加锁同步呀!确实可以,但不建议使用加锁的同步机制,违背了使用 ConcurrentHashMap 的初衷。在使用 ConcurrentHashMap 的时候,尽量使用这些原子性的复合操作方法来保证原子性

Collections 工具类(不重要)

Collections 工具类常用方法:

  • 排序

  • 查找,替换操作

  • 同步控制(不推荐,需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)

排序操作

void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序,由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时,将list后distance个元素整体移到前面。当distance为负数时,将 list的前distance个元素整体移到后面

查找,替换操作

int binarySearch(List list, Object key)//对List进行二分查找,返回索引,注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序,返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序,返回最大元素,排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引,找不到则返回-1,类比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素

同步控制

Collections 提供了多个synchronizedXxx()方法·,该方法可以将指定集合包装成线程同步的集合,从而解决多线程并发访问集合时的线程安全问题

我们知道 HashSetTreeSetArrayList,LinkedList,HashMap,TreeMap 都是线程不安全的。Collections 提供了多个静态方法可以把他们包装成线程同步的集合

最好不要用下面这些方法,效率非常低,需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合

方法如下:

synchronizedCollection(Collection<T>  c) //返回指定 collection 支持的同步(线程安全的)collection
synchronizedList(List<T> list)//返回指定列表支持的同步(线程安全的)List
synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步(线程安全的)Map
synchronizedSet(Set<T> s) //返回指定 set 支持的同步(线程安全的)set

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/906000.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

数字化导师坚鹏:2025年银行开门红营销规划、方法及案例工作坊

2025年银行开门红营销规划、方法及案例工作坊 ——数字化赋能 新策略启航 开门红必胜 课程背景&#xff1a; 面对即将打响的开门红战役&#xff0c;很多银行存在以下问题&#xff1a; 不知道如何分析银行开门红面临形势及机遇&#xff1f; 不知道如何制定科学高效的开…

普通的Java程序员,需要深究源码吗?

作为Java开发者&#xff0c;面试肯定被问过多线程。对于它&#xff0c;大多数好兄弟面试前都是看看八股文背背面试题以为就OK了&#xff1b;殊不知现在的面试官都是针对一个点往深了问&#xff0c;你要是不懂其中原理&#xff0c;面试就挂了。可能你知道什么是进程什么是线程&a…

ctfshow——web(总结持续更新)

文章目录 1、基础知识部分2、php伪协议2.1 php://input协议2.2 data://text/plain协议 3、webshell连接工具3.1 蚁剑连接一句话木马 4、各个web中间件重要文件路径4.1 Nginx 5、sqlmap使用6、php特性6.1 md5加密漏洞 7、TOP 10漏洞7.1 SQL注入 1、基础知识部分 识别base64编码…

MYSQL---TEST5(Trigger触发器综合练习)

触发器Trigger 数据库mydb16_trigger创建 表的创建 goods create table goods( gid char(8) primary key, #商品号 name varchar(10), #商品名 price decimal(8,2), #价格 num int&#xff1b;&#xff09; #数量orders create tabl…

layui 自定义验证单选框必填

对于输入框类型必填验证&#xff0c;只需要在 input 输入框加入 lay-verify "required" 即可。但对于单选按钮这种特殊的该怎么办呢&#xff1f;layui 为我们提供了自定义验证。 1. 在单选按钮上添加自定义验证的名称 2. 验证规则如下 // 单选框自定义验证form.ve…

OpenCV开发笔记(八十二):两图拼接使用渐进色蒙版场景过渡缝隙

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/143432922 长沙红胖子Qt&#xff08;长沙创微智科&#xff09;博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV…

「C/C++」C/C++标准库 之 #include<ctime> 时间日期库

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「C/C」C/C程序设计&#x1f4da;全部专栏「VS」Visual Studio「C/C」C/C程序设计「UG/NX」BlockUI集合「Win」Windows程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「PK」Parasoli…

安达发|零部件APS车间排程系统销售预测的优点

2024制造业面临着前所未有的挑战与机遇。为了保持竞争力&#xff0c;企业必须确保其生产系统能够高效、灵活地运作。在这方面&#xff0c;采用高级计划与排程系统&#xff0c;特别是零部件APS车间排程系统的预测方法&#xff0c;已成为提升生产效率和响应能力的关键策略。这种系…

【笔试刷题】笔记4

目录 1、过河卒 dfs bfs 动态规划 2、扑克牌顺子 排序 模拟 找规律 3、最长回文子串 中心拓展法 1、过河卒 5493. 过河卒 - AcWing题库 这道题我们很容易就能够想到dfs或bfs&#xff0c;但这两种算法都是会超时的 dfs #include <iostream> #include <v…

大模型中的token是什么;常见大语言模型的 token 情况

目录 大模型中的token是什么 常见大语言模型的 token 情况 大模型中的token是什么 定义 在大模型中,token 是文本处理的基本单位。它可以是一个字、一个词,或者是其他被模型定义的语言单元。简单来说,模型在理解和生成文本时,不是以完整的句子或段落为单位进行一次性处理…

kafka里的consumer 是推还是拉?

大家好&#xff0c;我是锋哥。今天分享关于【kafka里的consumer 是推还是拉&#xff1f;】面试题&#xff1f;希望对大家有帮助&#xff1b; kafka里的consumer 是推还是拉&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 在Kafka中&#xff0c;消费者&…

少儿编程培训市场突破500亿元:教育新蓝海的崛起与未来展望

近年来&#xff0c;随着科技的迅速发展和家长对教育方式的重视&#xff0c;少儿编程市场成为一片新的蓝海。据最新市场调研报告显示&#xff0c;2024年中国少儿编程培训市场规模已突破500亿元&#xff0c;预计未来五年将持续增长。这一趋势反映了少儿编程教育的迅速崛起&#x…

【如何使用api接入星火大模型】(超详细,亲测有效!)

1 实现思路&#xff1a; 1.鉴权说明: 先在控制台创建应用&#xff0c;利用应用中提供的appid&#xff0c;APIKey&#xff0c; APISecret进行鉴权&#xff0c;生成最终请求的鉴权url。1.2 鉴权参数 host&#xff08;请求主机&#xff09;、date&#xff08;当前时间戳&#xff0…

国标GB28181软件EasyGBS国标GB28181网页直播平台在邮政快递场景中的应用

随着电子商务的迅猛发展&#xff0c;邮政快递行业迎来了前所未有的发展机遇&#xff0c;但同时也面临着诸多挑战。如何在保障货物安全、提高运输效率的同时&#xff0c;实现全面的监控和管理&#xff0c;成为邮政快递企业亟需解决的问题。国标GB28181网页直播平台EasyGBS作为一…

渗透测试练习题解析 7 (CTF web)

一、[红明谷CTF 2021]write_shell 1 考点&#xff1a; 1、PHP 短标签 2、 符号的使用 通过代码可知 check 是一个过滤函数&#xff0c;利用正则的方式过滤掉 空格、php、eval 等一些关键字或符号&#xff0c;$dir 是路径&#xff0c;这个值可以通过 actionpwd 获取到&#…

day-77 超级饮料的最大强化能量

思路 动态规划&#xff1a;因为每一步要么选A&#xff0c;要么选B&#xff0c;所以问题可以转换为求最后一步从A选或从B选中的较大值 解题过程 定义而二维数组dp,dp[i][0]表示最后一步从A取能获得的最大能量&#xff0c;dp[i][1]表示最后一步从B取能获得的最大能量状态转换方程…

(03)萨班斯-奥克斯利法案(SOX)--- 你和公司的违法成本有多大?

【前言】如果你的公司需要去美国上市&#xff1f;你知道如果违反了萨班斯-奥克斯利法案&#xff08;SOX&#xff09;&#xff0c;你和公司的风险和成本吗&#xff1f; 一、萨班斯-奥克斯利法案&#xff08;SOX&#xff09;合规性是指什么- 你必须知道&#xff0c;如果你的公司要…

C++ | Leetcode C++题解之第517题超级洗衣机

题目&#xff1a; 题解&#xff1a; class Solution { public:int findMinMoves(vector<int> &machines) {int tot accumulate(machines.begin(), machines.end(), 0);int n machines.size();if (tot % n) {return -1;}int avg tot / n;int ans 0, sum 0;for (…

【Linux】从内核角度理解 TCP 的 全连接队列(以及什么是 TCP 抓包)

文章目录 概念引入理解全连接队列内核方面理解Tcp抓包方法注意事项 概念引入 我们知道&#xff0c;TCP的三次握手是由TCP协议 自动处理的&#xff0c;建立连接的过程与用户是否进行accept无关&#xff0c;accept()的作用主要是为当前连接创建一个套接字&#xff0c;用于进行后…

适合视频搬运的素材网站推荐——短视频素材下载宝库

对于摄影爱好者和短视频创作者来说&#xff0c;找到适合搬运和创作的视频素材至关重要。无论是用于丰富画面、增加背景细节&#xff0c;还是提升作品的视觉吸引力&#xff0c;这些素材网站都能为你的创作提供极大帮助。今天&#xff0c;我将为大家推荐几个优质的素材网站&#…