文章目录

• • 1.说说Java中常用的容器有哪些？
  • 2.详细说说 Arraylist 和 LinkedList的区别?
  • 3.ArrayList实现 RandomAccess接口有何作用？
  • 4.说一说Vector 和 ArrayList 的区别？
  • 5.说说ArrayList 的扩容机制？
  • 6.Array和ArrayList有何区别？
  • 7.遍历一个List有哪些不同的方式？
  • 8.comparable和comparator的区别？
  • 9.Collection和Collections有什么区别？
  • 10.说一下PriorityQueue？
  • 11.说一下HashSet的实现原理？
  • 12.HashMap的实现原理/底层数据结构？
  • 13.HashMap 的长度为什么是 2 的幂次方？
  • 14.说说HashMap的put方法执行流程？
  • 15.说说HashMap的get方法执行流程？
  • 16.说说HashMap的resize方法执行过程？
  • 17.HashMap什么时候会树化？
  • 18.HashMap底层为什么选择红黑树而不用其他树，比如二叉查找树？
  • 19.HashMap扩容（加载）因子为何默认是 0.75f？
  • 20.HashMap怎么计算 key 的 hash 值的？
  • 21.HashMap是怎么解决哈希冲突的？
  • 22.HashMap多线程操作导致死循环问题知道吗?
  • 23.说说LinkedHashMap 的实现原理？
  • 24.说说HashMap 和 HashSet 区别？
  • 25.说下HashMap 和 Hashtable 的区别？
  • 26.说一下HashMap 和 TreeMap 区别？
  • 27.为什么HashMap中String、Integer这样的包装类适合作为Key?
  • 28.说一下Queue 与 Deque 的区别？
  • 29.说说ArrayDeque 与 LinkedList 的区别？
  • 30.说一下 HashSet、LinkedHashSet 和 TreeSet 三者的异同？

1.说说Java中常用的容器有哪些？

容器主要包括Collection和Map两种，Collection 存储着对象的集合，而 Map 存储着键值对(两个对象)的映射表。

如图：

👨‍💻面试官追问：说说集合有哪些类及他们各自的区别和特点？

• Set
  • TreeSet基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。
  • HashSet基于HashMap实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
  • LinkedHashSet是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。内部使用双向链表维护元素的插入顺序。
• List
  • ArrayList基于动态数组实现，支持随机访问。
  • Vector和 ArrayList 类似，但它是线程安全的。
  • LinkedList基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。
• Queue
  • LinkedList可以用它来实现双向队列。
  • PriorityQueue基于堆结构实现，可以用它来实现优先队列。
  • ArrayQueue基于数组实现，可以用它实现双端队列，也可以作为栈。

👨‍💻面试官追问：说说Map有哪些类及他们各自的区别和特点？

• TreeMap基于红黑树实现。
• HashMap1.7基于数组+链表实现，1.8基于数组+链表+红黑树。链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
• HashTable和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。（现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高(1.7 ConcurrentHashMap 引入了分段锁, 1.8 引入了红黑树)。）
• LinkedHashMap继承自 HashMap。使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用(LRU)顺序。

2.详细说说 Arraylist 和 LinkedList的区别?

• ArrayList：底层是基于数组实现的，查找快，增删较慢。LinkedList不支持高效的随机元素访问，而ArrayList支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
• LinkedList：底层是基于链表实现的。确切的说是循环双向链表(JDK1.6之前是双向循环链表、JDK1.7之后取消了循环)，查找慢、增删快。LinkedList链表由一系列表项连接而成，一个表项包含3个部分︰元素内容、前驱表和后驱表。因此内存空间占用比ArrayList 更多。

👨‍💻面试官追问：ArrayList的增删一定比LinkedList要慢吗？

不一定的。

1. 如果增删都是在末尾来操作（每次调用的都是remove()和add()），此时 ArrayList就不需要移动和复制数组来进行操作了。如果数据量有百万级的时，速度是会比 LinkedList 要快的。
2. 如果删除操作的位置是在中间。由于LinkedList的消耗主要是在遍历上，ArrayList的消耗主要是在移动和复制上(底层调用的是arrayCopy()方法，是native方法)。LinkedList 的遍历速度是要慢于ArrayList的复制移动速度的。如果数据量有百万级的时，还是ArrayList要快。

