Java集合八股

本文最后更新于 2024年8月12日中午

Java集合八股

数组与集合的区别是什么

数组是固定长度的数据结构，一旦创建长度就无法改变，而集合是动态长度的数据机构，可以根据需要动态增加或减少元素。
数组可以包含基本数据类型和对象，而集合只能包含对象。
数组可以直接访问元素，而集合需要通过迭代器或其他方法来访问元素。

说一说Java中的集合

常见的Java集合分为两大类：Collection 和 Map。

Collection和Map

Collection

List：有序的集合，其中的元素可以重复。
- ArrayList：基于动态数组实现，查询速度快，但在中间插入和删除元素时速度较慢。
- LinkedList：基于双向链表实现，插入和删除速度快，但查询速度较慢。
- Vector：与ArrayList类似，但它是线程安全的。
Set：无序的集合，其中的元素不可以重复。
- HashSet：基于哈希表实现，不保证有序。
- LinkedHashSet：维护元素的插入顺序。
- TreeSet：基于红黑树实现，元素按照自然顺序或者自定义的比较器顺序进行排序。
Queue：一种先进先出的数据结构
- LinkedList：除了实现List接口外，还实现了Deque接口，可以作为双端队列使用。
- PriorityQueue：基于优先堆实现，元素可以按照自然顺序或者自定义的比较器顺序出队。
Deque：双端队列，可以在队头和队尾进行元素的插入和删除。
- ArrayDeque：基于动态数组实现的双端队列。
- LinkedList：同样可以作为双端队列使用。

Map：一个键值对集合，存储键、值和之间的映射。Key 无序，唯一；value 不要求有序，允许重复。

HashMap：基于哈希表实现，不保证有序。
LinkedHashMap：保持键的插入顺序。
TreeMap：基于红黑树实现，键按照自然顺序或者自定义的比较顺序进行排序。
HashTable：与HashMap类似，但它是线程安全的。

Java中的线程安全的集合是什么

在 java.util 包中的线程安全的类主要 2 个，其他都是非线程安全的：

Vector：线程安全的动态数组，其内部方法基本都经过synchronized修饰，如果不需要线程安全，并不建议选择，毕竟同步是有额外开销的。Vector 内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。
Hashtable：线程安全的哈希表，HashTable 的加锁方法是给每个方法加上 synchronized 关键字，这样锁住的是整个 Table 对象，不支持 null 键和值，由于同步导致的性能开销，所以已经很少被推荐使用，如果要保证线程安全的哈希表，可以用ConcurrentHashMap。

java.util.concurrent 包提供的都是线程安全的集合：

并发Map
- ConcurrentHashMap：这是一个线程安全的HashMap的变体。与HashTable相比，ConcurrentHashMap在并发环境下提供了更好的性能，因为它只会锁定部分段（segment），而不是整个数据结构。
- ConcurrentSkipListMap：线程安全的有序集合。它们内部使用跳表（Skip List）数据结构，可以提供与TreeMap类似的功能，但在并发环境下具有更好的性能。
并发Set
- ConcurrentSkipListSet：是线程安全的有序的集合。底层是使用ConcurrentSkipListMap实现。
- CopyOnWriteArraySet：在每次修改（例如添加或删除元素）时都会复制整个底层数组，从而实现线程安全。这使得在迭代期间可以不需要锁定，因此在读多写少的并发环境下表现很好。
并发List
- CopyOnWriteArrayList：它是 ArrayList 的线程安全的变体，其中所有写操作（add，set等）都通过对底层数组进行全新复制来实现，允许存储 null 元素。即当对象进行写操作时，使用了Lock锁做同步处理，内部拷贝了原数组，并在新数组上进行添加操作，最后将新数组替换掉旧数组；若进行的读操作，则直接返回结果，操作过程中不需要进行同步。
并发Queue
- ConcurrentLinkedQueue：一个线程安全的队列，使用链表实现。它采用了一种非阻塞的算法来实现线程安全，因此在高并发环境下性能很好。
- BlockingQueue：BlockingQueue 的主要功能并不是在于提升高并发时的队列性能，而在于简化多线程间的数据共享。BlockingQueue 提供一种读写阻塞等待的机制，即如果消费者速度较快，则 BlockingQueue 则可能被清空，此时消费线程再试图从 BlockingQueue 读取数据时就会被阻塞。反之，如果生产线程较快，则 BlockingQueue 可能会被装满，此时，生产线程再试图向 BlockingQueue 队列装入数据时，便会被阻塞等待。
并发Deque
- LinkedBlockingDeque：是一个线程安全的双端队列实现。它的内部使用链表结构，每一个节点都维护了一个前驱节点和一个后驱节点。同一时间只能有一个线程对其进行操作
- ConcurrentLinkedDeque：ConcurrentLinkedDeque是一种基于链接节点的无限并发链表。可以安全地并发执行插入、删除和访问操作。

