发布于 

2.Java集合

1、集合框架

1.1 集合框架

image.png
image.png

2、哪些集合类是线程安全的？

2.1 线程安全的集合类

  • Vector：就比 arraylist 多了个同步化机制（线程安全），因为效率较低， 现在已经不太建议使用。在 web 应用中，特别是前台页面，往往效率（页面响应速度）是优先考虑的。
  • Statck：堆栈类，先进后出。
  • HashTable：就比 HashMap 多了个线程安全。
  • ConcurrentHashMap：线程安全的集合类。
  • enumeration：枚举，相当于迭代器。

3、集合类线程不安全举例

3.1 ArrayList为什么是线程不安全的

请编写一个ArrayList不安全的案例并给出解决方案？

1
2
3
4
5
6
7
8
9
10
11
public class Main{
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= 30; i++) {
            new Thread(() ->{
                list.add(UUID.randomUUID().toString().substring(0, 8));
                System.out.println(list);
            }, String.valueOf(i)).start();
        }
    }
}

故障现象：这段代码创建了 30 个线程，每个线程都向一个共享的列表 list ，并且向其中添加一个长度为 8 的随机字符串，然后输出当前列表内容。由于多个线程同时对 list 进行操作，因此会出现线程安全问题。

结果会报java.util.ConcurrentModificationException异常

解决方案：

  1. 使用线程安全的数据结构，比如说Vector或者CopyOnWriteArrayList。
  2. 使用 Collections.synchronizedList() 方法将非线程安全的 ArrayList 转换成线程安全的。
  3. 在修改共享数据时，使用同步锁保证线程安全。其中使用同步锁时，要注意锁定的对象应该是所有线程共享的，而不是县城内部的局部变量。
1
2
3
4
5
6
7
8
9
10
11
public class Main{
    public static void main(String[] args) {
        List<String> list = Collections.synchronizedList(new ArrayList<>());
        for (int i = 0; i < 30; i++) {
            synchronized (list){
                list.add(UUID.randomUUID().toString().substring(0, 8));
                System.out.println(list);
            }
        }
    }
}

建议：在读多写少时，推荐使用CopyOnWriteArrayList，因为这个类里面是通过lock锁来实现线程同步的。

3.2 CopyOnWrite了解吗？

CopyOnWrite就是写时复制（也就是读写分离的思想）：在读取数据时，不加锁；在写入和删除时加锁，底层实现机制是：volatile + ReentrantLock；

具体过程：当往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后向新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。

优点：

提高并发，解决了并发场景下的安全问题，因为我们在CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。

缺点：

  • 内存占用：因为CopyOnWrite的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象（注意:在复制的时候只是复制容器里的引用，只是在写的时候会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存），可能导致GC。
  • 一致性：CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用CopyOnWrite容器。【当执行add或remove操作没完成时，get获取的仍然是旧数组的元素】

3.3 HashSet

HashSet底层数据结构是HashMap，那么为什么HashSet在执行add方法时，只添加1个元素，而不是HashMap中同时添加key和value呢？

通过查看源码：

1
2
3
4
5
6
7
8
9
private static final Object PRESENT = new Object();

public HashSet() {
    map = new HashMap<>();
}

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

可以发现，HashSet底层其实就是用HashMap实现的，Set在使用add添加元素的时候，用的就是HashMap的put方法，只不过在添加的时候，将需要添加的元素e作为key添加，而Value是一个默认的用final修饰的Object对象PRESENT。

4、ArrayList和LinkedList的区别

4.1 ArrayList和LinkedList的区别

  • 线程安全：两者都不同步，线程都不安全。
  • 底层数据结构：ArrayList底层使用的是Object数组；LinkedList底层使用的是双向链表。
  • 插入删除元素：ArrayList采用数组存储；LinkedList采用链表存储，所以与数据结构中数组和链表特性相同。
  • 快速访问：ArrayList可以通过元素序号快速访问对象；LinkedList不支持高效的元素访问。
  • 内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间； LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

5、ArrayList的扩容机制

5.1 ArrayList扩容机制

image.png
image.png

