Java集合框架

Java集合框架的接口

一共有15个接口，主要就是包括 Map 和 Collection 两种，Collection 存储对象的集合，Map 存储键值对的映射表

Java集合框架接口

Java集合框架的接口实现

Java集合框架接口的实现类

Java的容器里只能存放对象，对于基本数据类型需要将其包装成对象类型（Integer、Float、Double等）才会放到容器里

常见问题整理

说一说 List、Set、Queue、Map 四者的区别？

答：

List（对付顺序的好帮手）：存储的元素是 有序的、可重复的
Set（注重独一无二的性质）：存储的元素是 不可重复的
Queue（实现排队功能的叫号器）：按照特地的排队规则来确定先后的顺序，存储的元素是 有序的、可重复的
Map（用 key 来搜索的专家）：使用键值对（key-value）存储，类似于 y = f(x)，其中：key是无序的、不可重复的，value是无序的，可重复的，每个键最多映射到一个值上

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

答：

Vector、Hashtable、Stack 都是 线程安全 的
HashMap 则是 非线程安全 的，不过在 JDK1.5 之后随着 java.util.concurrent 并发包的出现，也存在了对应的线程安全类，例如：HashMap 对应的线程安全类就是 ConcurrentHashMap

Collection 和 Collections 有什么区别？

答：

Collection 是一个 集合接口，它提供了对集合对象进行基本操作的通用接口方法，所有集合都是它的子类，比如：List、Set 等
Collections 是一个 包装类，包含了很多静态方法，不能被实例化，就像一个工具类，比如提供排序的的方法：Collections.sort(list)

讲一下HashMap的工作原理？

答：

HashMap 的工作原理基于哈希表，是一种使用 哈希函数 将键映射到存储位置的数据结构。哈希表通过计算键的哈希值，并将其转化为数组索引，从而快速定位键值对的存储位置。在理想的情况下，哈希函数能将键均匀分布到哈希表上，以最小化哈希冲突。然而，当多个键哈希到同一个位置时，就需要解决哈希冲突
在 Java1.7 中，HashMap 主要使用链表来解决哈希冲突，将具有相同哈希值的键值对链接在一起
在 Java1.8 中，为了进一步提高性能，当链表长度和数组长度超过一定的阈值，链表就会转换为红黑树。红黑树是一种自平衡的二叉搜索树，能够在哈希冲突较多时提供更快的查找、插入和删除的操作
因此，HashMap 结合了哈希表、链表和红黑树的原理，实现了高效的键值对存储和查找功能

讲一下 HashMap 的 put 流程？

HashMap的put流程图

答：

首先判断键值对数组table是否为空或者 length = 0，是则执行 resize() 进行扩容
根据键值key计算hash值得到插入的数组索引 i ，如果 table[i] == null，则直接新建节点添加，转向 步骤 6，如果 table[i] 不为空，则转向 步骤 3
判断 table[i] 的首个元素是否和 key 一样，如果相同直接覆盖 value，否则转向 步骤 4，这里的相同指的是 hashcode 以及 equals
判断 table[i] 是否为 treeNode，即 table[i] 是否为红黑树，如果是红黑树，则直接在树上插入键值对，否则转向 步骤 5
遍历 table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树（同时满足容量条件），在红黑树中执行插入操作，否则执行链表的插入操作；遍历时发现key已经存在直接覆盖value即可
插入成功后，判断实际存在的键值对数量size是否超过了最大容量 threshold，如果超过了，则进行扩容

Java8 HashMap做了哪些优化？

答：

数组 + 链表 改成了 数组 + 链表/红黑树
链表的插入方式从 头插法 变成了 尾插法
扩容的时候，1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引 + 旧容量大小
在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容

HashMap什么时候进行扩容？

答：

HashMap扩容取决于一下两个元素：

Capacity：HashMap当前长度
LoadFactor：负载因子，默认值为 0.75f

当Map中的元素个数（包括数组、链表和红黑树中）超过了 16*0.75=12 之后进行扩容

还有一些其他导致扩容的情况：在 java8 中，当某个链表长度达到8，并且当前数组长度小于64，会触发扩容

