# 第 12 章：随堂复习与企业真题（集合框架）

# 一、随堂复习

# 1. 数组存储数据方面的特点和弊端

   数组存储多个数据方面的特点：
   > 数组一旦初始化，其长度就是确定的。
   > 数组中的多个元素是依次紧密排列的，有序的，可重复的
   > (优点) 数组一旦初始化完成，其元素的类型就是确定的。不是此类型的元素，就不能添加到此数组中。
      int[] arr = new int[10];
      arr[0] = 1;
      arr[1] = "AA";//编译报错

      Object[] arr1 = new Object[10];
      arr1[0] = new String();
      arr1[1] = new Date();
   > (优点)元素的类型既可以是基本数据类型，也可以是引用数据类型。

   数组存储多个数据方面的弊端：
   > 数组一旦初始化，其长度就不可变了。
   > 数组中存储数据特点的单一性。对于无序的、不可重复的场景的多个数据就无能为力了。
   > 数组中可用的方法、属性都极少。具体的需求，都需要自己来组织相关的代码逻辑。
   > 针对于数组中元素的删除、插入操作，性能较差。

# 2. 集合框架概述

java.util.Collection:存储一个一个的数据
    |-----子接口：List:存储有序的、可重复的数据 ("动态"数组)
           |---- ArrayList(主要实现类)、LinkedList、Vector

    |-----子接口：Set:存储无序的、不可重复的数据(高中学习的集合)
           |---- HashSet(主要实现类)、LinkedHashSet、TreeSet


java.util.Map:存储一对一对的数据(key-value键值对，(x1,y1)、(x2,y2) --> y=f(x),类似于高中的函数)
    |---- HashMap(主要实现类)、LinkedHashMap、TreeMap、Hashtable、Properties

学习的程度把握：
层次1：针对于具体特点的多个数据，知道选择相应的适合的接口的主要实现类，会实例化，会调用常用的方法。
层次2：区分接口中不同的实现类的区别。
*****************
层次3：① 针对于常用的实现类，需要熟悉底层的源码 ② 熟悉常见的数据结构 （第14章讲）

# 3. Collection 的常用方法

# 3.1 常用方法

add(Object obj)
addAll(Collection coll)
clear()
isEmpty()
size()
contains(Object obj)
containsAll(Collection coll)
retainAll(Collection coll)
remove(Object obj)
removeAll(Collection coll)
hashCode()
equals()
toArray()
**************
iterator() ---> 引出了迭代器接口

向Collection中添加元素的要求：
> 要求元素所属的类一定要重写equals()!

集合与数组的相互转换：
集合 ---> 数组：toArray()
数组 ---> 集合：调用Arrays的静态方法asList(Object ... objs)，返回一个List

# 3.2 迭代器接口

• 设计模式的一种
• 迭代器不负责数据的存储；负责对集合类的遍历

1. 如何获取迭代器(Iterator)对象？

Iterator iterator = coll.iterator();

2. 如何实现遍历(代码实现)

while(iterator.hasNext()){

    System.out.println(iterator.next()); //next ():①指针下移 ② 将下移以后集合位置上的元素返回

}

# 4. Collection 的子接口：List

• 常用方法

小结：

    增

        add(Object obj)

        addAll(Collection coll)

    删

        remove(Object obj)

        remove(int index)

    改

        set(int index, Object ele)

    查

        get(int index)

    插

        add(int index, Object ele)

        addAll(int index, Collection eles)

    长度

        size()

    遍历

        iterator() ：使用迭代器进行遍历

        增强for循环

        一般的for循环

List及其实现类特点
java.util.Collection:存储一个一个的数据
    |-----子接口：List:存储有序的、可重复的数据 ("动态"数组)
           |---- ArrayList:List的主要实现类；线程不安全的、效率高；底层使用Object[]数组存储
                           在添加数据、查找数据时，效率较高；在插入、删除数据时，效率较低
           |---- LinkedList:底层使用双向链表的方式进行存储；在对集合中的数据进行频繁的删除、插入操作时，建议							使用此类在插入、删除数据时，效率较高；在添加数据、查找数据时，效率较低；
           |---- Vector:List的古老实现类；线程安全的、效率低；底层使用Object[]数组存储

[面试题] ArrayList、Vector的区别？  ArrayList、LinkedList的区别？

# 5. Collection 的子接口：Set

• Set 中的常用的方法都是 Collection 中声明的方法，没有新增的方法
• 常见的实现类的对比

java.util.Collection:存储一个一个的数据
    |-----子接口：Set:存储无序的、不可重复的数据(高中学习的集合)
           |---- HashSet：主要实现类；底层使用的是HashMap，即使用数组+单向链表+红黑树结构进行存储。（jdk8中）
                |---- LinkedHashSet：是HashSet的子类；在现有的数组+单向链表+红黑树结构的基础上，又添加了
                                     一组双向链表，用于记录添加元素的先后顺序。即：我们可以按照添加元素的顺									序实现遍历。便于频繁的查询操作。
           |---- TreeSet：底层使用红黑树存储。可以按照添加的元素的指定的属性的大小顺序进行遍历。

• 难点： Set 中无序性、不可重复性的理解（以 HashSet 及其子类为例说明）

>无序性： != 随机性。
         添加元素的顺序和遍历元素的顺序不一致,是不是就是无序性呢？ No!
         到底什么是无序性？与添加的元素的位置有关，不像ArrayList一样是依次紧密排列的。
         这里是根据添加的元素的哈希值，计算的其在数组中的存储位置。此位置不是依次排列的，表现为无序性。

>不可重复性：添加到Set中的元素是不能相同的。
          比较的标准，需要判断hashCode()得到的哈希值以及equals()得到的boolean型的结果。
          哈希值相同且equals()返回true，则认为元素是相同的。

添加到HashSet/LinkedHashSet中元素的要求:
>要求元素所在的类要重写两个方法：equals() 和 hashCode()。
>同时，要求equals() 和 hashCode()要保持一致性！我们只需要在IDEA中自动生成两个方法的重写即可，即能保证两个方法的一致性。

