# 第 14 章：随堂复习与企业真题（数据结构与集合源码）

# 一、随堂复习

# 1. 数据结构

• 数据结构的研究对象：

  • ① 数据间的 逻辑关系 （集合关系、一对一、一对多、多对多）
  • ② 数据的 存储结构 （或物理结构）
    • 角度一：顺序结构、链式结构、索引结构、哈希结构
    • 角度二： 线性表 （一维数组、链表、栈、队列）、 树 （二叉树、B + 树）、 图 （多对多）、 哈希表 （HashMap、HashSet)
  • ③ 相关运算

• 树（了解）

• 相关数据结构的核心 Node的设计 （单向链表、双向链表、二叉树、栈、队列）（理解）

# 2. List 接口下的实现类的源码剖析

【面试题】ArrayList、Vector、LinkedList 的三者的对比？

• 层次 1：

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

• 层次 2：查看相关 api 的源码（见笔记，略）

# 3. Map 接口下的实现类的源码剖析

• （掌握）HashMap 的底层源码的剖析
• （熟悉）LinkedHashMap 的底层源码的剖析
• （了解）HashSet、LinkedHashSet 的底层源码的剖析

# 二、企业真题

# 2.1 数据结构相关

# 1. 链表和数组有什么区别？（腾 *）

# 2. 栈是如何运行的？(西 * 信息技术)

栈特点是 先进后出（FILO） ，数据只能在 栈顶 进行压入（push）和弹出（pop）操作。

栈是种抽象数据结构 ADT (abstract data type)，可以使用 数组 、 链表 实现栈结构。

在 计算机系统中 ，栈是一个具有以上属性的 动态内存区域 ，程序可以将数据压入栈中，也可以将数据从栈中弹出，压栈操作时栈增大，弹出操作是栈减小

# 2.2 List 集合源码相关

# 1. ArrayList 的默认大小是多少，以及扩容机制（顺 *、凡 * 科技）

类似问题：
> 说说ArrayList的扩容机制吧(国*电网)
> 讲一下ArrayList的扩容机制（*实在）
> ArrayList的扩容机制，为什么是10，为什么是1.5倍（*软国际）

Java 中的 ArrayList 类实例化时如果不指定长度，底层数组初始化为 {} ，只有在 首次添加元素时 才会创建默认容量为 10 的数组。当元素数量超过 ArrayList 的容量时，ArrayList 会自动扩容到原来的 1.5倍 。ArrayList 的扩容机制如下：

1. 当添加新元素时，如果当前容量不足以容纳新元素，则会调用 grow() 方法进行扩容。
2. grow () 方法会 计算新容量newCapacity ，其中 newCapacity = oldCapacity + (oldCapacity>> 1)，也就是原有容量的 1.5 倍。
3. 如果 newCapacity 仍然小于新添加元素后的数量，那么 newCapacity 就会被设置为新添加元素后的数量。
4. 然后，ArrayList 会调用 copyOf(T[] original, int newLength) 创建一个新的数组，并将原有元素拷贝到新数组中。
5. 最后，新元素会被添加到新数组的尾部。

需要注意的是，由于扩容会涉及到数组的拷贝操作，因此在实际开发中，尽量避免频繁对 ArrayList 进行扩容，以提高程序的性能。为了避免频繁扩容，可以在创建 ArrayList 对象时，指定一个足够大的初始容量，以便能够容纳预期数量的元素。

# 2. ArrayList 的底层是怎么实现的？（腾 *）

类似问题：
集合类的ArrayList底层（安全不安全，扩容，初始大小，添加删除查询是怎么操作的，底层是什么组成的）
（湖**利软件、汇*云通、猎*、苏州***动、上海*进天下、北京博*软件、*科软、大连*点科技、中*亿达、德*物流、天*伟业、猫*娱乐）

ArrayList 的底层实现是基于 Object[]数组 的。我们可以在集合中存储任意类型的数据，但是它是 线程不安全 的。由于它底层是基于数组实现的，所以它非常适合用于对元素进行查找， 查找效率非常高 。