3.ArrayList实现 RandomAccess接口有何作用？

public interface RandomAccess {
}

查看源码我们发现实际上RandomAccess接口中什么都没有定义。

从源码可以看出RandomAccess 接口只是一个标志接口，只要List集合实现这个接口，就能支持快速随机访问。通过查看Collections类中的binarySearch()方法，可以看出，判断List是否实现RandomAccess接口来实行indexedBinarySerach(list, key)或iteratorBinarySerach(list, key)方法。再通过查看这两个方法的源码发现：实现RandomAccess接口的List集合采用一般的 for循环遍历，而未实现这接口则采用迭代器，即ArrayList 一般采用for循环遍历，而 LinkedList 一般采用迭代器遍历

public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

👨‍💻面试官追问：为何LinkedList却没实现这个接口？

ArrayList底层是数组，而LinkedList底层是链表。

数组天然支持随机访问，时间复杂度为 O(1)，所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为 O(n)，所以不支持快速随机访问。

ArrayList实现了RandomAccess接口，就表明了他具有快速随机访问功能。RandomAccess接口只是标识，并不是说ArrayList实现RandomAccess接口才具有快速随机访问功能的！

4.说一说Vector 和 ArrayList 的区别？

他们两个都实现了List接口。底层数据结构都是数组。

不同的是：

1. vector通过remove、add等方法加上synchronized关键字实现线程同步，所以是线程安全的。而ArrayList是线程不安全的
2. 由于vector使用了synchronized进行加锁，所以性能不如ArrayList
3. Vector 扩容时，如果未指定扩容递增值capacityIncrement，或该值不大于 0 时，每次扩容为原来的2倍，否则扩容量为capacityIncrement的值。ArrayList每次扩容为旧容量的1.5倍

5.说说ArrayList 的扩容机制？

1. 当使用add方法的时候首先调用ensureCapacityInternal方法，传入size+1进去，检查是否需要扩容
2. 如果空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就初始化为默认大小10，获取“默认的容量”和要扩容的大小两者之间的最大值
3. 和当前数组长度比较，如果if (minCapacity - elementData.length > 0)执行grow扩容方法
4. 将数组扩容为原来的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);
5. 检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量
6. 再检查新容量newCapacity 是否超出了ArrayList所定义的最大容量，若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE（MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8）
7. ArrayList 中copy数组的核心就是System.arraycopy方法，将original数组的所有数据复制到copy数组中，这是一个本地方法

详细的扩容源码可以参考：https://www.cdsy.xyz/computer/programme/java/230513/cd43568.html

6.Array和ArrayList有何区别？

• Array可以容纳基本类型和对象，而ArrayList只能容纳对象
• Array是指定大小的，ArrayList 的容量是根据需求自动扩展
• ArrayList提供了更多的方法和特性，比如：addAll()，removeAll()，iterator()等等

👨‍💻面试官追问：什么时候更适合使用Array？

1. 如果列表的大小已经指定，大部分情况下是存储和遍历它们可以使用Array
2. 对于基本类型数据，ArrayList 使用自动装箱来减少编码工作量；而当处理固定大小的基本数据类型的时候，这种方式相对比较慢，这时候应该使用Array
3. 如果你要使用多维数组，使用[][]比 List更容易

7.遍历一个List有哪些不同的方式？

先说一下常见的元素在内存中的存储方式，主要有两种:

1. 顺序存储(Random Access)：相邻的数据元素在内存中的位置也是相邻的，可以根据元素的位置读取元素。
2. 链式存储(Sequential Access)：每个数据元素包含它下一个元素的内存地址，在内存中不要求相邻。例如LinkedList。

主要的遍历方式主要有三种：

1. for循环遍历：遍历者自己在集合外部维护一个计数器，依次读取每一个位置的元素
2. Iterator遍历：基于顺序存储集合的Iterator可以直接按位置访问数据。基于链式存储集合的Iterator，需要保存当前遍历的位置，然后根据当前位置来向前或者向后移动指针
3. foreach遍历：也就是增强for循环，foreach内部也是采用了Iterator的方式实现，但使用时不需要显示地声明Iterator

代码如下：

public class TestLinkedList {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        //for循环遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
        //Iterator遍历
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        //foreach遍历
        for (String s : list) {
            System.out.println(s);
        }
    }
}

