Java面试题-集合类

目录

1、请简单介绍下 Java 的集合类吧。

Collection

Set

TreeSet和HashSet

List

ArrayList 和 LinkedList

数组和链表的区别

Java 的列表有哪些实现类？

Vector

Queue

Map

能说下 HashMap 的实现原理吗？

能说下 HashMap 的扩容机制吗？

HashMap与HashTable

HashSet 和 HashMap

LinkedHashMap 有了解过吗？

TreeMap 有了解过吗？

IdentityHashMap 有了解过吗？

WeakHashMap 有了解过吗？

ConcurrentHashMap 1.7和1.8有什么区别？

ConcurrentHashMap#get 需要加锁吗？

为什么 ConcunentHashMap 不支持 key 或者 value 为 null ？

2、你有听过 Copy-0n-Write 吗？

3、ConcurentModificationException 这种错误有遇到过吗？为什么会出现这个错误？

扩展单线程情况下修改集合

---

1、请简单介绍下 Java 的集合类吧。

Java 集合从分类上看，有 collection 和 map 两种。前者是存储对象的集合类,后者存储的是键值对（ key-value)

Collection

Set

TreeSet和HashSet

主要功能是保证存储的集合不会重复，至于集合是有序还是无序的，需要看具体的实现类，比如 TreeSet 就是有序的， HashSet 是无序的

List

ArrayList 和 LinkedList

列表具体的实现类有 ArrayList 和 LinkedList。 两者的区别在于底层实现不同，前者是数组，后者是双向链表。

数组和链表的区别

数组的内存是连续的，且存储的元素大小是固定的，实现上是基于一个内存地址，然后由于元素固定大小，支持利用下标的直接访问。

而由于要保持内存连续这个持性，不能在内存中间空一块，所以删除中间元素时就需要搬迁元素，需进行内存拷贝，所以说删除的效率不高。

链表的内存不需要连续，它们是通过指针相连，这样对内存的要求没那么高（数组的申请需要一块连续的内存），链表就可以散装内存，不过链表需要额外存储指针，所以总体来说，链表的占用内存会大一些。

且由于是指针相连，所以直接无法随机访问一个元素，必须从头开始遍历。

空间局部性 (spatial locality) ：如果一个存储器的位置被引用，那么将来它附近的位置也会被引用。

根据这个原理就会有预读功能，像 CPU 缓存就会读连续的内存，这样一来如果你本就要遍历数组的，那么你后面的数据就已经被上一次读取前面数据的时候，一块被加载了，这样就是 CPU 亲和性。

反观链表，由于内存不连续，所以预读不到，所以CPU 亲和性低。

链表（数组）加了点约束的话，还可以用作栈、队列和双向队列。

Java 的列表有哪些实现类？

最常见的就是 ArrayList 和 LinkedList, 汪意这两者都不是并发容器，所以线程不安全。

ArrayList 是基于动态数组实现的，因此它的特性与数组一致，随机访问很快，删除和插入相对比较慢。

LinkedList 是基于双向链表实现的，因此两端都能操作，特性就是正常的链表特性，两端插入删除很快，但是随机访问需要遍历链表所以比较慢。

Vector

它也是基于动态数组实现，与 ArrayList 类似，但它是线程安全，所有方法都是同步的（都加了 synchronize 锁），也因为同步开销较大，所以它性能相对较低。

Queue

队列，有序，严格遵守先进先出，常用的实现类就是 LinkedList。

优先队列，即PriorityQueue, 内部是基于数组构建的，用法就是你定义一个 comparator ，自己定义对比规则，这个队列就是按这个规则来排列出队的优先级。

Map

实现类 HashMap 无序。

还有两个实现类， LinkedHashMap 和 TreeMap, 前者里面搞了个链表，这样塞入顺序就被保存下来了，后者是红黑树实现了，所以有序。

能说下 HashMap 的实现原理吗？

