Java中的集合与IO

1. 集合类中主要有几种接口？

• Collection：是集合List、Set、Queue的最基本的接口。
• Iterator：迭代器，可以通过迭代器遍历集合中的内容。
• Map：是映射表的基础接口。

2. 集合中泛型的优点

1. 保证了类型的安全性：泛型约束了变量的类型，保证了类型的安全性。
2. 避免了不必要得装箱、拆箱的操作，提高了程序的性能：泛型变量固定了类型，在使用时就已经知道是值类型还是引用类型。
3. 提高了代码的复用性。

3. List、Set、Queue、Map的区别

• List：存储的元素是有序、可重复的
• Set：存储的元素是无序、不可重复的
• Queue：按照特定的排队规则来确定先后顺序，存储的元素是有序、可重复的
• Map：使用键值对（K-V）的形式存储，其中key是无序、不可重复的，而v是无序、可重复的

4. 集合类的底层数据结构

-- List

• ArrayList：Object[]数组
• Vector：Object[]数组
• LinkedList：双向链表

-- Set

• HashSet：基于HashMap实现
• LinkedHashSet：是HashSet的子类，通过LinkedHashMap实现
• TreeSet：平衡的排序二叉树

-- Queue

• PriorityQueue：Object[]数组实现二叉堆
• ArrayQueue：Object[]数组 + 双指针

-- Map

• HashMap：JDK1.8之前是数组 + 链表；JDK1.8开始变为了数组 + 链表/红黑树
• LinkedHashMap：继承自HashMap，底层同样是数组 + 链表/红黑树
• HashTable：数组 + 链表
• TreeMap：平衡的排序二叉树

5. 如何选用集合类

-- 需要根据键值对获取元素则采用Map接口下的集合

• 需要排序时选用TreeMap
• 无需排序时选用HashMap
• 需要保证线程安全可以采用ConcurrentHashMap

-- 只需存放元素则采用Collection接口下的集合

• 需要保证元素唯一可以采用HashSet/TreeSet
• 无需保证元素唯一可以实现List接口，比如ArrayList、LinkedList

6. HashSet如何检查重复

当将一个新对象加入HashSet时，HashSet首先会计算它的hashcode值来确定该元素应当存入的位置，同时还会与其余要加入的对象的hashcode值进行对比，如果没有重复，则加入元素；否则HashSet会调用equals()方法来判断二者是否完全相同，若相同则添加失败。

7. HashSet与TreeSet的区别

• HashSet 是由一个hash表来实现的，因此其中的元素是无序、不可重复的。其中方法包括add()、remove()、contains()。
• TreeSet 是由一个树状的结构来实现的，其中的元素是有序、不可重复的。其中方法包括add()、remove()、contains()。

8. HashMap与HashSet的区别

9. HashMap与HashTable的区别

1. HashMap是线程非安全的；而HashTable是线程安全的，因为HashTable内部的方法基本都经过了synchronized关键字修饰
2. 由于线程安全的问题；HashMap的效率要高于HashTable
3. HashMap允许存储值为null的key与value，但为null的key只允许有一个，而value可以有多个；HashTable不允许有null的key与value，否则会抛出NullPointerexception
4. 创建时如果不指定初始值，HashMap的默认大小为16，之后每次扩容为原来的2倍；HashTable的默认大小为11，之后每次扩容为原来的2n + 1。
5. 创建时如果指定了初始值，HashMap会自动将其扩容值2^n，而HashTable则会采用指定的值作为初始值
6. JDK 1.8后HashMap的底层数据结构为数组 + 链表/红黑树；HashTable的底层数据结构为数组 + 链表

10. HashMap与TreeMap的区别

二者都继承自AbstractMap，但TreeMap还实现了NavigableMap与SortedMap接口，使得TreeMap还拥有对集合内元素进行搜索以及根据键值进行排序的能力。

11. ConcurrentHashMap与HashTable的区别

二者之间的区别主要体现在了实现线程安全的方式上。

• 底层数据结构 ConcurrentHashMap的底层数据结构与HashMap类似，在JDK 1.7时采用的是分段的数组 + 链表的形式；JDK1.8时采用的是数组 + 链表/红黑树的形式。HashTable的底层数据结构则是数组 + 链表的形式
• 实现线程安全的方式 ConcurrentHashMap实现线程安全的方式是采用了Segment分段分割，每一段上都会有一个同步锁。当多线程访问同一桶中不同段上的数据时就不会存在锁竞争的问题。在JDK 1.8时则摒弃了Segment分段分割的概念，ConcurrentHashMap实现线程安全的方式改变为synchronized + volatile/CAS。当存入新的元素时，首先会判断当前数组是否为空，如果为空则通过volatile + CAS进行初始化，随后将元素存入；否则会根据元素的hashcode获取元素应当存入的位置，在判断该处是否为空。如果为空则通过CAS进行添加，否则通过synchronized对整个数组加锁，然后在进行元素的添加或者替换操作。最后再判断是否触发数组结构转红黑树结构。HashTable实现线程安全则是通过synchronized关键字来实现，但他采用的是同一把锁，也就是说，当一个线程在访问同步方法时，其余线程会被阻塞，导致效率低下。

12. ArrayList与LinkedList的区别

1. 线程安全 二者都是线程非安全的
2. 底层数据结构 ArrayList的底层是一个Object数组，而LinkedList底层则是一个双向链表
3. 插入与删除和元素位置的关系

