集合类

典型回答 线程安全： HashMap是非线程安全的。 Hashtable 中的方法是同步的，所以它是线程安全的。 ConcurrentHashMap在JDK 1.8之前使用分段锁保证线程安全， ConcurrentHashMap默认情况下将hash表分为16个桶（分片），在加锁的时候，针对每个单独的分片进行加锁，其他分片不受影响。锁的粒度更细，所以他的性能更好。 ConcurrentHashMap在JDK 1.8中，采用了一种新的方式来实现线程安全，即使用了CAS+synchronized，这个实现被称为"分段锁"的变种，也被称为"锁分离"，它实现的锁的粒度更细。 ✅ConcurrentHashMap是如何保证线程安全的？ 继承关系： Hashtable是基于陈旧的Dictionary类继承来的。 HashMap继承了抽象类AbstractMap实现了Map接口。 ConcurrentHashMap同样继承了抽象类AbstractMap，并且实现了ConcurrentMap接口。 允不允许null值： HashTable中，key和value都不允许出现null值，否则会抛出NullPointerException异常。 HashMap中，null可以作为键或者值都可以。 ConcurrentHashMap中，key和value都不允许为null。 ✅为什么ConcurrentHashMap不允许null值？ 默认初始容量和扩容机制： HashMap的默认初始容量为16，默认的加载因子为0.75，即当HashMap中元素个数超过容量的75%时，会进行扩容操作。扩容时，容量会扩大为原来的两倍，并将原来的元素重新分配到新的桶中。 Hashtable，默认初始容量为11，默认的加载因子为0.75，即当Hashtable中元素个数超过容量的75%时，会进行扩容操作。扩容时，容量会扩大为原来的两倍加1，并将原来的元素重新分配到新的桶中。 ConcurrentHashMap，默认初始容量为16，默认的加载因子为0.75，即当ConcurrentHashMap中元素个数超过容量的75%时，会进行扩容操作。扩容时，容量会扩大为原来的两倍，并会采用分段锁机制，将ConcurrentHashMap分为多个段(segment)，每个段独立进行扩容操作，避免了整个ConcurrentHashMap的锁竞争。 遍历方式的内部实现上不同 ： HashMap使用EntrySet进行遍历，即先获取到HashMap中所有的键值对(Entry)，然后遍历Entry集合。支持fail-fast，也就是说在遍历过程中，若HashMap的结构被修改（添加或删除元素），则会抛出ConcurrentModificationException。如果只需要遍历HashMap中的key或value，可以使用KeySet或Values来遍历。 Hashtable使用Enumeration进行遍历，即获取Hashtable中所有的key，然后遍历key集合。这个过程也会判断是否存在并发修改： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 public T next() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); return nextElement(); } public void remove() { if (!iterator) throw new UnsupportedOperationException(); if (lastReturned == null) throw new IllegalStateException("Hashtable Enumerator"); if (modCount != expectedModCount) throw new ConcurrentModificationException(); synchronized(Hashtable.this) { Entry[] tab = Hashtable.this.table; int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length; for (Entry<K,V> e = tab[index], prev = null; e != null; prev = e, e = e.next) { if (e == lastReturned) { modCount++; expectedModCount++; if (prev == null) tab[index] = e.next; else prev.next = e.next; count--; lastReturned = null; return; } } throw new ConcurrentModificationException(); } } ConcurrentHashMap使用分段锁机制，因此在遍历时需要注意，遍历时ConcurrentHashMap的某个段被修改不会影响其他段的遍历。可以使用EntrySet、KeySet或Values来遍历ConcurrentHashMap，其中EntrySet遍历时效率最高。遍历过程中，ConcurrentHashMap的结构发生变化时，不会抛出ConcurrentModificationException异常，但是在遍历时可能会出现数据不一致的情况，因为遍历器仅提供了弱一致性保障。 ...

