首页  思维导图  详情

JAVA集合（含面试题整理）

2021-04-12 08:57:49   270  举报





AI智能生成

深入理解ArrayList、HashMap（1.7和1.8对比）、ConcurrentHashMap（1.7和1.8对比）等内容

Java集合

作者其他创作

大纲/内容

数组和集合的关系

数组

String[]、arr、int[]、object[]

数组缺点

长度确定（初始化固定），类型固定。

数组提供方法非常有限，增删修改操作不便，效率不高。

没有现成的属性方法可用，如获取实际元素个数。

存储特点：有序可重复，无法满足无序不重复的需求。

数组创建的两种方式

固定长度

Emp[] emps = new Emp[3];

向数组中添加

Emp emp = new Emp(null, "aaa", 12, "男");
Emp emp1 = new Emp(null, "bbb", 13, "女");
Emp emp2 = new Emp(null, "cccc", 14, "男");

Emp[] emps2 = {emp,emp1,emp2}

集合：可解决数组方面的弊端

collection接口

迭代器 Iterator

见设计模式的迭代器模式

List接口

ArrayList

说一下 ArrayList 的优缺点

优点

底层数组实现(Object[] elementData)
随机访问模式，实现 RandomAccess 接口
查找速度快O(1)

缺点

插入删除需要移动后面的所有元素，O(n)

线程不安全

Collections 的 synchronizedList 方法将ArrayList转换成线程安全的

List<String> synchronizedList = Collections.synchronizedList(list);
synchronizedList.add("aaa");
synchronizedList.add("bbb");

for (int i = 0; i < synchronizedList.size(); i++) {
System.out.println(synchronizedList.get(i));
}

集合与数组之间的转换

集合 --->数组：toArray()

Object[] arr = coll.toArray();
for(int i = 0;i < arr.length;i++){
System.out.println(arr[i]);
}

数组 --->集合:调用Arrays类的静态方法asList(T ... t)

List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
System.out.println(list);

构造方法

默认初始化方法

ArrayList list = new ArrayList();

private transient Object[] elementData;

为什么 ArrayList 的 elementData 加上 transient 修饰？

ArrayList 实现了 Serializable 接口

transient ：不希望 elementData 数组被序列化，重写了 writeObject 实现

每次序列化时，先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后遍历 elementData，只序列化已存入的元素，这样既加快了序列化的速度，又减小了序列化之后的文件大小。

JDK7：底层创建了长度为10的Object[]数组

JDK8：底层Object[] elementData初始化为{}，在使用时才会通过grow方法创建一个大小为10的数组。

指定容量的构造方法

指定collection元素列表

常用方法

增

add末尾添加

add指定位置添加

边界判定

IndexOutOfBoundsException异常

长度不足进行扩容

将当前位于该位置的元素以及所有后续元素右移一个位置。

System.arraycopy(elementData, index, elementData, index + 1, size - index);

int[] arr ={0,1,2,3,4,5,6}; System.arraycopy(arr,0,arr,3,3); 结果为：{0,1,2,0,1,2,6};

参数：原数组，原数组开始下标，新数组，新数组下标，原数组长度3；

删

remove(Object obj)

list.remove(new Integer(2));

需要删除元素，要装箱成对象

remove(int index)

System.arraycopy(elementData, index+1, elementData, index, numMoved);

list.remove(2);

按索引删除不会装箱生成对象

时间复杂度O(n)

改

set(int index , Object obj)

查

get(int index)

插入

add(int index, Object ele)

可插入null

时间复杂度O(n)

size()/indexOf()/lastIndexOf()

扩容机制

特性：动态数组（区别于数组的固定长度）

扩容1.5倍，扩容带来新数组的重新拷贝

JDK7：int newCapacity = (oldCapacity * 3)/2 + 1;

JDK8：int newCapacity = oldCapacity + (oldCapacity >> 1);

LinkedList

对于频繁的插入、删除操作，使用此类效率比ArrayList高；底层使用双向链表存储