当我们实例化一个 ArrayList 时，无参数构造函数默认将数组初始化为 {} ，只有在首次添加元素时为数组初始化长度为 10 。如果增加的元素个数超过了 10 个，那么 ArrayList 底层会新生成一个数组，长度为原数组的 1.5倍 ，然后将原数组的内容 复制 到新数组当中，并且后续增加的内容都会 追加 到新数组。

开发建议： ArrayList(int capacity){} 创建指定长度的数组：开发中，如果能大体确认数组长度，推荐使用这种带参构造器，因为 避免了扩容、复制数组带来的时空消耗 。

# 3. 在 ArrayList 中 remove 后面几个元素该怎么做？（惠 *、中 * 亿达）

前移。

# 4. ArrayList1.7 和 1.8 的区别（拓 * 思）

JDK 1.8 和 1.7 中 ArrayList 最明显的区别就是底层数组的初始化方式。

在 JDK1.8 中，如果不指定长度，使用 无参构造方法 ArrayList list = new ArrayList () 创建 List 集合时，底层的 Object [] elementData 初始化为 {}（空的数组） ，并没有直接创建长度为 10 的数组。而在第一次调用 add() 方法时，底层才创建了长度为 10 的数组，并将本次要添加的元素添加进去。这样做可节省内存消耗，因为在添加元素时，数组名将指针指向了新的数组，且老数组 {} 是一个空数组，这样有利于 System.gc ()，并不会一直占据内存。

相比之下，在 JDK1.7 中，使用 无参构造方法 创建 List 集合时，底层直接创建了长度是 10 的 Object [] 数组 elementData。后续的添加和扩容操作与 JDK1.8 无异。

# 5. 数组和 ArrayList 的区别（阿 *、* 科软）

ArrayList 看做是对数组的常见操作的封装。

# 6. 什么是线程安全的 List？(平 * 金服)

线程安全的 List 是指可以在多线程环境下安全使用的 List。这意味着，当多个线程同时访问和修改同一个 List 时，它能够保证 数据的一致性 和正确性。

Java 中提供了几种线程安全的 List 实现，包括 Vector 和 CopyOnWriteArrayList 。此外，我们还可以使用 Collections.synchronizedList() 方法来将任意一个 List 包装成线程安全的 List。

需要注意的是，虽然线程安全的 List 可以在多线程环境下安全使用，但它们通常比非线程安全的 List（如 ArrayList） 性能低 一些。因此，在选择使用哪种 List 时，应该根据实际情况进行权衡。

# 2.3 HashMap 集合源码相关

# 1. 说说 HahMap 底层实现 (新 * 股份、顺 *、猫 * 娱乐)

类似问题：
> HashMap的实现讲一下？（腾*，上海**网络）
> 说说HashMap的底层执行原理？（滴*，纬*软件，上海*想，*昂，*蝶**云，宇*科技，*东数科，猎*网）
> 详细说一下 HashMap 的 put 过程（*度）
> Java中的HashMap的工作原理是什么？（北京中**译咨询）
> 集合类的HashMap底层（安全不安全，扩容，初始大小，添加删除查询是怎么操作的，底层是什么组成的）（湖**利软件）
> HashMap 的存储过程（爱*信、杭州*智）
> Hashmap底层实现及构造（汇**通、猎*、苏州博*讯动、上海*进天下、北京博*软件、*科软、大连*点科技、中*亿达、德*物流、天*伟业、猫*娱乐）
> HashMap的实现原理（腾*、阿*）
> HaspMap底层讲一讲（*米）
> 说一下HashMap的实现，扩容机制？（*节）
> 讲一下 HashMap 中 put 方法过程？（阿*）

HashMap 的底层实现原理

HashMap 是 Java 中一种常用的数据结构，它实现了 Map 接口，能够以 键值对 的形式存储数据。它的底层实现是基于 哈希表 的，具体来说，它是通过 数组+单向链表+红黑树 的形式来实现的。

HashMap 的 put (key,value) 过程