👨‍💻面试官追问：那么对于以上三种遍历方式应该如何选取呢？

在Java集合框架中，提供了一个RandomAccess接口，该接口没有方法，只是一个标记。通常用来标记List的实现是否支持RandomAccess。所以在遍历时，可以先判断是否支持RandomAccess ( list instanceof RandomAccess)，如果支持可用for循环遍历，否则建议用Iterator或 foreach遍历。

8.comparable和comparator的区别？

• comparable接口出自java.lang包，可以理解为一个内比较器，因为实现了comparable接口的类可以和自己比较，要和其他实现了Comparable接口类比较，可以使用compareTo(objectobj)方法。compareTo方法的返回值是int，有三种情况：
  1. 返回正整数（比较者大于被比较者）
  2. 返回0（比较者等于被比较者）
  3. 返回负整数（比较者小于被比较者）
• comparator接口出自java.util包，它有一个compare(object obj1，object obj2)方法用来排序，返回值同样是int，有三种情况，和compareTo类似。

它们之间的区别：

1. 很多包装类都实现了comparable接口，像Integer、string等。所以直接调用co1lections.sort()直接可以使用。如果对类里面自带的自然排序不满意，而又不能修改其源代码的情况下，使用comparator就比较合适。
2. 此外使用comparator可以避免添加额外的代码与我们的目标类耦合，同时可以定义多种排序规则，这一点是comparable接口没法做到的
3. 从灵活性和扩展性讲Comparator更优，故在面对自定义排序的需求时，可以优先考虑使用comparator接口。

9.Collection和Collections有什么区别？

• Collection：是最基本的集合接口，它提供了对集合对象进行基本操作的通用接口方法。一个Collection代表一组Object，即Collection的元素。它的直接继承接口有List，Set 和Queue。
• Collections：是不属于Java的集合框架的，它是集合类的一个工具类。此类不能被实例化，服务于Java的Collection框架。它包含有关集合操作的静态多态方法，实现对各种集合的搜索、排序、线程安全等操作。

10.说一下PriorityQueue？

PriorityQueue是在 JDK1.5 中被引入的, 其与Queue的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

它有这些特点：

• PriorityQueue利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据。
• PriorityQueue通过堆元素的上浮和下沉，实现了在O(logn)的时间复杂度内插入元素和删除堆顶元素。
• PriorityQueue是非线程安全的，且不支持存储NULL和non-comparable的对象。
• PriorityQueue默认是小顶堆，但可以接收一个Comparator作为构造参数，从而来自定义元素优先级的先后。
• 默认容量是11。当数组比较小（小于64）的时候每次扩容容量翻倍。当数组比较大（大于等于64）的时候每次扩容只增加一半的容量。
• PriorityQueue不是有序的，只有堆顶存储着最小的元素

可以参考PriorityQueue源码：https://www.cdsy.xyz/computer/programme/java/230513/cd43570.html

11.说一下HashSet的实现原理？

HashSet的实现是依赖于HashMap的，HashSet 的值都是存储在HashMap中的。在 HashSet 的构造法中会初始化一个HashMap对象，HashSet 不允许值重复。因此，HashSet的值是作为HashMap的key存储在HashMap 中的，当存储的值已经存在时返回false。

👨‍💻面试官追问：HashSet有哪些特点？

• 无序性（存储元素无序）
• 唯一性（允许使用null）本质上，HashSet的值是作为HashMap的key存储在HashMap 中的，因此保证唯一性
• HashSet没有提供get()方法，同HashMap一样，因为Set内部是无序的，所以只能通过迭代的方式获得

12.HashMap的实现原理/底层数据结构？

• JDK1.7：数组 + 链表
• JDK1.8：数组 + （链表 | 红黑树）

HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

JDK1.8的hash方法：