HashMap 基于哈希表的数据结构实现，允许存储键值对，并且通过键快速访问对应的值。

它内部使用数组和链表（在 Java 8 及以后还可以使用红黑树）来存储元素，每个数组槽位 (bucket)对应一个链表或红黑树。

数组内的元素保存了 key 和 value。 当要塞入一个键值对的时候，会根据一个 hash 算法计算 key 的hash 值然后通过数组大小 n-1 & hash 值之后得到一个数组的下标，然后往那个位置塞入这键值对。

我们知道， hash 算法是可能产生冲突的，且数组的大小是有限的，所以很可能通过不同的 key 计算得到一样的下标，因此为了解决键值对冲突的问题，采了链表法，如下图所示：

当链表的长度大于 8 且数组大小大于等于 64 的时候，就把链表转化成红黑树，当红黑树节点小于6的时候，又会退化成链表。

能说下 HashMap 的扩容机制吗？

我们都知道 HashMap 是基于数组和链表（红黑树）来实现的。

在 HashMap 中有阈值的概念，比如我们设置一个16 大小的 map, 那么默认的阈值等于 16 * 0.75=12，也就是说，如果 map 中元素的数量超过 12 ，那么就会触发扩容。

扩容的时候，默认会新建一个数组，新数组的大小是老数组的两倍。然后将 map 内的元素重新 hash 映射搬运到新的数组中。

因为数组的长度是 2 的 n 次方，所以设以前的数组长度（ 16 ）二进制表示是 010000 ，那么新数组的长度 （32 ）二进制表示是 100000, 它们之间的差别就在于高位多了一个 1 ，而我们通过key 的 hash 值定位其在数组位置所采用的方法是（数组长度-1 ）& hash 。

HashMap与HashTable

线程安全性：

HashMap: 不是线程安全的。如果多个线程同时访问一个 HashMap, 并且至少有一个线程在结构上修改了它（比如添加或删除键值对），可以通过以下代码封装进行同步：

Map<String,String> map = Collections.synchronizedMap(new HashMap<>());

Hashtable: 是线程安全的。所有的方法都加了锁，可以在多线程环境中使用。

性能：

HashMap: 由于没有同步开销，所以它的性能一般比 Hashtable 更好，尤其是在单线程环境中。

Hashtable: 由于每个方法都进行同步，因此性能比HashMap 差。

null 值的处理：

HashMap: 允许一个 null 键和多个 null 值。

HashtabIe ：不允许 null 键和 null 值。如果将 null 键或值放入 Hashtable，会抛出 NullPointerException.

HashSet 和 HashMap

HashSet 其实内部的实现还是 HashMap!并且 HashSet 的add方法实际上调用的就是 HashMap 的put方法。

因此 HashSet 就是封装了一下 HashMap! 内部的实现逻辑其实都由 HashMap 来代劳。

LinkedHashMap 有了解过吗？

LinkedHashMap 的父类是 HashMap ，所以HashMap 有的它都有，然后基于 HashMap 做了一些扩展。

首先它把 HashMap 的 Entry 加了两个指针：before 和 after。

这目的已经很明显了，就是要把塞入的 Entry 之间进行关联，串成双向链表，如下图红色的就是新增的两个指针：

并且内部还有个 accessOrder 成员，默认是false, 代表链表是顺序是按插入顺序来排的，如果是 true 则会根据访问顺序来进行调整就是咱们熟知的 LRU 那种，如果哪个节点访问了，就把它移到最后，代表最近访问的节点。

具体实现其实就是 HashMap 埋了几个方法，然后 LinkedHashMap 实现了这几个方法做了操作，比如以下这三个，从方法名就能看出了．访问节点之后干啥；插入节点之后干啥；删除节点之后干啥。

举个 afterNodelnsertion 的例子，它埋在HashMap 的put里，在塞入新节点之后，会调用这个方法