1. 计算 key 的哈希值，并将其映射到数组下标

   调用 hashCode() 和 hash() 计算 key 的哈希值 hash。

   并根据 下式 计算该键值对被分配到数组中的索引位置 index，

   index = (hash & (capacity - 1))

   其中 hash 是键的哈希值，capacity 是数组的长度，& 运算符是按位与运算，运算结果的取值范围是 [0,capacity-1]，刚好对应数组的各个下标。

   下标位置称为 桶（bucket） 或 槽（slot） 。

2. 检查该 bucket 是否为空

   如果空，就直接将键值对添加到该 bucket 上，然后返回 null。

   添加情况 1

   如果该 bucket 不为空，执行下一步。

3. 处理哈希冲突，采用链表或红黑树的方式将多个键值对存储在同一个槽中

   如果该槽中存在一个键值对 (k,v)， 其键k的hash与当前键key的hash相同 ，并且， key.equals(k)返回ture ，则将该键值对的值 v 替换为当前值 value，并返回旧值 v。

   修改 value

   若二者的 hash不相同 ，或者， key.equals(k)返回false ，则将当前键值对先采用 单向链式存储（尾插法） 的方式添加到该 bucket 链表中，（当一个 bucket 中的链表长度超过一定 阈值 （默认为 8）时，Java 会将该链表转化为 红黑树 。这是因为链表的查找时间复杂度是 O (n)，而红黑树的查找时间复杂度是$O(log n)$，所以对于较长的链表，使用红黑树可以提高查询效率。）

   添加情况 2、3

4. 扩容

   当 HashMap 中的元素数量达到一定 阈值 （即负载因子与容量的乘积）时会触发扩容操作，步骤如下：

   • 创建一个 2倍长度的新数组
   • 将原数组中的元素 重新计算哈希值 ，并 重新分配 到新数组中，会导致元素在新数组中的 位置可能发生变化 。
   • 释放原数组的空间 ，将新数组设置为当前数组。

   注意：

   HashMap 中 负载因子默认是0.75 ，这意味着当 HashMap 中的元素数量达到数组长度的 75% 时，就会触发扩容操作。每次扩容时，它都会将数组的长度 增加一倍 。

   由于扩容操作需要重新计算所有元素的哈希值，并将它们添加到新数组中，这个过程需要大量的时间和内存。在创建 HashMap 时，如果我们能够预估元素数量，可以通过 指定初始容量 来 避免不必要的扩容操作 ，从而提高性能。

5. 返回结果

   如果添加成功，返回 null 。

   如果修改成功，返回该键对应的 旧值 。

# 2. HashMap 初始值 16，临界值 12 是怎么算的（软 ** 力）

底层源码中定义的成员变量 “ 默认初始容量 ”：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4

底层源码中定义的成员变量 “ 默认加载因子 ”：

static final float DEFAULT_LOAD_FACTOR = 0.75f;

临界值 = 数组的长度 * 加载因子

newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 16 * 0.75 = 12

# 3. HashMap 长度为什么是 2 的幂次方？(国 * 时代)

能保证哈希值能够均匀分布在数组中，从而减少哈希冲突

将 key 的哈希值 hash 映射到数组下标 i 的计算如下：

i = (n - 1) & hash

其中 n 就是 HashMap 的长度，当 n 是 2 的幂次方时， n-1的二进制是一个全为1的二进制数 。这样，哈希值与数组长度减 1 的 按位与运算 结果的取值范围就在 [0,table.length-1] 上，对应数组的每个下标。这样可以减少哈希冲突，提高 HashMap 的性能。

# 4. HashMap 怎么计算哈希值和索引？扩容机制？怎么解决 hash 冲突？（* 软国际、中软 * 腾）

类似问题：
> HashMap key的哈希冲突了怎么做（新*股份）
> HashMap的默认大小是多少，以及扩容机制（顺*、凡*科技）
> 讲一下HashMap的扩容机制？（好实*）

计算哈希值、索引

在 HashMap 中，计算哈希值的方式是先调用键对象的 hashCode() 方法得到哈希值，然后再对哈希值进行一些额外的计算 hash() ，以增强哈希值的随机性，通过一些位运算（例如使用异或和移位等）来消除高位的影响，以此来得到最终的哈希值。

