当前位置：首页 > news >正文

小林八股Java集合笔记（8k字概要版）

news 2025/5/23 8:56:24

Java集合

数组与集合区别：

数组固定长度，集合动态长度；数组可存基本数据类型，集合不可以；（因为集合基于泛型，泛型只接受引用，因为类型会擦除）

数组可直接访问对象，集合需要迭代器或其他方法（底层由数组实现可以随机访问）

集合类：（map也属于集合类，但不继承Collection）

ArrayList：动态数组，实现List接口

LinkedList：双向链表，也实现List接口

HashMap：基于哈希表的Map实现（无序），哈希表是数组+链表（或红黑树）

HshSet：基于HashMap的Set集合（无序）

TreeMap：基于红黑树实现的map集合（有序），按键排序

LinkedHashMap：基于哈希表和双向链表的Map集合，记录元素的插入顺序或访问顺序

PriorityQueue：优先队列，按照比较器或元素自然顺序排序

谈谈Java中的集合：

List是有序的Collection，使用此接口能精确控制每个元素插入位置，用户能根据索引访问List中元素。常用的由LinedList，ArrayList，Vector，Stack

ArrayList和LInkedList对比：

Set无序且不重复，常见实现HashSet，LinedHashSet和TreeSet

HashSet由HashMap实现，HashMap的Key为HashSet存储的元素，所有Key都是用的相同value，一个名为PRESENT的Object类型常量，线程不安全

LinedHashSet继承自HashSet，通过LinkedHashMap实现，使用双向链表维护元素插入顺序或访问顺序

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

Map是一个键值对集合。Key无序，唯一；value不要求有序，允许重复。Map没有继承Colletion接口。主要实现有TreeMap、HashMap、HashTable、LinedHashMap、ConcurrentHashMap

HashMap：jdk1.8之前由数组+链表组成，jdk1.8之后，当链表长度大于阈值（默认8），将链表转为红黑树

LinedHashMap：继承自HashMap，相比来说额外增加一条双向链表，记录插入顺序或访问顺序

HashTable：数组+链表组成，线程安全但性能相对来说较低

TreeMap：红黑树

ConcurrentHashMap：Node数组+链表+红黑树，线程安全（jdk1.8以前Segement锁，1.8之后volatile+CAS+synchronized）

线程安全的集合：

java.util两个：

Vector：线程安全的动态数组，内部方法基本都经过synchronized修饰，开销大

HashTable：给每个方法加synchronized关键字，不支持null键和值，开销大

java.util.concurrent都是：

并发Map：

ConcurrentHashMap：jdk1.8之前加Segment锁，之后直接在table元素加锁，实现对每一行进行加锁。对put操作，如果key对于的数组元素为null，则通过CAS（无锁，每次更新前先对比是否自己预估值，否则失败且自旋重试）操作设置值，如果部位null，则使用synchronized关键字锁住table元素

ConcurrentSkipListMap：实现了一个基于SkipList（调表）算法的可排序的并发集合

并发Set：

ConcurrentSkipListSet：是线程安全的有序的集合。底层是使用ConcurrentSkipListMap实现，基于CAS+分段所实现，支持高并发读写

CopyOnWriteArraySet：是线程安全的Set实现，他是线程安全的无序的集合，可以将他理解为线程安全的HashSet。CopyOnWriteArraySet和HashSet都继承于共同的父类AbstractSet；但是HashSet通过”散列表“实现，而CopyOnWriterArraySet通过”动态数组“（CopyOnWriterArrayList）实现的

并发List：

CopyOnWriteArrayList：它是ArrayList线程安全的变体，所有写操作（add、set、delete等）都通过对底层数组进行全新复制来实现，允许存储null元素。即当对象进行写操作时，使用了Lock锁做同步处理，内部拷贝了原数组，并在新数组上进行添加操作，最后将新数组替换掉旧数组；若进行读操作直接返回结果，不需要同步。实现读写分离，在高并发读优势很大

并发Queue：

ConcurrentLinkedQueue：一个适用于高并发场景的队列，它通过CAS，实现高并发时高性能

