第二章 集合

系列文章目录

提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加
例如：第一章 Python 机器学习入门之pandas的使用

---

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

说说HashMap 和 HashSet 区别？

HashSet 底层就是基于 HashMap 实现的。两者主要区别：

说下HashMap 和 Hashtable 的区别？

线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）

效率：因为Hashtable加了synchronized锁。所以HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它

对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。

初始容量大小和每次扩充容量大小的不同 ：
① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小。

为什么HashTable 的key和value 不能为 null 值 ？

key V 不能为 null 主要是为了线程安全所考虑
当通过get(k)获取对应的value时，如果获取到的是null时，无法判断，它是put（k,v）的时候value为null，还是这个key从来没有做过映射。假如线程1调用m.contains（key）返回true，然后在调用m.get(key)，这时的m可能已经不同了。因为线程2可能在线程1调用m.contains（key）时，删除了key节点，这样就会导致线程1得到的结果不明确，产生多线程安全问题，因此，Hashmap和ConcurrentHashMap的key和value不能为null。

而HashMap允许key和value为null，在单线程时，调用contains()和get()不会出现问题，但是多线程下，就是线程不安全的。如果要保证线程安全，应该使用ConcurrentHashMap 。

说说LinkedHashMap 的实现原理？

LinkedHashMap也是基于HashMap 实现的，不同的是它定义了一个Entry header，这个header不是放在Table里，它是额外独立出来的。LinkedHashMap通过继承hashMap 中的Entry，并添加两个属性Entrybefore，after和 header结合起来组成一个双向链表，来实现按插入顺序或访问顺序排序。

LinkedHashMap定义了排序模式 accessOrder，该属性为boolean型变量，对于访问顺序，为true，对于插入顺序，则为false。一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。

说一下HashMap 和 TreeMap 区别？

---

一、集合容器概述

1、 什么是集合 ，集合的特点 ？