计算哈希桶索引时，HashMap 会使用哈希值和哈希桶长度减 1的值进行 按位与运算 ，得到一个哈希桶索引，计算公式如下：

i = (n - 1) & hash

扩容机制

当 HashMap 中的元素数量达到一定 阈值 （即负载因子与容量的乘积）时会触发扩容操作，步骤如下：

• 创建一个 2倍长度的新数组
• 将原数组中的元素 重新计算哈希值 ，并 重新分配 到新数组中，会导致元素在新数组中的 位置可能发生变化 。
• 释放原数组的空间 ，将新数组设置为当前数组。

注意：

HashMap 中 负载因子默认是0.75 ，这意味着当 HashMap 中的元素数量达到数组长度的 75% 时，就会触发扩容操作。每次扩容时，它都会将数组的长度 增加一倍 。

由于扩容操作需要重新计算所有元素的哈希值，并将它们添加到新数组中，这个过程需要大量的时间和内存。在创建 HashMap 时，如果我们能够预估元素数量，可以通过 指定初始容量 来 避免不必要的扩容操作 ，从而提高性能。

处理哈希冲突

哈希冲突是指不同的键，其哈希值映射到同一个数组下标上。HashMap 使用 链表 或 红黑树 来存储哈希桶中的元素，以解决哈希冲突。

• 当添加一个键值对时，如果该键值对的哈希桶位置已经存在一个或多个键值对，那么 HashMap 就需要在这些键值对中查找具有相同键的键值对。

• 在查找过程中，HashMap 会 先比较键的哈希值 ，

  • 如果不同，则说明这个键在哈希桶中不存在，可以将新的键值对添加到链表或红黑树中。

  • 如果哈希值相同，HashMap 会 再比较键是否相等 ，

    • 如果相等，则说明这个键在哈希桶中已经存在，需要用新的值替换旧的值。

    • 如果键不相等，则说明发生了哈希冲突，需要将新的键值对添加到链表或红黑树中。

      如果 链表的长度超过8 ，且 数组长度达到64 时，则会将链表转化为红黑树。这是因为当链表长度较长时，查找键值对的时间复杂度可能会变为$O(N)$，而红黑树的查找时间复杂度是$O(logN)$，因此可以提高 HashMap 的查询性能。

# 5. HashMap 底层是数组 + 链表，有数组很快了，为什么加链表？（润 * 软件）

HashMap 底层使用链表是 为了解决哈希冲突 。

当我们向 HashMap 中添加一个键值对时，它会先计算键的哈希值，然后根据哈希值确定这个键值对在数组中的位置。如果两个不同的键具有相同的哈希值，那么它们会被存储在同一个 bucket 中。这种情况被称为哈希冲突。

为了解决哈希冲突，HashMap 会使用链表、红黑树来存储同一个 bucket 中的多个键值对。每个 bucket 都可以看作是一个链表的头节点或红黑树的根节点。如果遇到哈希冲突，就将新的键值对添加到链表或红黑树的末尾。

但是，由于链表和红黑树本身需要占用额外的空间，因此在 HashMap 的设计中需要进行权衡。通常来说，当哈希桶中的元素数量比较小时，使用链表就足够了，而当元素数量比较大时，使用红黑树可以更好地平衡时间和空间的开销。为了提高 HashMap 的性能， JDK8 开始引入了一种基于 “ 链表和红黑树的自适应存储方式 ”，也就是说，

• 当链表中的元素数量超过 8 个，且数组长度达到 64 时，会将链表转换为红黑树
• 当红黑树中的元素数量小于 6 个时，会将红黑树转换为链表

# 6. HashMap 为什么长度达到一定的长度要转化为红黑树（* 度）

类似问题：
> HashMap为什么用红黑树（*软国际）

• 因为 红黑树的增删改查操作的时间复杂度为O(logn) ，比单向链表的 O (n) 效率高。
• 可以 避免出现极长的单链表 ，导致空间浪费，提高了空间利用率