• 了解 TreeSet 的使用

# 6. Map 接口

• 常用的方法

增：
    put(Object key,Object value)
    putAll(Map m)
删：
    Object remove(Object key)
改：
    put(Object key,Object value)
    putAll(Map m)
查：
    Object get(Object key)
长度：
    size()
遍历：
   遍历key集：Set keySet()
   遍历value集：Collection values()
   遍历entry集：Set entrySet()

• 常用的实现类

java.util.Map:存储一对一对的数据(key-value键值对，(x1,y1)、(x2,y2) --> y=f(x),类似于高中的函数)
    |---- HashMap:主要实现类;线程不安全的，效率高;可以添加null的key和value值;底层使用数组+单向链表+红黑树结构存储（jdk8）
        |---- LinkedHashMap:是HashMap的子类；在HashMap使用的数据结构的基础上，增加了一对双向链表，用于记录添加的元素的先后顺序，进而我们在遍历元素时，就可以按照添加的顺序显示。开发中，对于频繁的遍历操作，建议使用此类。
    |---- TreeMap:底层使用红黑树存储;可以按照添加的key-value中的key元素的指定的属性的大小顺序进行遍历。需要考虑使用①自然排序 ②定制排序。
    |---- Hashtable:古老实现类;线程安全的，效率低;不可以添加null的key或value值;底层使用数组+单向链表结构存储（jdk8）
        |---- Properties:其key和value都是String类型。常用来处理属性文件。


[面试题] 区别HashMap和Hashtable、区别HashMap和LinkedHashMap、HashMap的底层实现（① new HashMap() ② put(key,value)）

HashMap中元素的特点:
> HashMap中的所有的key彼此之间是不可重复的、无序的。所有的key就构成一个Set集合。--->key所在的类要重写hashCode()和equals()
> HashMap中的所有的value彼此之间是可重复的、无序的。所有的value就构成一个Collection集合。--->value所在的类要重写equals()
> HashMap中的一个key-value,就构成了一个entry。
> HashMap中的所有的entry彼此之间是不可重复的、无序的。所有的entry就构成了一个Set集合。

• （了解）TreeMap 的使用

• （重要）Properties 的使用

  	public class PropertiesTest {
  	@Test
  	public void test() throws IOException { // 注意：因为设计到流的操作，为了确保流能关闭，建议使用 try-catch-finally
  	// 方式 1：数据和代码耦合度高；如果修改的话，需要重写的编译代码、打包发布，繁琐
  	// 数据
  	// String name = "Tom";
  	// String password = "abc123";
  	// 代码：用于操作 name,password
  	//...
  	// 方式 2：将数据封装到具体的配置文件中，在程序中读取配置文件中的信息。实现了
  	// 数据和代码的解耦；由于我们没有修改代码，就省去了重新编译和打包的过程。
  	File file = new File("info.properties"); // 注意，要提前创建好
  	// System.out.println(file.getAbsolutePath());
  	FileInputStream fis = new FileInputStream(file);
  	Properties pros = new Properties();
  	pros.load(fis); // 加载流中的文件中的数据
  	// 读取数据
  	String name = pros.getProperty("name");
  	String pwd = pros.getProperty("password");
  	System.out.println(name + ":" + pwd);
  	fis.close();
  	}
  	}

# 7. Collections 工具类的使用

区分Collection 和 Collections
Collection：集合框架中的用于存储一个一个元素的接口，又分为List和Set等子接口。
Collections：用于操作集合框架的一个工具类。此时的集合框架包括：Set、List、Map

• 熟悉常用的 Collections 中的方法即可。

# 二、企业真题

# 2.1 集合概述

# 1. List，Set，Map 是否继承自 collection 接口？（北京中 * 译咨询、思 * 贸易）

Map 不是。

# 2. 说说 List,Set,Map 的区别 (民 * 银行)

类似问题：
> Map与Set、List的区别（纬*）

List、Set 是存储单列数据集合，都继承与 Collection 接口。Map 是存储键值对这样的双列数据的集合，是个独立接口。

List 中存储的数据是有序的，可以是重复的。

Set 中存储的数据是无序的，且不允许重复。

Map 中存储的数据是无序的，他的键是不允许重复的，值是可以重复的。

# 3. 写出 list、map、set 接口的实现类，并说出其特点（华 ** 为）

类似问题：
> 集合有哪些， 各自有哪些特点， 各自的API有哪些？（湖**利软件）
> List Map Set三个接口在存储元素时个有什么特点（*软）

• List 接口的实现类
  • ArrayList
    • 动态数组，可扩容的 Object 数组
    • 支持随机访问元素，适用于频繁访问元素的场景
    • 插入和删除操作效率较低
  • LinkedList
    • 双向链表
    • 随机访问元素效率较低
    • 支持快速的插入和删除操作，适用于频繁插入和删除元素的场景
  • Vector
    • 与 ArrayList 类似，底层也是可扩容的 Object 数组
    • 线程安全，支持同步访问，也因此效率低，不适用于高并发场景
• Set 接口的实现类
  • HashSet
    • 哈希表
    • 不保证元素的顺序
  • LinkedHashSet
    • 哈希表 + 双向链表
    • 保证元素有序
  • TreeSet
    • 红黑树
    • 要求元素属于同一个类
    • 可以按照指定属性的大小顺序进行遍历
    • 可以实现自然排序 / 定制排序
• Map 接口的实现类
  • HashMap
    • 哈希表
    • 快速的查找和插入，不保证元素的顺序
  • LinkedHashMap
    • 哈希表 + 双向链表
    • 保证元素有序
  • TreeMap
    • 红黑树
    • 要求 key 都属于同一个类
    • 可以按照 key 中的指定属性的大小顺序进行遍历
    • 适用于需要有序的键值对集合
  • Hashtable
    • 哈希表
    • 线程安全
  • Properties
    • 哈希表
    • 键和值都是 String 类型
    • 适用于以键值对的方式存储配置信息