LinkedList list = new LinkedList(); 内部声明了Node类型的first和last属性，默认值为null

ArrayList 和 LinkedList 的区别是什么？

数据结构

ArrayList 是动态数组

LinkedList 是双向链表

随机访问效率

ArrayList：O(1)

LindedList：O(n)

增加和删除效率

ArrayList：O(n)

LindedList：O(1)

内存空间占用

LinkedList多两个引用

线程安全

都是线程不安全的

在哪里可以用到LinkedList

生产者消费者

生产者向链表尾部添加消息

linkedList.addLast

消费者从链表头部取出消息

linkedList.removeFirst()

Vector

~~作为List接口的古老实现类；线程安全的(synchronized修饰)，效率低；底层使用Object[] elementData存储~~

~~jdk7和jdk8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组。在扩容方面，默认扩容为原来的数组长度的2倍。~~

ArrayList 和 Vector 的区别是什么？

线程安全

Vector线程安全的

性能

因为加Synchronized锁，性能比ArrayList 低

扩容

ArrayList扩容1.5倍

Vector扩容2倍

Set接口

Set接口中没额外定义新的方法，使用的都是Collection中声明过的方法。

HashSet

HashSet与HashMap的区别

HashSet

实现Set接口

仅存储对象

value使用PRESENT占位（Dummy）

调用add（）方法向Set中添加元素，调用HashMap的put

源代码：同HashMap

HashMap

实现了Map接口

存储键值对

调用put（）向map中添加元素

对于 HashSet 中保存的对象，请注意正确重写其 equals 和 hashCode 方法，以保证放入对象的唯一性。

hashCode（）与equals（）的相关规定

如果两个对象相等，则hashcode一定也是相同的

两个对象相等,对两个equals方法返回true

两个对象有相同的hashcode值，它们也不一定是相等的

综上，equals方法被覆盖过，则hashCode方法也必须被覆盖

hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）

==与equals的区别

==，基本数据类型比较 “值”是否相等；引用类型比较的是所指向的对象的地址

equals方法，注意：equals方法不能作用于基本数据类型的变量，equals继承Object类，比较是否是同一个对象
如果没有对equals方法进行重写，则比较的是引用类型的变量所指向的对象的地址；
诸如String、Date等类对equals方法进行了重写，比较的是所指向的对象的内容。

LinkedHashSet

遍历可以按照添加的顺序遍历

添加数据时，需要记录此数据前一个数据和后一个数据的引用

对于频繁的遍历操作，LinkedHashSet效率高于HashSet。

TreeSet

可以照添加对象的指定属性，进行排序。

红黑树(平衡的排序二叉树)

List 和 Set 的区别

都继承自Collection 接口

List接口

存储特点：存储有序、可重复数据、可存多个null值

和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，会引起其他元素位置改变

Set接口

存储特点：存储无序、不可重复的数据、只可以存一个null值

无序性≠随机性

检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。

Queue

BlockingQueue

Deque

Map接口

存储key-value对数据，类似函数y=f(x)

Map中的key：无序的、不可重复的，使用Set存储的key

一个键值对：key-value构成了一个Entry对象。

Map中的entry:无序的、不可重复的，使用Set存储所有的entry

Map中的value:无序的、可重复的，使用Collection存储value

key所在的类要重写equals()和hashCode()

value所在的类要重写equals()

Hashtable

线程安全，效率低；不能存储null的key和value；数组＋链表，链表解决hash冲突

HashTable是直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大；

Properties

常用来处理配置文件。key和value都是String类型

HashMap

常用方法

添加：put(Object key,Object value)

删除：remove(Object key)

修改：put(Object key,Object value)

查询：get(Object key)

时间复杂度由链表长度决定

长度：size()

遍历：keySet() / values() / entrySet()

foreach

idea：iter

HashMap底层

初始化

无参构造器HashMap map = new HashMap()；

哈希表默认长度16，加载因子0.75（数组长度达到3/4进行扩容）