Collection和Collections的区别

Collection是Java集合框架中的一个接口，它是所有集合类的基础接口。它定义了一组通用的操作和方法，如添加、删除、遍历等，用于操作和管理一组对象。Collection接口有许多实现类，如List、Set和Queue等。
Collections（注意有一个s）是Java提供的一个工具类，位于java.util包中。它提供了一系列静态方法，用于对集合进行操作和算法。Collections类中的方法包括排序、查找、替换、反转、随机化等等。这些方法可以对实现了Collection接口的集合进行操作，如List和Set。

集合遍历的方法有哪些

普通 for 循环： 可以使用带有索引的普通 for 循环来遍历 List。
增强 for 循环（for-each循环）： 用于循环访问数组或集合中的元素。
Iterator 迭代器： 可以使用迭代器来遍历集合，特别适用于需要删除元素的情况。
ListIterator 列表迭代器： ListIterator是迭代器的子类，可以双向访问列表并在迭代过程中修改元素。
使用 forEach 方法： Java 8引入了 forEach 方法，可以对集合进行快速遍历。
Stream API： Java 8的Stream API提供了丰富的功能，可以对集合进行函数式操作，如过滤、映射等。

讲一下Java中list的几种实现，几种实现有什么不同

Vector 是 Java 早期提供的线程安全的动态数组，如果不需要线程安全，并不建议选择，毕竟同步是有额外开销的。Vector 内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。
ArrayList 是应用更加广泛的动态数组实现，它本身不是线程安全的，所以性能要好很多。与 Vector 近似，ArrayList 也是可以根据需要调整容量，不过两者的调整逻辑有所区别，**Vector 在扩容时会提高 1 倍，而 ArrayList 则是增加 50%**。
LinkedList 顾名思义是 Java 提供的双向链表，所以它不需要像上面两种那样调整容量，它也不是线程安全的。

Vector和ArrayList作为动态数组，其内部元素以数组形式顺序存储，非常适合随机访问，但插入和删除要移动大量的元素。

LinkedList 进行节点插入、删除却要高效得多，但是随机访问性能则要比动态数组慢。

ArrayList和LinkedList的区别，哪个是线程安全的

底层数据结构不同：ArrayList使用数组实现，通过索引进行快速访问元素。LinkedList使用链表实现，通过节点之间的指针进行元素的访问和操作。
插入和删除操作的效率不同：ArrayList在尾部的插入和删除操作效率较高，但在中间或开头的插入和删除操作效率较低，需要移动元素。LinkedList在任意位置的插入和删除操作效率都比较高，因为只需要调整节点之间的指针。
随机访问的效率不同：ArrayList支持通过索引进行快速随机访问，时间复杂度为O(1)。LinkedList需要从头或尾开始遍历链表，时间复杂度为O(n)。
空间占用：ArrayList在创建时需要分配一段连续的内存空间，因此会占用较大的空间。LinkedList每个节点只需要存储元素和指针，因此相对较小。
使用场景：ArrayList适用于频繁随机访问和尾部的插入删除操作，而LinkedList适用于频繁的中间插入删除操作和不需要随机访问的场景。

这两个集合都不是线程安全的，Vector是线程安全的

ArrayList线程安全吗？如何把ArrayList变成线程安全的

不是线程安全的

使用Vector类代替ArrayList，Vector是线程安全的List实现
1
Vector<String> vector = new Vector<>(arrayList);
使用Collections类的synchronizedList方法将ArrayList包装成线程安全的List
1
List<String> synchronizedList = Collections.synchronizedList(arrayList);