BlockingQueue：生产者满了就阻塞写，消费者没数据就阻塞读

并发Deque：

LinkedBlockingDeque：是一个线程安全的双端队列实现，内部使用链表，每个节点都维护一个前去和后驱节点。它没有进行读写锁分离，因此同一时间只有一个线程能操作

ConcurrentLinkedDeque：一种基于连接节点的无线并发链表，安全得并发插入、删除、访问操作。当许多线程同时访问一个公共集合时，它是合适的选择

Collections和Collection区别

Collection是接口，定义一组方法，如添加删除遍历

Collections是工具类，提供一系列静态方法对集合进行操作和算法包括排序、查找、替换、反转、随机化。这些方法可以对实现类Collection接口的集合进行操作

集合遍历的方法：

普通for循环

增强for循环（for-each）

Iterator迭代器

        List<String> list = new ArrayList<>();list.add("a");list.add("b");list.add("c");Iterator<String> iterator = list.iterator();while (iterator.hasNext()) {String s = iterator.next();System.out.println(s);}

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

使用forEach方法

Stream API

List

List的几种实现

Vector：早期线程安全数组，方法基本上由synchronized控制,扩容时2倍

ArrayList：线程不安全，扩容时位运算取一半+原容量（1.5倍）

LinkedList：双向链表，线程不安全

使用场景：

Vector和ArrayList适合随机访问存储，不适合插入删除

LinkedList相反

list可以一边遍历一边修改元素嘛

这取决于遍历的方式和具体实现类

使用普通for循环遍历：可以在遍历过程中修改元素，只要修改的索引不超出List的范围即可。使用增强for循环：不能修改不能删除（因为操作的是副本）使用迭代器：可以使用迭代器的remove来删除元素

ListIterator：可以修改添加删除元素

对于线程安全的list，如CopyOnWriteArrayList,由于其采用写时赋值，遍历时可以修改，但可能读到旧数据，因为修改操作在新的副本进行

list如何快速删除某个指定下标的元素

ArrayList提供了remove(int index)方法，删除该元素后会将后续元素向前移动。如果删除末尾时间复杂度O(1)；如果删除列表中间为O(n)

LinkedList的remove(int index)方法也可以删除，它需要先遍历到指定下标位置，然后修改指针指向。时间复杂度为O(n),不过，如果一直要删除的元素为链表的头节点或尾节点，可以直接修改头指针或为指针实现删除，时间复杂度为O(1)；（尾节点为O(1)前提是双向链表）

CopyOnWriteArrayList的remove方法同样可以指定下标。它在写操作时会创建一个新的数组，所有它操作的复杂度取决于数组的复制速度，通常为O(n)。但在并发情况下，它的删除操作不会影响读操作，具有较好的并发性能。读写分离

ArrayList和LinkedList区别：

底层数据结构：一个数组一个链表

插入删除效率：xxx在首部复杂度xxx, 在中间xxx，在尾部xxx。但LinkedList不支持随机访问，出来头节点外，擦汗如何删除的时间复杂度都为O(n)，效率也不高，基本没人用

随机访问效率：一个索引快速，一个遍历

空间占用：连续内存，碎片内存

使用场景：频繁随机访问，频繁插入删除（中间）

线程安全：都不安全

把ArrayList变成线程安全：

使用Collections类的synchronizedList方法包装：

List<String> synchronized = Collections.synchronizedList(arrayList)

使用CopyOnWriteArrayList代替，它线程安全：

CopyOnWriteArrayList<String> copyOnWriteArrayList = new CopyOnwriteArrayList<>(arrayList)

使用Vector代替：

Vector<String> vector = new Vector<>(arrayList)

为什么ArrayList不安全，具体说说：

在arrayList增加元素有三步，1.判断是否需要扩容。2.填入值。3.当前集合size++

高并发会暴露三个问题：

部分值为null（我们没有addnull进去）：假设两个线程都在size为9时进入，第一步都判断不需要扩容，然后两个线程先后设置了下标为9，并且size同时++，导致下标为10的地方为null