然后 LinkedHashMap 实现了这个方法，可以看到这个方法主要用来移除最老的节点。

看到这你能想到啥？假如你想用 map 做个本地缓存，由于缓存的数量不可能无限大，所以你就能继承 LinkedHashMap 来实现，当节点超过一定数量的时候，在插入新节点的同时，移除最老最久没有被访问的节点这样就实现了一个 LRU。

TreeMap 有了解过吗？

TreeMap 内部是通过红黑树实现的，可以让 key实现 Comparable 接囗或者自定义实现一个comparator 传入构造函数，这样塞入的节点就会根据你定义的规则进行排序。

基本特性：

• 数据结构： TreeMap 基于红黑树实现，红黑树是一种自平衡的二叉查找树，能够保证基本操作（插入、删除、查找）的时间复杂度为O(log n)。

• 键的有序性：TreeMap 中的键是有序的，默认按自然顺序（键的 ComparabIe 实现）排序，也可以通过构造时提供的 Comparator 进行自定义排序。

• 不允许 null 键： TreeMap 不允许键为 null, 但允许值为 null。

IdentityHashMap 有了解过吗？

它判断是否相等的依据不是靠 equals,而是对象本身是否是它自己。

什么意思呢？首先看它覆盖的 hash 方法：

可以看到，它用了个 System.identityHashCode(x) ,而不是 x.hashCode() 。

而这个方法会返回原来默认的 hashCode 实现，不管对象是否重写了 hashCode 方法，默认的实现返回的值是对象的内存地址转化成整数。

它判断 key 是否相等并不靠 hash 值和 equals, 而是直接用了==，而==其实就是地址判断！只有相同的对象进行==才会返回 true。

ldentityHashMap 的存储方式有点不一样，它是将 value 存在 key 的后面。

WeakHashMap 有了解过吗？

WeakHashMap 是 Java 中的一种特殊的 Map 实现，它使用弱引用（ WeakReference) 来存储键。

WeakHashMap 里对 key 的引用就是弱引用，所以当一个键不再有任何强引用时，即使它被WeakHashMap 引用着，垃圾回收器也可以回收该键和它对应的值。

它被使用在临时需要大量数据，但这些数据又可以因为内存吃紧随时被回收的场景。

比如一些缓存场景，例如缓存一些图片，当图片不再被其他部分引用时，它们可以被垃圾回收，从而避免内存泄漏。

在一些框架中需要为对象存储额外的元数据但不希望这些元数据影响对象的生命周期。可以用 WeakHashMap 来存储这些元数据。

ConcurrentHashMap 1.7和1.8有什么区别？

ConcurrentHashMap 1.7：

其实大体的哈希表实现跟 HashMap 没有本质的区别，都是经过 key 的 hash 定位到一个下标然后获取元素如果冲突了就用链表相连。

差别就在于引入了一个 Segments 数组，我们来看下大致的结构。

原理就是先通过 key 的 hash 判断得到 Segment数组的下标，将这个 Segment 上锁，然后再次通过 key 的 hash 得到 Segment 里 HashEntry数组的下标，下面这步其实就是 HashMap 一致了，所以我说差别就是引入了一个 Segments 数组。

因此可以简化的这样理解：每个 Segment 数组存放的就是一个单独的 HashMap。

可以看到，图上我们有 6 个 Segment, 那么等于有六把锁，因此共可以有六个线程同时操作这个ConcurrentHashMap, 并发度就是 6 ，相比于直接将 put 方法上锁，并发度就提高了，这就是分段锁。

具体上锁的万式来源于 Segment, 这个类实际继承了 ReentrantLock 因此它自身具备加锁的功能。

ConcurrentHashMap 1.8：

1.8 ConcurrentHashMap 做了更细粒度的锁控制，可以理解为 1.8 HashMap 的数组的每个位置都是一把锁，这样扩容了锁也会变多，并发度也会增加。