ArrayList的底层采用Object数组来存储数据，在往 ArrayList 里面添加元素时，才会涉及到扩容机制。

由于采用的是数组存储，所以会给数组设置默认长度10。

当数组中没有元素时，是不会设置为默认长度10 的，此时数组是一个空数组。只有要添加元素时，会进入 ensureCapacityInternal()进行判断，如果数据数组为空数组，在添加第一个元素时才将数组长度扩容为默认值10，如果数组不为空数组 ， 就在 ensureCapacityInternal()里 面 调 用 ensureExplicitCapacity()来判断是否需要扩容。

如果需要扩容，才调用 grow()方法进行扩容。在grow()方法里面，会通过右移位运算将数组长度的新长度扩容为**原来的 1.5倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右)**。

扩容后如果新容量不能满足所需容量，就将新容量扩大为所需容量。也即新容量大于 MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8，就调用hugeCapacity()方法来比较 minCapacity 和 MAX_ARRAY_SIZE 的大小，如果 minCapacity 大于默认最大容量，则新容量设为则为 Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE，即为 Integer.MAX_VALUE - 8。如果最大容量大于Integer.MAX_VALUE，那么就会转为负数，然后抛出异常。

最后将原数组中的元素拷贝到扩容后的新数组， 并将原数组的引用设置为拷贝后的数组。

5.2 如果new ArrayList<>(20)，此时需要扩容几次？

此时不会扩容，因为如果通过构造函数直接指定了ArrayList的长度，初始化时就会直接分配给ArrayList指定大小的容量，而不会触发扩容机制。

6、HashSet如何检查重复？

6.1 HashSet去重原理

把对象添加到HashSet中时，

  1. HashSet会计算对象的hashCode值，来判断对象加入的位置，同时也会与其他加入的对象hashCode值作比较；
  2. 如果没有相同的hashcode，HashSet会假设对象没有重复出现；
  3. 如果有相同的hashCode，会调用equals来检查hashCode相同的对象是否真的相同；
  4. 如果用equals比较之后，两者相同，那么HashSet就不会让这个元素加入。

简单总结：首先比较hashCode是否相等，再使用equals比较值是否相等。

7、HashMap的底层实现

7.1 JDK 1.8之前

1.8之前HashMap
1.8之前HashMap

底层采用数组+链表，HashMap 通过它的hash()方法获取 key 对应的hashCode值，然后通过(n-1) & hash 判断当前元素存放的位置，如果当前位置存在元素的话，就判断该元素与要存入的 hash 值以及 key 是否相同，如果相同就直接覆盖，不相同的话，就通过拉链法解决 hash 冲突，将元素存放到链表中。

7.2 JDK 1.8之后

1.8及之后HashMap
1.8及之后HashMap

JDK1.8 之后底层采用的是数组+（链表和红黑树），主要不同在于解决hash冲突时，当链表长度超过设定的阈值长度时（默认为 8），会先判断数组的长度是否小于 64(初始最大容量)，如果小于的话，并不是直接转为红黑树，而是进行扩容，只有当数组长度大于 64 时，才会将对应的链表转换为红黑树。

7.2.1 为什么HashMap的底层要用红黑树，而不是平衡树呢？

因为HashMap中需要频繁的新增或删除数据，一旦树中节点需要改变，那必然导致树的结构需要调整。而红黑树不像平衡树那样追求“完全平衡”，红黑树只需要部分达到平衡即可，所以其增删节点时旋转的次数会比平衡树降低很多，这也就意味着红黑树的调整效率比平衡树高很多，同样也更好设计和实现。

7.3 put的具体过程

