欢迎关注专栏，文章内容会持续更新。带🔥标记的内容是高频内容。

集合概述

🔥什么是集合？集合有哪些？

Java 集合（容器）主要由两大接口派生而来：一个是 Collection 接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。

说说 List、Set、Map 三者的区别？

• List：存储的元素是有序的、可重复的。
• Set：存储的元素是无序的、不可重复的；Set 就是所有 key 都指向同一个 value 的 Map，这个 value 是一个 Object 对象。
• Map：使用键值对（key-value）存储，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

🔥List、Set、Map 底层数据结构是什么？

List：

• ArrayList： Object[] 数组。
• Vector：Object[] 数组。
• LinkedList： 双向链表（JDK 1.6 之前为循环链表，JDK 1.7 取消了循环）。

Set：

• HashSet(无序，唯一)：基于 HashMap 实现，底层采用 HashMap 来保存元素。
• LinkedHashSet：LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。
• TreeSet(有序，唯一)：红黑树（自平衡的排序二叉树）。

Map：

• HashMap：
  • JDK 1.8 之前 HashMap 是由数组 + 链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。
  • JDK 1.8 以后是由数组 + 链表 + 红黑树组成的，在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。执行转换之前如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树。
• LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组 + 链表 + 红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
• Hashtable： 数组 + 链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的。它是 HashMap 的古老实现类，与 HashMap 不同，它是线程安全的。
• TreeMap： 红黑树（自平衡的排序二叉树）。

如何选用集合?

主要根据集合的特点来选用，比如我们需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap，不需要排序时就选择 HashMap，需要保证线程安全就选用 ConcurrentHashMap。

当我们只需要存放元素值时，就选择实现Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用。

为什么要使用集合？

当我们需要保存一组类型相同的数据的时候，我们应该是用一个容器来保存，这个容器就是数组，但是，使用数组存储对象具有一定的弊端。

1. 数组的缺点是一旦声明之后，长度就不可变了；
2. 声明数组时的数据类型也决定了该数组存储的数据的类型；
3. 数组存储的数据是有序的、可重复的。

集合提高了数据存储的灵活性，Java 集合不仅可以用来存储不同类型不同数量的对象，还可以保存具有映射关系的数据。

Collection 子接口之 List

ArrayList 和 Array（数组）的区别？

ArrayList 内部基于动态数组实现，比 Array（静态数组） 使用起来更加灵活：

• ArrayList 会根据实际存储的元素动态地扩容或缩容，而 Array 被创建之后就不能改变它的长度了。
• ArrayList 允许你使用泛型来确保类型安全，Array 则不可以。
• ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）。Array 可以直接存储基本类型数据，也可以存储对象。
• ArrayList 支持插入、删除、遍历等常见操作，并且提供了丰富的 API 操作方法，比如 add()、remove()等。Array 只是一个固定长度的数组，只能按照下标访问其中的元素，不具备动态添加、删除元素的能力。
• ArrayList 创建时不需要指定大小，而Array创建时必须指定大小。

ArrayList 和 Vector 的区别？

• ArrayList 是 List 的主要实现类，底层使用 Object[]存储，适用于频繁的查找工作，线程不安全；
• Vector 是 List 的古老实现类，底层使用Object[] 存储，线程安全。

Vector 和 Stack 的区别？

• Vector 和 Stack 两者都是线程安全的，都是使用 synchronized 关键字进行同步处理
• Stack 继承自 Vector，是一个后进先出的栈，而 Vector 是一个列表

随着 Java 并发编程的发展，Vector 和 Stack 已经被淘汰，推荐使用并发集合类（例如 ConcurrentHashMap、CopyOnWriteArrayList 等）或者手动实现线程安全的方法来提供安全的多线程操作支持

🔥ArrayList 与 LinkedList 区别？

• 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，不保证线程安全；
• 底层数据结构： ArrayList 底层使用的是 Object 数组；LinkedList 底层使用的是双向链表（JDK1.6 之前为双向循环链表，JDK1.7 取消了循环）
• 插入和删除是否受元素位置的影响：
  • ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位/向前移一位的操作。
  • LinkedList 采用链表存储，所以，如果是在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst() 、 removeLast()），时间复杂度为 O(1)，如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)、remove(Object o)）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入。
• 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，查询时间复杂度为 O(n)；而 ArrayList（实现了RandomAccess 接口） 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)，查询时间复杂度为 O(1)。
• 内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放数据以及直接后继和直接前驱的位置）。