# 4. 常见集合类的区别和适用场景（饿 **）

Java 中常见的集合类有 List、Set、Map。

区别（元素特点）：

• List 中的元素是有序，可重复的；
• Set 中的元素是无序，不可重复的；
• Map 是由键值对组成的，键不可以重复，值可以重复。

区别（实现类的底层数据结构）：

• List 的实现类

  • ArrayList 是一个动态数组
  • LinkedList 是一个双向链表
  • Vector 是一个线程安全的动态数组

• Set 的实现类

  • HashSet 是基于哈希表实现的
  • LinkedHashSet 是基于哈希表、双向链表实现的
  • TreeSet 是基于红黑树实现的

• Map 的实现类

  • HashMap 是基于哈希表实现的
  • LinkedHashMap 是基于哈希表、双向链表实现的
  • TreeMap 是基于红黑树实现的

适用场景：

• List

  • ArrayList：需要频繁访问元素时使用
  • LinkedList：需要频繁插入或删除元素时使用
  • Vector：需要线程安全时使用

• Set

  • HashSet：需要去重时使用，不保证元素的顺序
  • TreeSet：需要排序时使用

• Map

  • HashMap：需要快速的查找和插入，不要求元素的顺序时使用
  • LinkedHashMap：需要保证键值对元素的顺序时使用
  • TreeMap：需要排序时使用

# 5. 集合的父类是谁？哪些安全的？（北京中 ** 信）

Collection、List、Set、Map 都是接口，不是类。

（线程）不安全：ArrayList、HashSet、HashMap

这些都是常用的，当需要线程安全时，调用 Collections 工具类中的同步方法对集合进行包装

（线程） 安全：Vector、Hashtable

反而不常用，因为效率低

# 6. 集合说一下哪些是线程不安全的（* 科软）

除了 Vector 和 Hashtable。

# 7. 遍历集合的方式有哪些？（恒 * 电子）

• 迭代器 Iterator 用来遍历 Collection，不能用来遍历 Map！

  map.keySet().iterator() 、 map.values().iterator() 、 map.entrySet().iterator() 本质上都是迭代器对 Set、Collection 进行遍历

• 增强 for

  for (Object obj : 集合对象)

• 一般的 for：可以用来遍历 List

# 2.2 List 接口

# 1. List 下面有哪些实现（软 ** 力）

ArrayList、LinkedList、Vector

# 2. ArrayList 与 LinkedList 区别？(O**O、滴 *、汇 * 天下、拓 * 软件、博纳 ** 软件、上海 * 进天下，北京永生 ** 信息、* 联、在 * 途游)

类似问题：
> ArrayList跟LinkedList的区别详细说出？（阿*校招、*东）

ArrayList 和 LinkedList 的区别如下：

• ArrayList 是基于动态数组实现的，而 LinkedList 是基于双向链表实现的。
• 对于随机访问 get 和 set，ArrayList 更快，因为 ArrayList 可以根据下标以 O (1) 时间复杂度对元素进行随机访问；而 LinkedList 需要移动指针遍历每个元素直到找到为止。
• 对于新增和删除操作 add 和 remove，LinkedList 更快，因为 ArrayList 在新增和删除元素时，可能需要扩容和复制数组；而 LinkedList 除了实例化对象需要时间外，只需要修改指针即可。

补充上第 14 章中的源码（底层的数据结构）

# 3. ==ArrayList 与 Vector 区别呢？== 为什么要用 ArrayList 取代 Vector 呢？(湖 ** 利软件)

ArrayList 和 Vector 的区别如下：

• ArrayList 不是同步的，而Vector 是线程安全的，也就是说是同步的。
• ArrayList 在性能方面更优，因为 ArrayList 没有使用 synchronized 加锁，不加锁，所以处理速度会快一些。
• 扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只不过在Vector 扩容每次会增加 1 倍，而 ArrayList 只会增加 50%。

因此，如果不需要线程安全的话，建议使用 ArrayList。

# 4. Java.util.ArrayList 常用的方法有哪些？（华 ** 为）

• Collection 接口中的方法
• List 接口中的方法
• ArrayList 类特有的方法

例如：

• 增
  • add (E obj)：在列表的末尾添加指定元素
  • addAll(Collection other)
• 删
  • clear()
  • remove (Object obj)：移除列表中首次出现的指定元素，如果存在，返回 true，否则返回 false
  • removeAll(Collection coll)
  • retainAll(Collection coll)
  • remove(int index)
• 改
  • set(int index, Object ele)
• 查
  • get(int index)
  • subList(int fromIndex, int toIndex):
  • indexOf(Object obj)
  • lastIndexOf(Object obj)
• 插
  • add(int index, Object ele)
  • addAll(int index, Collection eles)
• 长度
  • size ()：返回列表中实际存储的元素个数
• 遍历
  • iterator()
  • 增强 for 循环
  • 普通 for 循环
• 其他
  • isEmpty()
  • contains(Object obj)
  • containsAll(Collection coll)
  • equals(Object obj)
  • toArray()
  • hashCode()
• ArrayList 类特有
  • ensureCapacity(int minCapacity)：确保列表的容量至少等于指定的最小值
  • trimToSize()：将列表的容量调整为列表的当前大小
  • clone()：返回一个 ArrayList 对象的浅拷贝

# 5. Arraylist 是有序还是无序？为什么？（蜜 * 信息）

有序；底层使用数组：Object []

# 2.3 Set 接口

# 1.Set 集合有哪些实现类，分别有什么特点？（拓 * 软件）

类似问题：
> Set的实现类有哪些？（博*科技）

• HashSet

  • 主要实现类
  • 基于哈希表
  • 存取速度快
  • 不保证元素的顺序
  • 允许 null