HashMap的resize扩容流程？

答：

当put时，如果发现当前的bucket占用程度已经超过了LoadFactor所希望的比例，就会发生resize。在resize过程中，简单说就是把bucket扩容为2倍，之后重新计算index，再把节点放到新的bucket中
如果超出限制的时候就会重新resize，然而因为使用的是2次幂的扩展（指长度扩为原来的2倍），所以，元素的位置要么在原位置，要么在原位置再移动2次幂的位置
因此，在扩容HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0，是0则表示索引没变，是1索引则变为 “原索引 + oldCap”（也就是newIndex = oldIndex + 原来数组的大小）
因此resize的过程中，均匀的把之前冲突的节点分散到新的bucket中

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

答：

为了让HashMap存取高效，尽量减少碰撞，也就是要尽量把数据分配均匀
但是Hash取值范围有大概40亿的映射空间，内存是放不下的，用之前需要对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标，数组下标的计算方法就是 (n-1) & hash，其中 n 表示数组长度

为什么HashMap默认负载因子是0.75这个值呢？设太大和太小有什么问题吗？

答：

因为对于使用链表法的哈希表来说，查找一个元素的平均时间是 O(1+n)，这里的 n 表示遍历链表的长度
加载因子越大，对空间的利用也就越充分，这就意味着链表的长度越长，查找的效率就越低
加载因子越小，那么哈希表的数据就过于稀疏，对空间造成严重的浪费（因为比如：16 * 0.5 = 8，当元素数量达到8时，就进行一次扩容，扩容频率太快，对资源过于浪费）

Java8 链表转红黑树和红黑树转链表为什么是8和6？

答：

首先红黑树的 TreeNode 是链表中的 Node 所占空间的2倍，虽然红黑树的查找效率为 O(logN)，要优于链表的 O(N)，但当链表长度比较小的时候，即使全部遍历，时间复杂度也不会太高

链表转红黑树的阈值为8：因为Java的源码贡献者在进行大量的实验发现，默认的随机hashcode碰撞次数与泊松分布有关。hash碰撞发生8次的概率微乎其微，几乎为不可能事件，如果真的碰撞发生了8次，那么这个时候说明由于元素本身和hash函数的原因（这里可以重写hashcode方的）。此时的链表性能已经非常差了，操作的hash碰撞的可能性非常大，后续还会继续发生hash碰撞，所以，在这种极端的情况下才会把链表转换为红黑树，链表转换为红黑树也是需要消耗性能的，为了挽回性能，权衡之下，才使用红黑树，提高性能，大部分情况下hashMap还是使用链表
红黑树转链表的阈值为6：主要是因为，如果将该阈值设为8，那么当hash碰撞个数在8左右时，会发生链表和红黑树不停相互激荡转换，白白浪费资源。中间有个差值7可以防止链表和树之间的频繁转换

Java8 为什么这里把Key的hashcode取出来，然后把它右移16位，然后取异或？

答：

因为int是4个字节，也就是32位，大概是有40亿的空间，如果哈希函数运用的比较松散，一般是很难出现哈希碰撞的。但是现实中一个长度为40亿的数组空间是存放不下的并且HashMap在扩容前的数组的默认初始值为16，因此直接拿Hashcode值来用是不现实的，因此需要做一些运算，我们右移16位也就是把高位的数据右移到低位的16位，然后与自己做异或，那就是把高位和低位的数据进行混合，以此来加大低位的随机性，同时混合后的低位掺杂了高位的特征，这样高位的信息也变相保存了下来

HashMap多线程操作导致的死循环问题？

答：

JDK1.7 及之前版本的HashMap在多线程环境下扩容操作可能出现死循环问题，这是因为当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束
JDK1.8 版本的 HashMap 采用了尾插法来避免链表倒置，使得插入的节点永远放在链表的末尾，避免了链表中的环形结构
但是不建议在多线程下使用HashMap，因为在多线程下使用HashMap会存在数据覆盖的问题，并发情况下，推荐使用 ConcurrentHashMap

HashMap中Key可以为null吗？

答：

可以为null