介绍一下 ArrayList

1. ArrayList 的特点：
   1. 实现了 List 接口，存储有序的、可以重复的数据，可以存储任何类型的对象，包括 null 值
   2. 底层使用 Object[] 存储
   3. 线程不安全
2. ArrayList 源码解析：

   1. jdk7 版本：

      // 如下代码的执行：底层会初始化数组，数组的长度为10。
      // Object[] elementData = new Object[10];
      ArrayList<String> list = new ArrayList<>();
      
      list.add("AA"); //elementData[0] = "AA";
      list.add("BB"); //elementData[1] = "BB";
      ...
      
      // 当要添加第11个元素的时候，底层的elementData数组已满，则需要扩容。
      // 默认扩容为原来长度的1.5倍。并将原有数组中的元素复制到新的数组中。
      

   2. jdk8 版本：

      // 如下代码的执行：底层会初始化数组，
      // 即：Object[] elementData = new Object[]{};
      ArrayList<String> list = new ArrayList<>();
      
      list.add("AA"); 
      //首次添加元素时，会初始化数组elementData = new Object[10];elementData[0] = "AA";
      list.add("BB");//elementData[1] = "BB";
      ...
      
      // 当要添加第11个元素的时候，底层的elementData数组已满，则需要扩容。
      // 默认扩容为原来长度的1.5倍。并将原有数组中的元素复制到新的数组中。
      

3. 小结：
   1. jdk1.7 中，ArrayList 类似于饿汉式
   2. jdk1.8 中，ArrayList 类似于懒汉式

🔥ArrayList 是怎么扩容的？

ArrayList 底层是数组 elementData，用于存放插入的数据。jdk8 中，初始大小是0，当有数据插入时，默认大小 DEFAULT_CAPACITY = 10，在创建时也可以指定 initialCapacity 为初始大小。

扩容分为创建数组和复制两个步骤：

1. 当添加元素时，如果底层的 elementData 数组已满就进行扩容，创建一个容量为原来 1.5 倍的新数组
2. 将旧数组内容调用 Arrays.copyof() 复制到新数组中

🔥为什么开辟新的数组而不是在原有数组上扩展？

数组在创建之后长度是不可变的。

🔥为什么数组开辟出来的长度是不可变的？

数组是一种连续的内存结构，创建数组时需要一段连续的内存空间来存储元素。由于内存的分配是在编译时或者运行时确定的，所以数组的长度在创建后就已经固定了。Java 垃圾回收器管理的是一整块内存，如果一个数组的长度可变，那么将难以有效管理其中的空间，从而造成破碎的内存。

介绍一下 LinkedList

1. LinkedList 的特点：

   1. 实现了 List 接口，存储有序的、可以重复的数据
   2. 底层使用双向链表存储
   3. 线程不安全

2. LinkedList 在 jdk8 中的源码解析：

   LinkedList<String> list = new LinkedList<>(); //底层也没做啥
   list.add("AA"); 
   // 将"AA"封装到一个Node对象1中，list对象的属性first、last都指向此Node对象1
   list.add("BB"); 
   // 将"BB"封装到一个Node对象2中，对象1和对象2构成一个双向链表，同时last指向此Node对象2
   ...
   
   // 因为LinkedList使用的是双向链表，不需要考虑扩容问题。
   
   // LinkedList内部声明：
   // private static class Node<E> {
   //     E item;
   //     Node<E> next;
   //     Node<E> prev;
   // }
   

介绍一下 Vector

1. Vector 的特点：

   1. 实现了 List 接口，存储有序的、可以重复的数据
   2. 底层使用 Object[] 数组存储
   3. 线程安全

2. Vector源码解析：(以jdk1.8.0_271为例)

   Vector v = new Vector(); 
   // 底层初始化数组，长度为10. Object[] elementData = new Object[10];
   v.add("AA"); // elementData[0] = "AA";
   v.add("BB"); // elementData[1] = "BB";
   ...
   // 当添加第11个元素时，需要扩容，默认为原来的两倍
   

Collection 子接口之 Set

介绍一下自然排序和定制排序（compareTo 和 compare）

Comparable 和 Comparator 的区别：

• Comparable 接口来自 java.lang 包，它的 compareTo(Object obj) 方法用来排序；
• Comparator 接口来自 java.util 包，它的 compare(Object obj1, Object obj2) 方法用来排序。

自然排序和选择排序的区别（以 TreeSet 为例，默认情况下，TreeSet 采用自然排序）：