• LinkedHashSet

  • HashSet 的子类

  • 基于哈希表 + 双向链表

  • 记录了元素的添加顺序，便于频繁查询

  • 插入性能略低 于 HashSet，但 迭代访问性能 优于 HashSet

    LinkedHashSet 的插入性能低于 HashSet，是因为 LinkedHashSet 除了维护一个哈希表外，还要维护一个双向链表来记录元素的插入顺序 ²³。这样在插入元素时，需要额外的操作来更新链表的指针，而 HashSet 不需要这样做¹²。

    LinkedHashSet 的迭代性能优于 HashSet，是因为LinkedHashSet 可以直接按照链表的顺序来遍历元素，而不需要对哈希表进行排序或者查找²⁴。而HashSet 在遍历时，需要根据哈希值来确定元素的位置，可能会遇到哈希冲突或者空桶的情况，导致性能下降¹²。

• TreeSet

  • 基于红黑树
  • 要求元素属于同一个类，不允许 null
  • 可以按照元素的指定属性的大小顺序进行排序（自然排序 / 定制排序）

# 2. List 集合和 Set 集合的区别？（亚 * 科技、* 海 * 翼科技，* 华电 * 系统，达 * 贷）

List 集合和 Set 集合的区别有以下几点 ¹²：

• List 集合是有序的，可以按照元素的插入顺序（LinkedList）或者指定的索引（ArrayList）来访问元素，而Set 集合是无序的，不能通过索引来访问元素 ¹²。
• List 集合可以包含重复的元素，也可以包含多个 null 元素，而Set 集合不允许包含重复的元素，最多只能包含一个 null 元素¹²。
• List 集合继承了 Collection 接口，并提供了一些额外的方法，如 get (int index), set (int index, E element), add (int index, E element), remove (int index) 等，而Set 集合没有提供这些方法¹²。
• List 集合的实现类有 ArrayList, LinkedList 和 Vector，而Set 集合的实现类有 HashSet, LinkedHashSet 和 TreeSet¹²。

# 3. Set 里的元素是不能重复的，那么用什么方法来区分重复与否呢？是用还是 equals ()? 它们有何区别？==（鸿 * 网络）

类似问题：
> 1.HashSet如何检查重复(创*科技)
> 3.Set使用哪个区分不能重复的元素的？（北京创**荣信息）

Set 里的元素是不能重复的，它是通过调用元素的 equals() 和 hashCode() 方法来判断两个元素是否相等的 ¹²。如果两个元素的 equals () 方法返回 true，并且它们的 hashCode () 方法返回相同的值，那么它们就被认为是相等的，Set 就不会存储重复的元素 ¹²。

== 和 equals() 都是用来比较两个对象是否相等的，但它们有以下区别 ³：

• == 是一个运算符，它可以用来比较基本数据类型和引用数据类型，而 equals() 是一个方法，它只能用来比较引用数据类型。
• == 比较的是两个对象的内存地址，即它们是否指向同一个对象，而 equals() 比较的是两个对象的内容，即它们是否逻辑上相等³。
• == 的比较规则是固定的，而 equals() 的比较规则可以根据不同的类来重写，例如 String 类就重写了 equals () 方法，使得它可以比较两个字符串的值是否相同 ³。

# 4. TreeSet 两种排序方式在使用的时候怎么起作用？（拓 * 软件）

在添加新的元素时，需要调用 compareTo() 或 compare() 。

TreeSet 是一个基于红黑树实现的有序集合，它可以按照元素中的指定属性的自然排序或者定制排序来存储和遍历元素¹²。它的两种排序方式在使用的时候有以下区别：

• 自然排序：如果元素实现了 Comparable 接口，那么 TreeSet 会调用元素的 compareTo () 方法来比较元素的大小，并按照升序排列 ¹²³。例如，String 类就实现了 Comparable 接口，它的 compareTo () 方法是按照字典顺序比较字符串的 ¹²。
• 指定排序：如果元素没有实现 Comparable 接口，或者想要使用不同的排序规则，那么可以在构造 TreeSet 时传入一个 Comparator 对象，它是一个比较器接口，可以自定义比较元素的方法 ¹²⁴。这种方式可以覆盖元素的自然顺序，也可以对没有自然顺序的元素进行排序 ¹²。例如，Student 类没有实现 Comparable 接口，但是可以通过传入一个 Comparator 对象来按照学号或者姓名等属性进行排序

# 5. TreeSet 的数据结构（* 米）

TreeSet 是一个有序集合，它的内部实现是基于一个红黑树的 TreeMap。TreeMap 是一个键值对的映射，它的键是按照自然顺序或者指定的比较器顺序来排序的。TreeSet 只使用了 TreeMap 的键，而把值设置为一个固定的常量。

红黑树是一种自平衡的二叉搜索树，它满足以下性质：

• 每个节点要么是红色，要么是黑色
• 根节点是黑色
• 每个叶子节点（空节点）是黑色
• 如果一个节点是红色，那么它的两个子节点都是黑色
• 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

这些性质保证了红黑树的高度近似于$log(n)$，从而使得插入、删除和查找操作的时间复杂度都是$O(log(n))$。

TreeSet 使用红黑树的意义是为了保证集合中的元素可以按照一定的顺序进行存储和遍历，同时也为了提高集合中的插入、删除和查找操作的效率¹²³。

TreeSet 使用红黑树的好处有以下几点 ¹²³：

• 红黑树是一种 **自平衡的二叉搜索树**，它可以保证在最坏情况下，插入、删除和查找操作的时间复杂度都是$O(log(n))$，而不会退化成链表或者倾斜树
• 红黑树可以按照元素的自然顺序或者指定的比较器顺序来排序，这样可以方便地对集合中的元素进行遍历、查找、范围查询等操作
• 红黑树可以利用节点的颜色信息来维持树的平衡，这样可以减少旋转和重构的次数，提高操作的性能

# 2.4 Map 接口

# 1. 说一下 Java 的集合 Map 有哪些实现类？（奥 * 医药）

Java 的集合 Map 有以下几种常见的实现类：