集合就是一个放数据的容器，准确的说是放数据对象引用的容器
集合类存放的都是对象的引用，而不是对象的本身
集合类型主要有3种：set(集）、list(列表）和map(映射)。

集合的特点主要有如下两点：
集合用于存储对象的容器，对象是用来封装数据，对象多了也需要存储集中式管理。
和数组对比对象的大小不确定。因为集合是可变长度的。数组需要提前定义大小

2、集合和数组的区别 ?

数组是固定长度的；集合可变长度的。
数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。
数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。

3、使用集合框架的好处 ?

容量自增长；
提供了高性能的数据结构和算法，使编码更轻松，提高了程序速度和质量；
可以方便地扩展或改写集合，提高代码复用性和可操作性。

4、说说Java中常用的容器有哪些？也就是常用的集合类有哪些？

.

Collection接口 和 Map接口 是所有集合框架的父接口：

Collection接口的子接口包括：Set接口和List接口
Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等
List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等
Map接口的实现类主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等

5、List，Set，Map三者的区别 ？

Java 容器分为 Collection 和 Map 两大类，Collection集合的子接口有Set、List、Queue三种子接
口。我们比较常用的是Set、List，Map接口不是collection的子接口。

Collection集合主要有List和Set两大接口
List：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多
个null元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。
Set：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一
个null元素，必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及TreeSet。

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

6、集合框架底层数据结构

Collection

List
Arraylist： Object数组
Vector： Object数组
LinkedList： 双向循环链表*

Set
HashSet（无序，唯一）：基于 HashMap 实现的，底层采用 HashMap 来保存元素
LinkedHashSet： LinkedHashSet 继承与 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。
TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树。)

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

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

HashTable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突
而存在的
TreeMap： 红黑树（自平衡的排序二叉树）

7、哪些集合类是线程安全的？

Vector：就比Arraylist多了个 synchronized （线程安全），因为效率较低，现在已经不太建议使
用。

hashTable：就比hashMap多了个synchronized (线程安全)，不建议使用。

ConcurrentHashMap：是Java5中支持高并发、高吞吐量的线程安全HashMap实现。它由Segment数组结构和HashEntry数组结构组成。Segment数组在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键-值对数据。一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构；一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素；每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。（推荐使用）

8、 Java集合的快速失败机制 “fail-fast”？

是java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生
fail-fast 机制。

例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时
候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这
个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。
原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集
合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()
遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍
历；否则抛出异常，终止遍历。

解决办法：
在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。
使用CopyOnWriteArrayList来替换ArrayList

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

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

示例代码如下：

List<String> list = new ArrayList<>();
list. add("x");
Collection<String> clist = Collections. unmodifiableCollection(list);
clist. add("y"); // 运行时此行报错
System. out. println(list. size());

List

10 、 List 和 Set 的区别 ？

List：有序集合（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多
个null元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。

Set：无序集合（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一
个null元素，必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及TreeSet。

11 、 迭代器 Iterator 是什么？

Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来
获取迭代器实例。迭代器取代了 Java 集合框架中的 Enumeration，迭代器允许调用者在迭代过程
中移除元素。
因为所有Collection接继承了Iterator迭代器

public interface Collection<E> extends Iterable<E>{// Query Operations
}

12、Iterator 怎么使用？有什么特点？

Iterator 使用代码如下：
先调用iterator 方法获取到 迭代器，然会判断是否有元素或者下一个元素，再调用 next 获取元素List<String> list = new ArrayList<>();Iterator<String> it = list. iterator();while(it. hasNext()){String obj = it. next();System. out. println(obj);}

特点
Iterator 的特点是只能单向遍历，但是更加安全，因为它可以确保，在当前遍历的集合元素被更改
的时候，就会抛出 ConcurrentModificationException 异常。

14. 如何边遍历边移除 Collection 中的元素？
15. Iterator 和 ListIterator 有什么区别？
16. 遍历一个 List 有哪些不同的方式？每种方法的实现原理是什么？Java 中 List遍历的最佳实践是什么？
17. 如何实现数组和 List 之间的转换？
    8.comparable和comparator的区别？
    9.Collection和Collections有什么区别？
    10.说一下PriorityQueue？

ArrayList

46. Array 和 ArrayList 有何区别？
47. 如何实现 Array 和 List 之间的转换？
    2.详细说说 Arraylist 和 LinkedList的区别?
48. 说一下 ArrayList 的优缺点
    3.ArrayList实现 RandomAccess接口有何作用？
    5.说说ArrayList 的扩容机制？
    6.Array和ArrayList有何区别？
    4.说一说Vector 和 ArrayList 的区别？
49. 插入数据时，ArrayList、LinkedList、Vector谁速度较快？阐述
50. 多线程场景下如何使用 ArrayList？
51. 为什么 ArrayList 的 elementData 加上 transient 修饰？

Set接口
24. 说一下 HashSet 的实现原理？
25. HashSet如何检查重复？HashSet是如何保证数据不可重复的？
26. HashSet与HashMap的区别
linkedllist和linkledHashSet的区别
28. 什么是链表

三、Map接口
27. 什么是Hash算法
20.HashMap怎么计算 key 的 hash 值的？
35. 能否使用任何类作为 Map 的 key？
27.为什么HashMap中String、Integer这样的包装类适合作为Key?
37. 如果使用Object作为HashMap的Key，应该怎么办呢？
34. HashMap是怎么解决哈希冲突的？
38. HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？
12.HashMap的实现原理/底层数据结构？
13.HashMap 的长度为什么是 2 的幂次方？
14.说说HashMap的put方法执行流程？
15.说说HashMap的get方法执行流程？
33. HashMap的扩容操作是怎么实现的？
16.说说HashMap的resize方法执行过程
31. 什么是红黑树
17.HashMap什么时候会树化？
18.HashMap底层为什么选择红黑树而不用其他树，比如二叉查找树？
19.HashMap扩容（加载）因子为何默认是 0.75f？
39. HashMap 的长度为什么是2的幂次方
22.HashMap多线程操作导致死循环问题知道吗?

28.说一下Queue 与 Deque 的区别？
29.说说ArrayDeque 与 LinkedList 的区别？
30.说一下 HashSet、LinkedHashSet 和 TreeSet 三者的异同？

30. HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底层实现

31. 什么是TreeMap 简介

32. 如何决定使用 HashMap 还是 TreeMap？

33. HashMap 和 ConcurrentHashMap 的区别

34. ConcurrentHashMap 和 Hashtable 的区别？

35. ConcurrentHashMap 底层具体实现知道吗？实现原理是什么？
    四、辅助工具类

36. comparable 和 comparator的区别？

37. Collection 和 Collections 有什么区别？

38. TreeMap 和 TreeSet 在排序时如何比较元素？Collections 工具类中的 sort()方法如何比较元素？

39. Collection 和 Collections 有什么区别？

40. TreeMap 和 TreeSet 在排序时如何比较元素？Collections 工具类中的 sort()方法如何比较元素？