Java基础知识学习07

墨蓝 2024-03-23 14:59 41阅读 0赞

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

Java 集合框架如下图所示：  
![在这里插入图片描述][595a7013812544c6a00e3f80aa159a6a.png]  
图中只列举了主要的继承派生关系，并没有列举所有关系。比方省略了`AbstractList`, `NavigableSet`等抽象类以及其他的一些辅助类。

***2、List、Set、Queue、Map四者的区别？***

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

***3、集合框架底层数据结构总结***

***List：***

*  `ListArrayList`： Object\[\] 数组
 *  `Vector`：Object\[\] 数组
 *  `LinkedList`： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)

***Set：***

*  `HashSet`(无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素
 *  `LinkedHashSet`: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现一样，不过还是有一点点区别的
 *  `TreeSet`(有序，唯一): 红黑树(自平衡的排序二叉树)

***Queue：***

*  `PriorityQueue`: Object\[\] 数组来实现二叉
 *  `ArrayQueue`: Object\[\] 数组 + 双指针

***Map：***

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

***4、如何选用集合？***

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

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

***5、为什么要使用集合？***

当我们需要保存一组类型相同的数据的时候，我们应该是用一个容器来保存，这个容器就是数组，但是，`使用数组存储对象具有一定的弊端， 因为我们在实际开发中，存储的数据的类型是多种多样的，于是，就出现了“集合”`，集合同样也是用来存储多个数据的。`数组的缺点是一旦声明之后，长度就不可变了；同时，声明数组时的数据类型也决定了该数组存储的数据的类型；而且，数组存储的数据是有序的、可重复的，特点单一`。 但是集合提高了数据存储的灵活性，`Java 集合不仅可以用来存储不同类型不同数量的对象，还可以保存具有映射关系的数据。`

***6、ArrayList 和 Vector 的区别？***

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

***7、ArrayList 与 LinkedList 区别?***

*  **是否保证线程安全：** `ArrayList` 和 `LinkedList` 都是不同步的，也就是**不保证线程安全**；
 *  **底层数据结构：** `ArrayList` 底层使用的是 `Object` 数组；`LinkedList` 底层使用的是 `双向链表` 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别）
 *  **插入和删除是否受元素位置的影响**：  
    1、`ArrayList` 采用**数组存储**，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行`add(E e)`方法的时候， `ArrayList` 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 `O(1)`。但是如果要在指定位置 `i` 插入和删除元素的话（`add(int index, E element)`）时间复杂度就为 `O(n-i)`。因为在进行上述操作的时候集合中第 `i` 和第 `i` 个元素之后的`(n-i)`个元素都要执行向后位/向前移一位的操作。  
    2、`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` 不支持高效的随机元素访问，而 ArrayList（实现了`RandomAccess`接口） 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于`get(int index)`方法)。
 *  ***内存空间占用：*** `ArrayList` 的空间浪费主要体现在在 `list` 列表的\*\*`结尾会预留一定的容量空间`\*\*，而 `LinkedList` 的空间花费则体现在`它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）`。我们在项目中`一般是不会使用到 LinkedList 的`，需要用到 `LinkedList` 的场景几乎都可以使用 `ArrayList` 来代替，并且，性能通常会更好！

注意：⚠️ 不要下意识地认为 `LinkedList` 作为链表就最适合元素增删的场景。`LinkedList` 仅仅`在头尾插入或者删除元素的时候时间复杂度近似 O(1)，其他情况增删元素的时间复杂度都是 O(n) 。`

***8、comparable 和 Comparator 的区别？***

*  `comparable` 接口实际上是出自`java.lang`包 它有一个 `compareTo(Object obj)`方法用来排序
 *  `comparator`接口实际上是出自 `java.util` 包它有一个`compare(Object obj1, Object obj2)`方法用来排序

一般我们需要`对一个集合使用自定义排序`时，我们就要`重写compareTo()方法或compare()方法`，当我们需要`对某一个集合实现两种排序方式`，比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话，我们`可以重写compareTo()方法和使用自制的Comparator方法或者以两个 Comparator` 来实现歌名排序和歌星名排序，第二种代表我们只能使用两个参数版的 `Collections.sort()`

***8、无序性和不可重复读的含义是什么？***

*  无序性不等于随机性 ，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是根据数据的哈希值决定的。
 *  不可重复性是指添加的元素按照 equals() 判断时 ，返回 false，需要同时重写 equals() 方法和 hashCode() 方法。

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

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

***10、Queue 与 Deque 的区别？***

`Queue` 是**单端队列**，只能从一端插入元素，另一端删除元素，实现上一般遵循 `先进先出（FIFO）` 规则。

`Queue` **扩展了** `Collection` 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在**操作失败后会抛出异常**，另一种则会**返回特殊值**。  
![在这里插入图片描述][689590681a8f4bc7839cd2b9035fcbc6.png_pic_center]

`Deque` 是**双端队列**，在队列的两端均可以插入或删除元素。`Deque` **扩展了** `Queue` 的接口, 增加了**在队首和队尾进行插入和删除的方法**，同样根据失败后处理方式的不同分为两类：  
![在这里插入图片描述][65fcbc5f3ab545799f6012b2ea70490f.png_pic_center]

事实上，`Deque` 还提供有 `push()` 和 `pop()` 等其他方法，可用于模拟栈。

[595a7013812544c6a00e3f80aa159a6a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/6aabfd32aa3c46de997dc727ecba2438.png
[689590681a8f4bc7839cd2b9035fcbc6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/0b6f6d776db44ae1a1409ac52ff30edf.png
[65fcbc5f3ab545799f6012b2ea70490f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/d52e41522e3c498f99e11ba66b52818c.png