使用CopyOnWriteArrayList类代替ArrayList，它是一个线程安全的List实现

1	`CopyOnWriteArrayList<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>(arrayList);`

为什么ArrayList不是线程安全的

在高并发添加数据下，ArrayList会暴露三个问题：

部分值为null（我们并没有add null进去）
索引越界异常
size与我们add的数量不符

ArrayList和LinkedList的应用场景

ArrayList适用于需要频繁访问集合元素的场景。它基于数组实现，可以通过索引快速访问元素，因此在按索引查找、遍历和随机访问元素的操作上具有较高的性能。
LinkedList适用于频繁进行插入和删除操作的场景。它基于链表实现，插入和删除元素的操作只需要调整节点的指针，因此在插入和删除操作上具有较高的性能。

说一说ArrayList的扩容机制说一下

ArrayList在添加元素时，如果当前元素个数已经达到了内部数组的容量上限，就会触发扩容操作。

计算新的容量：一般情况下，新的容量会扩大为原容量的1.5倍（在JDK 10之后，扩容策略做了调整），然后检查是否超过了最大容量限制。
创建新的数组：根据计算得到的新容量，创建一个新的更大的数组。
将元素复制：将原来数组中的元素逐个复制到新数组中。
更新引用：将ArrayList内部指向原数组的引用指向新数组。
完成扩容：扩容完成后，可以继续添加新元素。

CopyWriteArrayList是如何实现线程安全的

CopyOnWriteArrayList底层也是通过一个数组保存数据，使用volatile关键字修饰数组，保证当前线程对数组对象重新赋值后，其他线程可以及时感知到。

在写入操作时，加了一把互斥锁ReentrantLock以保证线程安全。

public boolean add(E e) {
    //获取锁
    final ReentrantLock lock = this.lock;
    //加锁
    lock.lock();
    try {
        //获取到当前List集合保存数据的数组
        Object[] elements = getArray();
        //获取该数组的长度（这是一个伏笔，同时len也是新数组的最后一个元素的索引值）
        int len = elements.length;
        //将当前数组拷贝一份的同时，让其长度加1
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        //将加入的元素放在新数组最后一位，len不是旧数组长度吗，为什么现在用它当成新数组的最后一个元素的下标？建议自行画图推演，就很容易理解。
        newElements[len] = e;
        //替换引用，将数组的引用指向给新数组的地址
        setArray(newElements);
        return true;
    } finally {
        //释放锁
        lock.unlock();
    }
}

写入新元素时，首先会先将原来的数组拷贝一份并且让原来数组的长度+1后就得到了一个新数组，新数组里的元素和旧数组的元素一样并且长度比旧数组多一个长度，然后将新加入的元素放置都在新数组最后一个位置后，用新数组的地址替换掉老数组的地址就能得到最新的数据了。

读是没有加锁的，所以读是一直都能读

HashMap的实现原理介绍以下

在 JDK 1.7 版本之前， HashMap 数据结构是数组和链表，HashMap通过哈希算法将元素的键（Key）映射到数组中的槽位（Bucket）。如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上，因为链表的查询时间是O(n)，所以冲突很严重，一个索引上的链表非常长，效率就很低了。

Java7 HashMap结构

在 JDK 1.8 版本的时候做了优化，当一个链表的长度超过8的时候就转换数据结构，不再使用链表存储，而是使用红黑树，查找时使用红黑树，时间复杂度O（log n），可以提高查询性能，但是在数量较少时，即数量小于6时，会将红黑树转换回链表。

Java8 HashMap结构

哈希冲突解决方法有哪些

链接法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。
开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。
再哈希法（Rehashing）：当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存储键值对。
哈希桶扩容：当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

HashMap是线程安全的吗

解决方法

多线程环境可以使用Collections.synchronizedMap同步加锁的方式，还可以使用HashTable，但是同步的方式显然性能不达标，而ConurrentHashMap更适合高并发场景使用。

HashMap的put过程介绍一下