典型回答 对于HashMap来说，底层是基于散列算法实现，散列算法分为散列再探测和拉链式。HashMap 则使用了拉链式的散列算法，即采用数组+链表/红黑树来解决hash冲突，数组是HashMap的主体，链表主要用来解决哈希冲突。这个数组是Entry类型，它是HashMap的内部类，每一个Entry包含一个key-value键值对 get方法 下面是JDK 1.8中HashMap的get方法的简要实现过程： 首先，需要计算键的哈希值，并通过哈希值计算出在数组中的索引位置。 如果该位置上的元素为空，说明没有找到对应的键值对，直接返回null。 如果该位置上的元素不为空，遍历该位置上的元素，如果找到了与当前键相等的键值对，那么返回该键值对的值，否则返回null。 1 2 3 4 public V get(Object key) { Node<K, V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } get 方法看起来很简单，就是通过同样的 hash 得到 key 的hash 值。重点看下 getNode方法： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 final Node<K, V> getNode(int hash, Object key) { //当前HashMap的散列表的引用 Node<K, V>[] tab; //first：桶头元素 //e：用于存放临时元素 Node<K, V> first, e; //n：table 数组的长度 int n; //元素中的 k K k; // 将 table 赋值为 tab，不等于null 说明有数据，(n = tab.length) > 0 同理说明 table 中有数据 //同时将 该位置的元素 赋值为 first if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //定位到了桶的到的位置的元素就是想要获取的 key 对应的，直接返回该元素 if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) { return first; } //到这一步说明定位到的元素不是想要的，且该位置不仅仅有一个元素，需要判断是链表还是树 if ((e = first.next) != null) { //是否已经树化 if (first instanceof TreeNode) { return ((TreeNode<K, V>) first).getTreeNode(hash, key); } //处理链表的情况 do { //如果遍历到了就直接返回该元素 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { return e; } } while ((e = e.next) != null); } } //遍历不到返回null return null; } put方法 下面是JDK 1.8中HashMap的put方法的简要实现过程： ...

典型回答 我们知道，第一次创建HashMap的时候，就会指定其容量（如果未显示制定，默认是16），那随着我们不断的向HashMap中put元素的时候，就有可能会超过其容量，那么就需要有一个扩容机制。 ✅HashMap是如何扩容的？ 从代码中我们可以看到，在向HashMap中添加元素过程中，如果 元素个数（size）超过临界值（threshold） 的时候，就会进行自动扩容（resize），并且，在扩容之后，还需要对HashMap中原有元素进行rehash，即将原来桶中的元素重新分配到新的桶中。 在HashMap中，临界值（threshold） = 负载因子（loadFactor） * 容量（capacity）。 loadFactor是负载因子，表示HashMap满的程度，默认值为0.75f，也就是说默认情况下，当HashMap中元素个数达到了容量的3/4的时候就会进行自动扩容。 为什么选择0.75呢？背后有什么考虑？为什么不是1，不是0.8？不是0.5，而是0.75呢？ 在JDK的官方文档中，有这样一段描述： As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). 大概意思是：一般来说，默认的负载因子(0.75)在时间和空间成本之间提供了很好的权衡。更高的值减少了空间开销，但增加了查找成本(反映在HashMap类的大多数操作中，包括get和put 试想一下，如果我们把负载因子设置成1，容量使用默认初始值16，那么表示一个HashMap需要在"满了"之后才会进行扩容。 那么在HashMap中，最好的情况是这16个元素通过hash算法之后分别落到了16个不同的桶中，否则就必然发生哈希碰撞。而且随着元素越多，哈希碰撞的概率越大，查找速度也会越低。 0.75的数学依据 另外，我们可以通过一种数学思维来计算下这个值是多少合适。 ...

典型回答 为什么需要扩容？假设现在散列表中的元素已经很多了，但是现在散列表的链化已经比较严重了，哪怕是树化了，时间复杂度也没有O(1)好，所以需要扩容来降低Hash冲突的概率，以此来提高性能。 我们知道，当++size > threshold 之后(详见java.util.HashMap#putVal方法)，HashMap就会初始化新的新的桶数组，该桶数组的size为原来的两倍，在扩大桶数组的过程中，会涉及三个部分： 如果某桶节点没有形成链表，则直接rehash到其他桶中 如果桶中形成链表，则将链表重新链接 如果桶中的链表已经形成红黑树，但是链表中的元素个数小于6，则进行取消树化的操作 桶元素重新映射 如果桶中只有一个元素，没有形成链表，则将原来的桶引用置为null，同时，将该元素进行rehash即可，如下代码所示： 1 2 3 if (e.next == null) { newTab[e.hash & (newCap - 1)] = e; } 链表重新链接 假设有4个key，分别为a，b，c，d，且假定他们的hash值如下： 1 2 3 4 hash(a) = 3; hash(a) & 7 = 3; hash(a) & 8 = 0; hash(b) = 11; hash(b) & 7 = 3; hash(b) & 8 = 8; hash(c) = 27; hash(c) & 7 = 3; hash(c) & 8 = 8; hash(d) = 59; hash(d) & 7 = 3; hash(d) & 8 = 8; 假如此时HashMap的cap为8，某个桶中已经形成链表，则可得到：table[3]=a->b->c->d ...

典型回答 扩展知识 下面是JDK 1.8中HashMap的remove方法的简要实现过程： 首先，remove方法会计算键的哈希值，并通过哈希值计算出在数组中的索引位置。 如果该位置上的元素为空，说明没有找到对应的键值对，直接返回null。 如果该位置上的元素不为空，检查是否与当前键相等，如果相等，那么将该键值对删除，并返回该键值对的值。 如果该位置上的元素不为空，但也与当前键不相等，那么就需要在链表或红黑树中继续查找。 遍历链表或者红黑树，查找与当前键相等的键值对，找到则将该键值对删除，并返回该键值对的值，否则返回null。 源码解读 1 2 3 4 5 public V remove(Object key) { Node<K, V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } 重点还是来看下 removeNode 方法： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 /** * Implements Map.remove and related methods. * * @param hash hash 值 * @param key key 值 * @param value value 值 * @param matchValue 是否需要值匹配 false 表示不需要 * @param movable 不用管 * @return the node, or null if none */ final Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { //当前HashMap 中的散列表的引用 Node<K, V>[] tab; //p：表示当前的Node元素 Node<K, V> p; // n：table 的长度 // index：桶的下标位置 int n, index; //(tab = table) != null && (n = tab.length) > 0 条件成立，说明table不为空（table 为空就没必要执行了） // p = tab[index = (n - 1) & hash]) != null 将定位到的捅位的元素赋值给 p ，并判断定位到的元素不为空 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { //进到 if 里面来了，说明已经定位到元素了 //node：保存查找到的结果 //e：表示当前元素的下一个元素 Node<K, V> node = null, e; K k; V v; // 该条件如果成立，说明当前的元素就是要找的结果（这是最简单的情况，这个是很好理解的） if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) { node = p; } //到这一步，如果 (e = p.next) != null 说明该捅位找到的元素可能是链表或者是树，需要继续判断 else if ((e = p.next) != null) { //树，不考虑 if (p instanceof TreeNode) { node = ((TreeNode<K, V>) p).getTreeNode(hash, key); } //处理链表的情况 else { do { //如果条件成立，说明已经匹配到了元素，直接将查找到的元素赋值给 node，并跳出循环（总体还是很好理解的） if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } //将正在遍历的当前的临时元素 e 赋值给 p p = e; } while ((e = e.next) != null); } } // node != null 说明匹配到了元素 //matchValue为false ，所以!matchValue = true，后面的条件直接不用看了 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { //树，不考虑 if (node instanceof TreeNode) { ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable); } // 这种情况是上面的最简单的情况 else if (node == p) { //直接将当前节点的下一个节点放在当前的桶位置（注意不是下一个桶位置，是该桶位置的下一个节点） tab[index] = node.next; } else { //说明定位到的元素不是该桶位置的头元素了，那直接进行一个简单的链表的操作即可 p.next = node.next; } //移除和添加都属于结构的修改，需要同步自增 modCount 的值 ++modCount; //table 中的元素个数减 1 --size; //啥也没做，不用管 afterNodeRemoval(node); //返回被移除的节点元素 return node; } } //没有匹配到返回null 即可 return null; } 我想对你说的话都在注释里面了，亲一定要好好看哦。 ...

典型回答 在JDK 1.7中，ConcurrentHashMap使用了分段锁技术，即将哈希表分成多个段，每个段拥有一个独立的锁。这样可以在多个线程同时访问哈希表时，只需要锁住需要操作的那个段，而不是整个哈希表，从而提高了并发性能。 虽然JDK 1.7的这种方式可以减少锁竞争，但是在高并发场景下，仍然会出现锁竞争，从而导致性能下降。 在JDK 1.8中，ConcurrentHashMap的实现方式进行了改进，使用节点锁的思想，即采用“CAS+Synchronized”的机制来保证线程安全。 在JDK 1.8中，ConcurrentHashMap会在添加元素时，使用CAS无锁化初始化桶和将元素插入空桶；针对已有节点的桶，使用synchronized加锁，再次尝试put。这样可以避免分段锁机制下的锁粒度太大，以及在高并发场景下，由于线程数量过多导致的锁竞争问题，提高了并发性能。 ✅ConcurrentHashMap为什么在JDK 1.8中废弃分段锁？ 扩展知识 源码分析 ConcurrentHashMap将哈希表分成多个段，每个段拥有一个独立的锁，这样可以在多个线程同时访问哈希表时，只需要锁住需要操作的那个段，而不是整个哈希表，从而提高了并发性能。下面是ConcurrentHashMap中分段锁的代码实现： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 static final class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; volatile V val; volatile Node<K,V> next; Node(int hash, K key, V val, Node<K,V> next) { this.hash = hash; this.key = key; this.val = val; this.next = next; } // ... } static final class Segment<K,V> extends ReentrantLock implements Serializable { private static final long serialVersionUID = 2249069246763182397L; transient volatile HashEntry<K,V>[] table; transient int count; transient int modCount; transient int threshold; final float loadFactor; } 在上面的代码中，我们可以看到，每个Segment都是ReentrantLock的实现，每个Segment包含一个HashEntry数组，每个HashEntry则包含一个key-value键值对。 ...

典型回答 在 JDK 1.8 中，ConcurrentHashMap作为一个并发容器，他是解决了fail-fast的问题的，也就是说，他是一个fail-safe的容器。 通过以下两种机制来实现 fail-safe 特性： 首先，在 ConcurrentHashMap 中，遍历操作返回的是弱一致性迭代器，这种迭代器的特点是，可以获取到在迭代器创建前被添加到 ConcurrentHashMap 中的元素，但不保证一定能获取到在迭代器创建后被添加/删除的元素。 弱一致性是指在并发操作中，不同线程之间的操作可能不会立即同步，但系统会在某个时刻趋于一致。这种弱一致性的特性有助于实现 fail-safe 行为，即使在迭代或操作过程中发生了并发修改，也不会导致异常或数据损坏。即他不会抛出ConcurrentModifiedException 另外。在 JDK 1.8 中，ConcurrentHashMap 中的 Segment 被移除了，取而代之的是使用类似于cas+synchronized的机制来实现并发访问。在遍历 ConcurrentHashMap 时，只需要获取每个桶的头结点即可，因为每个桶的头结点是原子更新的，不会被其他线程修改。这个设计允许多个线程同时修改不同的桶，这减少了并发修改的概率，从而降低了冲突和数据不一致的可能性。 也就是说，ConcurrentHashMap 通过弱一致性迭代器和 Segment 分离机制来实现 fail-safe 特性，可以保证在遍历时不会受到其他线程修改的影响。 扩展知识 弱一致性保障 ConcurrentHashMap 提供的是弱一致性保障，这是因为在多线程并发修改 ConcurrentHashMap 时，可能会出现一些短暂的不一致状态，即一个线程进行了修改操作，但是另一个线程还没有看到这个修改。因此，在并发修改 ConcurrentHashMap 时，不能保证在所有时刻 ConcurrentHashMap 的状态都是一致的。 首先就是因为前面提到的弱一致性迭代器，在 ConcurrentHashMap 中，使用迭代器遍历时，不能保证在迭代器创建后所有的元素都被迭代器遍历到。这是因为在迭代器遍历过程中，其他线程可能会对 ConcurrentHashMap 进行修改，导致迭代器遍历的元素发生变化。为了解决这个问题，ConcurrentHashMap 提供了一种弱一致性迭代器，可以获取到在迭代器创建前被添加到 ConcurrentHashMap 中的元素，但是可能会无法获取到迭代器创建后被添加/删除的元素。

典型回答 在调用集合前，使用synchronized或者ReentrantLock对代码加锁（读写都要加锁） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public class SynchronizedCollectionExample { private List<Integer> list = new ArrayList<>(); public void add(int value) { synchronized (SynchronizedCollectionExample.class) { list.add(value); } } public int get(int index) { synchronized (SynchronizedCollectionExample.class) { return list.get(index); } } } 使用ThreadLocal，将集合放到线程内访问，但是这样集合中的值就不能被其他线程访问了 1 2 3 4 5 6 7 8 9 10 11 public class ThreadLocalCollectionExample { private ThreadLocal<List<Integer>> threadLocalList = ThreadLocal.withInitial(ArrayList::new); public void add(int value) { threadLocalList.get().add(value); } public int get(int index) { return threadLocalList.get().get(index); } } 使用Collections.synchronizedXXX()方法，可以获得一个线程安全的集合 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import java.util.Collections; import java.util.List; import java.util.ArrayList; public class CollectionsSynchronizedExample { List<Integer> synchronizedList = Collections.synchronizedList(new ArrayList<Integer>()); public void add(int value) { synchronizedList.add(value); } public int get(int index) { return synchronizedList.get(index); } } 使用不可变集合进行封装，当集合是不可变的时候，自然是线程安全的 1 2 3 4 5 6 7 8 9 import com.google.common.collect.ImmutableList; public class ImmutableCollectionExample { private ImmutableList<Integer> immutableList = ImmutableList.of(1, 2, 3); public int get(int index) { return immutableList.get(index); } } 或者： ...

Copy-On-Write简称COW，是一种用于程序设计中的优化策略。其基本思路是，从一开始大家都在共享同一个内容，当某个人想要修改这个内容的时候，才会真正把内容Copy出去形成一个新的内容然后再改，这是一种延时懒惰策略。 从JDK1.5开始Java并发包里提供了两个使用CopyOnWrite机制实现的并发容器,它们是CopyOnWriteArrayList和CopyOnWriteArraySet。CopyOnWrite容器非常有用，可以在非常多的并发场景中使用到。 CopyOnWriteArrayList相当于线程安全的ArrayList，CopyOnWriteArrayList使用了一种叫写时复制的方法，当有新元素add到CopyOnWriteArrayList时，先从原有的数组中拷贝一份出来，然后在新的数组做写操作，写完之后，再将原来的数组引用指向到新数组。 这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。 注意：CopyOnWriteArrayList的整个add操作都是在锁的保护下进行的。也就是说add方法是线程安全的。 **CopyOnWrite并发容器用于读多写少的并发场景。**比如白名单，黑名单，商品类目的访问和更新场景。 和ArrayList不同的是，它具有以下特性： 支持高效率并发且是线程安全的 因为通常需要复制整个基础数组，所以可变操作（add()、set() 和 remove() 等等）的开销很大 迭代器支持hasNext(), next()等不可变操作，但不支持可变 remove()等操作 使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照 若有收获，就点个赞吧

典型回答 Java 8是一个比较大的版本，目前很多人还在用，他有很多内容的升级，关于HashMap也有很多，其中最主要的就是引入了红黑树，除此之外hash、resize等方法都有些改动。 特性 JDK 1.7 JDK 1.8 数据结构 数组+链表 数组+链表+红黑树 插入方式 头插法 尾插法 扩容机制 全量 rehash 高位拆分免 rehash 哈希计算 4 次位运算 + 5 次异或 简化扰动：1 次位运算 + 1 次异或 红黑树 Java 1.7中的HashMap使用一个数组+链表的数据结构来存储键值对，这会导致在处理hash冲突时性能下降，特别是当链表变得很长的时候时。Java 1.8中的HashMap引入了红黑树来替代链表，以解决冲突时性能问题。这意味着当链表变得过长时，HashMap可以将链表转换为树，从而提高了查找、插入和删除操作的性能。 ✅为什么在JDK8中HashMap要转成红黑树 节点变化 在JDK 1.8中，Node用于代替了旧版本中的普通链表节点（Entry），在旧版本中，每个桶中的元素都需要一个单独的Entry对象，而在新版本中，使用Node来代替，并且为了支持红黑树还引入了TreeNode。在Node中hash字段变成了final类型，一定确定就不再可变。 1.7中的Entry： 1 2 3 4 5 6 static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; } 1.8中的Node： 1 2 3 4 5 6 static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; } 1 2 3 4 5 6 7 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; } 尾插法 为了解决1.7中的并发场景中存在的死循环的问题，JDK1.8把头插法改成了尾插法。 ...