• 自然排序：TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系，然后将集合元素按升序（默认情况）排列。
  • 如果试图把一个对象添加到 TreeSet 时，则该对象的类必须实现 Comparable 接口。
  • 实现 Comparable 的类必须实现 compareTo(Object obj) 方法。
• 定制排序：如果元素所属的类没有实现 Comparable 接口，或不希望按照默认情况的方式排列元素或希望按照其它属性大小进行排序，则考虑使用定制排序。定制排序，通过 Comparator 接口来实现。需要重写 compare(T o1,T o2) 方法。
  • 利用 int compare(T o1,T o2) 方法，比较 o1 和 o2 的大小：如果方法返回正整数，则表示 o1 大于 o2；如果返回0，表示相等；返回负整数，表示 o1 小于 o2。
  • 要实现定制排序，需要将实现 Comparator 接口的实例作为形参传递给 TreeSet 的构造器。

比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

• HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。
• HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现，包括数组、单向链表，JDK 8 还使用了红黑树）。LinkedHashSet 的底层数据结构是双向链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
• 底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景。

Map 接口

Set 和 Map 有什么区别？

Set：

1. Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个 Set 集合中，则添加操作失败。
2. Set 就是所有 key 都指向同一个 value 的 Map，这个 value 是 Object 对象。

Map：

1. 用于保存具有映射关系的数据：key-value。
2. Map 中的 key 用 Set来存放，不允许重复，即同一个 Map 对象所对应的类，须重写 hashCode() 和 equals() 方法。
3. key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的 value，不同 key 对应的 value 可以重复。Map 会判断 value 是否相等，因此 value 所在的类要重写 equals() 方法。
4. key 和 value 构成一个 entry。所有的 entry 彼此之间是无序的、不可重复的。
5. 所有的 key 构成 Set，所有的 value 构成 Collection。

🔥介绍一下 HashMap

HashMap 中元素的特点

1. HashMap 中的所有的 key 彼此之间是不可重复的、无序的。所有的 key 构成一个 Set 集合，key 所在的类要重写 hashCode() 和 equals()。
2. HashMap 中的所有的 value 彼此之间是可重复的、无序的。所有的 value 就构成一个 Collection 集合，value所在的类要重写 equals()。
3. HashMap 中的一个 key-value，就构成了一个 entry。
4. HashMap 中的所有的 entry 彼此之间是不可重复的、无序的。所有的 entry 就构成了一个 Set 集合。
5. 线程不安全。

HashMap 源码解析

JDK7 中创建对象和添加数据过程：

// 创建对象的过程中，底层会初始化数组Entry[] table = new Entry[16];
HashMap<String,Integer> map = new HashMap<>();
...
map.put("AA",78); // "AA"和78封装到一个Entry对象中，考虑将此对象添加到table数组中。
...

添加 / 修改的过程：

将 (key1,value1) 添加到当前的map中： 首先，需要调用 key1 所在类的 hashCode() 方法，计算 key1 对应的哈希值1，此哈希值1经过 hash() 之后，得到哈希值2。 哈希值2 再经过 indexFor() 之后，就确定了 (key1,value1) 在数组 table 中的索引位置 i

1. 如果此索引位置 i 的数组上没有元素，则 (key1,value1) 添加成功。 → 情况1
2. 如果此索引位置 i 的数组上有元素 (key2,value2)，则需要继续比较 key1 和 key2 的哈希值2 → 哈希冲突
   1. 如果 key1 的哈希值2 与 key2 的哈希值2不相同，则 (key1,value1) 添加成功。 → 情况2
   2. 如果 key1 的哈希值2与 key2 的哈希值2相同，则需要继续比较 key1 和 key2 的 equals()。要调用 key1 所在类的 equals()，将 key2 作为参数传递进去。
      1. 调用equals()，返回 false：则 (key1,value1) 添加成功。 → 情况3
      2. 调用equals()，返回 true：则认为 key1 和 key2 是相同的。默认情况下，value1 替换原有的 value2。

   说明：

   1. 情况1：将 (key1,value1) 存放到数组的索引 i 的位置；情况2、情况3：(key1,value1) 元素与现有的 (key2,value2) 构成单向链表结构，(key1,value1) 指向 (key2,value2)。
   2. 随着不断地添加元素，当 (size >= threshold) && (null != table[i]) 时，会考虑扩容：当元素的个数达到临界值（数组的长度 * 加载因子），且当前要存放元素的位置不为空时，就考虑扩容。默认的临界值 = 16 * 0.75 = 12。默认扩容为原来的2倍。
   3. 修改元素的 key 不会改变哈希值2，因此插入 (key1,value1) 后修改为 (key2,value1) ，再删除 (key2,value1) 可能不成功。