static final int hash(Object key) {
    int h;
    // key.hashCode()：返回散列值也就是hashcode
    // ^ ：按位异或
    // >>>:无符号右移，忽略符号位，空位都以0补齐
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

JDK1.7的hash方法：

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

从源码可以看出JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

13.HashMap 的长度为什么是 2 的幂次方？

1. 计算索引时效率更高：hash % tab.length，而计算机中直接求余运算效率不如位移运算。所以源码中做了优化，使用hash & (tab.length- 1)来寻找桶位。而实际上hash % length等于hash & ( length - 1)的前提是 length 必须为 2 的 n 次幂
2. 扩容时重新计算索引效率更高：hash & oldCap == 0的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap
3. 当根据 key 的 hash 值寻址计算确定桶位下标 index 时，如果HashMap 的数组长度 tab.length 是 2 的 n 次幂数，那么就可以保证新插入数组中的数据均匀分布，每个桶位都有可能分配到数据，而如果数组长度不是 2 的 n 次幂数，那么就可能导致一些桶位上永远不会被插入到数据，反而有些桶位频繁发生 hash 冲突，导致数组空间浪费，冲hash 突概率增加。

14.说说HashMap的put方法执行流程？

1. 计算key的hash值
2. 如果桶（数组）数量为0，则初始化桶
3. 如果key所在的桶没有元素，则直接插入
4. 如果key所在的桶中的第一个元素的key与待插入的key相同，说明找到了元素，转后续流程（9）处理
5. 如果第一个元素是树节点，则调用树节点的putTreeVal()寻找元素或插入树节点
6. 如果不是以上三种情况，则遍历桶对应的链表查找key是否存在于链表中
7. 如果找到了对应key的元素，则转后续流程（9）处理
8. 如果没找到对应key的元素，则在链表最后插入一个新节点并判断是否需要树化
9. 如果找到了对应key的元素，则判断是否需要替换旧值，并直接返回旧值
10. 如果插入了元素，则数量加1并判断是否需要扩容

详细的HashMap方法执行过程可以参考：【JDK源码】HashMap源码分析（附常见面试题）

15.说说HashMap的get方法执行流程？

1. 计算key的hash值
2. 找到key所在的桶及其第一个元素
3. 如果第一个元素的key等于待查找的key，直接返回
4. 如果第一个元素是树节点就按树的方式来查找
5. 否则就按链表方式查找
6. 如果都没有，返回null

16.说说HashMap的resize方法执行过程？

1. 如果使用是默认构造方法，则第一次插入元素时初始化为默认值，容量为16，扩容门槛为12
2. 如果使用的是非默认构造方法，则第一次插入元素时初始化容量等于扩容门槛，扩容门槛在构造方法里等于传入容量向上最近的2的n次方
3. 如果旧容量大于0，则新容量等于旧容量的2倍，但不超过最大容量2的30次方，新扩容门槛为旧扩容门槛的2倍
4. 创建一个新容量的桶
5. 搬移元素，原链表分化成两个链表，低位链表存储在原来桶的位置，高位链表搬移到原来桶的位置加旧容量的位置

关于这部分建议详细看看源码：【JDK源码】HashMap源码分析（附常见面试题）

17.HashMap什么时候会树化？

必须满足两个条件：

• 链表长度超过树化阈值>8
• 数组容量>=64

当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度，如果数组容量已经 >=64，才会进行树化。

👨‍💻面试官追问：那什么时候树化退化？

• 情况1：在扩容时如果拆分树时，树元素个数<= 6则会退化链表
• 情况2：移除之前，remove 树节点时，若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表

18.HashMap底层为什么选择红黑树而不用其他树，比如二叉查找树？

二叉查找树在特殊情况下也会变成一条线性结构，和原先的长链表存在一样的深度遍历问题，查找性能慢，如图：

使用红黑树主要是为了提升查找数据的速度，红黑树是平衡二叉树的一种，插入新数据（新数据初始是红色结点插入）后会通过左旋，右旋，变色等操作来保持平衡，解决单链表查询深度的问题。

👨‍💻面试官追问：那为什么要将链表中转红黑树的阈值设为8？

之所以以8为树化门槛，是因为经过大量测试，8 这个值是最合适的。理想情况下，使用随机的哈希码，节点分布在 hash 桶中的频率遵循泊松分布，按照泊松分布的公式计算，长度超过 8 的链表出现概率是0.00000006。树化阈值选择 8 就是为了让树化几率足够小

👨‍💻面试官继续追问：那为什么不一开始直接使用红黑树？

• 当链表数据量少的时候，遍历线性链表比遍历红黑树消耗的资源少 (因为少量数据，红黑树本身自选、变色保持平衡也是需要消耗资源的)，所以前期使用线性表。
• 然后TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表

19.HashMap扩容（加载）因子为何默认是 0.75f？

1. 在空间占用与查询时间之间取得较好的权衡
2. 大于这个值，空间节省了，但链表就会比较长影响性能
3. 小于这个值，冲突减少了，但扩容就会更频繁，空间占用也更多

20.HashMap怎么计算 key 的 hash 值的？

我们先看源码：

static final int hash(Object key) {
    int h;
    //key==null直接返回0
    //1、否则调用key的hashCode()方法计算出key的哈希值然后赋值给h,
    //2、h >>> 16。后与h无符号右移16位后的二进制进行按位异或得到最后的hash值,
    //3、这样做是为了使计算出的hash更分散，让高16位可以参与（低16位具有高16位的特征）
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

可以看出：

1. 首先，计算对象的hashCode()
2. 然后将 key 的 hashCode 的高 16 位和 hashCode 低 16 位 进行异或（XOR）运算，最终得到新的 hash 值。二次 hash() 是为了综合高位数据，让哈希分布更为均匀

关于第二点，这里举个例子就知道了：

我们知道，HashMap 新插入的数据需要经过寻址算法index = hash & (tab.length - 1)来确定桶位下标。tab.length就是数组长度，我们这里设其为 n。

如果当 n 即数组长度很小，假设是 n = 16 的话，那么 n - 1 是 15 ，其二进制数为 1111 ，这样的值和 hashCode 直接做按位与操作，实际上只使用了哈希值的后 4 位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题

我们来看一个分析图：

由上图，可以知道如果只使用 key.hashCode()方法计算得到的 hash 值，那么当 hash 值高位变化较大，而低位变化较小时，通过寻址算法 hash & (tab.length - 1) 得到的桶位下标 index 就更容易出现 hash 冲突了！

21.HashMap是怎么解决哈希冲突的？

哈希冲突：hashMap在存储元素时会先计算key的hash值来确定存储位置，因为key的hash值计算最后有个对数组长度取余的操作，所以即使不同的key也可能计算出相同的hash值，这样就引起了hash冲突。hashMap的底层结构中的链表/红黑树就是用来解决这个问题的。

HashMap中的哈希冲突解决方式可以主要从三方面考虑（以JDK1.8为背景)

1. 拉链法
   HasMap中的数据结构为数组+链表/红黑树，当不同的key计算出的hash值相同时，就用链表的形式将Node结点（冲突的key及key对应的value)挂在数组后面。