• HashMap：基于哈希表的 Map 接口的实现，允许使用 null 键和 null 值，不保证映射的顺序，是线程不安全的，支持快速的插入、删除和查找操作
• TreeMap：基于红黑树的 Map 接口的实现，按照键的自然顺序或者指定的比较器顺序来排序，不允许使用 null 键，但可以使用 null 值，是线程不安全的，支持有序的插入、删除和查找操作
• LinkedHashMap：基于哈希表和双向链表的 Map 接口的实现，按照插入顺序或者访问顺序来排序，允许使用 null 键和 null 值，是线程不安全的，结合了 HashMap 的查询速度和 LinkedHashSet 的插入顺序
• Hashtable：基于哈希表的 Map 接口的旧版本实现，不允许使用 null 键和 null 值，保证映射的顺序，是线程安全的，但效率低于 HashMap 和 ConcurrentHashMap
• ConcurrentHashMap：基于哈希表和分段锁或者 CAS 技术的 Map 接口的实现，不允许使用 null 键和 null 值，不保证映射的顺序，是线程安全的，并发性能高于 Hashtable

# 2. final 怎么用，修饰 Map 可以继续添加数据吗？（* 深蓝）

final 是一个关键字，可以用来修饰类、方法、变量等。final 的作用有以下几点：

• 修饰类：表示该类不能被继承，如 String 类
• 修饰方法：表示该方法不能被重写，如 Object 类的 getClass () 方法
• 修饰变量：表示该变量是一个常量，只能被赋值一次，如 Math 类的 PI 常量

final 修饰 Map 时，表示该 Map 的引用是一个常量，不能再指向其他的对象。但是，这并不影响 Map 中的键值对的添加、删除和修改。因为 final 只保证了引用的不变性，而不保证了引用指向的对象的不变性。

如果想要让 Map 中的键值对也不能被修改，可以使用 Collections.unmodifiableMap() 方法来返回一个不可修改的 Map 视图。

例如：

// 创建一个普通的 HashMap

Map<String, Integer> map = new HashMap<> ();

map.put("a", 1);

map.put("b", 2);

System.out.println(map); // {a=1, b=2}

// 使用 final 修饰 map 的引用

final Map<String, Integer> finalMap = map;

//finalMap = new HashMap<> (); // 编译错误，不能再赋值

finalMap.put("c", 3); // 可以添加数据

System.out.println(finalMap); // {a=1, b=2, c=3}

// 使用 Collections.unmodifiableMap () 返回一个不可修改的 Map 视图

Map<String, Integer> unmodifiableMap = Collections.unmodifiableMap(map);

//unmodifiableMap.put ("d", 4); // 运行时异常，不能添加数据

System.out.println(unmodifiableMap); // {a=1, b=2, c=3}

# 3. Set 和 Map 的比较（亚 * 科技）

HashSet 底层就是 HashMap

LinkedHashSet 底层就是 LinkedHashMap

TreeSet 底层就是 TreeMap

Set 和 Map 是 Java 中两种不同的集合接口，它们有以下几点区别：

• 元素特点

  • Set 是一个不包含重复元素的集合，它只存储键，而不存储值
  • Map 是一个键值对的映射，它存储键和值，且键不能重复，但值可以重复

• 无序性

  • Set 是一个无序的集合，它不保证元素的存储顺序，除非使用有序的实现类如 TreeSet 或 LinkedHashSet
  • Map 也是一个无序的映射，它不保证键或值的存储顺序，除非使用有序的实现类如 TreeMap 或 LinkedHashMa

• 遍历方式

  • Set可以直接遍历其元素，使用 iterator () 方法或 foreach 循环
  • Map 不能直接遍历其元素，需要使用 keySet ()、values () 或 entrySet () 方法先获取其键集、值集或键值对集，然后再使用 iterator () 方法或 foreach 循环遍历

• null

  • Set最多只能存储一个 null 元素
  • Map最多只能有一个 null 键和任意个 null 值

• 实现类的特点、用途

  • Set

    • HashSet 是基于哈希表的 Set 实现类，它提供了快速的插入和查找操作，但不保证元素的顺序
    • LinkedHashSet 是基于哈希表和双向链表的 Set 实现类，它按照元素的插入顺序来排序，同时也保持了 HashSet 的查询速度
    • TreeSet 是基于红黑树的 Set 实现类，它按照元素的自然顺序或指定的比较器顺序来排序，但插入和查找操作较慢

  • Map

    • HashMap 是基于哈希表的 Map 实现类，它提供了快速的插入、删除和查找操作，但不保证键或值的顺序
    • LinkedHashMap 是基于哈希表和双向链表的 Map 实现类，它按照键的插入顺序或访问顺序来排序，同时也保持了 HashMap 的查询速度
    • TreeMap 是基于红黑树的 Map 实现类，它按照键的自然顺序或指定的比较器顺序来排序，但插入、删除和查找操作较慢

# 4. 介绍一下 HashMap，是线程安全的吗？（* 米）

类似问题：
> HashMap为什么线程不安全？（微*银行）
> HashMap是线程安全的吗？为什么不安全？（*团、*东、顺*）

HashMap 是一种基于哈希表的 Map 接口实现，它可以存储键值对 (key-value) 映射，具有以下特点:

• HashMap 是无序的，也就是说它不会记录插入的顺序，而是根据键的哈希值来决定元素在数组中的位置

• HashMap 是线程不安全的，也就是说如果多个线程同时对 HashMap 进行修改操作，可能会导致数据丢失、死循环或数据覆盖等问题。如果需要线程安全的 Map 实现，可以使用 Hashtable、 Collections.synchronizedMap() 或 ConcurrentHashMap

• HashMap最多一个 null 键，任意个 null 值

• HashMap 有两个重要的参数：

  • 初始容量大小是创建时给数组分配的容量大小，默认值为 16，加载因子默认 0.75f，用数组容量大小乘以加载因子得到一个值，一旦数组中存储的元素个数超过该值就会调用 resize() 将数组容量增加到原来的两倍，专业术语叫做扩容。扩容的操作非常消耗性能，因为需要重新计算所有元素的哈希值并重新分配到新的数组中