JDK8 与 JDK7 的不同之处：

1. 在 jdk8 中，当我们创建了 HashMap 实例以后，底层并没有初始化 table 数组。当首次添加 (key,value) 时，进行判断，如果发现 table 尚未初始化，则对数组进行初始化。
2. 在 jdk8 中，HashMap 底层定义了 Node 内部类，替换 jdk7 中的 Entry 内部类。意味着，我们创建的数组是 Node[]。
3. 元素在插入到链表中时，在 jdk7 使用头插法，jdk8 使用尾插法。jdk8 首先通过 hashCode 经过 hash 和 indexFor 方法，通过按位与得到下标 i，对链表从上到下使用 equals 方法进行遍历，如果 key 相等就覆盖掉，如果不相等就添加到尾部。
4. 存储结构：
   1. jdk7：数组 + 单向链表，jdk8：数组 + 单向链表 + 红黑树
   2. 什么时候会使用单向链表变为红黑树？如果数组索引 i 位置上的元素的个数达到 8，并且数组的长度达到 64 时，我们就将此索引 i 位置上的多个元素改为使用红黑树的结构进行存储。
   3. 为什么修改？红黑树进行 put()/get()/remove() 操作的时间复杂度为 O(logn)，比单向链表的时间复杂度O (n) 的好，性能更高。
   4. 什么时候会使用红黑树变为单向链表？当使用红黑树的索引 i 位置上的元素的个数减少到 6 的时候，就会将红黑树结构退化为单向链表。

如何确定插入的下标 i？

确定 i 有以下两种思路：

1. hash值 % table.length，这样我们可以得到一个［0，table.length-1］范围内的值，但是%的运算效率没有&的运算效率高，因此HashMap会选择思路2。

2. hash值& (table.length-1)，因为table.length是2n，那么table.length-1的二进制数就是一个低位全是1高位全是0的数，所以hash值& (table.length-1)的结果一定在［0，table.length-1］范围内

   

HashMap 的重要属性？

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的初始容量 16
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量  1 << 30
static final float DEFAULT_LOAD_FACTOR = 0.75f;  //默认加载因子
static final int TREEIFY_THRESHOLD = 8; //默认树化阈值8，当链表的长度达到这个值后，要考虑树化
static final int UNTREEIFY_THRESHOLD = 6;//默认反树化阈值6，当树中结点的个数达到此阈值后，要考虑变为链表
//当单个的链表的结点个数达到8，并且table的长度达到64，才会树化。
//当单个的链表的结点个数达到8，但是table的长度未达到64，会先扩容
static final int MIN_TREEIFY_CAPACITY = 64; //最小树化容量64
transient Node<K,V>[] table; //数组
transient int size;  //记录有效映射关系的对数，也是Entry对象的个数
int threshold; //阈值，当size达到阈值时，考虑扩容
final float loadFactor; //加载因子，影响扩容的频率

🔥引入红黑树是对插入还是查询性能有优化？

红黑树讲解 - csdn

首先看插入的时间复杂度，jdk7 的链表插入使用的是头插法，时间复杂度是 O(1)，红黑树的插入复杂度是 O(logn)，所以相对 jdk7 来说没有优化；jdk8 的链表插入使用的是尾插法，时间复杂度是 O(n)，所以相对 jdk8 自己的链表来说有优化。

对于查询的话，链表的查询时间复杂度是 O(n)，红黑树的查询复杂度也是 O(logn)，所以对查询有优化。

🔥将 HashMap 的 Key 设置为自定义的类，它的 hashCode 永远返回 1、equals 方法永远返回 false，不断 put 一个同样的 KV 的会怎样

hashCode 为 1 的话，元素经过 hash 和 indexFor 方法得到的下标值是一样的，元素会通过链表的尾插法（1.8）插入到同一个 hash 槽的链表中。

🔥put 同一个 KV 10 次，那现在的数据结构是什么样的？

在数组长度大于等于 64 的情况下，链表长度为 8 之后会转为红黑树。

🔥如果要 get 这个 key 会返回什么结果？

因为 equals 方法永远返回 false，所以 get 的值为 null。

🔥1.7 中 HashMap 产生死循环的原因是什么？

参考：

JDK7的HashMap头插法循环的问题 - bilibili