# 7. HashMap 什么时候扩充为红黑树，什么时候又返回到链表？（汉 *）

类似问题：
> HashMap什么时候转换为红黑树（杭州*智公司）
> 当HashMap中相同hashcode值的数据超过多少时会转变成红黑树？（百*云创）
> 什么时候是数据+链表，什么时候是红黑树（*软国际）

链表 -> 红黑树：当同一个 bucket 中的 链表元素数量超过8 ，且 数组长度达到64 时，该 bucket 的链表需要转换为红黑树，这是为了提高增删改查的性能。

红黑树 -> 链表：当同一个 bucket 中的 红黑树元素数量减少到6 时，那么该 bucket 的红黑树转换回链表，这是为了节省内存空间。

# 8. 在 JDK1.8 中，HashMap 的数据结构与 1.7 相比有什么变化，这些变化的好处在哪里？（海 * 科）

数据结构的变化

• JDK1.8 中的 HashMap 仍然使用数组和链表结构，但是 当链表长度达到一定阈值时，会将链表转换成红黑树 ，好处：

  • 可以提高增删改查的性能，因为红黑树在最坏情况也也能保证$O(logN)$的时间复杂度
  • 可以避免出现极长的单链表，导致空间浪费，提高了空间利用率

• 此外，链表的插入方法从 jdk1.7 的头插法变成了 jdk1.8 的 尾插法 ，好处：

  • 可以避免 JDK1.7 中，并发情况下，扩容，形成环状链表，造成死循环的问题。

其他变化

• jdk1.7 中的 Entry 内部类，在 jdk1.8 中改名为 Node
• HashMap 调用无参构造器进行实例化时，在 jdk1.7 中会将数组的容量初始化为 16（饿汉式），在 jdk1.8 中不会初始化数组（懒汉式：只在首次添加元素时，才将数组容量初始化为 16），好处是：
  • 减少内存的浪费：在实例化 HashMap 对象时，如果立即初始化底层数组的大小，可能会导致数组过大或过小，从而浪费内存
• jdk1.7 的扩容条件是 size达到threshold，且table[i]!=null ，jdk1.8 在此基础上增加了一个可以触发扩容操作的条件：遇到哈希冲突时，如果 链表的长度达到8，但数组的长度未超过64 ，也需要扩容。

# 9. HashMap 的 get () 方法的原理？（顺 *）

1. 计算键的哈希值。
2. 使用哈希值来确定键值对在 HashMap 内部数组中的索引位置。
3. 检查该索引位置是否为空。如果为空，则返回 null。
4. 如果该索引位置不为空，则检查该位置的第一个元素是否与给定键匹配。如果匹配，则返回与该键关联的值。
5. 如果第一个元素与给定键不匹配，则遍历该位置处的链表（或红黑树），直到找到与给定键匹配的元素或到达链表末尾。
6. 如果找到匹配项，则返回与该键关联的值；否则，返回 null。

# 10. HashMap 的 remove () 方法的原理？

1. 计算键的哈希值。
2. 使用哈希值来确定键值对在 HashMap 内部数组中的索引位置。
3. 检查该索引位置是否为空。如果为空，则返回 null。
4. 如果该索引位置不为空，则检查该位置的第一个元素是否与给定键匹配。如果匹配，则删除该元素并返回与该键关联的值。
5. 如果第一个元素与给定键不匹配，则遍历该位置处的链表（或红黑树），直到找到与给定键匹配的元素或到达链表末尾。
6. 如果找到匹配项，则删除该元素并返回与该键关联的值；否则，返回 null。

# 2.4 hashCode 和 equals

# 1. hashCode () 和 equals () 的区别？（海 * 供应链管理）

hashCode () 和 equals () 都是 Java 中 Object 类中定义的方法，用于 判断对象是否相等 。它们通常被重写，并且一起使用，用于在集合类（如 HashMap）中确定对象的唯一性。