image.png
image.png
  1. 判断键值对数组 table[i]是否为空或为null，若是，则执行 resize()进行扩容；否则进行下一步 ；
  2. 根据 key计算hash 值得到插入的数组索引 i，如果 table[i]==null，直接新建节点添加，如果 table[i]不为空，则进行下一步；
  3. 判断 table[i]的首个元素是否和 key 一样，如果相同直接覆盖 value，否则进行下一步，这里的相同指的是 hashCode 以及 equals；
  4. 判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则操作链表；
  5. 遍历 table[i]，判断链表长度是否大于 8，大于 8 的话就准备将链表转换为红黑树，（当红黑树内节点数 <= 6时，会将红黑树退化成链表）在将链表转换为红黑树之前，会进行判断是否真的转为红黑树。
  6. 如果当前数组的长度小于64，那么会先进行数组的扩容，否则才会真的转红黑树，然后在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key 已经存在直接覆盖 value 即可；
  7. 插入成功后，判断实际存在的键值对数量 size 是否超过了最大容量 threshold(数组长度*0.75)，如果超过，进行扩容。

7.4 为什么负载因子是0.75？

loadFactor 太大导致查找元素效率低，存放的数据拥挤，hash冲突概率大大提升；太小会导致数组的利用率低，存放的数据会很分散。

loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值，可以保证查询性能和空间利用效率之间取得平衡。

7.5 讲一讲HashMap的扩容机制

  1. 初始化或达到扩容阈值（数组长度 * 0.75）时，调用resize()方法进行扩容，第一次添加数据初始化数组长度为16；
  2. 创建新的数组，新数组长度是原来数组长度的2倍；
  3. 将原数组上的数据移到新数组上，其中没有Hash冲突的key，直接计算其在新数组中的索引位置添加；
  4. 如果存在Hash冲突的key，先采用链地址法解决，如果是红黑树，则直接在红黑树中添加；如果是链表，则需要拆分链表，要么该元素留在原来的位置，要么移动到原来位置+增加的数组大小这个位置上。
  5. 所有的元素移动完毕后，原数组的引用替换为新数组的引用，完成扩容操作。

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

当我们往 HashMap 里面 put元素的时候，会通过 hashMap 的 hash 方法，获取 key 对应的 hashCode 值，然后拿这个值去判断该元素要存放在那个地方。

这里采用的是(n-1) & hash，也即右移16位，其中 n 为 HashMap 的长度，这个操作只有当 n 是 2 的幂次方时，(n-1) & hash 才和 hash % n 表示的是一个意思，这样才能找到这个 key 在数组中对应的位置。

如果不是 2 的幂次方， (n-1) & hash 是不等于 hash%n 的，之所以采用位运算的好处是：相较于%操作，它的计算效率更高，能保证散列均匀分布。

9、HashMap有哪几种常见的遍历方式？

  1. 迭代器（Iterator）方式遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// entrySet遍历
Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<Integer, String> entry = iterator.next();
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
}

// keySet遍历
Iterator<Integer> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
    Integer key = iterator.next();
    System.out.println(key);
    System.out.println(map.get(key));
}
  1. For Each方式遍历
1
2
3
4
5
6
7
8
9
10
11
// entrySet遍历
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
}

// keySet遍历
for (Integer key : map.keySet()) {
    System.out.println(key);
    System.out.println(map.get(key));
}
  1. Lambda表达式遍历
1
2
3
4
5
// lambda表达式遍历
map.forEach((key, value) -> {
    System.out.println(key);
    System.out.println(value);
});
  1. Streams API遍历
1
2
3
4
5
6
7
8
9
10
// 单线程遍历
map.entrySet().stream().forEach((entry) -> {
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
});
// 多线程遍历
map.entrySet().parallelStream().forEach((entry) -> {
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
});

9.1 性能测试

entrySet的性能比keySet的性能好，尽量使用entrySet来遍历Map集合。

KeySet 在循环时使用了 map.get(key)，而 map.get(key) 相当于又遍历了一遍 Map 集合去查询 key 所对应的值。

为什么要用“又”这个词？

那是因为在使用迭代器或者 for 循环时，其实已经遍历了一遍 Map 集合了，因此再使用 map.get(key) 查询时，相当于遍历了两遍。而 EntrySet 只遍历了一遍 Map 集合，之后通过代码“Entry<Integer, String> entry = iterator.next()”把对象的 key 和 value 值都放入到了 Entry 对象中，因此再获取 key 和 value 值时就无需再遍历 Map 集合，只需要从 Entry 对象中取值就可以了。