索引越界异常：size为9时，线程2在线程1未执行size++时进入，当线程1size++执行后，线程2开始插入元素，此时size为10，将报错

size与我们add数量不符：线程1和线程2拿到一样的size值加完了同时覆盖，就导致有一次没加上（根本原因在于size++操作内部非原子）

ArrayList扩容机制：

一把里说，扩容1.5倍，根据计算的结果创建容量更大的新数组，将元素赋值，更新引用。之所以扩容是 1.5 倍，是因为 1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数。

线程安全的List，CopyOnwriteArrayList如何实现：

底层使用volatile修饰数组，保证当前线程对对象重新赋值后，其它线程可感知

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

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

替换地址前，读的时老数组的数据，是有效数据，执行操作后，读取新数据，同样有效数据，读写分离更高效

Map

常见map结合：

HashMap：根据键的hash值存贮获取键值对，底层数组+链表+红黑树，非线程安全

LinkedHashMap：继承自HashMap，额外维护双向链表维护了插入顺序或访问顺序，使得的等待与插入顺序或访问顺序一直，线程不安全，多线程时与HashMap问题相同

TreeMap：底层红黑树，根据键进行排序，默认自然顺序，可以指定比较器排序。非线程安全

HashTable：早期提供的线程安全Map，实现方式与HashMap类时，但在方法上都使用sychronized保证安全

ConcurrentHashMap：jdk1.8以前使用分段锁，之后使用volatile+CAS或者synchronized保证线程安全

如何快速遍历map：

for-each+entrySet()方法

for-each+keySet()方法

获取Map的entrySet()或keySe()的迭代器，在需要删除元素操作时比较有用

lambda表达式+foreach方法

StreamAPI

HashMap原理：

Hash算法将key映射到数组中的bucket

1.7使用数组+链表，但后面一个索引上的的链表太长

1.2优化，当链表长度超过八转换为红黑树，查询时间复杂度O(logn)，在数量小于6时回退链表

哈希冲突解决办法：

链接发：使用链表或其他数据结构连接在一个bucket中

开放寻址法：在哈希表中找到另一个可用位置存储而不是存在链表中，（线性探测、二次探测、双重散列）

再哈希法：发生冲突时，使用另一个哈希函数再次计算哈希值，知道找到空bucket

哈希桶扩容：冲突过多时，可以动态扩大哈希桶数量，重新分配键值对

如何保证线程安全：

使用Collections.synchronizedMap方法同步加锁方式，还可以使用HashTable，ConcurrentHashMap

HashMap的put过程：

桶索引只靠 hash 的低位，hash 比较靠全部 hash 值，equals 是最终裁判。

1.根据key计算索引（bucket）

2.检查该位置是否为空：如果为空，直接创建一个Entry对象存储键值对。将HashMap的修改次数(modCount)加1，一遍在迭代时发现并发修改。return

3.如果已经存在其它键值对，检查该位置第一个键值对的Hash码和键是否与要添加的键值对相同：

如果相同，表示找到了同样的键，直接将新值替换旧值完成更新。return

4.如果不相同，遍历链表或红黑树查找：

如果键值对集合是链表，从头部开始逐个比较键的哈希码和equals()方法，直到找到相同键（新值换旧值)或达到链表末尾（将新的键值加到链表头部）

如果键值对集合时红黑树，则在红黑树中使用equals()方法，根据键的哈希码定位到红黑树，逐个比较键，直到找到相同的键(新值换旧值)或达到红黑树末尾（将新的加到红黑树）

（使用哈希定位原因：比较 hash 值快，可以提前排除大部分不相等的 key；equals 是精确判断，不能仅靠 hash 相等就认为 key 相等）

5.检查链表长度是否达到阈值（默认8）：如果超过阈值，且HashMap的数组长度≥64（红黑树维护结构开销大，如果数组太小（比如长度=16），还不如先扩容解决冲突。），则链表转为红黑树

6.检查负载因子是否超过阈值（默认0.75）：如果键值对的数量比数组的长度比值大于阈值，则需要扩容（维持散列效率，避免太多哈希冲突，提升整体性能。）

