八股_java集合

概念

1.数组和集合的区别，用过哪些？

数组和集合的区别：

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

我用过的Java集合类有：

• ArrayList：动态数组，实现了List接口，支持动态增长
• LinkedList：双向链表，也实现了List接口，支持快速插入和删除操作–头尾O(1)，其他O(n)。
• HashMap：基于哈希表的Map实现，存储键值对，通过键快速查找值。
• HashSet：基于HashMap实现的有序Set集合，用于存储唯一元素。
• TreeMap：基于红黑树实现的有序Map集合，可以按照键的顺序进行排序
• LinkedHashMap：基于哈希表和双向链表实现的Map集合，保持插入顺序或访问顺序
• PriorityQueue：优先队列，可以按照比较器或元素的自然顺序进行排序(升序)

2.说说Java中的集合

List是有序（插入顺序）的Collection，使用此接口能够精确的控制每个元素的插入位置，用户能根据索引访问List中元素。常用的实现List的类有LinkedList，ArrayList，Vector，Stack。

• ArrayList是容量可变的非线程安全列表，其底层使用数组实现。当几何扩容时，会创建更大(1.5倍)的数组，并把原数组复制到新数组。ArrayList支持对元素的快速随机访问，但插入与删除速度很慢。

• LinkedList本质是一个双向链表，与ArrayList相比,，其插入和删除速度更快，但随机访问速度更慢。

Set不允许存在重复的元素，与List不同，set中的元素是无序的。常用的实现有HashSet，LinkedHashSet和TreeSet.

• HashSet通过HashMap实现，HashMap的Key即HashSet存储的元素，所有Key都是用相同的Value,一个名为PRESENT的Object类型常量。使用Key保证元素唯一性，但不保证有序性。由于HashSet是HashMap实现的，因此线程不安全。

• LinkedHashSet继承自HashSet，通过LinkedHashMap实现，使用双向链表维护元素插入顺序。

• TreeSet通过TreeMap实现的，添加元素到集合时按照比较规则将其插入合适的位置，保证插入后的集合仍然有序。

Map 是一个键值对集合，存储键、值和之间的映射。Key 无序，唯一;value 不要求有序，允许重复。Map 没有继承于 Collection 接口，从 Map 集合中检索元素时，只要给出键对象，就会返回对应的值对象。主要实现有TreeMap、HashMap、HashTable、LinkedHashMap、ConcurrentHashMap。

• HashMap:JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)，JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值(默认为 8)时，将链表转化为红黑树，以减少搜索时间，小于6时退化为链表。

• LinkedHashMap:LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。

• HashTable:数组+链表组成的，数组是 HashTable 的主体，链表则是主要为了解决哈希冲突而存在的

• TreeMap:红黑树(自平衡的排序二叉树)

• ConcurrentHashMap:Node数组+链表+红黑树实现，线程安全的(jdk1.8以前Seqment锁，1.8以后volatile + CAS 或者 synchronized)

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

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

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

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

并发Map：

• ConcurrentHashMap：它与HashTable的主要区别是加锁粒度的不同，在JDK1.7,ConcurrentHashMap加的是分段锁，也就是Segment锁，每个Segment 含有整个 table 的一部分，这样不同分段之间的并发操作就互不影响。在JDK1.8，它取消了Segment字段，直接在table元素上加锁实现对每一行进行加锁，进一步减小了并发冲突的概率。对于put操作，如果Key对应的数组元素为null，则通过CAS操作(Compare and Swap)将其设置为当前值。如果Key对应的数组元素(也即链表表头或者树的根元素)不为null，则对该元素使用 synchronized 关键字申请锁，然后进行操作。如果该put 操作使得当前链表长度超过一定阈值，则将该链表转换为红黑树，从而提高寻址效率。
• ConcurrentskipListMap:实现了一个基于SkipList(跳表)算法的可排序的并发集合，SkipList是一种可以在对数预期时间内完成搜索、插入、删除等操作的数据结构，通过维护多个指向其他元素的”跳跃”链接来实现高效查找。

并发Set:

• ConcurrentskipListSet:是线程安全的有序的集合。底层是使用ConcurrentSkipListMap实现。
• CopyOnWriteArraySet:是线程安全的Set实现，它是线程安全的无序的集合，可以将它理解成线程安全的HashSet。有意思的是，CopyOnWriteArraySet和HashSet虽然都继承于共同的父类AbstractSet;但是，HashSet是通过“散列表”实现的，而CopyOnWriteArraySet则是通过”动态数组(CopyOnWriteArrayList)“实现的，并不是散列表。

并发List:

• CopyOnWriteArrayList:它是 ArrayList 的线程安全的变体，其中所有写操作(add，set等)都通过对底层数组进行全新复制来实现，允许存储 null 元素。即当对象进行写操作时，使用了Lock锁做同步处理，内部拷贝了原数组，并在新数组上进行添加操作，最后将新数组替换掉旧数组;若进行的读操作。则直接返回结果，操作过程中不需要进行同步。

并发 Queue：

• ConcurrentlinkedQueue:是一个适用于高并发场景下的队列，它通过无锁的方式(CAS)，实现了高并发状态下的高性能。通常，ConcurrentLinkedQueue 的性能要好于 BlockingQueue 。
• BlockingQueue:与 ConcurrentLinkedQueue 的使用场景不同，BlockingQueue 的主要功能并不是在于提升高并发时的队列性能，而在于简化多线程间的数据共享。BlockingQueue 提供一种读写阻塞等待的机制，即如果消费者速度较快，则 BlockingQueue 则可能被清空，此时消费线程再试图从BlockingQueue 读取数据时就会被阻塞。反之，如果生产线程较快，则 BlockingQueue 可能会被装满，此时，生产线程再试图向 BlockingQueue 队列装入数据时，便会被阻塞等待。

并发 Deque:

• LinkedBlockingDeque:是一个线程安全的双端队列实现。它的内部使用链表结构，每一个节点都维护了一个前驱节点和一个后驱节点。LinkedBlockingDeque 没有进行读写锁的分离，因此同一时间只能有一个线程对其进行操作。
• ConcurrentlinkedDeque:ConcurrentLinked Deque是一种基于链接节点的无限并发链表。可以安全地并发执行插入、删除和访问操作。当许多线程同时访问一个公共集合时，ConcurrentLinkedDeque是个合适的选择。

4.Collections和Collection的区别？

5.集合的遍历方法有哪些？

在Java中，集合的遍历方法主要有以下几种：

• 普通 for 循环： 可以使用带有索引的普通 for 循环来遍历 List。

  List<String> list = new ArrayList<>();
  list.add("A");
  list.add("B");
  list.add("C");
    
  for (int i = 0; i < list.size(); i++) {
      System.out.println(list.get(i));
  }

• 增强 for 循环（for-each循环）： 用于循环访问数组或集合中的元素。

  List<String> list = new ArrayList<>();
  list.add("A");
  list.add("B");
  list.add("C");
  
  for (String s : list) {
      System.out.println(s);
  }

• Iterator 迭代器： 可以使用迭代器来遍历集合，特别适用于需要删除元素的情况。

  List<String> list = new ArrayList<>();
  list.add("A");
  list.add("B");
  list.add("C");
  
  Iterator<String> iterator = list.iterator();
  while (iterator.hasNext()) {
      System.out.println(iterator.next());
  }

• ListIterator 列表迭代器： ListIterator是迭代器的子类，可以双向访问列表并在迭代过程中修改元素。

  List<String> list = new ArrayList<>();
  list.add("A");
  list.add("B");
  list.add("C");
  
  ListIterator<String> iterator = list.listIterator();
  while (iterator.hasNext()) {
      System.out.println(iterator.next());
  }

• 使用 forEach 方法： Java 8引入了 forEach 方法，可以对集合进行快速遍历。

  List<String> list = new ArrayList<>();
  list.add("A");
  list.add("B");
  list.add("C");
  
  list.forEach(element -> System.out.println(element));

• Stream API： Java 8的Stream API提供了丰富的功能，可以对集合进行函数式操作，如过滤、映射等。

  List<String> list = new ArrayList<>();
  list.add("A");
  list.add("B");
  list.add("C");
  
  list.stream().forEach(element -> System.out.println(element));

List

1.讲一下java里面list的几种实现，几种实现有什么不同？

主要有三个：ArrayList、LinkedList、Vector。