所以，EntrySet 的性能比 KeySet 的性能高出了一倍，因为 KeySet 相当于循环了两遍 Map 集合，而 EntrySet 只循环了一遍。

9.2 安全性能

我们不能在遍历中使用集合 map.remove() 来删除数据，这是非安全的操作方式，但我们可以使用迭代器的 iterator.remove() 的方法来删除数据，这是安全的删除集合的方式。同样的我们也可以使用 Lambda 中的 removeIf 来提前删除数据，或者是使用 Stream 中的 filter 过滤掉要删除的数据进行循环，这样都是安全的，当然我们也可以在 for 循环前删除数据在遍历也是线程安全的。
所以，尽量使用迭代器（Iterator）来遍历EntrySet的遍历方式操作Map集合

10、有哪些解决哈希冲突的方法？

  1. 开放定址法：在发生冲突时，会去寻找一个新的空地址存放；
    1. 线性探测法：如果冲突了，就往后找空的地方放；
    2. 平方探测法：如果冲突了，进行平方，向前或向后找空地方放；
  2. 再Hash法：如果发生冲突，那就再进行hash计算，直到没有发生冲突为止；
  3. 链地址法。HashMap用的就是这种方法；

11、为什么HashMap中String、Integer这样的包装类适合作为Key？

String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效地减少Hash碰撞的几率。

因为这些包装类都是final类型，具有不可变性，可以保证存储的key具有不可更改性，不会存在获取hash值不同的情况。而同时，这些包装类的内部已经重写equals、hashCode等方法，遵守了HashMap内部的规范，不容易出现hash值计算错误的情况。

12、ConcurrentHashMap和HashTable的区别？

底层数据结构：ConcurrentHashMap在JDK1.8之前，采用的是数组+链表来实现；而在JDK1.8及之后的版本，采用的是数组+链表/红黑树。HashTable采用的是数组+链表实现的。

实现线程安全的方式：

  • 在 JDK1.7 的时候，ConcurrentHashMap（分段锁 ReentrantLock） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
image.png
image.png
  • 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组 + 链表 + 红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的 数据结构，但是已经简化了属性，只是为了兼容旧版本；
image.png
image.png
  • HashTable(同一把锁) : 使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈，效率也会越低。
image.png
image.png

13、ConcurrentHashMap的线程安全是怎么实现的？

13.1 JDK1.8之前

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。 Segment 实现了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。 

1
2
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 的写入是可以并发执行的。

13.2 JDK1.8及之后

ConcurrentHashMap 取消了 Segment 分段锁，采用 Node + CAS + synchronized 来保证并发安全。

数据结构跟 HashMap 1.8 的结构类似，数组+链表/红黑二叉树。

Java 8 在链表长度超过一定阈值（8）时，会判断数组长度是否64，是的话就将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）。

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

13.3 总结

  • 线程安全实现方式 ：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 数组的大小，并发度更大。

13.4 ConcurrentHashMap已经用了synchronized为什么还要用CAS呢？

简单来说，都是保证了多线程下的原子性。CAS用于在数组中插入新节点，因为CAS操作是乐观锁，并没有加锁，而且实现比较简单，适用于无竞争的情况。而**synchronized用于在链表中或红黑树中插入删除节点**，如果到了要插入链表或者红黑树的地步，那说明竞争就比较激烈了，所以用synchronized锁首节点。

  • 当数组中当前位置为空的时候，可以通过CAS把新的节点写到数组中对应的位置；
  • 当数组中当前位置不为空时，通过synchronized来添加或删除节点。如果当前位置是链表，就遍历链表找到合适的位置插入或删除节点。如果当前位置是红黑树，就按照红黑树的规则插入或删除节点；
  • 当链表长度大于阈值（默认为8）时，就把链表转换为红黑树。当红黑树节点数小于等于阈值（默认为6）时，就把红黑树转换为链表。