JDK7：调用构造器时产生默认长度、加载因子的哈希表，while方式产生

JDK8：默认为空，在第一次添加数据时进行初始化。位运算方式产生

有参构造器HashMap(int initialCapacity, float loadFactor）

传入的值为k，初始化会是大于k的2的整数次方。如传入10，产生16的容量大小

hashcode函数设计

JDK7

进行了四次异或操作

JDK8

首先获得key的hashcode是int型共32位，
用hashcode的高16位和低16位进行异或操作（^），
(n - 1) & hash 通过hash值与容量-1相与操作来定位hash值在table哈希表中的位置。

为什么这么设计？

一定要尽可能降低hash碰撞，越分散越好；

为什么HashMap的容量会小于数组长度？

算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；

只用key的hashcode占用内存过大

(n - 1) & hash，如果与n正好是2的幂次，n-1满足全1，不满足全1，有零位相与始终为零，增加了碰撞概率。

JDK7：流程分析

JDK8：源码分析

HashMap在jdk8中相较于jdk7在底层实现方面的不同（为什么做这几点优化）

JDK7new的时候创建长度为16的数组，
JDK8在首次调用put()方法时，底层创建长度为16的数组

节省空间

jdk7底层结构：数组+链表。
jdk8底层结构：数组+链表+红黑树。

为防止发生hash冲突，链表长度过长，将时间复杂度由O(n)降为O(logn)

当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，
此时此索引位置上的链表改为红黑树存储。树节点个数<6时再转换成链表。防止徘徊发生频繁转换。

形成链表时，（七上八下）
头插法jdk7：新的元素指向旧的元素。
尾插法jdk8：旧的元素指向新的元素。

并发环境下

JDK7可能产生死链（环）

JDK8可能产生数据丢失问题

扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，
1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；

扩容前长度16，扩容后长度32，按位与操作，与15,1111和与31，11111；
分两种情况，hash值第五位为0，位置不变；
hash值第五位为1，hash&（n-1）后，多出第五位1，所以加上旧容量的大小。

HashMap底层典型属性说明

补：java中的位运算

图片流程

LinkedHashMap

LinkedHashMap内部提供了Entry

保证在遍历map元素时，可以照添加的顺序实现遍历。

在原的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。

对于频繁的遍历操作，此类执行效率高于HashMap。

TreeMap

按照Key的自然顺序或者Comprator的顺序进行排序，内部是通过红黑树来实现。

key所属的类实现Comparable接口

自定义一个实现了Comparator接口的比较器，传给TreeMap用于key的比较。

ConcurrentHashMap

说说ConcurrentHashMap解决了什么问题

JDK7HashMap出现的多线程死链问题（环）

JDK8改进JDK7由头插法改为尾插法，多线程场景下存在数据丢失问题

提高HashMap的并发安全性

解决

见：读操作get为什么是线程安全的

JDK7中的ConcurrentHashMap

segment分段锁

哈希桶数组包含多个segment，一个segment包含多个HashEntry（桶）

segment上锁不影响其他segment操作

segment继承ReentrantLock

value值volatile修饰

访问可见性

底层用数组+链表实现

get操作

根据 key 计算出 hash 值定位到具体的 Segment ，再根据 hash 值获取定位 HashEntry 对象，并对 HashEntry 对象进行链表遍历，找到对应元素。

volatile 可以保证内存可见性，所以不会读取到过期数据

put操作

先定位到相应的 Segment

获取对象锁成功

定位分段内的桶下标

遍历链表内容

key 已存在看是否覆盖value

key不存在头插法插入

尝试获取锁失败

尝试自旋获取锁

循环式的判断对象锁是否能够被成功获取，直到获取到锁才会退出循环，防止执行 put 操作的线程频繁阻塞

重试的次数达到一定次数改为阻塞锁

ConcurrentHashMap 的并发度是什么？

程序不产生锁竞争的最大线程数

JDK7里是segment的数量

过大，可以在一个segment内访问，变成两个segment，命中效率降低

过小，容易产生锁竞争

JDK8里并发度等于数组的大小

JDK8中的ConcurrentHashMap

采用更细粒度的锁，锁住桶数组中桶节点

使用CAS+Synchronized方式，保证线程并发安全

JDK8对Sychronized做大量优化后相对ReentrantLock可以减少内存开销。

因为只对桶下标进行上锁。ReentrantLock对每个节点都需要通过继承 AQS 来获得同步支持

底层使用数组+链表+红黑树实现

提升查询效率

数据添加：由JDK7的头插法改为尾插法

尾插法的优势

初始化：由饿汉式改为懒汉式

饿汉式创建非常消耗资源

get操作

get，无锁操作（仅需要保证可见性，除Treebin的读写锁），扩容过程中 get 操作拿到的是 ForwardingNode 它会让 get 操作在新table 进行搜索

get 流程

根据 key 计算出 hash 值，判断哈希表table为空

返回null

如果读取的bin头节点为null

返回null

如果是链表结构，就到链表中查询

如果是红黑树结构，就从红黑树里面查询

读操作get为什么是线程安全的

读操作一般不加锁(TreeBin的读写锁除外)，读写操作可并行；因为C13Map的写操作都要获取bin头部的syncronized互斥锁，能保证最多只有一个线程在做更新，单线程写、多线程读的并发安全性的问题。

如果读取的bin是一个链表,
头节点是个普通Node

如果正在发生链表向红黑树的treeify工作，因为treeify本身并不破坏旧的链表bin的结构，
只是在全部treeify完成后将头节点一次性替换为新创建的TreeBin，可以放心读取。

如果正在发生resize且当前bin正在被transfer，因为transfer本身并不破坏旧的链表bin的结构，
只是在全部transfer完成后将头节点一次性替换为ForwardingNode，可以放心读取。

扩容期间hash桶查询数据会发生什么？

扩容前，扩容中可以访问原数组

正在迁移的hash桶

迁移形成的链是复制的，而非移动，复制不影响原数组的遍历，不会阻塞get操作

扩容完成的

头结点的hash 为负数表示整个数组在扩容

头结点标记为ForwardNode

转发到新数组进行查询

如果其它线程正在操作链表，在当前线程遍历链表的任意一个时间点，
都有可能同时在发生add/replace/remove操作。
ConcurrentHashMap 弱一致性

如果是add操作，因为链表的节点新增从JDK8以后都采用了尾插法，会多遍历或者少遍历一个tailNode。

如果是remove操作，存在遍历到某个Node时，正好有其它线程将其remove，导致其孤立于整个链表之外；
但因为其next引用未变，整个链表并没有断开，还是可以照常遍历链表直到tailNode。

如果是replace操作，链表的结构未变，只是某个Node的value发生了变化，没有安全问题。

不能保证happen before

结论：链表线性数据结构，单线程写且插入操作尾插法，并发读取是安全的；
不会存在误读、链表断开导致的漏读、读到环状链表等问题。

如果读取的bin是一个红黑树，
说明头节点是TreeBin节点。

如果正在发生红黑树向链表的untreeify操作，因为untreeify本身并不破坏旧的红黑树结构，
只是在全部untreeify完成后将头节点一次性替换为新创建的普通Node，可以放心读取。

如果正在发生resize且当前bin正在被transfer，因为transfer本身并不破坏旧的红黑树结构，
只是在全部transfer完成后将头节点一次性替换为ForwardingNode，可以放心读取。

如果其他线程在操作红黑树，在当前线程遍历红黑树的任意一个时间点，都可能有单个的其它线程发生add/replace/remove/红黑树的翻转等操作，参考红黑树的读写锁实现。

put流程

首先会判断 key、value 是否为空，如果为空就抛异常！

null区别

ConCurrentHashMap：if (key == null || value == null) throw new NullPointerException();
如果key或者value其中一个null，就报空指针异常

HashMap：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
HashMap允许存入key为null

为什么ConcurrentHashMap不能存null

在并发的情况下带来二义性

HashMap中

map.get(key)方法得到值为null

map.contains(key)方法来判断不存在还是值为null

ConcurrentHashMap中

两次调用值可能被改变

计算key的hash值

spread(key.hashCode())保证为正数

判断桶数组为空，创建桶数组

当前线程正在创建另一个线程等待

创建方式区别

JDK8仅计算size容量，懒惰式创建

JDK7直接创建数组，占用内存

判断当前数组下标是否第一次插入，为空，使用casTabAt创建Node头结点

要创建链表头节点

cas操作保证线程安全，若同时有两个线程进行同一个位置的数据添加，只有一个会成功，失败的线程进入下一次for循环。

取代分段锁思想

更细粒度的锁，cas只会对hash表的一个链表头结点上锁，不影响其他链表头的操作（一个位置一把锁）

扩容期间hash桶插入数据会发生什么？

已扩容

hash值为-1，说明为ForwardingNode，有线程正在扩容，当前线程帮忙扩容

正在扩容的头结点

synchronized锁住桶下标，doubleCheck检测是否变化

是链表，用链表方式插入

找到相同的 key

如果允许更新，进行value值的更新

没有找到

链表尾部进行添加操作（JDK8的尾插法）

链表长度大于8且table长度大于64，进行树化操作

是红黑树，用红黑树方式插入

其他线程无法获得锁，被阻塞，不能操作正在迁移的hash桶

未扩容

可直接插入

最后判断是否进行扩容操作

什么时候触发扩容？（transfer）

addCount：在调用 addCount 方法增加集合元素计数后发现当前集合元素个数到达扩容阈值时就会触发扩容

helpTransfer：扩容状态下其他线程对集合进行插入、修改、删除、合并、compute 等操作时遇到 ForwardingNode 节点会触发扩容

tryPresize：putAll 批量插入或者插入节点后发现存在链表长度达到 8 个或以上，但数组长度为 64 以下时会触发扩容

ForwardingNode

hash值MOVED=-1 ，ForwardingNode存在表示集合正在扩容状态，nextTable 指向扩容后的数组。

扩容时如果table某个bin（头结点）迁移完毕, 用 ForwardingNode 作为旧 table bin 的头结点（占位功能）

get遍历到旧table，如果头结点标识为ForwardingNode，则到新表中get遍历，不会阻塞查询操作（转发功能）

sizeCtl 属性在各个阶段的作用

新建而未初始化时

int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) +1));
this.sizeCtl = cap;