• hashCode()： 根据对象的属性计算对象的哈希码值 ，是一个整数。哈希码值通常用于快速确定对象在集合中的位置。例如，在 HashMap 中，hashCode () 方法用于确定键值对在内部数组中的索引位置。
  • 如果两个对象的哈希码不相等，则它们肯定不相等
  • 反之，如果两个对象的哈希码相等，则它们不一定相等，还需要调用 equals () 进一步判断
• equals()：
  • 默认情况下，equals () 方法 比较的是两个对象的引用值 ，即它们是否指向同一个内存地址。
  • 但通常被重写，用于 比较两个对象（的属性）是否相等 。
  • 在 HashMap 中，如果两个键具有相同的哈希码值，则会调用 equals () 方法来确定它们是否真正相等。
• 二者之间有一个重要的关系：如果两个对象使用 equals () 方法比较相等，则它们必须具有相同的哈希码值。这意味着，如果重写了 equals () 方法，则也必须重写 hashCode () 方法，以确保它们之间的 一致性 。

# 2. hashCode () 与 equals () 生成算法、方法怎么重写？（阿 * 校招）

省流版

equals()判断中使用的属性，通常也都会参与到hashCode()的计算中 。

重写时可以借助 Objects.equals 和 Objects.hash() 。

详细版

hashCode () 方法用于返回对象的哈希码，重写该方法时需要满足以下 规则 ：

• 如果两个对象使用 equals () 方法比较返回 true，那么它们的 hashCode () 方法返回的值必须相等；
• 如果两个对象使用 equals () 方法比较返回 false，那么它们的 hashCode () 方法返回的值可以相等，也可以不相等；
• 如果两个对象使用 equals () 方法比较返回 false，但是它们的 hashCode () 方法返回的值相等，那么它们被称为哈希冲突，可能会影响散列表等数据结构的性能。

常见的 hashCode () 方法 实现方式 有：

• 对象的属性值的异或和；
• 乘法因子法；
• 幂和积法等。

具体实现可以根据业务需求和对象的属性值来选择。

equals () 方法用于比较两个对象是否相等，重写该方法时需要满足以下 规则 ：

• 自反性：对于任意非空的引用值 x，x.equals (x) 必须返回 true；
• 对称性：对于任意非空的引用值 x 和 y，如果 x.equals (y) 返回 true，那么 y.equals (x) 也必须返回 true；
• 传递性：对于任意非空的引用值 x、y 和 z，如果 x.equals (y) 返回 true，并且 y.equals (z) 返回 true，那么 x.equals (z) 也必须返回 true；
• 一致性：对于任意非空的引用值 x 和 y，在对象的属性值没有改变的情况下，多次调用 x.equals (y) 的结果必须一致；
• 对于任意非空的引用值 x，x.equals (null) 必须返回 false。

常见的 equals () 方法 实现方式 有：

• 比较两个对象的引用值是否相等；
• 比较两个对象的属性值是否相等；
• 比较两个对象的类型是否相等等。

具体实现可以根据业务需求和对象的属性值来选择。

示例代码：

public class Person {

    private String name;

    private int age;

    public Person(String name, int age) {

        this.name = name;

        this.age = age;

    }

    @Override

    public int hashCode() {

        // 方式一：乘法因子法

        // int result = 17;

        // result = 31 * result + name.hashCode();

        // result = 31 * result + age;

        // return result;

        // 方式二：借助 Objects.hash ()

        return Objects.hash(name, age);

    }

    @Override

    public boolean equals(Object obj) {

        // 判断传入的对象是否为当前对象的引用

        if (this == obj) return true;

        // 判断传入的对象是否属于当前类型

        if (obj == null || getClass() != obj.getClass()) return false;

        // 如果传入的对象属于当前类型，则进行强制转换

        Person person = (Person) obj;

        // 方式一：

        // return age == person.age && name.equals(person.name);

        // 方式二：借助 Integer.compare ()、Objects.equals ()

        return Integer.compare(age,person.age) && Objects.equals(name,person.name);

    }

}

# 3. 说一下 equals 和 == 的区别，equals 相等 hash 值一定相等吗？hash 值相等 equals 一定相等吗？（南 * 电网、上海 * 智网络）

