Map集合

Alan2023-07-202023-10-19

一、Java常用的集合、分类、涉及到的接口

	List	Set	Map	Queue
定义	一个有序集合，允许重复元素	一个无序集合，不允许重复的元素	由键值对组成的集合，键和值可以都是任意对象	一种特殊的集合，按照特定规则进行元素插入和明除
存储	以索引方式维护元素顺序	不维护元素顺序	使用键值唯一标识和访问值	依据某种策略保持元素顺字
可重复性	允许重复元素	不允许重复元素	键不允许重复，值允许重复	允许重复元素
实现类	ArrayList、LinkedList、Vetcor等	HashSet、LinkedHashSet、TreeSet等	HashMap、LinkedHashMap、TreeMap等	LinkedList、PriorityQueue等
遍历	可使用索遍历或者使用迭代器遍历	可以使用迭代器遍历	可以通过键或Entry遍历	通常按照特定顺序遍历
查找	根据索引位置或具体元素进行查找	根据元素进行查找	通过键查找值，可以使用containsKey和containsValue方法	通常按照某种策略进行查找
应用场景	需要按照顺序存储元素，可能存在重复元素的情况	需要保证元素的唯一性，不关心元素顺序	需要通过键值对来存储和访问数据	需要按照特定规则进行元素插入和删除，如任务调度等

Collection接口： Collection 是集合 List、 Set、 Queue 的最基本的接口。

List（列表）：按照元素插入的顺序保存元素，允许重复元素。常见的有ArrayList、LinkedList等。
Set（集合）：不允许重复元素的无序集合。常见的有HashSet、TreeSet等。
Queue（队列）：按照先进先出（FIFO）的原则进行元素操作的集合。常见的有ArrayDeque、PriorityQueue等。

Map接口：是映射表的基础接口

Map（映射）：存储键值对（key-value）的集合，根据唯一的键来查找和访问值。常见的有HashMap、TreeMap等。

Iterator接口：迭代器，可以通过迭代器遍历集合中的数据

Java中的所有集合类都实现了Iterator接口。Iterator接口是Java集合框架提供的一种用于遍历集合元素的通用方式。它定义了一系列用于访问集合元素的方法，包括判断是否还有下一个元素、获取下一个元素、删除当前元素等操作

二、 HashMap底层原理

1. JDK1.8之前

HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法换句话说使用扰动函数之后可以减少碰撞。

2. JDK1.8及以后**

相比于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

总结：HashMap在JDK1.7使用的是数组+链表的结构，在哈希冲突时通过链表进行解决；而JDK1.8引入了红黑树的概念，当链表长度超过一定阈值时，链表会转换成红黑树，以提高查询效率。

三、HashMap为什么用红黑树不用B树

HashMap 使用红黑树（Red-Black Tree）而不是 B 树的主要原因是效率和复杂度。

效率：红黑树相对于 B 树，在插入、删除和查找操作上具有更好的平均性能。红黑树的平衡性质可以保证树的高度相对较小，从而减少了搜索的路径长度，提高了操作的效率。
复杂度：B 树是一种多路搜索树，节点可以包含多个关键字和指针，适合用于磁盘存储等场景，可优化磁盘 IO 操作。然而，在内存中的数据结构中，红黑树的实现更为简单，代码的复杂度较低。同时，红黑树的性能在典型的 HashMap 使用场景中通常表现出良好的性能。

另外，HashMap 维护了一个哈希表和一个链表或红黑树的混合结构（JDK8 之后），当发生哈希冲突时，会使用链表或红黑树来处理冲突。链表适合处理冲突较少的情况，而红黑树则适合处理冲突较多的情况。红黑树相对于链表具有更高的查找效率，因此在冲突较多的情况下能够提供更好的性能。

总之，HashMap 使用红黑树而不是 B 树主要是出于对效率和复杂度的考虑。红黑树在内存中的实现更简单，对于典型的 HashMap 使用场景能够提供良好的性能，且适用于处理冲突较多的情况。

总结HashMap使用红黑树而不是B树，是因为红黑树相对于B树在插入、删除和查找等操作上的平衡性能更好，且红黑树的节点比B树的节点更小，占用的内存更少，适合存储在内存中的数据结构。

