Java 的集合类有哪些,哪些是线程安全的,哪些是线程不安全的?
Java 中的集合类主要由 Collection 和 Map 这两个接口派生而出,其中 Collection 接口又派生出三个子接口,分别是 Set、List、Queue。所有的 Java 集合类,都是 Set、List、Queue、Map 这四个接口的实现类。
-
- List 接口:有序集合,允许重复元素。常见的实现类有 ArrayList、LinkedList 等。
- Set 接口:不允许重复元素的集合。常见的实现类有 HashSet、LinkedHashSet、TreeSet 等。
- Queue 接口:用于表示队列的数据结构。 常见的实现类有 LinkedList、PriorityQueue 等。
- Map 接口:表示键值对的集合。常见的实现类有 HashMap、LinkedHashMap、TreeMap 等。
线程不安全的集合类
- ArrayList、LinkedList、HashSet、HashMap:这些集合类是非线程安全的。在多线程环境中,如果没有适当的同步措施,对这些集合的并发操作可能导致不确定的结果。
- TreeMap、TreeSet: 虽然 TreeMap 和、 TreeSet 是有序的集合,但它们也是非线程安全的。
线程安全的集合类
- Vector:类似于 ArrayList,它的方法都是同步的,因此是线程安全的。然而,它相对较重,不够灵活,现在通常建议使用 ArrayList。
- HashTable:类似于 HashMap,但它是线程安全的,通过同步整个对象实现。但它的使用已经不太推荐,通常建议使用 HashMap。
- ConcurrentHashMap:提供更好的并发性能,通过锁分离技术实现线程安全。
- Collections.synchronizedList、Collections.synchronizedSet、Collections.synchronizedMap: 这些方法可以将非线程安全的集合包装成线程安全的集合。
ArrayList 和 Array 有什么区别?ArrayList 和 LinkedList 的区别是什么?
- ArrayList vs Array:
- ArrayList 是动态数组的实现,而 Array 是固定长度的数组。
- ArrayList 提供了更多的功能,比如自动扩容、增加和删除元素等,Array 则没有这些功能。
- Array 可以直接存储基本类型数据,也可以存储对象。 ArrayList 中只能存储对象。对于基本类型数据,需要使用其对应的包装类(如 Integer、Double 等)
- 在随机访问时,Array 由于其连续内存存储,性能通常优于 ArrayList。
- ArrayList vs LinkedList:
- ArrayList 基于动态数组,LinkedList 基于双向链表。
- 随机访问:ArrayList 在随机访问时性能更好,而 LinkedList 访问元素时效率较低,因为需要从头开始或从尾开始通过链接遍历,时间复杂度为 O(n)。
- 删除/添加元素:在 ArrayList 末尾添加元素通常很快,但在 ArrayList 中间或开始插入或删除元素时,可能需要移动后续元素,时间复杂度为 O(n)。而 LinkedList 添加和删除元素时性能更佳,只需改变节点的引用。
- 扩容:当容量不足以容纳更多元素时,ArrayList 会扩容,这个过程涉及创建新数组和复制旧数组的内容,有一定的开销。
- 使用场景:选择 ArrayList 或者 LinkedList 通常取决于你的 Java 应用是否需要频繁的随机访问操作,还是更多的插入和删除操作。
总结来说,ArrayList 和 Array 的主要区别在于动态大小和功能,而 ArrayList 和 LinkedList 的主要区别在于底层数据结构和它们对元素操作的性能特点。选择使用哪一个取决于具体的应用场景和性能需求。
ArrayList 扩容机制
- ArrayList 扩容的本质就是计算出新的扩容数组的 size 后实例化,并将原有数组内容复制到新数组中去。(不是原数组,而是新数组然后给予数组对象地址)。
- 当创建一个 ArrayList 对象时,它会分配一定的初始容量,通常为 10。
- 当 ArrayList 中的元素数量达到当前容量时,ArrayList 会自动增加其容量。ArrayList 扩容的计算是在一个 grow() 方法里面,grow 方法先尝试将数组扩大为原数组的 1.5 倍。(默新容量 = 旧容量右移一位(相当于除于 2)在加上旧容量)
- 若新的容量满足需求,会调用一个 Arrays.copyof 方法, 将所有的元素从旧数组复制到新数组中,这个方法是真正实现扩容的步骤。如果扩容后的新容量还是不满足需求,那新容量大小为当前所需的容量加 1。
HashMap 的底层实现是什么?
在 JDK 1.8 之前,HashMap 由数组和链表组成,当发生哈希冲突时,多个元素会以链表的形式存储在同一个数组位置。JDK 1.8 开始引入了红黑树,当链表长度超过一定阈值(TREEIFY_THRESHOLD,默认为 8)且当前数组的长度大于 64 时,链表会转换成红黑树,以提高搜索效率。
为什么链表大小超过 8 会自动转为红黑树,小于 6 时重新变成链表?
根据泊松分布 ,在负载因子默认为 0.75 的时候,单个 hash 槽内元素个数为 8 的概率小于百万分 之一,所以将 7 作为一个分水岭, 等于 7 的时候不转换,大于等于 8 的时候才转换成红黑树,小于等于 6 的时候转化为链表。
HashMap 读和写的时间复杂度是多少?
读:
- 在最佳情况下:读操作的时间复杂度是 O(1)
- 最坏情况下:发生哈希冲突,链表为 O(n),红黑树为 O(log n)。
写:
- 理想情况:与读操作类似,如果哈希函数分布均匀,写操作的时间复杂度也是 O(1)。
- 处理哈希冲突:如果发生哈希冲突,需要在链表尾部添加新元素或将链表转换为红黑树。在这种情况下,写操作的时间复杂度可能达到 O(n),其中 n 是链表的长度。
解决 hash 冲突的方法有哪些?HashMap 是如何解决 hash 冲突的?
解决哈希冲突的方法主要有以下两种:
- 链地址法:在数组的每个位置维护一个链表。当发生冲突时,新的元素会被添加到链表的尾部。
- 开放寻址法:当发生冲突时,根据某种探测算法在哈希表中寻找下一个空闲位置来存储元素。
Java 中的 HashMap 使用链地址法解决 hash 冲突。
HashMap 的 put 方法流程
- 判断键值对数组是否为空或为 null,否则执行 resize() 进行扩容;
- 根据键值 key 计算 hash 值得到插入的数组索引 i,如果 table[i]==null,直接新建节点添加,转向步骤 6,如果 table[i] 不为空,转向步骤 3;
- 判断数组的首个元素是否和 key 一样,如果相同直接覆盖 value,否则转向 4,这里的相同指的是 hashCode 以及 equals;
- 判断 table[i] 是否为 treeNode,即 table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向 5;
- 遍历 table[i],判断链表长度是否大于 8,大于 8 的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现 key 已经存在直接覆盖 value即可;
- 插入成功后,判断实际存在的键值对数量 size 是否超多了最大容量,如果超过,进行扩容。
HashMap 的扩容机制
JDK 1.7 扩容机制
- 生成新数组;
- 遍历老数组中的每个位置上的链表上的每个元素;
- 获取每个元素的 key,并基于新数组长度,计算出每个元素在新数组中的下标;
- 将元素添加到新数组中去;
- 所有元素转移完之后,将新数组赋值给 HashMap 对象的 table 属性。
JDK 1.8 扩容机制
- 生成新数组;
- 遍历老数组中的每个位置上的链表或红黑树;
- 如果是链表,则直接将链表中的每个元素重新计算下标,并添加到新数组中去;
- 如果是红黑树,则先遍历红黑树,先计算出红黑树中每个元素对应在新数组中的下标位置;
- 统计每个下标位置的元素个数:如果该位置下的元素个数超过了 8,则生成一个新的红黑树,并将根节点添加到新数组的对应位置。如果该位置下的元素个数没有超过 8,那么则生成一个链表,并将链表的头节点添加到新数组的对应位置;
- 所有元素转移完了之后,将新数组赋值给 HashMap 对象的 table 属性。
HashMap 为什么是线程不安全的? 如何实现线程安全
为什么是线程不安全的
主要原因是它的操作不是原子的,即在多个线程同时进行读写操作时,可能会导致数据不一致性或抛出异常.
- 并发修改:当一个线程进行写操作(插入、删除等)时,另一个线程进行读操作,可能会导致读取到不一致的数据,甚至抛出 ConcurrentModificationException 异常。
- 非原子性操作:HashMap 的一些操作不是原子的,例如,检查是否存在某个键、获取某个键对应的值等,这样在多线程环境中可能发生竞态条件。
如何实现线程安全
为了实现线程安全的 HashMap,有以下几种方式:
- 使用 Collections.synchronizedMap() 方法:可以通过 Collections.synchronizedMap() 方法创建一个线程安全的 HashMap,该方法返回一个同步的 Map 包装器,使得所有对 Map 的操作都是同步的。
- 使用 ConcurrentHashMap:ConcurrentHashMap 是专门设计用于多线程环境的哈希表实现。它使用分段锁机制,允许多个线程同时进行读操作,提高并发性能。
- 使用锁机制:可以在自定义的 HashMap 操作中使用显式的锁(例如 ReentrantLock)来保证线程安全。
ConcurrentHashMap 如何保证线程安全
- ConcurrentHashMap 在 JDK 1.7 中使用的数组加链表的结构,其中数组分为两类,大树组 Segment 和小数组 HashEntry,ConcurrentHashMap 的线程安全是建立在 Segment 加 ReentrantLock 重入锁来保证。
- ConcurrentHashMap 在 JDK1.8 中使用的是数组+链表+红黑树的方式实现,它是通过 CAS 或者 synchronized 来保证线程安全的,并且缩小了锁的粒度,查询性能也更高。
HashMap 和 ConcurrentHashMap 的区别
- 线程安全性:
- HashMap 不是线程安全的。在多线程环境中,如果同时进行读写操作,可能会导致数据不一致或抛出异常。
- ConcurrentHashMap 是线程安全的,它使用了分段锁(Segment Locking)的机制,将整个数据结构分成多个段(Segment),每个段都有自己的锁。这样,不同的线程可以同时访问不同的段,提高并发性能。
- 同步机制:
- HashMap 在实现上没有明确的同步机制,需要在外部进行同步,例如通过使用 Collections.synchronizedMap() 方法。
- ConcurrentHashMap 内部使用了一种更细粒度的锁机制,因此在多线程环境中具有更好的性能。
- 迭代时是否需要加锁:
- 在 HashMap 中,如果在迭代过程中有其他线程对其进行修改,可能抛出 ConcurrentModificationException 异常。
- ConcurrentHashMap 允许在迭代时进行并发的插入和删除操作,而不会抛出异常。但是,它并不保证迭代器的顺序,因为不同的段可能会以不同的顺序完成操作。
- 初始化容量和负载因子:
- HashMap 可以通过构造方法设置初始容量和负载因子。
- ConcurrentHashMap 在 JDK 8 及之后版本中引入了 ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) 构造方法,允许设置初始容量、负载因子和并发级别。
- 性能:
- 在低并发情况下,HashMap 的性能可能会比 ConcurrentHashMap 稍好,因为 ConcurrentHashMap 需要维护额外的并发控制。
- 在高并发情况下,ConcurrentHashMap 的性能通常更好,因为它能够更有效地支持并发访问。
总的来说,如果需要在多线程环境中使用哈希表,而且需要高性能的并发访问,通常会选择使用 ConcurrentHashMap。如果在单线程环境中使用,或者能够手动进行外部同步管理,那么 HashMap 可能是更简单的选择。
HashSet 和 HashMap 的区别
HashMap 适用于需要存储键值对的情况,而 HashSet 适用于只关心元素唯一性的情况。在某些情况下,可以使用 HashMap来模拟 HashSet 的行为,只使用键而将值设为固定的常量。
- 使用
- HashMap 用于存储键值对,其中每个键都唯一,每个键关联一个值。
- HashSet 用于存储唯一的元素,不允许重复。
- 内部实现:
- HashMap 使用键值对的方式存储数据,通过哈希表实现。
- HashSet 实际上是基于 HashMap 实现的,它只使用了 HashMap 的键部分,将值部分设置为一个固定的常量。
- 元素类型:
- HashMap 存储键值对,可以通过键获取对应的值。
- HashSet 存储单一元素,只能通过元素本身进行操作。
- 允许 null:
- HashMap 允许键和值都为 null。
- HashSet 允许存储一个 null 元素。
- 迭代方式:
- HashMap 的迭代是通过迭代器或增强型 for 循环遍历键值对。
- HashSet 的迭代是通过迭代器或增强型 for 循环遍历元素。
- 关联关系:
- HashMap 中的键与值是一一对应的关系。
- HashSet 中的元素没有关联的值,只有元素本身。
- 性能影响:
- HashMap 的性能受到键的哈希分布和哈希冲突的影响。
- HashSet 的性能也受到元素的哈希分布和哈希冲突的影响,但由于它只存储键,通常比 HashMap 的性能稍好。
HashMap 和 HashTable 的区别
- 同步
Hashtable 是同步的,即它的方法是线程安全的。这是通过在每个方法上添加同步关键字来实现的,但这也可能导致性能下降。
HashMap 不是同步的,因此它不保证在多线程环境中的线程安全性。如果需要同步,可以使用 Collections.synchronizedMap() 方法来创建一个同步的 HashMap。
- 性能
- 由于 Hashtable 是同步的,它在多线程环境中的性能可能较差。
- HashMap 在单线程环境中可能比 Hashtable 更快,因为它没有同步开销。
- 空值
- Hashtable 不允许键或值为 null。
- HashMap 允许键和值都为 null。
- 继承关系
Hashtable 是 Dictionary 类的子类,而 HashMap 是 AbstractMap 类的子类,实现了 Map 接口。
- 迭代器
- Hashtable 的迭代器是通过 Enumerator 实现的。
- HashMap 的迭代器是通过 Iterator 实现的。
- 初始容量和加载因子
- Hashtable 的初始容量和加载因子是固定的。
- HashMap 允许通过构造方法设置初始容量和加载因子,以便更好地调整性能。