sizeCtl值为2的幂次

记录集合在实际创建时应该使用的大小

初始化过程中

U.compareAndSwapInt(this, SIZECTL, sc, -1)

将 sizeCtl 值设置为 -1 表示集合正在初始化

其他线程发现该值为 -1 时会让出CPU资源以便初始化操作尽快完成。

初始化完成后

sc = n - (n >>> 2);
sizeCtl = sc;

记录下一次扩容的阈值

正在扩容时

U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)

第一条扩容线程设置的某个特定基数

U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)

后续线程加入扩容大军时每次加 1

U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)

线程扩容完毕退出扩容操作时每次减 1

sizeCtl 用于记录当前扩容的并发线程数情况

此时 sizeCtl 的值为：((rs << RESIZE_STAMP_SHIFT) + 2) + (正在扩容的线程数) ，并且该状态下 sizeCtl < 0 。

面试题

说说什么是fail-fast

线程不安全集合（ArrayList、HashMap）

当前线程遍历时，结构上被另一个线程修改，抛出ConcurrentModificationException异常，不再继续遍历

原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

如何解决

使用JUC包下的集合

ConcurrentHashMap

CopyOnWriteArrayList

怎么确保一个集合不能被修改？

Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合，
这样改变集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。

Collections工具类

作用：操作Collection和Map的工具类

常用方法

reverse(List)：反转 List 中元素的顺序

shuffle(List)：对 List 集合元素进行随机排序

sort(List)：根据元素的自然顺序对指定 List 集合元素升序排序