• HashMap 的数据结构是 **数组 + 链表 + 红黑树**。

  • 数组是主要的数据结构，每个数组元素又是一个链表或红黑树的头节点。
  • 当通过键的哈希值计算出数组下标时，
    • 如果该位置没有元素，则直接插入
    • 如果该位置有元素，则需要判断该元素与插入元素的hashCode 是否相等
      • 如果相等则覆盖
      • 如果不等则以链表或红黑树的形式插入到该位置，当链表的长度超过 8 时，会将链表转换为红黑树，以提高查找效率

HashMap 的主要操作有 put () 和 get () 方法，它们的实现原理如下:

• put()

  • 首先将键和值封装成一个 Node 对象
  • 然后调用键的 hashCode () 方法得到哈希值，并通过哈希函数转换成数组下标

    • 如果该下标位置没有元素，则直接插入

    • 如果该位置有元素，则遍历该位置的链表或红黑树，比较每个节点的键是否与插入元素的键相等

      • 如果相等则覆盖
      • 如果不等则插入到链表尾部或红黑树中

    • 最后判断是否需要扩容

• get()

  • 首先调用键的 hashCode () 方法得到哈希值，并通过哈希函数转换成数组下标
  • 然后根据下标找到对应的链表或红黑树头节点，遍历该链表或红黑树，比较每个节点的键是否与查找元素的键相等
    • 如果相等则返回该节点的值
    • 如果不等则继续查找，如果遍历完毕没有找到，则返回 null

# 5. HashMap 和 Hashtable 的区别？(银 * 数据、阿 ** 巴芝麻信用、* 众银行、爱 * 信、杭州 * 智公司)

类似问题：
> HashMap 和 HashTable 有什么区别，以及如何使用，以及他的一些方法？（阿*校招、*东、*度校招、顺*）

HashMap 和 Hashtable 都是实现了 Map 接口的类，它们都可以存储键值对 (key-value) 映射，但是它们之间也有一些区别:

• HashMap 是线程不安全的，也就是说如果多个线程同时对 HashMap 进行修改操作，可能会导致数据丢失、死循环或数据覆盖等问题。Hashtable 是线程安全的，它的方法都使用了 synchronized 关键字来保证同步，但是这也降低了效率

• HashMap 允许键和值都为 null，但是最多只能有一个键为 null 的元素。Hashtable 不允许键和值为 null，否则会抛出 NullPointerException 异常

  • HashMap 是在 JDK1.2 中引入的，它是为了提供更高效和灵活的 Map 实现，而不考虑线程安全和兼容性。HashMap 允许键值为 null，是因为它使用了特殊的处理逻辑来处理 null 键值，比如使用 0 作为 null 键的哈希值，使用 equals 方法而不是 == 来比较 null 值等。这样做的好处是可以使得 HashMap 更通用和灵活，可以适应不同的场景和需求。

  • Hashtable 是在 JDK1.0 中引入的，它是为了提供一个线程安全和兼容性较好的 Map 实现，而不考虑效率和灵活性。Hashtable 不允许键值为 null，是因为它直接使用了键值的 hashCode () 方法和 == 运算符来计算哈希值和比较对象，如果键值为 null，就会抛出 NullPointerException 异常。这样做的好处是可以使得 Hashtable 更简单和稳定，可以避免一些潜在的错误和异常 。

• HashMap 的底层数组长度必须为 2 的幂次方，这样可以利用 & 运算代替 % 运算提高效率，并且使得元素分布更均匀。Hashtable 的底层数组长度可以为任意值，但是一般使用质数来减少哈希冲突

• HashMap 的哈希函数使用了键的 hashCode () 方法和高低位异或运算来计算哈希值，并且在链表长度超过 8 时会转换为红黑树来提高查找效率。Hashtable 的哈希函数只使用了键的 hashCode () 方法，并且一直使用链表来解决冲突

# 6. Hashtable 是怎么实现的，为什么线程安全？（迪 * 创新）

哈希表（数组 + 单向链表）；底层方法使用 synchronized 修饰。

Hashtable 是一种基于哈希表的 Dictionary 的子类，它实现了 Map 接口，可以存储键值对 (key-value) 映射：

• Hashtable 的内部数据结构是一个 Entry 数组，每个 Entry 是一个单向链表的头节点，用来解决哈希冲突。当插入或查找一个元素时，首先根据键的 hashCode () 方法和取模运算计算出数组下标，然后遍历对应位置的链表，比较每个节点的键是否与目标元素的键相等，如果相等则返回或覆盖，如果不等则插入或继续查找
• Hashtable 的所有方法都使用了 synchronized 关键字来修饰，这意味着它是线程安全的，多个线程可以共享一个 Hashtable 对象。但是这也导致了它的效率较低，因为每次操作都需要获取锁和释放锁
• Hashtable不允许键和值为 null，否则会抛出 NullPointerException 异常。这是因为它直接使用了键和值的 hashCode () 方法和 equals () 方法来计算哈希值和比较对象，如果键或值为 null，就会导致空指针异常
• Hashtable 有两个重要的参数：初始容量大小和加载因子。初始容量大小是创建时给数组分配的容量大小，默认值为 11，加载因子默认 0.75f，用数组容量大小乘以加载因子得到一个值，一旦数组中存储的元素个数超过该值就会调用 rehash 方法将数组容量增加到原来的两倍加一（通常为质数），专业术语叫做扩容。扩容的操作非常消耗性能，因为需要重新计算所有元素的哈希值并重新分配到新的数组中

# 7. HashMap 和 LinkedHashMap 的区别（北京 * 晨阳光）

HashMap 和 LinkedHashMap 都是实现了 Map 接口的类，它们都可以存储键值对 (key-value) 映射，但是它们之间也有一些区别：