7.扩容：创建一个新的两倍大小数组，将就数组中键值对重新计算哈希码分配到新数组中，更新mao的数组引用和与之参数

8.完成添加操作

hashmap调用get一定安全吗：

空指针异常：如果你的hashmap未初始化会报错。HashMap支持null键

线程安全：多线程中，当一个线程调用get读取数据，而另一个线程同时修改结构（如增加或删除），可能导致读取错误。

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

平衡二叉树（AVL树）追求完全平衡，任何节点的左右子树高度差不超过1，这样要求太严格，每次插入删除几乎都会破坏规则发生自旋调整，消耗性能（适合查找为主、结构稳定、数据变化少例如字典树、索引树、配置项等）

红黑树追求若平衡，整个树的最长路径不会超过最短路径的2倍。牺牲一部分查找性能，换取维持树平衡的成本。（适合查找+平凡插入删除，追求整体吞吐）

hashmap的key可以是null吗

可以，当key为null，哈希值为0，不走key.hashCode()方法

null作为key只能有一个，作为value可以随意

重写HashMap的equal和hashcode方法需要注意什么：

如果o1.equals(o2)，那么o1.hashCode() == o2.hashCode()总是为true的。

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

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

可能会出现equals方法返回true而hashCode却false

多线程hashmap出现问题？

jdk1.7的hashmap使用头插法插入元素，多线程时，扩容可能导致环形链表形成死循环

jdk1.8使用尾插法，扩容时保持链表元素原本顺序，不会出现环形链表问题

多线程put同一个key，导致元素丢失

读到null：一个线程写入另一个线程读，指针未完全写入，读出空值

size不一致：多线程写入size++无法同步，最终size小于实际

空指针异常：读到null后调用方法或属性，发生异常

hashmap扩容机制

负载因子0.75，如果hashmap中元素个数超过了数组长度的75%会出发扩容，有两步，第一步将hash表长度扩展两倍，第二部将旧hash表数据放到新表

因为我们使用2次幂扩展（指长度扩为原来两倍），所以元素位置要么时在原位置，要么在原位置移动2次幂

因此，在扩展hashmap时，不许哟啊重新计算hash，只要看看原来的hash新增的bit是1还是0就好了，是0索引不变，是1 索引编程“原索引+oldCap”

hashmap大小为什么是2的n次方：

HashMap 的容量设计为 2 的 n 次方，主要是为了优化性能。一方面，这样可以用位运算 & (length - 1) 快速计算桶下标，代替取模运算 %。

另一方面，JDK 1.8 在扩容时只需要判断 hash 的某一位是否为 1，就可以快速决定元素是否需要移动，避免了重新 hash 的开销。

同时，这种设计还能让哈希分布更均匀，减少冲突。

hashmap负载因子：

默认9.75，提供空间和时间复杂度的良好平衡

太低导致大量空桶，太高导致大量碰撞，降低查询性能

CondurrentHashMap实现：

get 操作永远不需要加锁，依赖 volatile 和原子操作保证线程安全。

jdk1.7中使用数组+链表实现，而数组分为大数组Segment和小数组HashEntry。Segment是一种可重入锁（ReentrantLock），在ConcurrentHashMap中扮演锁角色，HashEntry用于存储键值对数据。一个ConcurrentHashMap包含一个Segment数组，一个Segment里包含一个HashEntry[]数组，每个HashEntry是一个链表结构的元素。此时采用用分段锁，给每一段数据配一把锁，实现并发（受限当时synchronized重，比reentrantlock更重，reentrantlock有一点重，细粒度控制开销很大，jdk1.8对synchronized优化很大（JVM内置锁））

jdk1.8主要通过volatile+CAS或者synchronized实现，添加元素时首先判断容器是否为空：

如果为空使用volatile+CAS初始化

如果不为空，则根据存储的元素计算该位置是否为空：

如果根据存储的元素计算为空，利用CAS设置该节点

如果根据存储的元素计算结果不为空，使用synchronized，然后遍历桶中数据，并替换或新增节点到桶，最后判断是否转换红黑树