13.5 ConcurrentHashMap的put操作的流程？

  1. 计算key的hash值；
  2. 如果当前table还没有初始化就会调用initTable方法进行初始化；
  3. 如果table对应的位置为空，那么直接用CAS操作直接插入即可；
  4. 如果检测到内部正在进行扩容操作，该线程就会帮它一起扩容；
  5. 如果table对应的位置不为空，会先用synchronized锁住链表或红黑树的头元素。然后再继续对链表或红黑树执行添加操作；
  6. 如果链表长度已经大于8（默认），就会判断是否要转为红黑树。（操作和HashMap一样）
  7. 如果添加成功就调用addCount()方法统计size，并检查是否需要扩容。

13.6 ConcurrentHashMap是怎么扩容的？

需要扩容的情况：

  1. 当前容量超过阈值；
  2. 当链表元素大于8个，并且数组长度小于64的时候；
  3. 当其他线程扩容时，会帮助一起扩容；

扩容过程：通过CAS设置sizeCtl、transferindex等变量，协调多个线程并发扩容，其中无锁的关键就是CAS操作。

  1. 需要扩容时，假设此时原table数组长度是64，那么此时记录transferindex = 63，sizeCtl = 48（sizeCtl的含义指的是扩容的阈值），若要进行扩容操作，会使得sizeCtl = -2（-2表示此时的hash桶正在处于扩容的过程中，这里用来记录当前并发扩容线程的数量）；

  2. 创建一个新数组newTable，长度为原数组table的两倍，也即128；

  3. 扩容线程A会先划分区间，让transferindex - 16 = 47，然后线程A会将table[63]到table[47]这个区间的hash桶向newTable中倒序进行数据迁移；

  4. 迁移时，会将桶内的链表或红黑树，按照一定的算法拆分成两份，分别插入到newTable[i]和newTable[n + i]的位置上（其中n为原数组的长度，这里就是64）。

  5. 该桶内的元素迁移完毕之后，会被设置为ForwardingNode节点，目的是告诉后来的其他线程，这个节点已经数据迁移完毕了，没有节点了；

  6. 若此时线程B访问到了这个ForwardingNode节点。

    • 如果线程B执行的是put等写操作，会先协助扩容，线程B去到transferindex标记的位置，重复上述线程A的操作，将transferindex减16，然后对自己负责的这部分区间进行倒序数据迁移，此时的sizeCtl = sizeCtl - 1 = -3表示新来了个线程。
    • 如果线程B执行的是get等读操作，则会调用ForwardingNode中的find方法，去newTable中找自己需要的元素，此时不会帮忙扩容；

    注：线程B和线程A此时是同步进行扩容迁移操作的，因为两个线程负责的是不同的区间，所以他们之间是互不干扰的；

  7. 如果线程A先执行完原本区间的迁移工作，就会到transferindex 的位置，又会继续上面的过程，继续执行扩容迁移操作，直到transferindex的值等于0结束，才表示这个线程的扩容操作已经结束。每一个线程走到transferindex = 0的位置，就会让sizeCtl的值+1。

  8. 只有当transferindex = 0并且sizeCtl = -1时，才表示整个扩容的流程结束，然后会重新初始化，将table = newTable，并且sizeCtl = 128 * 0.75 = 96。

13.7 迁移时会按一定的算法将红黑树和链表拆分为两份，这个算法具体是什么？

13.7.1 链表迁移

image-20230803154308536
  1. 首先会锁住Node节点，然后再进行迁移操作；
  2. 先找到lastRun节点，将其设置为hn链表的节点；
  3. 从首节点开始遍历链表，将蓝色的节点设置为ln链表中的节点，红色的节点设置为hn链表中的节点；
  4. 依次循环上述步骤，直到原链表被拆分为hn链表和ln节点链表两个链表，这样就拆分为两个链表了；

注：lastRun节点保证了后面的节点与自己的与运算结果相同，避免了没有必要的循环，所以到lastRun开始就不循环了。从这开始后面要不然全是红的，要不然全是蓝的；

13.7.2 红黑树迁移

image-20230803155324831
  1. 首先会锁住数组上的TreeBin节点，再进行迁移；
  2. 还是一样以链表的方式遍历红黑树，将其拼接到hn和ln两个链表上；
  3. 不满足红黑树条件的，将其转换为普通的链表；
  4. 满足红黑树条件的将其转换为红黑树；