首先， == 是一个运算符，而 equals() 是一个方法。

其次，二者都可用于比较两个对象。 == 运算符用于比较两个对象的引用是否相等，即比较的是两个对象的内存地址，与 equals() 方法一样。

但是 equals() 通常被重写，例如 String、Integer、Date 等类对 equals() 方法进行了重写，所以在这些类中， equals() 比较的是两个对象的内容。

如果两个对象通过 equals () 方法比较相等，那么它们的 hash 值也应该相等。但是，如果两个对象的 hash 值相等，并不意味着它们通过 equals () 方法比较也一定相等，这是因为不同的对象可能会产生相同的 hash 值。

# 2.5 Set 集合源码相关

# 1. HashSet 存放数据的方式？（拓 * 软件）

HashSet 实际上是基于 HashMap 实现的，内部有一个 HashMap 类型的成员变量，用于存储元素。当向 HashSet 中添加一个元素时，实际上是将该元素添加到 HashMap的键 中，而该键对应的 值则是一个固定的Object对象 。

由于 HashMap 中的键不能重复，所以当你向 HashSet 中添加重复元素时，实际上是向 HashMap 中添加重复键，这样就能保证 HashSet 中不会有重复元素。此外，由于 HashMap 允许键为 null，所以HashSet 也允许有 null 值。

# 2. Set 是如何实现元素的唯一性？（湖 ** 利软件）

Set 的元素存储在 Map 的键中

因为 Set 实际上是基于 Map 实现的，Set 的元素实际上存储在 Map 的键中，而Map 的键是唯一的，不能重复的，因此 Set 的元素是唯一的。

Map 如何实现键的唯一性？

Map 接口的不同实现类使用不同的数据结构和算法来保证键的唯一性。

• HashMap：依赖于 键的哈希值 和 equals() 。通过哈希值来快速定位 key 所在的位置，再通过比较函数判断 key 是否相等。因此，在使用 Map 时，我们需要保证键对象的 hashCode () 和 equals () 方法都正确实现，才能保证 Map 中的 key 唯一性。

  例如，HashMap 是基于 哈希表 实现的。当你向 HashMap 中添加一个键值对时，它会根据键的哈希码值来确定该键值对在哈希表中的存储位置。如果该位置已经有一个键值对，那么 HashMap 会调用 equals() 方法来检查新添加的键与已有的键是否相等。如果 equals() 方法返回 true ，则新添加的键与已有的键重复，新添加的键值对将替换已有的键值对。如果 equals() 方法返回 false ，则新添加的键与已有的键不重复，新添加的键值对将被添加到哈希表中。

• TreeMap：依赖于 键的自然排序 或者 指定的比较器

  对于 TreeMap，它是基于 红黑树 实现的。当你向 TreeMap 中添加一个键值对时，它会根据键的自然顺序或者指定的比较器来确定该键值对在红黑树中的位置。如果你尝试向 TreeMap 中添加重复键，那么新添加的键值对将不会被添加到红黑树中。

总之，Map 接口的不同实现类通过使用不同的数据结构和算法来保证键的唯一性。

# 3. 用哪两种方式来实现集合的排序（凡 * 科技）

类似问题：
> 集合怎么排序？（北京中**信科技）

在 Java 中，可以使用以下两种方式来实现集合的排序：

1. 自然排序：集合元素实现了 Comparable 接口 ，通过重写 compareTo() 方法 来定义元素之间的排序关系。Java 中的一些内置类型（如 Integer、String 等）已经实现了 Comparable 接口，可以直接使用自然排序。例如，可以使用 Collections.sort () 方法对实现了 Comparable 接口的 List 进行排序。
2. 定制排序：使用一个比较器（Comparator）对象来定义元素之间的排序关系。需要创建一个实现了 Comparator 接口 的比较器对象，并实现了 compare() 方法 来定义元素之间的排序关系。通过在集合类的构造器的排序方法参数中传入比较器对象，可以实现自定义排序。例如，可以使用 Collections.sort () 方法对实现了 Comparator 接口的 List 进行排序。