首页  思维导图  详情

JAVA集合（含面试题整理）

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





AI智能生成

为你推荐

查看更多



【java集合】经典面试题总结-史上最全面试题思维导图总结

Java之面试题大全（持续更新ing）

前端面试题大全

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

Java集合

作者其他创作

大纲/内容

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

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

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

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

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

数组缺点

Emp[] emps = new Emp[3];

固定长度

向数组中添加

数组创建的两种方式

数组

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

数组和集合的关系

见设计模式的迭代器模式

迭代器 Iterator

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

优点

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

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));}

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

线程不安全

缺点

说一下 ArrayList 的优缺点

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

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

List<String> list = Arrays.asList(new String[]{\"AA\

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

集合与数组之间的转换

private transient Object[] elementData;

ArrayList 实现了 Serializable 接口

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

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

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

ArrayList list = new ArrayList();

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

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

默认初始化方法

指定容量的构造方法

指定collection元素列表

构造方法

add末尾添加

IndexOutOfBoundsException异常

边界判定

长度不足进行扩容

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

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

add指定位置添加

增

list.remove(new Integer(2));

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

remove(Object obj)

list.remove(2);

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

remove(int index)

时间复杂度O(n)

删

改

get(int index)

查

可插入null

插入

size()/indexOf()/lastIndexOf()

常用方法

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

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

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

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

扩容机制

ArrayList

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

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

ArrayList 是动态数组

LinkedList 是双向链表

数据结构

ArrayList：O(1)

LindedList：O(n)

随机访问效率

ArrayList：O(n)

LindedList：O(1)

增加和删除效率

LinkedList多两个引用

内存空间占用

都是线程不安全的

线程安全

ArrayList 和 LinkedList 的区别是什么？

linkedList.addLast

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

linkedList.removeFirst()

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

生产者消费者

在哪里可以用到LinkedList

LinkedList

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

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

Vector线程安全的

因为加Synchronized锁，性能比ArrayList 低

性能

ArrayList扩容1.5倍

Vector扩容2倍

扩容

ArrayList 和 Vector 的区别是什么？

Vector

List接口

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

实现Set接口

value使用PRESENT占位（Dummy）

仅存储对象

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

源代码：同HashMap

HashSet

实现了Map接口

存储键值对

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

HashMap

HashSet与HashMap的区别

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

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

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

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

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

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

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

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

==与equals的区别

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

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

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

LinkedHashSet

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

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

TreeSet

Set接口

都继承自Collection 接口

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

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

无序性≠随机性

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

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

List 和 Set 的区别

BlockingQueue

Deque

Queue

collection接口

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

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

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

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

value所在的类要重写equals()

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

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

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

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

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

Properties

Hashtable

删除：remove(Object key)

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

查询：get(Object key)

长度：size()

foreach

idea：iter

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

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

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

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

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

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

初始化

进行了四次异或操作

JDK7

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

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

只用key的hashcode占用内存过大

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

为什么这么设计？

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

JDK8

hashcode函数设计

JDK7：流程分析

节省空间

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

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

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

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

JDK7可能产生死链（环）

JDK8可能产生数据丢失问题

并发环境下

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

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

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

JDK8：源码分析

图片流程

补：java中的位运算

HashMap底层典型属性说明

HashMap底层

LinkedHashMap内部提供了Entry

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

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

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

LinkedHashMap

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

key所属的类实现Comparable接口

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

TreeMap

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

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

提高HashMap的并发安全性

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

解决

说说ConcurrentHashMap解决了什么问题

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

segment上锁不影响其他segment操作

segment继承ReentrantLock

segment分段锁

访问可见性

value值volatile修饰

底层用数组+链表实现

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

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

get操作

key 已存在看是否覆盖value

key不存在头插法插入

遍历链表内容

定位分段内的桶下标

获取对象锁成功

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

尝试自旋获取锁

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

尝试获取锁失败

先定位到相应的 Segment

put操作

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

过小，容易产生锁竞争

JDK7里是segment的数量

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

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

ConcurrentHashMap 的并发度是什么？

JDK7中的ConcurrentHashMap

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

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

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

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

提升查询效率

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

尾插法的优势

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

饿汉式创建非常消耗资源

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

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

返回null

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

如果读取的bin头节点为null

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

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

get 流程

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

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

正在迁移的hash桶

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

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

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

头结点标记为ForwardNode

转发到新数组进行查询

扩容完成的

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

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

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

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

不能保证happen before

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

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

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

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

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

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

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

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

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

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

null区别

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

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

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

HashMap中

两次调用值可能被改变

ConcurrentHashMap中

为什么ConcurrentHashMap不能存null

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

计算key的hash值

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

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

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

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

创建方式区别

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

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

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

取代分段锁思想

要创建链表头节点

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

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

已扩容

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

找到相同的 key

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

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

没有找到

是链表，用链表方式插入

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

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

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

正在扩容的头结点

可直接插入

未扩容

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

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

put流程

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

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

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

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

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

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

ForwardingNode

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

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

sizeCtl值为2的幂次

新建而未初始化时

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

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

初始化过程中

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

记录下一次扩容的阈值

初始化完成后

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

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

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

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

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

正在扩容时

sizeCtl 属性在各个阶段的作用

JDK8中的ConcurrentHashMap

ConcurrentHashMap

Map接口

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

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

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

CopyOnWriteArrayList

使用JUC包下的集合

如何解决

说说什么是fail-fast

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

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

面试题

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

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

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

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

sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序