思想的转变就是把粒度更加细化。不分段了，我直接把 Node 数组的每个节点分别上一把锁，这样并发度不就更高了吗？

并且 1.8 也不借助于 ReentrantLock 了，直接用synchronized ，这也侧面证明，都 1.8 了synchronized 优化后的速度已经不下于ReentrantLock 了。

1.8 的扩容，它允许协助扩容，也就是多线程扩容。

ConcurrentHashMap#get 需要加锁吗？

不需要加锁。保证 Put 的时候线程安全之后， get 的时候只需要保证可见性即可，而可见性不需要加锁。具体是通过 Unsafe#getXXXVolatile 和用 volatile 来修饰节点的 val 和 next 指针来实现的。

为什么 ConcunentHashMap 不支持 key 或者 value 为 null ？

1 ）避免二义性

因为在多线程情况下， get 方法返回 null 时，无法区分 map 里到底是不存在在这个 key ，还是说被 put(key, null) 了。

这里可能有人会说，那 HashMap 不一样有这个问题？ HashMap 可以通过 containsKey 来判断是否存在这个 key ，而多线程使用的ConcurrentHashMap 就不能够。

比如你 get (key) 得到了 null, 此时 map 里面没有这个 key 的，但是你不知道，所以你想调用 containsKey 看看，而恰巧在你调用之前，别的线程 Put 了这个 key ，这样你 containsKey 就发现有这个 key, 这是不是就发生"误会"了？

2 ）简化实现

不支持 null, 这样在并发环境下，可以避免对 null 的特殊处理，可以减少代码中的条件分支，提高性能和可维护性。

2、你有听过 Copy-0n-Write 吗？

顾名思义，当需要 write 的时候 copy 。

我们都知道操作系统有父子进程的概念，当父进程创建子进程之后，父子进程的内存空间是共享的，只有当子进程（或父进程）尝试写入或修改数据的时候，才需要复制一个内存新页面写入。

这样有什么好处？

因为一开始共享内存，所以在没有发生写入的时候，内存其实压根不需要新复制一份，当写入的时候才发生复制，这就不仅节省内存，也避免了内存频繁复制的开销。

copy-on-write 对读比较友好，多个并发读可以共享互相不会阻塞，且当有个写在修改数据的时候，也不会阻塞读，因为可以读老的数据。但是写是独占的。（读写分离）

不过 Copy-On-Write 也有缺点，写操作会延迟，因为写的时候需要拷贝数据，这并不快。

如果写操作非常频繁就会一直拷贝数据，开销比较大，所以它适合读多写少的场景。

在 Java 中主要有 CopyOnWriteArrayList 这个实现类，底层基于数组存储，写的时候会烤贝一个新数组。它是线程安全的，读不会被写阻塞。

3、ConcurentModificationException 这种错误有遇到过吗？为什么会出现这个错误？

这个错误发生在迭代集合对象时候，修改集合本身内容，包括新增、修改和删除。

其实这个错误是为了检测并发修改的行为，在非线程安全的集合中，并发修改集合数据可能会发生数据丢失等一些奇怪的问题。

因此 Java 引入了这个错误，是为了保证集合迭代时语义的一致性。简单来说就是规矩就这样定了！这个集合非并发安全的，不让你改，改了就报错。

它的原理是在集合内部维护了一个修改次数的记录，如果发生了修改，那么这个次数会增加。在每次迭代的时候会检查这个次数，发现增加了就立马报错。

如果非要修改那么可以使用线程安全的集合，例如可以使用 collections.synchronizedList 将List包装为线程安全的集合或者直接使用CopyOnWriteArrayListConcurrentHashMap 。

扩展单线程情况下修改集合

如果单线程在一个循环中遍历集合的同时直接修改集合也会报这个错，可以通过 lterator 进行遍历，并使用 lterator 提供的 remove 方法来删除元素可以避免 ConcurentModificationException。