2. hash函数
   key的hash值经过两次扰动， key的hashcode值与key的hashcode值的右移16位进行异或，然后对数组的长度取余（实际为了提高性能用的是位运算，但目的和取余一样)，这样做可以让hashcode取值出的高位也参与运算，进一步降低hash冲突的概率，使得数据分布更平均。
3. 红黑树
   在拉链法中，如果hash冲突特别严重，则会导致数组上挂的链表长度过长，性能变差，因此在链表长度大于8时，将链表转化为红黑树，可以提高遍历链表的速度。

22.HashMap多线程操作导致死循环问题知道吗?

在jdk1.7之前，主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。

这部分建议详细参考：hashmap扩容时死循环问题

23.说说LinkedHashMap 的实现原理？

• LinkedHashMap也是基于HashMap实现的，不同的是它定义了一个Entry header，这个header不是放在Table里，它是额外独立出来的。LinkedHashMap通过继承hashMap 中的Entry，并添加两个属性Entrybefore，after和 header结合起来组成一个双向链表，来实现按插入顺序或访问顺序排序。
• LinkedHashMap定义了排序模式accessOrder，该属性为boolean型变量，对于访问顺序，为true，对于插入顺序，则为false。一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。

24.说说HashMap 和 HashSet 区别？

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

HashMap	HashSet
实现了Map接口	实现了set接口
存储键值对	存储对象
key 唯一，value不唯一	存储对象唯一
HashMap使用键(Key )计算Hashcode	HashSet 使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以equals()方法用来判断对象的相等性
速度相对较快	速度相对较慢

25.说下HashMap 和 Hashtable 的区别？