11张图让你彻底明白jdk1.7 hashmap的死循环是如何产生的

HashMap 通过 resize 方法进行扩容。

单线程的扩容：首先创建一个大小为原来两倍的数组，然后遍历原始的数组，遍历其中的每一个链表。对于一个链表，链表头元素记为 e，下一个元素为 next。计算元素 e 的下标 i 头插法插入到新的数组中，然后将 next 指定为 e，e 的下一个元素记为 next，重复执行到链表尾部。

多线程的扩容：有两个线程都在进行扩容操作，如果它们都执行到记链表头元素为 e 这一步之后，有一个线程被挂起，另一个线程继续执行就会产生死循环。记链表前两个元素为 a 和 b，挂起的线程会将 a 记为 e，b 记为 next。当第一个线程执行完毕之后，由于是头插法，在新数组中 b 的下一个元素指向了 a，也就是 next 的下一个元素指向了 e。此时第二个线程继续扩容，首先将节点 e（也就是 a）插入到新数组中，然后 next（b）被记为 e，e 的下一个元素（a）又被记为 next，由于这里 a 和 b 构成了一个环形引用，重复执行的时候就会产生死循环。

把头插法换成尾插法就解决了这个问题。

介绍一下 LinkedHashMap

1. LinkedHashMap 与 HashMap 的关系：

   1. LinkedHashMap 是 HashMap 的子类。
   2. LinkedHashMap 在 HashMap 使用的数组 + 单向链表 + 红黑树的基础上，又增加了一对双向链表，记录添加的 (key,value) 的先后顺序，便于我们遍历所有的 key-value。
   3. LinkedHashMap 重写了 HashMap 的如下方法：

   Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
       LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
       linkNodeLast(p);
       return p;
   }
   

2. 底层结构：LinkedHashMap 内部定义了一个 Entry：

   static class Entry<K,V> extends HashMap.Node<K,V> {
       Entry<K,V> before, after; //增加的一对双向链表
       Entry(int hash, K key, V value, Node<K,V> next) {
           super(hash, key, value, next);
                   }
   }
   

介绍一下 Properties

1. Properties 类是 Hashtable 的子类，该对象用于处理属性文件；
2. Properties 中 key 和 value 都是字符串类型；
3. 存取数据时，建议使用 setProperty(String key,String value) 方法和 getProperty(String key) 方法。

HashMap 和 Hashtable 的区别

• 线程是否安全： HashMap 是非线程安全的，Hashtable 是 HashMap 的古老实现类，是线程安全的，因为 Hashtable 内部的方法基本都经过 synchronized 修饰（如果要保证线程安全的话就使用 ConcurrentHashMap）
• 效率： 因为线程安全的问题，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 中的 tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小，后面会介绍到为什么是 2 的幂次方。
• 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间。Hashtable 没有这样的机制。

HashMap 和 HashSet 区别

HashSet 底层就是基于 HashMap 实现的。HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject() 是 HashSet 自己不得不实现的之外，其他方法都是直接调用 HashMap 中的方法。

HashMap 和 TreeMap 区别

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

实现 NavigableMap 接口说明 TreeMap 有了对集合内元素的搜索的能力；实现 SortedMap 接口说明 TreeMap 有了对集合中的元素根据键排序的能力。除此之外：

1. TreeMap 存储 key-value 对时，会根据 key-value 对进行排序。
2. TreeMap 底层使用红黑树结构存储数据。
3. TreeMap 中 Key 特点：不允许重复、实现排序。
4. TreeMap 两种排序方法：自然排序和定制排序。默认情况下，TreeMap 采用自然排序。

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

1. 如果数组的长度是2^n，那么 table.length-1 的二进制数就是一个低位全是 1 高位全是 0 的数，hash 值& (table.length-1) 的结果除一定在［0，table.length-1］，也使 index 取值更均匀和全面。如果数组长度不是2^n，那么哈希冲突的概率会变得更大。

   

2. 如果数组进行扩容，那么数组长度就会发生变化，存储位置 index=hash&(length-1)也可能会发生变化，重新计算后的index如果与原来的不同，那么就涉及移动Entry对象，这可不是个小工程。但是如果数组长度是2^n，那么扩容后也依然是2^n，扩容后的n-1与原来n-1的二进制只有一位差异，也就是多出了最左位的1，这样在通过 hash&(length-1)时，只要hash对应的最左边的那一个差异位是0，就能保证得到的key在新数组索引index值和在旧数组索引index值一致，大大减少了之前已经散列良好的旧数组的数据位置重新调换个数，所以只需要调换hash对应的最左边的差异位是1的Entry即可。

   