四、、HashMap什么时候扩容

在JDK1.7中，当HashMap中元素数量超过当前容量与负载因子（默认为0.75）的乘积时，会触发扩容操作，扩容后的容量为当前容量的两倍。例如，初始容量为16，当元素数量达到12时会触发扩容，扩容后的容量为32。
在JDK 1.8中，HashMap的扩容和红黑树转换是两个独立的操作，且顺序是先扩容，然后再进行红黑树的转换。当HashMap中的元素数量超过负载因子（默认为0.75）与数组容量的乘积时，会触发扩容操作。扩容会重新调整数组的大小，并将原来数组中的元素重新分配到新的数组位置上。扩容操作会导致原本哈希冲突较多的链表长度变长，因此当链表长度超过阈值（默认为8）时，会将链表转化为红黑树。综上所述，在JDK 1.8中，HashMap的操作顺序是先扩容，然后再进行红黑树的转换。扩容是为了减少哈希冲突，提高HashMap的性能和效率，而链表转红黑树的操作则是为了在特定情况下提供更好的查找、插入和删除元素的性能。

五、HashMap的长度为什么是 2的 N 次方

为了能让 HashMap 存数据和取数据的效率高，尽可能地减少 hash 值的碰撞，也就是说尽量把数

据能均匀的分配，每个链表或者红黑树长度尽量相等。我们首先可能会想到 % 取模的操作来实现。

**下面是回答的重点哟：**

取余（%）操作中如果除数是 2 的幂次，则等价于与其除数减一的与（&）操作（也就是说hash % length == hash &(length - 1) 的前提是 length 是 2 的 n 次方）。并且，采用二进制位操作 & ，相对于 % 能够提高运算效率。

这就是为什么 HashMap 的长度需要 2 的 N 次方了

总结：HashMap的长度选择为2的N次方是为了提高散列算法的效率和分布均匀性，通过使用2的幂次方作为长度，可以确保哈希码的高位和低位可以均匀参与到散列计算中，减少哈希冲突的发生，并提高散列算法的效率和性能。

六、HashMap和HashTable区别

	HashMap	HanhTable
线程安全性	非线程安全	线程安全
空键和空值	允许空键和空值	不允许空键和空值
底层实现	数组+链表/红黑树（JDK1.8+）	数组+链表

线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用ConcurrentHashMap 吧！）；

对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。

效率： 因为线程安全的问题，HashMap 要比Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它；

初始容量大小和每次扩充容量大小的不同： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。

底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

总结：HashMap是非线程安全的、允许空键和空值，并使用数组+链表/红黑树底层实现；HashTable是线程安全的、不允许空键和空值，并使用数组+链表底层实现。

七、ConcurrentHashMap和HashMap的区别

特性	ConcurrentHashMap	HashMap
线程安全	高度线程安全，支持并发读写操作	非线程安全，不支持并发读写慢作
锁策略	分段锁机制(Segment)	无锁
性能	在高并发环境下，读写操作性能较好	在单线程或低并发情况下性能较好
扩容机制	动志扩容，可以同时进行读写操作	扩容时需要暂停所有操作
允许null键值	允许存储null键和null值	允许存储一个null键和多个null值
迭代器致性	提供弱一致性保证，允许迭代器在遍历过程中可能看到插入、更新和删除操作后的结果	提供强一致性保证，确保迭代器在遍历过程中不会抛出ConcurrentModificationException异常
继承关系	实现了ConcurrentMap接门，并继承自AbstractMap	继承自AbstractMap

ConcurrentHashMap和HashMap是Java中常用的两种Map实现，它们之间有以下几个区别：

1. 线程安全性：ConcurrentHashMap是线程安全的，多个线程可以同时对其进行读写操作而不需要额外的同步措施；而HashMap是非线程安全的，如果多个线程同时对其进行读写操作，可能会导致数据不一致或抛出异常。

2. 锁粒度：ConcurrentHashMap通过分段锁（Segment）实现并发访问的高效性。相比之下，HashMap只能通过全局锁来保证线程安全性，因此在并发场景下性能较低。