1. 线程是否安全：HashMap是非线程安全的，Hashtable是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized修饰。（如果你要保证线程安全的话就使用ConcurrentHashMap吧！）
2. **效率：**因为Hashtable加了synchronized锁。所以HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它
3. 对 Null key 和 Null value 的支持：HashMap可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable不允许有 null 键和 null 值，否则会抛出NullPointerException。
4. 初始容量大小和每次扩充容量大小的不同 ：
   ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。
   ② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而HashMap会将其扩充为 2 的幂次方大小。也就是说HashMap总是使用 2 的幂作为哈希表的大小。
5. 底层数据结构：JDK1.8 以后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

26.说一下HashMap 和 TreeMap 区别？

TreeMap和HashMap都继承自AbstractMap，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap接口。

• 实现NavigableMap接口让TreeMap有了对集合内元素的搜索的能力。
• 实现SortedMap接口让TreeMap有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。

示例代码如下：

/**
 * @author xppll
 * @date 2022/1/1 21:35
 */
public class Person {
    private Integer age;

    public Person(Integer age) {
        this.age = age;
    }

    public Integer getAge() {
        return age;
    }

    public static void main(String[] args) {
        TreeMap<Person, String> treeMap = new TreeMap<>((o1, o2) -> {
            return Integer.compare(o1.getAge() - o2.getAge(), 0);
        });
        treeMap.put(new Person(2), "person1");
        treeMap.put(new Person(42), "person2");
        treeMap.put(new Person(22), "person3");
        treeMap.put(new Person(10), "person4");
        treeMap.forEach((key, value) -> System.out.println(value));
    }
}
//输出：
person1
person4
person3
person2

可以看出，TreeMap中的元素已经是按照Person的 age 字段的升序来排列了。

综上，相比于HashMap来说TreeMap主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力

27.为什么HashMap中String、Integer这样的包装类适合作为Key?

1. 这些包装类都是final修饰，是不可变性的，保证了key的不可更改性，不会出现放入和获取时哈希值不同的情况。
2. 它们内部已经重写过hashcode()，equal()等方法。

👨‍💻面试官追问：如果使用Object作为HashMap的Key，应该怎么办呢？

1. 重写hashcode()方法，因为需要计算hash值确定存储位置
2. 重写equals()方法，因为需要保证key的唯一性

👨‍💻面试官继续追问：能否使用任何类作为Map 的key？

可以，但要注意以下两点:

1. 如果类重写了equals()方法，也应该重写hashcode()方法。
2. 最好定义key类是不可变的，这样key对应的hashcode()值可以被缓存起来，性能更好，这也是为什么string特别适合作为HashMap 的key 。

28.说一下Queue 与 Deque 的区别？

Queue是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循先进先出（FIFO）规则。Queue 扩展了Collection的接口，根据因为容量问题而导致操作失败后处理方式的不同可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

Queue 接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

Deque是双端队列，在队列的两端均可以插入或删除元素。Deque 扩展了Queue的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

Deque 接口	抛出异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查询队首元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

除此之外。Deque还提供有push()和pop()等其他方法，可用于模拟栈。

29.说说ArrayDeque 与 LinkedList 的区别？

ArrayDeque和LinkedList都实现了Deque接口，两者都具有队列的功能，也都可以实现栈。连着区别：

• ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
• ArrayDeque 不支持存储NULL数据，但 LinkedList 支持。
• ArrayDeque 是在JDK1.6才被引入的，而LinkedList 早在JDK1.2时就已经存在。
• ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用ArrayDeque来实现队列要比LinkedList更好。

ArrayDeque 源码可以参考：【JDK源码】ArrayDeque源码分析

LinkedList 源码可以参考：【JDK源码】LinkedList源码分析

30.说一下 HashSet、LinkedHashSet 和 TreeSet 三者的异同？

HashSet、LinkedHashSet和TreeSet都是Set接口的实现类，都能保证元素唯一，并且都不是线程安全的。他们的不同点：

• HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同：
  1. HashSet的底层数据结构是哈希表（基于HashMap实现）
  2. LinkedHashSet的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO
  3. TreeSet底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序
• 底层数据结构不同又导致这三者的应用场景不同：
  1. HashSet用于不需要保证元素插入和取出顺序的场景
  2. LinkedHashSet用于保证元素的插入和取出顺序满足 FIFO 的场景
  3. TreeSet用于支持对元素自定义排序规则的场景