• HashMap 是基于哈希表的，它根据键的 hashCode () 方法和取模运算计算出数组下标，然后在对应位置的链表中查找或插入元素。HashMap 不保证元素的顺序，遍历时取得数据的顺序是完全随机的。
• LinkedHashMap 是继承自 HashMap 的，它在 HashMap 的基础上增加了一个双向链表，用来维护元素的插入顺序或访问顺序。LinkedHashMap 保证元素的顺序，遍历时取得数据的顺序是按照插入或访问的先后顺序。
• HashMap 和 LinkedHashMap 在性能方面：
  • 插入、删除元素：由于 LinkedHashMap 需要额外维护一个双向链表，所以在 插入和删除元素 时会比 HashMap 慢一些。
  • 迭代遍历：LinkedHashMap 在 遍历元素 时会比 HashMap 快一些，因为 LinkedHashMap 的遍历速度只和实际数据有关，和容量无关。而HashMap 的遍历需要遍历底层数组，以及每个数组元素对应的链表 / 红黑树，数组的长度就是 HashMap 的容量，如果容量太大，那么遍历数组就会花费很多时间。

# 8. HashMap 和 TreeMap 的区别（度，太极 *、* 线途游、阿 * 校招）

HashMap 和 TreeMap 都是实现了 Map 接口的类，用来存储键值对，但是它们有以下几个方面的区别：

• 数据结构：HashMap 是基于哈希表来实现的，而 TreeMap 是基于红黑树来实现的
• 排序：HashMap不保证映射的顺序，而 TreeMap 根据键的自然顺序或者指定的比较器来对键进行排序
• 空值：HashMap 可以允许一个 null 键和多个 null 值，而 TreeMap不允许 null 键，但是可以允许多个 null 值
• 性能：
  • 增、删、查：HashMap 在添加、查找、删除等操作上速度会比较快，因为它只需要计算哈希值和数组下标，而 TreeMap 在这些操作上速度会比较慢，因为它需要维护红黑树的平衡和顺序
  • 内存：HashMap 会占用更多的空间，因为它需要保存一个数组，而 TreeMap 会占用更少的空间，因为它只需要保存节点
  • 另外，HashMap 如果出现哈希冲突或者扩容的话，效率会降低

# 9. HashMap 里面实际装的是什么？（惠 *）

JDK7：HashMap 内部声明了 Entry，实现了 Map 中的 Entry 接口。（key，value 作为 Entry 的两个属性出现）

JDK8：HashMap 内部声明了 Node，实现了 Map 中的 Entry 接口。（key，value 作为 Node 的两个属性出现）

HashMap 的内部结构包括以下几个部分：

• 一个动态数组，用来存放 Node 对象，每个 Node 对象包含一个 Entry 对象，Entry 对象中保存了键、值、哈希值等信息。
• 一个哈希函数，用来根据键的哈希值计算出数组的下标。
• 一个负载因子，用来控制数组的扩容时机，当数组中的元素个数超过数组长度乘以负载因子时，就会触发扩容操作。
• 一个链表或者红黑树，用来解决哈希冲突，即当多个键的哈希值相同或者映射到同一个数组下标时，就会把这些键值对连接起来，形成一个链表或者红黑树。链表在元素个数达到 8 时会转换为红黑树，以提高查找效率

# 10. HashMap 的 key 存储在哪里？和 value 存储在一起吗？那么 value 存储在哪里？说具体点？（湖 ** 利软件、天 * 伟业）

HashMap 的key 和 value 都存储在 Node 对象中，其中 Node 是 HashMap 的内部类，实现了 Map.Entry 接口。Node 对象是一个链表节点或者红黑树节点，它有一个 next 属性指向下一个 Node 对象。

HashMap 的底层结构是一个动态数组，数组的每个元素是一个 Node 对象，当多个 Node 对象的 key 的哈希值相同或者映射到同一个数组下标时，就会形成一个链表或者红黑树，通过 Node 对象的 next 属性连接起来。

所以，可以说 HashMap 的 key 和 value 存储在动态数组中的 Node 对象中，Node 对象可以形成链表或者红黑树来解决哈希冲突。

# 11. 自定义类型可以作为 Key 么？（阿 *）

Java 中自定义类型可以作为 HashMap 的 Key，但是需要注意一些问题：

• 自定义类型必须重写 hashCode() 和 equals() 方法，以保证相同属性的对象有相同的哈希值和相等性判断，否则会导致 HashMap 无法正确存取元素。
• 自定义类型的 hashCode () 和 equals () 方法应该遵循以下原则：
  • 如果两个对象相等，则两个对象的 hashCode () 必须相等；
  • 如果两个对象不相等，则两个对象的 hashCode () 尽量不要相等，以减少哈希冲突的可能性；
  • equals () 方法应该满足自反性、对称性、传递性、一致性，即对于任意非空对象 x、y 和 z，有：
    • x.equals (x) 为 true；
    • x.equals (y) 为 true 当且仅当 y.equals (x) 为 true；
    • 如果 x.equals (y) 为 true 且 y.equals (z) 为 true，则 x.equals (z) 也为 true；
    • 多次调用 x.equals (y) 的结果不会改变，除非 x 或 y 的属性发生变化。
• 自定义类型的属性应该是不可变的，或者至少在作为 HashMap 的 Key 期间不要改变，否则会导致哈希值和相等性判断发生变化，从而导致 HashMap 无法正确存取元素。

# Collections

# 1. 集合类的工具类是谁？用过工具类哪些方法？（顺 *）

Collections 是一个集合工具类，它提供了一系列静态方法，用于对集合类（Collection、List、Set、Map 等）进行操作，例如排序、查找、复制、同步等。

Collections 类的常用方法有：