打个比方：ArrayList就像数组教室里的连排座椅，座位紧挨着，找第5个同学直接数过去就行，很快；但要在中间插个人，后面所有人都得挪位子。LinkedList就像寻宝游戏的线索链，每个节点拿着”下一个在哪”的纸条，插入删除只要改纸条指向就行，但要找第5个元素，得从第1个开始一个个顺藤摸瓜。

Vector是ArrayList的”老前辈”，方法都加了synchronized，线程安全但性能差，现在基本没人用了。

2.list可以一边遍历一边修改元素吗？

要看怎么遍历。用普通的下标for循环可以随便改，因为是按下标操作的，不涉及迭代器状态，但要注意删元素后size变化可能漏掉元素或越界。

用增强for或者Iterator遍历时，直接调list.add()或list.remove()会抛ConcurrentModificationException。因为ArrayList内部有个modCount计数器，每次结构修改就+1，迭代器创建时记下这个值，每次next()都会检查，对不上就报错。要删的话得用iterator.remove()，它内部会同步更新modCount和迭代器的expectedModCount。

3.ArrayList和LinkedList的区别，哪个集合是线程安全的？

两个都不是线程安全的。区别核心就一句话：ArrayList底层是数组，LinkedList底层是双向链表。

ArrayList随机访问O(1)，尾部增删均摊O(1)，中间增删O(n)。LinkedList随机访问O(n)，头尾增删O(1)，但中间增删也得先遍历到那个位置，所以也是O(n)。实际开发中ArrayList几乎碾压LinkedList，因为CPU缓存对连续内存更友好，LinkedList的节点散落在堆里，缓存命中率很低。

4.ArrayList线程安全吗?把ArrayList变成线程安全有哪些方法？

不安全。要变安全有几条路：

• Collections.synchronizedList(new ArrayList<>())——给每个方法加synchronized，简单粗暴，但并发性能差，所有线程排队进门。
• CopyOnWriteArrayList——读不加锁，写的时候复制整个数组再改，适合读多写少的场景，比如配置列表、监听器列表。
• 自己加锁，比如用ReentrantLock手动控制。

5.为什么ArrayList不是线程安全的，具体来说是哪里不安全？

add方法和扩容时。

在add()方法里那几行代码不是原子的：先检查容量，再赋值elementData[size] = e，最后size++。假设size=5，两个线程同时进来：

线程A执行了elementData[5] = a，还没来得及size++；线程B也执行了elementData[5] = b，把A的值覆盖了。然后两个线程各自size++，size变成7，但实际只加了两个元素，elementData[6]是null。

另一个经典翻车是扩容：线程A在扩容复制数组，线程B在往里写数据，写到旧数组里去了，数据直接丢。

6.ArrayList的扩容机制说一下。

默认初始容量是10（第一次add时才真正分配数组）。当size + 1超过数组长度时触发扩容，新容量是旧的1.5倍，底层用的是oldCapacity + (oldCapacity >> 1)，右移一位比除以2快一点。

扩容就是三步：创建新数组→Arrays.copyOf把老数据复制过去→引用指向新数组。这个过程挺耗时的，所以如果你知道要放10000个元素，最好new ArrayList<>(10000)提前指定容量，省得反复搬家。

7.线程安全的List，CopyonWriteArrayList是如何实现线程安全的？

核心思想是写时复制。读操作完全不加锁，直接读内部数组引用，所以读性能非常好。写操作进来时先加ReentrantLock，然后复制一份整个数组，在新数组上修改，改完后把引用指向新数组，是原子性的替换。

打个比方，就像一个公告栏，大家随时可以看，要更新内容时不是在原板上改，而是准备好一块新的公告栏，改好后一把替换上去。看的人要么看到旧的，要么看到新的，不会看到改了一半的状态。

缺点是写一次就复制整个数组，内存和时间开销都大，所以只适合读远多于写的场景。另外迭代器拿到的是创建时的快照，遍历期间别人的修改看不到，也不会抛ConcurrentModificationException。

Map

1.HashMap的底层实现原理？

HashMap底层是”数组+链表+红黑树”的结构，也叫拉链法。数组是主体，每个数组位置叫做一个”桶”(bucket)。当我们put一个键值对时，先对key算hash值，然后用(n-1) & hash （用位运算代替取模）定位到数组下标。如果这个桶里已经有元素了（哈希冲突），就用equals逐个比较，key相同就覆盖value，key不同就挂到链表后面。