• ArrayList 采用数组存储，因而插入与删除与元素位置有关
• LinkedList 采用双向链表存储，在首尾插入与删除时其时间复杂度近似为O(1)，其余情况下为O(n)，因为要移动到指定位置再进行操作

1. 是否支持快速访问 ArrayList由于是数组存储，因而支持快速访问；而LinkedList则不支持
2. 内存空间的占用 ArrayList的空间浪费体现在list列表的结尾会预留一定的容量空间；LinkedList的空间浪费体现在其每一个元素除了存储数据以外还需要存放前驱与后继

13. HashMap底层实现原理

• JDK 1.8之前

HashMap的底层数据结构是数组 + 链表。当存入新元素时，会通过该元素的hashcode值计算应当存入的位置。若为空，则直接存入；否则会对二者的key值进行比较，若想等则替换；不等则通过拉链法将元素存入

• JDK 1.8之后

HashMap的底层数据结构转变为了数组 + 链表/红黑树的形式。与上面的区别在于，再添加元素时，会判断链表的长度是否超过了8，如果超过了8，则会将数组结构转变为红黑树结构，便于查找；在此之前若数组长度不超过64，会进行resize扩容，扩容后的数组长度为原数组长度的2倍。

14. HashMap的resize扩容

HashMap是否触发resize扩容与两个因素有关：load factor负载因子（默认为0.75，从源码注释中可知这是时间上的最优解）、capacity初始容量。

当存入元素后使得HashMap中数组的长度大于负载银子与初始容量的乘积时便会触发resize扩容。主要包括两个阶段：

1. 新建一个node[]数组，数组长度为原数组的2倍
2. 将原数组中的元素rehash到新的数组中

注：在创建数组时若要指定数组长度，最好使要指定的数组长度小于2^n与负载因子的乘积。则n即为需要指定的数组长度。例：需要创建的数组长度为1000，则应当new HashMap(1000);，但理论上采用new HashMap(1024);更为合适。然而，1024 * 0.75 < 1000，为了避免resize问题，需要指定为new HashMap(2048);

15. 为什么HashMap中数组的长度需要是$2^n$

因为在计算存入元素位置时，采用的公式是hashcode(key) % n，其中n为数组的长度。而%运算的效率低，为了提高计算效率，减少hash碰撞的概率，可以利用&运算来代替，而如此做的条件便是n是2的整数幂，且二者之间的关系为hashcode(key) % n = hashcode(key) & (n - 1)

16. Collection与Collections之间的区别

• Collection是集合类的上级接口，继承自它的接口的主要是set与list
• Collections则是针对集合类的一个工具类，提供了诸如排序、搜索、线程安全化等操作

17. 数组Array与列表ArrayList的区别

• Array可以包含基本类型与对象类型；ArrayList只能包含对象类型
• Array的大小是固定的；ArrayList的大小是动态变化的

18. BIO与NIO的区别

• BIO指的是同步阻塞式IO 在此方式下，用户进行在发起一个IO操作时，必须等待该IO操作结束，用户进程才会结束
• NIO指的是异步非阻塞式IO NIO采用了双向通道进行数据传输，可以在通道上注册事件，包括：连接事件、读写事件；NIO主要有三大核心部分：Channel通道、Buffer缓冲区、Selector监视器。传统IO基于字节流与字符流进行操作；NIO则是基于Channel与Buffer进行操作。数据总是从Channel通道中读取到Buffer缓冲区中，或者从Buffer缓冲区中写入到Channel通道中。Selector监视器则用于监听多个通道的事件，如：连接打开、数据到达等。

19. Java中的流

1. 按照流的方向：

• 输入流
• 输出流

1. 按照实现功能：

• 节点流
• 处理流

1. 按照处理数据的单位：

• 字节流
• 字符流

20. 字节流和字符流的区别

• 字节流一般用于处理图像、视频、音频、PPT、Word等类型的文件。字符流一般用于处理纯文本类型的文件
• 字节流本身没有缓冲区，缓冲字节流相对于字节流效率非常高；而字符流本身就有缓冲区，缓冲字符流较比字符流的提升不是很大

21. 为什么有了字节流还要有字符流

字符流是由Java虚拟机将字节转换得到的，而这个过程非常耗时，同时如果编码类型未知就会出现乱码问题，因此IO流就提供了一个直接操作字符的接口

22. 什么是Java序列化？如何实现Java序列化？

• 序列化：

是一种用来处理对象流的机制，而所谓的对象流就是将对象的内容进行流化，可以对流化后的对象进行对写操作，也可将流化后的对象传输于网路之间。序列化是为了解决在对象流进行读写操作时所引发的问题

• 序列化的实现：

将需要被序列化的类实现Serializable接口，该接口没有需要实现的方法，只是用来标注该对象可被序列化，然后使用一个输出流（如：FileOutputStream）来构造一个ObjectOutputStream（对象流）对象，接着使用ObjectOutputStream对象的writeObject(Object obj)方法就可以将参数为obj的对象保存，若要恢复则可以使用输入流

23. 红黑树的特征

```mermaid graph LR 红黑树的特征--> 每个节点都是红色或者黑色的 红黑树的特征--> 根节点是黑色的 红黑树的特征--> 每个叶子节点都是黑色的/指向空的叶子节点 红黑树的特征--> 如果一个叶子节点是红色,那么其子节点必须都是黑色的 红黑树的特征--> 从一个节点到该节点的子孙节点的所有路径上包括相同数目的黑节点