根据要添加的键的哈希码计算在数组中的位置（索引）。
检查该位置是否为空（即没有键值对存在），如果为空，则直接在该位置创建一个新的Entry对象来存储键值对。将要添加的键值对作为该Entry的键和值，并保存在数组的对应位置。将HashMap的修改次数（modCount）加1，以便在进行迭代时发现并发修改。
如果该位置已经存在其他键值对，检查该位置的第一个键值对的哈希码和键是否与要添加的键值对相同，如果相同，则表示找到了相同的键，直接将新的值替换旧的值，完成更新操作。
如果第一个键值对的哈希码和键不相同，则需要遍历链表或红黑树来查找是否有相同的键
- 如果键值对集合是链表结构，从链表的头部开始逐个比较键的哈希码和equals()方法，直到找到相同的键或达到链表末尾。如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。如果没有找到相同的键，则将新的键值对添加到链表的头部。
- 如果键值对集合是红黑树结构，在红黑树中使用哈希码和equals()方法进行查找。根据键的哈希码，定位到红黑树中的某个节点，然后逐个比较键，直到找到相同的键或达到红黑树末尾。如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。如果没有找到相同的键，则将新的键值对添加到红黑树中。
检查链表长度是否达到阈值（默认为8）。如果链表长度超过阈值，且HashMap的数组长度大于等于64，则会将链表转换为红黑树，以提高查询效率。
检查负载因子是否超过阈值（默认为0.75）。如果键值对的数量（size）与数组的长度的比值大于阈值，则需要进行扩容操作。
扩容操作：
- 创建一个新的两倍大小的数组。
- 将旧数组中的键值对重新计算哈希码并分配到新数组中的位置。
- 更新HashMap的数组引用和阈值参数。
完成添加操作。

HashMap的put(key, val)和get(key)过程

存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。
获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

HashMap调用get方法一定安全吗

空指针异常（NullPointerException）：如果你尝试用 null 作为键调用 get 方法，而 HashMap 没有被初始化（即为 null），那么会抛出空指针异常。不过，如果 HashMap 已经初始化，使用 null 作为键是允许的，因为 HashMap 支持 null 键。
线程安全：HashMap 本身不是线程安全的。如果在多线程环境中，没有适当的同步措施，同时对 HashMap 进行读写操作可能会导致不可预测的行为。例如，在一个线程中调用 get 方法读取数据，而另一个线程同时修改了结构（如增加或删除元素），可能会导致读取操作得到错误的结果或抛出 ConcurrentModificationException。如果需要在多线程环境中使用类似 HashMap 的数据结构，可以考虑使用 ConcurrentHashMap。

HashMap一般用什么做Key？为什么呢

用 String 做 key，因为 String对象是不可变的，一旦创建就不能被修改，这确保了Key的稳定性。如果Key是可变的，可能会导致hashCode和equals方法的不一致，进而影响HashMap的正确性。

为什么HashMap要用红黑树而不是平衡二叉树

平衡二叉树追求的是一种 “完全平衡” 状态：任何结点的左右子树的高度差不会超过 1，优势是树的结点是很平均分配的。这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
红黑树不追求这种完全平衡状态，而是追求一种 “弱平衡” 状态：整个树最长路径不会超过最短路径的 2 倍。优势是虽然牺牲了一部分查找的性能效率，但是能够换取一部分维持树平衡状态的成本。与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整，这也是我们为什么大多数情况下使用红黑树的原因

HashMap Key可以为null吗

可以为null

hashMap中使用hash()方法来计算key的哈希值，当key为空时，直接另key的哈希值为0，不走key.hashCode()方法；
hashMap虽然支持key和value为null，但是null作为key只能有一个，null作为value可以有多个；因为hashMap中，如果key值一样，那么会覆盖相同key值的value为最新，所以key为null只能有一个。

重写HashMap的equals和hashCode方法需要注意什么

所有不允许存储重复数据的集合类都使用hashCode()和equals()去查找重复，所以正确实现它们非常重要。equals()和hashCode()的实现应该遵循以下规则：

如果o1.equals(o2)，那么o1.hashCode() == o2.hashCode()总是为true的。
如果o1.hashCode() == o2.hashCode()，并不意味着o1.equals(o2)会为true。

重写HashMap的equals方法不当会出现什么问题

HashMap在比较元素时，会先通过hashCode进行比较，相同的情况下再通过equals进行比较。所以 equals相等的两个对象，hashCode一定相等。hashCode相等的两个对象，equals不一定相等（比如散列冲突的情况）