JDK1.8开始，当链表长度超过8且数组长度达到64时，链表会转成红黑树，查找时间复杂度从O(n)降到O(logn)。当红黑树节点数少于6时又退化成链表。打个比方，桶就像快递柜的格子，同一个格子里包裹太多了，找起来费劲，就升级成自动分拣系统。

JDK1.7和1.8的主要区别：1.7是数组+链表，头插法，多线程下扩容可能形成环形链表导致死循环；1.8改成尾插法，解决了这个问题，并且引入了红黑树优化长链表的查询。

2.HashMap的put()流程说一下

大致分四步：

1. 对key调用hashCode()，再经过扰动函数(h = key.hashCode()) ^ (h >>> 16)得到最终hash值。扰动函数把高16位和低16位做异或，让hash分布更均匀，减少碰撞。
2. 用(n-1) & hash算出数组下标。如果该位置为空，直接放入。
3. 如果该位置有元素，遍历链表（或红黑树）。找到key相同的节点就覆盖value；没找到就挂到链表尾部（尾插法）。
4. 挂完后判断链表长度是否超过8，超过就转红黑树。最后检查总元素数是否超过阈值（容量×负载因子0.75），超过就扩容。

3.HashMap的hash计算为什么要做扰动？

直接用hashCode()的值有个问题：hashCode是32位的int，但数组长度一般很小，比如默认16，(n-1) & hash实际上只用了hash的低位几位。如果低位恰好很集中（比如hashCode都是偶数），就会大量冲突。

扰动函数h ^ (h >>> 16)把高16位的信息也混到低16位里，相当于让高位也参与下标计算，让分布更均匀。可以理解为：原来只看身份证后4位分班，现在把后4位和前4位做个运算再分，冲突概率就低了。

4.为什么HashMap的容量必须是2的幂次方？

核心原因是用位运算代替取模。(n-1) & hash等价于hash % n，但位运算比取模快得多。这个等价关系只在n是2的幂次方时成立——因为2的幂次方减1后二进制全是1（比如16-1=15，二进制1111），与hash做&运算恰好就是取低位。

另外扩容时也能用位运算优化：元素在新数组中的位置要么不变，要么往后挪一个旧容量的距离，只需要看hash值新增的那一位是0还是1就行，不用重新算下标。

5.HashMap的扩容机制

默认容量16，负载因子0.75，也就是元素数超过容量×0.75时触发扩容。扩容后容量翻倍，比如16→32→64。

扩容过程：创建新数组，遍历旧数组的每个桶。对于桶里的每个节点，用hash & oldCap判断它在新数组中的位置——如果结果为0，位置不变；如果不为0，新位置 = 旧位置 + 旧容量。

这里有个巧妙之处：因为容量是2倍扩容，所以新旧下标只差一个bit位，不需要重新做(n-1) & hash，只要判断hash中对应那一位是0还是1就行。

如果知道大概要放多少元素，可以提前指定容量。比如要放1000个，new HashMap<>((int)(1000/0.75) + 1)，避免反复扩容。

6.HashMap的链表什么时候转红黑树？阈值为什么是8？

链表长度≥8且数组长度≥64时转红黑树。如果数组长度不到64，优先扩容而不是转树。

阈值8是个经验值，源码注释里提到，在合理的hash分布下，链表长度达到8的概率极低（泊松分布算出来大约千万分之六）。也就是说正常情况下根本不会触发转树，8是一个”兜底”的保守值。转成红黑树后查询从O(n)变O(logn)，防止恶意构造hash导致所有元素挤在一个桶里，查询退化成O(n)。

红黑树节点数≤6时退化回链表，之所以不是8，是留一个缓冲区间，避免在8附近反复转换。

7.HashMap为什么线程不安全？

最典型的场景是并发put。比如两个线程同时对同一个桶做put：

线程A判断桶为空准备插入，线程B也判断桶为空并且先插进去了。线程A还是执行插入，直接把B的节点覆盖了，数据丢失。

另一个问题是并发扩容。两个线程同时触发resize，各自创建新数组并迁移数据，最后只有一个线程的数组被保留，另一个线程迁移的数据就丢了。还有size的问题，两个线程同时++size，不是原子操作，和ArrayList的size++问题一样。