• sort(List list)：按照自然顺序对 list 进行升序排序，list 中的元素必须实现 Comparable 接口
• sort(List list, Comparator c)：按照定制的顺序对 list 进行排序，c 是一个比较器，用来控制排序逻辑
• reverse(List list)：反转 list 中的元素顺序
• shuffle(List list)：随机打乱 list 中的元素顺序
• swap(List list, int i, int j)：交换 list 中 i 和 j 位置的元素
• fill(List list, Object obj)：用 obj 替换 list 中的所有元素
• copy(List dest, List src)：将 src 中的所有元素复制到 dest 中，dest 必须至少和 src 一样长
• max(Collection coll)：根据自然顺序返回 coll 中的最大元素，coll 中的元素必须实现 Comparable 接口
• max(Collection coll, Comparator c)：根据定制的顺序返回 coll 中的最大元素，c 是一个比较器，用来控制比较逻辑
• min(Collection coll)：根据自然顺序返回 coll 中的最小元素，coll 中的元素必须实现 Comparable 接口
• min(Collection coll, Comparator c)：根据定制的顺序返回 coll 中的最小元素，c 是一个比较器，用来控制比较逻辑
• frequency(Collection c, Object o)：返回 o 在 c 中出现的次数
• indexOfSubList(List source, List target)：返回 target 在 source 中第一次出现的索引，如果不存在则返回 - 1
• lastIndexOfSubList(List source, List target)：返回 target 在 source 中最后一次出现的索引，如果不存在则返回 - 1
• replaceAll(List list, Object oldVal, Object newVal)：用 newVal 替换 list 中所有等于 oldVal 的元素
• synchronizedCollection(Collection c)：返回一个线程安全的Collection，它包装了 c
• synchronizedList(List list)：返回一个线程安全的 List，它包装了 list
• synchronizedSet(Set s)：返回一个线程安全的 Set，它包装了 s
• synchronizedMap(Map m)：返回一个线程安全的 Map，它包装了 m

# 2. Collection 和 Collections 的区别？（平 * 金服、* 软）

Collection 是一个集合接口，定义了一些操作集合的方法，有子接口 List 和 Set。

Collections 是一个集合工具类，提供了一系列静态方法去操作 Collection、List、Set、Map 等集合框架。

# 3. ArrayList 如何实现排序？（阿 *）

ArrayList 是一个实现了 List 接口的动态数组，它可以存储任意类型的对象，也可以对其中的元素进行排序。有以下几种方法可以对 ArrayList 进行排序：

• 使用 Collections.sort(List list) 方法，它会按照元素的自然顺序（升序）对 list 进行排序，list 中的元素必须实现 Comparable 接口，或者是基本类型的包装类。
• 使用 Collections.sort(List list, Comparator c) 方法，它会按照定制的顺序（由 c 指定）对 list 进行排序，c 是一个比较器，用来控制排序逻辑。
• 使用 List.sort(Comparator c) 方法，它会按照定制的顺序（由 c 指定）对 list 进行排序，c 是一个比较器，用来控制排序逻辑。这个方法是在 Java 8 中引入的，默认调用 Arrays.sort(Object[] a, Comparator c) 方法。
• 使用 Arrays.sort(Object[] a) 方法，它会按照元素的自然顺序（升序）对数组 a 进行排序，a 中的元素必须实现 Comparable 接口，或者是基本类型的包装类。这个方法需要调用 toArray () 先将 ArrayList 转换为数组。
• 使用 Arrays.sort(Object[] a, Comparator c) 方法，它会按照定制的顺序（由 c 指定）对数组 a 进行排序，c 是一个比较器，用来控制排序逻辑。这个方法需要调用 toArray () 先将 ArrayList 转换为数组。

下面给出一些示例代码：

@Test

public void test1() {

    // 创建一个 ArrayList 存储整数

    List<Integer> list = new ArrayList<>();

    list.add(5);

    list.add(3);

    list.add(7);

    list.add(1);

    // 方式一：使用 Collections.sort (List list) 方法按照自然顺序（升序）排序

    Collections.sort(list);

    System.out.println(list); // 输出 [1, 3, 5, 7]

    // 方式二：使用 Collections.sort (List list, Comparator c) 方法按照定制的顺序（降序）排序

    Collections.sort(list, new Comparator<Integer>() {

        @Override

        public int compare(Integer o1, Integer o2) {

            return o2 - o1; // 降序

        }

    });

    System.out.println(list); // 输出 [7, 5, 3, 1]

    // 方式三：使用 List.sort (Comparator c) 方法按照定制的顺序（降序）排序

    list.sort(new Comparator<Integer>() {

        @Override

        public int compare(Integer o1, Integer o2) {

            return o2 - o1; // 降序

        }

    });

    System.out.println(list); // 输出 [7, 5, 3, 1]

    // 方式四：使用 Arrays.sort (Object [] a) 方法按照自然顺序（升序）排序

    Integer[] array1 = list.toArray(new Integer[list.size()]); // 将 ArrayList 转换为数组

    Arrays.sort(array1);

    System.out.println(Arrays.toString(array1)); // 输出 [1, 3, 5, 7]

    // 方式五：使用 Arrays.sort (Object [] a, Comparator c) 方法按照定制的顺序（降序）排序

    Integer[] array2 = list.toArray(new Integer[list.size()]); // 将 ArrayList 转换为数组

    Arrays.sort(array2, new Comparator<Integer>() {

        @Override

        public int compare(Integer o1, Integer o2) {

            return o2 - o1; // 降序

        }

    });

    System.out.println(Arrays.toString(array2)); // 输出 [7, 5, 3, 1]

}

# 4. HashMap 是否线程安全，怎样解决 HashMap 的线程不安全（中 * 卫星）

类似问题：
> 怎么实现HashMap线程安全？（*团、*东、顺*）

HashMap 不是线程安全的。如果您希望在多线程环境中使用线程安全的 HashMap，可以使用以下方法之一：

1. 使用Hashtable，它通过对整个表上锁来实现线程安全，但效率较低。
2. 使用 Collections.synchronizedMap(Map m) 包装 HashMap。这样可以返回一个由指定映射支持的同步（线程安全）映射。
3. 使用ConcurrentHashMap，它是 Java 5 之后引入的一个线程安全的 HashMap。它将哈希表分为 16 个桶（默认值），常用操作（如 get、put、remove）只锁定当前需要用到的桶。