单列Collection
和双列Map
集合
在 Java 中,集合有分为单列Collection
和双列Map
集合
单列集合又分为Set
和List
集合.
List
接口有多个子类延伸,常见的有以下几种:
-
ArrayList
:- 优点:支持快速随机访问,通过索引可以快速获取元素;动态扩容,当容量不足时自动增加容量。
- 缺点:插入和删除元素时,需要移动后面的元素,效率较低;线程不安全。
- 底层实现原理:使用数组存储元素,通过维护一个容量来动态扩容。扩容机制:当需要扩容时,会创建一个新的数组,其容量是原数组的 1.5 倍(或其他指定的增长因子)。
-
LinkedList
:- 优点:插入和删除元素效率高,只需修改指针;适用于频繁的插入和删除操作。
- 缺点:随机访问元素效率较低,需要遍历链表;占用更多内存,因为每个节点都需要存储指针。
- 底层实现原理:使用双向链表结构,每个节点包含前一个节点和后一个节点的引用。
-
Vector
:- 优点:线程安全,适用于多线程环境。
- 缺点:性能相对较低,由于加锁机制导致并发操作效率不高。
- 底层实现原理:与
ArrayList
类似,使用数组存储元素,但在多线程环境下通过加锁来保证线程安全。扩容机制:与ArrayList
类似,但可以通过构造函数指定扩容因子。
-
Stack
:- 优点:实现了栈的数据结构,提供了栈的基本操作,如入栈和出栈。
- 缺点:功能相对简单,只适用于栈的特定场景。
- 底层实现原理:继承自
Vector
,通过对push
和pop
等方法的实现来模拟栈的行为。
-
CopyOnWriteArrayList
:- 优点:线程安全,在读多写少的场景下性能较好;迭代过程中不会抛出
ConcurrentModificationException
。 - 缺点:写入时需要复制整个数组,开销较大;不适合频繁写入的场景。
- 底层实现原理:当进行写入操作时,会复制一个新的数组来进行修改,然后将原数组引用指向新数组。扩容机制:与
ArrayList
类似,新数组的容量通常是原容量的 2 倍或其他指定的增长因子。
- 优点:线程安全,在读多写少的场景下性能较好;迭代过程中不会抛出
在选择使用哪个子类时,需要根据具体的应用场景和需求来权衡其优缺点。如果需要高效的随机访问,可选择 ArrayList
;如果需要频繁的插入和删除,可选择 LinkedList
;如果需要线程安全,可选择 Vector
或 CopyOnWriteArrayList
。
Set
接口有多个子类延伸,常见的有以下几种:
集合类 | 优点 | 缺点 | 底层实现原理 | 对红黑树的操作 |
---|---|---|---|---|
HashSet | 快速查找、添加和删除元素;不允许重复元素。 | 不保证元素的顺序。 | 基于哈希表实现,通过哈希函数将元素映射到特定的存储位置。 | 不涉及红黑树操作。 |
LinkedHashSet | 保持元素的插入顺序;快速查找、添加和删除元素。 | 比 HashSet 略慢,因为需要维护元素的顺序。 | 结合了哈希表和链表的特性,在哈希表的基础上维护了元素的插入顺序。 | 不涉及红黑树操作。 |
TreeSet | 有序存储元素;支持自然排序或自定义排序规则;高效的插入、删除和查找操作。 | 插入和删除元素的性能相对较低。 | 使用红黑树实现,自动对元素进行排序。 | 插入操作:将元素插入到红黑树中,并根据元素的值进行排序,可能需要进行颜色调整和旋转操作。 删除操作:从红黑树中删除指定元素,可能涉及到节点的替换和颜色调整。 查找操作:根据元素的值在红黑树中进行查找,快速定位到目标元素。 |
在选择使用哪个集合类时,需要考虑以下因素:
- 是否需要保持元素的顺序:如果需要,选择 LinkedHashSet 或 TreeSet;如果不需要,HashSet 可能更适合。
- 对性能的要求:如果注重查找、添加和删除的速度,HashSet 通常是较好的选择;如果需要有序性且对性能要求不是特别高,TreeSet 是不错的选择。
- 是否需要自定义排序规则:如果需要,选择 TreeSet 并提供相应的比较器。
红黑树是一种平衡二叉搜索树,它通过颜色标记和旋转操作来保持树的平衡,从而提供高效的插入、删除和查找操作。TreeSet 利用红黑树的特性来实现有序集合,使得元素能够按照特定的顺序进行存储和访问。
双列集合 Map
集合:
Map 集合类 | 优点 | 缺点 | 底层实现原理 |
---|---|---|---|
HashMap | 快速查找、添加和删除元素;不保证元素的顺序。 | 不支持线程安全(多线程环境下需要额外的同步措施)。 | 基于哈希表实现,通过哈希函数将键映射到特定的存储位置。 |
LinkedHashMap | 保持元素的插入顺序;快速查找、添加和删除元素。 | 比 HashMap 略慢,因为需要维护元素的顺序。 | 结合了哈希表和链表的特性,在哈希表的基础上维护了元素的插入顺序。 |
TreeMap | 有序存储键值对;支持自然排序或自定义排序规则。 | 插入和删除元素的性能相对较低。 | 使用红黑树实现,自动对键进行排序。 |
选择使用哪个 Map
子类时,需要考虑以下因素:
- 是否需要保持元素的顺序:如果需要,选择
LinkedHashMap
或TreeMap
;如果不需要,HashMap
可能更适合。 - 对性能的要求:如果注重查找、添加和删除的速度,
HashMap
通常是较好的选择。 - 是否需要自定义排序规则:如果需要,选择
TreeMap
并提供相应的比较器。
与 Set
不同,Map
存储的是键值对,每个键对应一个值。Map
提供了丰富的操作方法,如获取值、添加键值对、删除键值对等。
需要注意的是,在多线程环境下,如果需要线程安全的 Map
,可以使用 ConcurrentHashMap
或其他线程安全的 Map
实现类。
ArrayList
和 linkedList
区别?
ArrayList
和 LinkedList
是 Java 中常用的两种集合类,它们在数据结构实现、随机访问效率、增加和删除效率、内存空间占用以及线程安全等方面存在一些区别。
-
数据结构实现:
ArrayList
是基于动态数组的数据结构实现。LinkedList
则是基于双向链表的数据结构实现,每个节点包含两个指针,分别指向直接后继和直接前驱。
-
随机访问效率:
- 由于
ArrayList
底层是数组,可以通过索引直接访问元素,因此在随机访问时效率较高。 - 而
LinkedList
需要通过移动指针从前往后依次查找,所以在随机访问方面效率相对较低。
- 由于
-
增加和删除效率:
- 对于非首尾位置的增加和删除操作,
LinkedList
效率更高。因为它只需修改相关节点的指针,无需移动其他元素。 - 而
ArrayList
在进行非首尾位置的增删操作时,可能需要移动其他元素以保持数组的连续性,效率相对较低。
- 对于非首尾位置的增加和删除操作,
-
内存空间占用:
LinkedList
除了存储数据本身,还需要额外存储两个引用(指向前驱和后继节点),因此相比ArrayList
会占用更多的内存空间。
-
线程安全:
- 两者都是非线程安全的,在多线程环境下需要进行额外的同步处理。
综上所述,在选择使用 ArrayList
还是 LinkedList
时,可以根据具体的需求来考虑:
- 如果需要频繁读取集合元素,对随机访问效率有较高要求,可选择
ArrayList
。 - 如果集合的插入和删除操作较多,尤其是在非首尾位置,可选择
LinkedList
。
HashMap
详解
一、引言
HashMap 是 Java 中常用的数据结构之一,用于存储键值对。它基于哈希表实现,提供了高效的插入、查找和删除操作。本文将深入探讨 HashMap 的底层原理、解决哈希冲突的方法、扩容机制以及与 ConcurrentHashMap 的区别等方面。
二、哈希与哈希冲突
- 哈希:将任意长度的二进制映射为固定长度的较小二进制值。
- 哈希冲突:不同输入值计算出相同哈希值的现象。
三、HashMap 解决哈希冲突的方法
- 链表法:相同哈希值的对象组织成链表放在Hash值对应的槽位。
- 开放地址法:当某个槽位已经被占用, 通过探测算法寻找下一个可用槽位。
四、HashMap 的底层原理
- 数据结构:数组和链表结合。
- 插入元素:计算哈希值确定下标,处理哈希冲突。
- 获取元素:找到对应下标,进一步判断键是否相同。
HashMap 是 Java 中常用的一种数据结构,用于存储键值对。它的底层实现主要基于数组和链表(或红黑树)。
-
数组存储:HashMap 使用一个数组来存储键值对。数组的每个元素称为一个“桶”(bucket),每个桶可以存储一个键值对或者一个链表(或红黑树)。
-
哈希函数:HashMap 使用哈希函数将键转换为一个整数哈希码。哈希码用于确定键值对应该存储在哪个桶中。
-
解决冲突:由于哈希函数可能会导致不同的键产生相同的哈希码,因此可能会发生冲突。HashMap 通过链表(或红黑树)来解决冲突。当多个键值对被映射到同一个桶时,它们会被存储在该桶的链表(或红黑树)中。
-
链表存储:在发生冲突时,HashMap 使用链表来存储冲突的键值对。每个链表节点包含键、值以及指向下一个节点的引用。
-
红黑树存储(可选):当链表长度大于 阈值(默认为8) 时,HashMap 会将链表转换为红黑树, 以减少搜索时间,提高查询性能。扩容 resize( ) 时,红黑树拆分成的树的结点数小于等于临界值6个,则退化成链表。红黑树是一种自平衡的二叉搜索树,能够快速地进行查找、插入和删除操作。
-
扩容机制:当 HashMap 中的元素数量超过一定比例(默认是 0.75)时,HashMap 会进行扩容操作。扩容会创建一个更大的数组,并将原来的键值对重新映射到新的数组中。
通过以上底层原理,HashMap 能够实现高效的键值对存储和快速的查找操作。它的平均时间复杂度为 O(1),在大多数情况下能够提供较好的性能。
需要注意的是,HashMap 是非线程安全的,如果在多线程环境下使用,需要进行适当的同步处理或使用线程安全的 ConcurrentHashMap。
五、HashMap 的 put 方法流程
- 判断数组是否为空或 null,否则扩容。
- 根据键计算哈希值得到索引。
- 处理哈希冲突,覆盖或添加到链表/红黑树。
- 插入成功后判断是否需要扩容。
六、HashMap 的扩容机制
- 超过阀值或初始化时扩容。
- 扩容为原来的 2 倍。
- 元素重新分发。
七、为何 HashMap 数组长度为 2 的次幂
- 提高计算索引效率。
- 扩容时重新计算索引更高效。
- 均匀分配数据,减少哈希冲突。
八、ConcurrentHashMap
- 线程安全的高效 Map 集合。
- JDK1.7:分段数组+链表,锁粒度较大。
- JDK1.8:Node+CAS+Synchronized,锁粒度更精细。
九、HashMap 与 ConcurrentHashMap 的区别
- 线程安全性:HashMap 非线程安全,ConcurrentHashMap 线程安全。
- 键值对是否允许 null:HashMap 允许,ConcurrentHashMap 不允许。
十、总结
HashMap 是一种常用的数据结构,通过哈希表实现高效的存储和访问。理解其底层原理、解决哈希冲突的方法以及扩容机制对于正确使用和优化 HashMap 非常重要。ConcurrentHashMap 则提供了线程安全的版本,适用于多线程环境。在实际应用中,根据具体需求选择合适的 Map 实现。