8.HashMap和HashTable的区别

几个核心区别：

• 线程安全：HashTable方法都加了synchronized，线程安全但性能差；HashMap不安全但性能好。
• null支持：HashMap允许一个null key和多个null value；HashTable的key和value都不允许null，put null直接抛NullPointerException。
• 初始容量：HashMap默认16，扩容2倍；HashTable默认11，扩容2n+1。
• hash计算：HashMap有扰动函数，分布更均匀；HashTable直接用key.hashCode() & 0x7FFFFFFF。
• 迭代器：HashMap用fail-fast迭代器，HashTable同时支持fail-fast和fail-safe（Enumerator）。

实际开发中HashTable基本不用了，需要线程安全就用ConcurrentHashMap。

9.HashMap和ConcurrentHashMap的区别？ConcurrentHashMap如何实现线程安全？

两者底层结构类似（数组+链表+红黑树），核心区别在并发控制：

JDK1.7：分段锁(Segment)。把数组分成16个Segment，每个Segment有自己的锁。不同线程操作不同Segment时互不影响，并发度最高16。就像把一个大仓库分成16个小隔间，每个隔间有独立的锁。

JDK1.8：取消了Segment，锁粒度细化到每个桶（数组的每个位置）。用synchronized + CAS实现：

• 如果桶为空，用CAS尝试写入，失败就自旋重试。
• 如果桶不为空，用synchronized锁住这个桶的头节点，只锁这一个桶，不影响其他桶的并发操作。
• 扩容时多线程可以协助迁移（transfer），每个线程分到一部分桶去迁移。

相比HashTable锁整个表，ConcurrentHashMap锁单个桶，并发性能高很多。

10.LinkedHashMap怎么实现的？

LinkedHashMap继承自HashMap，在HashMap的数组+链表+红黑树基础上，额外维护了一条双向链表。每个Entry节点除了key、value、hash、next，还多了before和after两个指针，指向前一个和后一个插入的节点。

这条双向链表维护了元素的顺序。默认是插入顺序，也可以设成访问顺序（构造方法传accessOrder=true）。访问顺序模式下，每次get或put已有key时，会把该节点移到链表尾部，这样链表头部就是最久没访问的元素，天然实现了LRU缓存。

头节点通过一个head引用维护，新节点插入时总是追加到链表尾部（尾插法），同时保持HashMap的所有特性不变。

Set

1.HashSet、LinkedHashSet、TreeSet的区别

三者都实现Set接口，保证元素不重复，区别在底层结构和有序性：

• HashSet：底层就是HashMap，元素存在HashMap的key上，value统一是一个叫PRESENT的Object常量。无序，不允许重复，允许一个null。可以理解为”只存key不存value的HashMap”。
• LinkedHashSet：继承HashSet，底层用LinkedHashMap实现。在HashSet基础上多了一条双向链表维护插入顺序，遍历时按插入顺序输出。
• TreeSet：底层是TreeMap（红黑树），元素按自然顺序或自定义Comparator排序。不允许null（因为null没法比较大小）。添加、删除、查找都是O(logn)。

简单记忆：HashSet无序最快，LinkedHashSet保持插入顺序，TreeSet自动排序。

2.HashSet是如何保证元素不重复的？

靠HashMap的key唯一性。add一个元素时，实际调的是HashMap的put，元素作为key存入。put的过程：先算hash定位桶，再用equals比较桶里已有元素的key。如果hash相同且equals返回true，说明元素已存在，直接覆盖value（对Set来说就是什么都不做）；否则挂到链表后面。

所以HashSet判重的两步：先比hashCode()（决定在哪个桶），再比equals()（决定是不是同一个元素）。自定义对象存入HashSet时，这两个方法必须一起重写，不然hash不同就进不了同一个桶，equals永远不会被调用，重复元素就混进去了。

3.Set有哪些遍历方式？

Set没有下标，不能用普通for循环。常用三种方式：

• 增强for：for(Object o : set)，底层用的Iterator。
• Iterator迭代器：Iterator it = set.iterator(); while(it.hasNext())，需要删元素时用it.remove()。
• forEach + Stream：set.forEach(...)或set.stream().forEach(...)，Java 8的写法。

注意Set遍历时不能直接调set.add()或set.remove()，同样会抛ConcurrentModificationException，规则和List一样。