13.8 如果一个ConcurrentHashMap在被多个线程同时操作，这个时候进行扩容会有几个线程在处理？

这个要分类讨论，假设一个ConcurrentHashMap在同时被10个线程操作，此时进行扩容操作：

  • 如果其中有5个线程执行的是put等写操作，那么扩容的时候就会有5个线程在一起进行扩容；
  • 如果剩下的5个线程执行的时get等读操作，这些线程是不会协助扩容的。

简单来说：只有执行写操作的线程才会帮忙扩容，读操作的线程并不会执行协助扩容操作。

13.9 ConcurrentHashMap在get时会加锁吗？为什么？

get 方法不需要加锁，因为 Node 的元素 val 和指针 next 是用 volatile 修饰的，在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。

13.10 ConcurrentHashMap为什么不允许key和value为null？HashMap允许吗？

HashMap允许key和value为null，但是只允许一个key为null，不能有多个。

因为ConcurrentHashMap的应用场景一般都是多线程，如果map.get(key)得到的结果是null，就会出问题，因为无法判断是这个key对应的value本来就是null，还是没有找到对应的key才返回的null，这就有了二义性。

而HashMap可以这么操作是因为HashMap的应用场景是单线程情况下，可以用containsKey(key)判断map内是否存在了这个key。

13.11 ConcurrentHashMap中的size()方法实现原理知道吗？

JDK1.8 ConCurrentHashMap的 size 通过 baseCount 和 counterCells 两个变量维护：

  • 在没有并发的情况下，使用一个volatile修饰的 baseCount 变量即可；
  • 当有并发时，CAS 修改 baseCount 失败后，会使用 CounterCell 类，即创建一个CounterCell对象，设置其volatile修饰的 value 属性为 1，并将其放在ConterCells数组的随机位置；

最终在sumCount()方法中通过累加 baseCount和CounterCells数组里每个CounterCell的值得出Map中的总大小Size。

注：然而返回的值是一个估计值；如果有并发插入或者删除操作，和实际的数量可能有所不同。

另外size()方法的最大值是 Integer 类型的最大值，而 Map 的 size 有可能超过 Integer.MAX_VALUE，所以jdk 8 建议使用 mappingCount()。

14、了解HashMap在1.7中多线程死循环问题吗？

因为HashMap在1.7中的底层数据结构采用的是数组＋链表实现的，在插入新元素的时候采用的是头插法。而在数组进行扩容的时候，会进行数据迁移，这个过程中有可能会导致死循环。

比如说，现在有两个线程。

线程一：读取到当前HashMap数据中的一个链表，在准备进行扩容的时候，线程二介入。

线程二：读取HashMap，直接进行扩容。因为插入元素采用的是头插法，所以链表的顺序会倒过来，比如原来是AB，扩容后会变成BA，线程二执行结束。

当线程一再回来继续执行的时候就会导致链表出现环结构，从而出现死循环问题。

在1.8中，插入链表的方法更改为尾插法，保持了与扩容前一样的顺序，就避免了出现死循环问题。

大厂面试爱问的HashMap死锁问题，看这一篇就够了_hashmap的死锁问题_wildyuhao的博客-CSDN博客

15、HashMap和HashTable的区别

  • 线程是否安全：HashMap线程不安全，HashTable线程安全；
  • 效率：因为HashTable是线程安全的，内部的方法基本都经过synchronized 修饰，所以其效率是不如HashMap的；
  • 是否支持null的key：HashMap支持存null的key和value，但是只支持一个null的key，而HashTable不允许有null的key和value；
  • 底层数据结构不同：HashMap是数组+链表/红黑树，而HashTable是数组+链表；
  • 默认初始容量和扩容大小不同：HashMap数组的默认初始容量是16，每次扩容为2n，而HashTable默认初始容量大小为11，扩容为2n+1。

16、HashMap和TreeMap的区别

TreeMap比HashMap多了对集合中的元素根据键排序的能力，以及对集合内元素的搜索能力。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

本站由 Cccccpg 使用 Stellar 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。