3. 迭代器弱一致性：ConcurrentHashMap的迭代器是弱一致的，即在迭代过程中可以容忍在迭代开始时已有的修改和在迭代期间的新增修改。HashMap的迭代器在迭代过程中如果发生结构性修改（例如增加或删除元素），会抛出ConcurrentModificationException异常。

4. 初始容量和扩容机制：ConcurrentHashMap在初始化时可以指定并发级别和初始容量，可以通过合理设置参数来提高并发访问的效率。而HashMap默认的初始容量较小，加载因子较大，在元素数量达到一定阈值时会触发扩容操作，而扩容操作比较耗时。

5.**null值和null键：**ConcurrentHashMap中既不允许存储null值，也不允许存储null键；而HashMap允许存储一个null值和多个null键。

总体来说，ConcurrentHashMap适用于高并发的场景，能够提供更好的性能和线程安全性；而HashMap适用于单线程环境或者在已知不存在并发访问的情况下。选择使用哪种Map实现要根据具体的需求和场景进行权衡。

总结：ConcurrentHashMap是线程安全的并发哈希表，支持高效地并发访问，而HashMap是非线程安全的哈希表，适用于单线程环境下的使用。

八、ConcurrentHashMap和HashTable区别，他们如何保证线程安全

特性	ConcurrentHashMap	HashTable
线程安全	高度线程安全，支持并发读与操作	线程安全，支持并发读与操作
锁策略	分段锁机制 (Segment)	互斥锁 (synchronized)
性能	在高并发环境下，读写操作性能较好	在低并发或无并发的情况下性能较好
扩容机制	动态扩容，可以同时进行读写操作	扩容时需要暂停所有操作
允许null键值	允许存储null过和null值	不允许存储nult和null值
迭代器弱一致性保证	提供弱一致性保证，允许选代器在遍历过程中可能石到插入、更新和删除操作后的结果	提供强一致性保证，确保选代器在遍历过程中不会抛出ConcurrentModificationException异常
继承关系	实现了ConcurrentMap接口，并继承自AbstractMap	继承自Dictionary类，已被推荐使用ConourrentHashMap替代

底层数据结构：

JDK1.7 的 ConcurrentHashMap 底层采用分段的数组+链表实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。

Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；

实现线程安全的方式（重要）：

在 JDK1.7 的时候，ConcurrentHashMap（分段锁）对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后对 synchronized 锁做了很多优化）整个看起来就像是优化过且线程安全的HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；

Hashtable(同一把锁) : 使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

总结：ConcurrentHashMap和HashTable的区别在于并发性和线程安全性，ConcurrentHashMap利用分段锁（Segment）实现高效的并发访问和更新，而HashTable使用全局锁（synchronized）来保证线程安全。

九、ArrayList与LinkedList区别

特性	ArrayList	LinkedList
底层数据结构	数组	链表
查询时间复杂度	O(1)	O(n)
插入/删除时间复杂度	在未尾: 平均O(1)，最坏O(n)	在任意位置: O(1)
内存占用	相对较少	相对较多
随机访问	优化较好	不支持
迭代器遍历	高效	比较低效
数据元素顺序	按插入顺序保存	按插入顺序保存

是否保证线程安全： ArrayList 和LinkedList 都是不同步的，也就是不保证线程安全；

底层数据结构： Arraylist 底层使用的是Object 数组；LinkedList 底层使用的是双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）

插入和删除是否受元素位置的影响：

ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候，ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
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 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。

内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

时间复杂度：

对于ArrayList：查询单个元素的时间复杂度为O(1)，即常数时间。由于ArrayList使用了数组来存储元素，每个元素都可以通过索引直接访问，因此根据索引获取元素的操作非常高效。

对于LinkedList：查询单个元素的时间复杂度为O(n)，即线性时间。由于LinkedList是基于链表实现的，每个元素只能通过遍历链表来找到目标元素，因此随着链表长度的增加，查询操作需要遍历更多的元素，导致时间复杂度增加。

总结：ArrayList基于数组实现，适合随机访问但插入/删除效率低；LinkedList基于链表实现，适合频繁的插入/删除操作但访问元素效率较低。