🔥ConcurrentHashMap 线程安全的具体实现方式

JDK 1.8 之前：

首先将数据分为一段一段（这个“段”就是 Segment）的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable {}

一个 ConcurrentHashMap 里包含一个 Segment 数组，Segment 的个数一旦初始化就不能改变。 Segment 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。

Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。也就是说，对同一 Segment 的并发写入会被阻塞，不同 Segment 的写入是可以并发执行的。

JDK 1.8 之后：

JDK 8 重写了 ConcurrentHashMap，取消了 Segment 分段锁，采用 Node + CAS + synchronized 来保证并发安全。数据结构跟 HashMap 1.8 的结构类似，数组 + 链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）。

JDK 8 中，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。

不同点：

• 线程安全实现方式 ：JDK 1.7 采用 Segment 分段锁来保证安全， Segment 是继承自 ReentrantLock。JDK1.8 放弃了 Segment 分段锁的设计，采用 Node + CAS + synchronized 保证线程安全，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点。
• Hash 碰撞解决方法 : JDK 1.7 采用拉链法，JDK1.8 采用拉链法结合红黑树（链表长度超过一定阈值时，将链表转换为红黑树）。
• 并发度 ：JDK 1.7 最大并发度是 Segment 的个数，默认是 16。JDK 1.8 最大并发度是 Node 数组的大小，并发度更大。

🔥HashMap 能并发访问吗？如何保证线程安全？

不能，HashMap 在 put 元素的时候是有并发问题的，可以使用 Hashtable 和 ConcurrentHashSet 实现并发访问的功能，通过锁机制实现并发控制的功能。

Hashtable 是对整个数组加锁，同一时刻只有一个人持有锁去操作，其它人排队等待，效率会很低。

ConcurrentHashSet 是很细粒度的锁，在 1.8 之后，16 个 hash 槽位就有 16 个锁，同一时刻可以有 16 个线程去操作 16 个槽位，提升了效率。

🔥把一些集合中的对象属性转变成 map，有时会出现重复 key 的这种异常，应该怎么处理？

java8 对象转 map 时重复 key Duplicate key xxxx

@Getter
@Setter
@AllArgsConstructor
public class Student{
    private String className;
    private String studentName;

    public static void main(String[] args) {
        List<Student> list = new ArrayList<>();
        list.add(new Student("一年级二班", "小明"));
        list.add(new Student("一年级二班", "小芳"));
        list.add(new Student("一年级二班", "小华"));
        list.add(new Student("一年级三班", "翠花"));
        list.add(new Student("一年级三班", "香兰"));
        // 集合中对象属性转map
        Map<String, String> map = list.stream().collect(Collectors.toMap(Student :: getClassName, Student :: getStudentName)); // Duplicate key xxxx
        System.out.println(map);
     }
}

这里我们是将对象的 className 作为 key，studentName 作为 value，由于 key 值重复就报错。可以使用 toMap 的另外一个重载的方法 Collectors.toMap(keyMapper, valueMapper, mergeFunction)，前两个参数是与之前一样 key 和 value 属性， 第三个参数是当 key 发生重复时处理的合并函数。该合并函数有两个参数，第一个参数是被重复的 key 对应的 value，第二个是新的key 对应的 value，返回的是最终的 value。

可以利用这个函数使用新 value 替换旧 value，或者将 value 的值构建成一个集合。

Map<String, String> map = list.stream().collect(Collectors.toMap(Student :: getClassName, Student :: getStudentName,
        (value1, value2 )->{
            return value2;
        }));

// 输出：{一年级三班=香兰, 一年级二班=小华}

// ---
Map<String, List<String>> map = list.stream().collect(Collectors.toMap(Student :: getClassName,
    // 此时的value 为集合，方便重复时操作
    s ->  {
        List<String> studentNameList = new ArrayList<>();
        studentNameList.add(s.getStudentName());
        return studentNameList;
    },
    // 重复时将现在的值全部加入到之前的值内
    (List<String> value1, List<String> value2) -> {
        value1.addAll(value2);
        return value1;
    }
));

// 输出：{一年级三班=[翠花, 香兰], 一年级二班=[小明, 小芳, 小华]}

参考内容：

1. Java 面试指南 | JavaGuide
2. 《剑指 Java：核心原理与应用实践》

其它参考内容在文章中已有引用