重写了equals方法，不重写hashCode方法时，可能会出现equals方法返回为true，而hashCode方法却返回false，这样的一个后果会导致在hashmap等类中存储多个一模一样的对象，导致出现覆盖存储的数据的问题，这与hashmap只能有唯一的key的规范不符合。

列举HashMap在多线程下可能出现的问题

JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。

说一说HashMap的扩容机制

思索。。。

HashMap的大小为什么是2的n次方大小

思索

往HashMap存20个元素，会扩容几次

一般情况下默认初始容量为16

插入第 1 到第 12 个元素时，不需要扩容。
插入第 13 个元素时，达到负载因子限制，需要扩容。此时，HashMap 的容量从 16 扩容到 32。
插入第 14 到第 20 个元素时，不需要扩容。

扩容一次

说说HashMap的负载因子

HashMap 负载因子 loadFactor 的默认值是 0.75，当 HashMap 中的元素个数超过了容量的 75% 时，就会进行扩容。

默认负载因子为 0.75，是因为它提供了空间和时间复杂度之间的良好平衡。负载因子太低会导致大量的空桶浪费空间，负载因子太高会导致大量的碰撞，降低性能。0.75 的负载因子在这两个因素之间取得了良好的平衡。

HashMap和HashTable有什么不一样？

HashMap线程不安全，效率高一点，可以存储null的key和value，null的key只能有一个，null的value可以有多个。默认初始容量为16，每次扩充变为原来2倍。创建时如果给定了初始容量，则扩充为2的幂次方大小。底层数据结构为数组+链表，插入元素后如果链表长度大于阈值（默认为8），先判断数组长度是否小于64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。
HashTable线程安全，效率低一点，其内部方法基本都经过synchronized修饰，不可以有null的key和value。默认初始容量为11，每次扩容变为原来的2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组+链表。它基本被淘汰了，要保证线程安全可以用ConcurrentHashMap。

ConcurrentHashMap怎么实现的

分段锁怎么加锁的

分段锁是可重入的吗

已经用了synchronized，为什么还要用CAS呢

ConcurrentHashMap用了悲观锁还是乐观锁

HashTable底层实现原理是什么

HashTable线程安全是怎么实现的

它的put，get做成了同步方法，保证了Hashtable的线程安全性，每个操作数据的方法都进行同步控制之后，由此带来的问题任何一个时刻只能有一个线程可以操纵Hashtable，所以其效率比较低。Hashtable是通过使用了 synchronized 关键字来保证其线程安全。

在Java中，可以使用synchronized关键字来标记一个方法或者代码块，当某个线程调用该对象的synchronized方法或者访问synchronized代码块时，这个线程便获得了该对象的锁，其他线程暂时无法访问这个方法，只有等待这个方法执行完毕或者代码块执行完毕，这个线程才会释放该对象的锁，其他线程才能执行这个方法或者代码块。

HashTable和concurrentHashMap有什么区别

HashMap和HashTable、ConcurrentMap有什么区别

Set集合有什么特点？如何实现key无重复的

set集合特点：Set集合中的元素是唯一的，不会出现重复的元素。
set实现原理：Set集合通过内部的数据结构（如哈希表、红黑树等）来实现key的无重复。当向Set集合中插入元素时，会先根据元素的hashCode值来确定元素的存储位置，然后再通过equals方法来判断是否已经存在相同的元素，如果存在则不会再次插入，保证了元素的唯一性。

有序的Set是什么？记录插入顺序的集合是什么

有序的 Set 是TreeSet和LinkedHashSet。TreeSet是基于红黑树实现，保证元素的自然顺序。LinkedHashSet是基于双重链表和哈希表的结合来实现元素的有序存储，保证元素添加的自然顺序。
记录插入顺序的集合通常指的是LinkedHashSet，它不仅保证元素的唯一性，还可以保持元素的插入顺序。当需要在Set集合中记录元素的插入顺序时，可以选择使用LinkedHashSet来实现。

八股 > Java

#Java #八股 #集合

Java集合八股

https://love-enough.github.io/2024/08/03/Java集合八股/

作者

GuoZihan

发布于

2024年8月3日

更新于

2024年8月12日

许可协议

Java并发八股上一篇

Java基础八股下一篇