正文 Java容器 拾年之璐 V管理员 /2022年 /381 阅读 0706 主要是由两大接口派生而来 `Collection`接口，主要用于存放单一元素 - List - Set - Queue `Map` 接口，主要用于存放键值对 - Map ## 概述 ### 说说 List, Set, Queue, Map 四者的区别？ - `List`(对付顺序的好帮手): 存储的元素是有序的、可重复的。 - `Set`(注重独一无二的性质): 存储的元素是无序的、不可重复的。 - `Queue`(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。 - `Map`(用 key 来搜索的专家): 使用键值对（key-value）存储，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。 ### List - `Arraylist`： `Object[]` 数组 - `Vector`：`Object[]` 数组 - `LinkedList`： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环) ### Set - `HashSet`(无序，唯一): 基于 `HashMap` 实现的，底层采用 `HashMap` 来保存元素 - `LinkedHashSet`: `LinkedHashSet` 是 `HashSet` 的子类，并且其内部是通过 `LinkedHashMap` 来实现的。 - `TreeSet`(有序，唯一): 红黑树(自平衡的排序二叉树) ### Queue - `PriorityQueue`: `Object[]` 数组来实现二叉堆 - `ArrayQueue`: `Object[]` 数组 + 双指针 ### Map - `HashMap`： JDK1.8 之前 `HashMap` 由数组+链表组成的，数组是 `HashMap` 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间 - `LinkedHashMap`： `LinkedHashMap` 继承自 `HashMap`，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，`LinkedHashMap` 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。 - `Hashtable`： 数组+链表组成的，数组是 `Hashtable` 的主体，链表则是主要为了解决哈希冲突而存在的 - `TreeMap`： 红黑树（自平衡的排序二叉树） ## Collection 子接口之 List ### Arraylist 和 Vector 的区别? 线程安全 ### Arraylist 与 LinkedList 区别? - 线程安全 : 都不是 - 底层数据结构 - 插入和删除元素是否受元素位置的影响 - 是否支持快速随机访问 - 内存空间占用 ### ArrayList 的扩容机制 **ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右** ## Collection 子接口之 Set ### 比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同 - 线程安全 : 都不是 - 底层数据结构 - 应用和场景不同 ## Map接口 ### HashMap 和 Hashtable 的区别 - 线程安全 - 效率 - 对null key 和 null value的支持 - 初始容量和每次扩容大小不同 - `Hashtable` 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1 - `HashMap` 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍 - 底层数据结构不同 ### HashMap 和 TreeMap 区别 `TreeMap` 和`HashMap` 都继承自`AbstractMap` ，但是需要注意的是`TreeMap`它还实现了`NavigableMap`接口和`SortedMap` 接口。 - 实现 `NavigableMap` 接口让 `TreeMap` 有了对集合内元素的搜索的能力。 - 实现`SortedMap`接口让 `TreeMap` 有了对集合中的元素根据键排序的能力。 ### ConcurrentHashMap 和 Hashtable 的区别 主要体现在实现线程安全的方式上不同。 - 底层数据结构 : JDK1.7 的 `ConcurrentHashMap` 底层采用 **分段的数组+链表** 实现，JDK1.8 采用的数据结构跟 `HashMap1.8` 的结构一样，数组+链表/红黑二叉树 - 实现线程安全的方式 : 1. **在 JDK1.7 的时候，`ConcurrentHashMap`（分段锁）** 对整个桶数组进行了分割分段(`Segment`)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 **到了 JDK1.8 的时候已经摒弃了 `Segment` 的概念，而是直接用 `Node` 数组+链表+红黑树的数据结构来实现，并发控制使用 `synchronized` 和 CAS 来操作。** 2. **`Hashtable`(同一把锁)** :使用 `synchronized` 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态 本文采用创作共用版权 CC BY-NC-SA 3.0 CN 许可协议，转载或复制请注明出处！ -- 展开阅读全文 --