HashMap 中使用 hash() 方法来计算key的哈希值，当key为空时，直接令key的哈希值为0，不走key.hasCode() 方法
HashMap虽然支持key和value都为null，但是null作为key只能有一个，null作为value可以有多个
因为在HashMap中，如果key值一样，那么会覆盖相同key值的value为最新，所以key为null只能有一个

static final int hash(Object key) {
    int h;
    // 当key为null的时候，不走hashcode() 方法
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashMap 和 HashTable 有什么区别？

答：

HashMap 是线程不安全的，HashTable 是线程安全的
由于线程安全，HashTable 的效率比不上 HashMap
HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null，而 HashTable 不允许
HashMap 默认初始化数组的大小为 16，HashTable 为 11，前者扩容时，扩大两倍，后者 扩大两倍+1
HashMap 需要重新计算 hash 值（指的是JDK1.7之前），而 HashTable 直接使用对象的 hashCode

HashMap、LinkedHashMap、TreeMap有什么区别？

答：

HashMap 略
LinkedHashMap 保存了记录的插入顺序，在用 Iterator 遍历时，先取到的记录肯定是先插入的，遍历比HashMap 慢
TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序（默认按照键值升序排序，也可以指定排序的比较器）

为什么 ConcurrentHashMap 比 HashTable 效率要高？

答：

底层结构：

JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组 + 链表 实现
JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样：数组 + 链表/红黑树
而 HashTable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都采用的 数组+链表 的形式
- 数组是HashMap的主体
- 链表则是主要为了解决哈希冲突存在的

实现线程安全的方式：

在 JDK1.7 时，ConcurrentHashMap 对整个桶数组进行了分割分段 (Segment, 分段锁) ，每一把锁只锁容器其中的一部分数据，多线程访问容器里不同数据段的数据，就不会出现锁竞争，提高并发访问率
在 JDK1.8 时，ConcurrentHashMap 摒弃了 Segment 的概念，直接使用 Node数组 + 链表 + 红黑树 的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作，这是因为在 JDK1.6 之后 synchronized 锁做了很多优化，整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本
HashTable（同一把锁）：使用synchronized来保证线程安全，效率非常低下。

讲一下java里面List的几种实现？

答：

ArrayList：应用于更广泛的动态数组实现，它本身不是线程安全的，所以性能要好很多。与 Vector 类似，是可以根据需要调整容量，但两者调整逻辑不同，Vector 在扩容时会调整1倍，而 ArrayList 则是增加50%
LinkedList：Java 提供的双向链表，不是线程安全的
Vector：与 ArrayList 相似，也实现了 List 接口，但是 Vector 主要方法是 synchronized 方法，即：通过互斥同步方法保证操作的线程安全。在多线程环境下，如果需要对集合进行写操作，可以考虑使用 Vector 来保证线程安全
Stack：是一个同步容器，它的方法也用 synchronized 进行同步，它是继承于 Vector 类

ArrayList 和 Array（数组）的区别？

答：

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

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

ArrayList 和 LinkedList 的区别？

答：

是否保证线程安全：

ArrayList 和 LinkedList 都是不同步的，不能保证线程安全

底层数据结构：

ArrayList 底层使用的是 Object 数组
LinkedList 底层使用的是双向链表数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环）

插入和删除是否受元素位置的影响：

ArrayList 采用数组存储，插入和删除的时间复杂度受元素位置的影响
LinkedList 采用链表存储，插入和删除的时间复杂度不受元素位置的影响

是否支持快速随机访问：

ArrayList 支持
LinkedList 不支持

内存空间占用：

ArrayList 空间浪费主要体现在 list 列表的结尾会预留一定的容量空间
LinkedList 的空间浪费则体现在它的每一个元素都消耗比 ArrayList 更多的空间

ArrayList 线程安全吗？把ArrayList变成线程安全有哪些方法？

答：

不是线程安全。ArrayList 变成线程安全的方法有：

使用 Collections 类的 synchronizedList 方法将 ArrayList 包装成线程安全的 List：
1
List<String> synchronizedList = Collections.synchronizedList(arrayList);
使用 CopyOnWriteArrayList 或者 Vector 等并发安全的类替代 ArrayList

Set集合有什么特点？如何实现key无重复的？

答：

Set集合特点：Set集合中的元素是唯一的，不会出现重复的元素
Set实现原理：Set集合通过内部的数据结构（如：哈希表、红黑树等）来实现 key 的无重复性。当向 Set 集合中插入元素时，会先根据元素的 hashcode 值来确定元素的存储位置，然后再通过 equals 方法来判断是否存在相同的元素，如果存在则不会再次插入，保证了元素的唯一性

说一下HashSet的原理？

答：

HashSet 是基于 HashMap 实现的，HashSet 底层使用 HashMap 来保存所有元素，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来实现的，HashSet 是不允许重复的值

Comparable 和 Comparator 的区别？

答：

二者都是 Java 中用于排序的接口
Comparable 接口实际上是出自 java.lang 包，它有一个 compareTo(Object obj) 方法进行排序
Comparator 接口实际上是出自 java.util 包，它有一个 compare(Object obj1, Object obj2) 方法进行排序
应用：
- 当我们要对一个集合使用自定义排序时，就要重写 compareTo() 方法或者 compare() 方法
- 当我们需要对一个集合采用两种排序方式时，可以重写 compareTo() 方法和使用自制的 Comparator方法或者以两个 Comparator 来实现两者的排序

eg：

/**
* T重写compareTo⽅法实现按年龄来排序
* compareTo 默认是升序排序
*/
@Override
public int compareTo(Person o) {
	if (this.age > o.getAge()) {
		return 1;
	}

    if (this.age < o.getAge()) {
		return -1;
	}
    
	return 0;
}

// 定制排序的⽤法
Collections.sort(arrayList, new Comparator<Integer>() {
	@Override
	public int compare(Integer o1, Integer o2) {
		return o2.compareTo(o1) ;
        // o2.compareTo(o1) 这个为降序，o1.compareTo(o2) 这个为升序
	}
});

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

答：

HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素的唯一，并且都不是线程安全的
三者主要区别在于底层数据结构的不同：
- HashSet 的底层数据结构是哈希表（基于 HashMap 实现）
- LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和删除满足FIFO
- TreeSet 的底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序
三者应用场景的不同：
- HashSet 不需要保证元素插入和取出顺序的场景
- LinkedHashSet 用于保证元素的插入和取出顺序满足FIFO的场景
- TreeSet 用于支持元素自定义排序规则的场景

Queue 和 Deque 的区别？

答：

设计目标：
- Queue（队列）遵循 FIFO 原则的数据结构，这意味着元素按照被添加的顺序进行处理
- Deque（双端队列，全称为：Double-Ended Queue）支持在两端添加和移除元素，既可作为 FIFO 队列使用，又可作为 LIFO 栈使用
操作：
- Queue 定义了队列的基本操作，如：add、offer（添加元素）、remove、poll（移除元素）以及peek（查看但不移除头部元素）
- Deque 接口拓展了 Queue 的功能，提供了队列两端进行操作的方法，例如：push、pop、addFirst、addLast、offerFirst、offerLast、removeFirst、removeLast、pollFirst、pollLast等
特殊队列类型：
- Queue 接口有几个特殊类型的实现，如：PirorityQueue（优先队列，元素根据自然顺序或者比较器定义的顺序进行处理）和 ConcurrentLinkedQueue（线程安全的队列，适用于多线程环境）
- Deque 接口的实现类，如：LinkedList 和 ArrayDeque，通常用于需要灵活地在两端添加或移除元素的场景

ArrayDeque 和 LinkedList 的区别？

答：

两者都是实现了 Deque 接口，都具有队列的功能

两者区别：

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

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

说一说 PriorityQueue？

答：

PriorityQueue 是在 JDK1.5 被引入的，其与 Queue 的主要区别就是：元素出队的顺序与优先级相关，即总是优先级最高的元素先出队

特点：

PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
PriorityQueue 通过堆元素的上浮和下沉，实现了 O(logn) 的时间复杂度内插入元素和删除堆顶元素
PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable
PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后

应用：

算法题：堆排序，求第K大的数、带权图的遍历等