目录
Set
在Java中，Set是一种不包含重复元素的集合，它继承了Collection接口。Set用于存储无序（存入和取出顺序不一定相同）的元素，值不能重复。对象是否相等的本质就是根据对象的hashCode值（Java是根据对象的内存地址计算出的此序号）来进行判断的，如果想让两个不同的对象视为相等的，就必须重写Object类的hashCode()和equals()方法。Java中常见的Set实现类主要有HashSet、LinkedHashSet和TreeSet。
hashCode方法和equals方法
hashCode()方法的返回值是一个整数，将其称为哈希码，哈希码用于在哈希表中快速查找对象，Object类中默认的hashCode方法的实现是返回根据对象内存地址转换成的整数。
equals()方法的返回值是true或者false，它是用来判断两个对象的内容是否相等，Object类的默认实现比较的是两个对象的引用是否相等。
为了确保哈希表中的对象行为是正确的，Java定义了一套hashCode方法和equals方法的规范：
· 当两个对象使用equals方法进行比较的返回值是true时，两个对象的hashCode方法的返回值必须相等，必须是相同的整数；
· 当两个对象使用equals方法进行比较的返回值是false时，两个对象的hashCode方法的返回值可以相等也可以不相等，但两个对象返回不同的哈希码时，可以提高哈希表的性能。
· 在程序执行期间，只要对象的状态没有改变，hashCode方法的返回的整数值应该是一致的，也就是说同一个对象多次调用hashCode方法应该得到相同的返回值。
由于Java对于hashCode方法和equals方法定义的这一套规范，因此在重写equals方法时必须重写hashCode方法，以确保两个相同的对象具有相同的哈希码。如果只重写equals方法而不重写hashCode方法可能会导致在哈希表中插入、查找和删除对象时出现问题。
常见的Set实现类
Java中常见的Set实现类有HashSet、LinkedHashSet、TreeSet。
· HashSet：HashSet是Set的一个实现类，它基于哈希表实现，具有快速插入、删除和查找的操作。HashSet不保证元素的迭代顺序，允许null值存在，但只能有一个null元素，它不是线程安全的，如果多个线程同时访问或修改HashSet，需要在外包进行同步操作。当使用HashSet存储自定义对象时，需要重写hashCode()方法和equals()方法，以确保对象的唯一性。HashSet插入/删除/查找的时间复杂度是O(1)，它在插入/删除/查找时首先根据key计算哈希地址，然后进行插入和删除操作。
· LinkedHashSet：LinkedHashSet是HashSet的子类，它是基于哈希表和双向链表实现，既继承了HashSet类又基于LinkedHashMap来实现的。可以维护元素的插入顺序，相较于HashSet增加了顺序性。其主要是将元素按照插入的顺序进行迭代，同时继承了HashSet的所有特性。因此当需要保持元素插入顺序时，可以选择使用LinkedHashSet。
· TreeSet：TreeSet是Set接口的另一个实现类，它是基于红黑树实现的，可以对元素进行自定义排序和自然排序（升序）。TreeSet也是线程不安全的，其不允许null值存在。当存储自定义对象时，如果想要对其进行排序就需要实现Comparable接口并重写CompareTo方法，或提供自定义的Comparator对象来进行排序。TreeSet插入/删除/查找的时间复杂度是O(log2N)，它插入/删除/查找的方式是按照红黑树的特性进行的。
HashSet适用于需要快速查找，对元素顺序要求不高的场景；LinkedHashSet适用于需要保持元素插入顺序的场景；TreeSet适用于需要对元素进行排序的场景。
HashSet的底层原理
HashSet是Java中一个常用的集合类，它用于存储不重复的元素，其底层实现依赖于HashMap。
基本结构
HashSet底层使用HashMap来存储元素，具体来说，当我们在HashSet中插入元素时，这个元素实际上是作为HashMap的key来存储的，其value是是一个固定的常量对象。
添加元素(add方法)
当调用HashSet的add方法时，HashSet会将该元素作为键插入到HashMap中，其值是一个常量对象PRESENT。HashMap的put方法会检查键是否已经存在，如果不存在则插入新键值对。如果键已经存在，则更新键值对并返回旧值。因此，HashSet能够保证元素唯一性。
元素查找(contains方法)
HashSet的contains方法其实是调用HashSet的containsKey方法，HashMap的containsKey方法通过计算键的hashCode值来快速定位元素的位置，再进行比较。
删除元素(remove方法)
HashSet的remove方法也是调用HashMap的remove方法来删除元素的。
Map
Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap等。Map中存放的是键值对，其中键是唯一的，但是值可以重复。
HashMap
HashMap是Map的一个实现类，主要存放键值对，它是基于哈希表实现的，可以进行快速的查找、删除、插入操作。HashMap不是线程安全的，如果有多个线程同时操作HashMap需要在外部对其进行同步操作。HashMap允许存在一个null的键和多个null的值，它不保证映射顺序，特别是它不保证随着时间的推移其顺序不会发生改变。HashMap提供了时间复杂度为O(1)的基本操作(例如get和put方法)，但前提是哈希函数的分布良好且冲突较少。
工作原理
HashMap使用哈希表来存储数据，哈希表是基于数组和链表的组合。
· 哈希函数：HashMap使用键的hashCode()方法来计算哈希值，然后将哈希值映射到数组的索引位置。
· 数组和链表：HashMap使用一个数组来存储链表或树结构(树结构是jdk1.8之后有的)，每个数组位置被称为一个“桶”，每个桶存储链表或树。
· 冲突处理：当两个键的哈希值相同时，它们会被存储在同一个桶中，形成一个链表(或树)，这种情况被称为哈希冲突。
· 再哈希：当HashMap中的元素数量超过容量的负载因子(默认0.75)时，HashMap会进行再哈希，将所有元素重新分配到一个更大的数组中。
计算hashCode()值与扰动函数
HashMap使用键的hashCode()值来生成哈希码，并对其进行扰动函数处理，以提高哈希表的性能和均匀分布。下图为计算哈希值的源码。
由源码可知，首先根据键的hashCode()方法获得一个整数类型的哈希码，之后再将这个哈希码与哈希码右移16位后得到的结果进行异或运算，得到最终的哈希值。这里对原始哈希码进行一些额外处理的行为就称为扰动函数。
扰动函数的目的是为了提高哈希码的质量，使其在哈希表中更均匀的分布。它的存在可以减少哈希冲突，通过将高位和低位混合，扰动函数减少了哈希码的模式性，降低了哈希冲突的概率；可以使哈希码在哈希表中均匀分布，扰动后的哈希码更加均匀的分布在哈希表的桶中，从而提高了哈希表的性能。
例如，一个键对象的hashCode()返回值是123456，通过哈希函数计算器哈希值。首先调用key.hashCode()方法得到哈希值h为123456，之后再进行扰动函数计算int hash = h ^ (h >>> 16);
具体计算过程如下：
①123456的二进制位11110001001000000；
②对其右移16位，则 h >>> 16 等于1；
③11110001001000000 与 1 进行异或运算，得到的结果为11110001001000001，即123457.
HashMap的容量扩充(2的幂次)
在HashMap中，初始化设置长度时，会自动转换成2的幂次长度，这样做的目的是为了：高效计算索引、减少哈希冲突、简化扩容、内存对齐和效率。
· 高效计算索引：HashMap使用哈希值来确定键值对在哈希表中的位置，HashMap使用按位与的方式替代了取模运算以提高效率，具体代码为 int index = (n - 1) & hash；
· 减少哈希冲突：在哈希表中，哈希冲突是一个主要问题。哈希冲突发生时，不同的键计算出的索引相同，导致它们被存储在同一个桶中。通过将容量设置为 2 的幂次，哈希表能够更均匀地分布哈希值，减少冲突。当容量是 2 的幂次时，哈希值的低位和高位都能均匀地影响最终索引。这是因为扰动函数hash = h ^ (h >>> 16)将高位和低位混合在一起，使得哈希值的分布更均匀。
· 简化扩容：HashMap在进行扩容时，通常会将容量加倍。如果容量是2的幂次，那么扩容后也是2的幂次，这样可以简化扩容过程中的计算和重新哈希操作。
· 内存对齐和效率：计算机内存分配通常更高效地处理 2 的幂次大小的内存块。使用 2 的幂次长度可以更好地利用内存对齐，提高内存访问效率。
当我们初始化HashMap时，我们指定的容量会被自动转换为大于或者等于指定容量的最小的2的幂次。例如我们指定初始容量为15，那么会自动转换为16。此处n = cap - 1操作是为了保证当传入的数是2的幂次时，得到的结果就是指定的数4，如果不进行 - 1操作，那么得到的值会是8.
当HashMap的大小超过了负载因子定义的容量时，HashMap会进行扩容操作(resize)。假设当前HashMap的容量是A，其负载因子是B，当插入的键值对数量超过A * B时，就会进行扩容操作，扩容的具体步骤：
· 计算新的容量：新的容量通常是当前容量的两倍。
· 创建新的桶数组：根据新的容量创建一个新的桶数组。
· 重新哈希所有的键值对：对旧桶数组中的所有键值对重新计算哈希值，并将它们放入新的桶数组中。这一步是必要的，因为哈希值是基于数组长度计算的，数组长度改变后，哈希值也需要重新计算。
HashMap的主要参数
· 初始容量：初始容量是HashMap在创建时分配的桶数组的大小，如果在创建HashMap时不指定初始容量，其默认是16.
· 负载因子：负载因子是一个衡量HashMap什么时候需要扩容的参数，默认的负载因子是0.75，也就是说当HashMap中存储的键值对数量达到当前容量的75%时就会出发扩容机制。负载因子越多，哈希表中空闲位置越多，负载因子越高，哈希表中存放的数据越多。
· 阈值：阈值是HashMap需要扩容的临界点，计算方式为初始容量 * 负载因子。当实际存储的键值对数量超过这个阈值时，HashMap会进行扩容。
· 红黑树转换阈值：当单个桶中的链表长度超过这个阈值时，就会将链表结构转换为红黑树结构，默认阈值是8。但转换为红黑树必须是单个桶的链表长度超过8，且整个哈希表中的键值对数量超过64。
· 最小树化容量：当HashMap的容量小于这个值时，即使链表长度超过Treeify Threshold，也不会将链表转换为红黑树，而是会先进行扩容。默认值是 64。
· 扩容因子：当HashMap的大小超过阈值时，容量会加倍。即新的容量是旧容量的两倍。
· 版本（modCount）：HashMap维护了一个内部版本号modCount，用于跟踪HashMap的结构修改次数。这在迭代器中用于检测并发修改。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于等于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于等于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是2的幂次倍
transient Node<k,v>[] table;
// 一个包含了映射中所有键值对的集合视图
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 阈值(容量*负载因子) 当实际大小超过阈值时，会进行扩容
int threshold;
// 负载因子
final float loadFactor;
}哈希碰撞的解决方法
· 链地址法：链地址法是最常见的解决哈希冲突的方法之一。在这种方法中，每个桶包含一个链表（或者树结构jdk1.8以上版本）。当发生哈希碰撞时，新的键值对被添加到相应桶的链表中。该方法的优点是简单易实现、可以动态调整链表长度，不需要提前知道元素数量；缺点是当链表长度过长时，查找效率会变低，需要额外的存储空间来存储指针。
· 开放地址法：开放地址法不使用链表，而是在哈希表中寻找空闲的位置来存储冲突的键值对，常见的开放地址法有：线性探测法、二次探测法、双重散列法、再哈希法等。
①线性探测法：线性探测法即当发生哈希冲突时，线性探测法在哈希表中向后依次寻找下一个空闲的位置。其优点是不需要额外的存储空间，实现简单；缺点是当哈希表接近满时，查找效率非常低（称为“主群集问题”）。
②二次探测法：二次探测法在发生哈希碰撞时，按照平方序列查找空闲位置（如 1, 4, 9, 16, ...）。其优点是解决了线性探测法当哈希表接近满时，查找效率非常低的问题；缺点是实现较为复杂，可能会导致二次群集问题。
③双重散列法：双重散列法使用两个不同的哈希函数，当第一个哈希函数发生碰撞时，使用第二个哈希函数计算新的索引。其优点是减少了群集问题，有较好的查找性能；缺点是实现复杂，需要设计两个有效的哈希函数。
HashMap如何解决哈希冲突
HashMap的扩容主要发生在两种情况下：
· 当添加元素时，如果当前数组为空，会进行初始化：默认情况下，会创建一个长度为16的数组，并且负载因子默认为0.75；
· 当数组中的元素数量大于或等于数组长度与负载因子的乘积时，会触发扩容机制，扩容操作会将数组的长度翻倍，即初始容量若为16，扩容后的容量就是32，并且重新哈希原数组中的所有元素到新的数组中。
哈希冲突是指不同的键计算得到了相同的哈希值，从而在哈希表中映射到同一个位置。HashMap通过以下策略解决哈希冲突：
· 链表法（链表或红黑树）：在HashMap中，每个位置(索引)可以存储一个链表(或红黑树)。当发生哈希冲突时，新的元素会被添加到对应的链表中。在JDK1.8之后，默认情况下当链表的长度达到8，且HashMap中存储的键值对数量达到64时会转换为红黑树，以优化性能。
· 哈希函数：为了降低哈希冲突的概率，HashMap使用了一个精心设计的哈希函数来计算键的哈希值（首先根据键获取到hashCode方法后得到的哈希码h，之后将h右移16位，右移后的哈希码与h进行异或运算，得到最终的哈希值）。这种设计可以保证哈希码可以更均匀地分布，减少冲突的可能性。
· 初始容量和负载因子：初始容量和负载因子有可能会影响哈希冲突的概率。较大的初始容量和较小的负载因子可以降低哈希冲突的概率，但也会增加空间开销。因此，在选择这些参数时需要根据具体需求进行权衡。
HashMap在jdk1.7和jdk1.8的区别
数据结构
JDK1.7中HashMap的数据结构主要由数组和链表组成，每个数组的元素是链表的头结点；链表主要是在发生哈希冲突时将冲突的键值对数据存储在对应索引位置的链表中。
JDK1.8中HashMap的数据结构由数组、链表、红黑树组成，当链表中结点个数超过8，且HashMap中存储的键值对个数超过64时，会将链表结构转换为红黑树结构。
存储过程
JDK1.7的实现中，当向HashMap存储一个键值对时，首先通过键的hashCode()方法得到哈希值并进一步处理以减少哈希冲突；通过哈希值确定数组索引位置；之后插入结点，如果索引位置为空则直接插入，不为空则需要处理哈希冲突。
在JDK1.8中，对于hashCode方法得到的哈希值进行处理时所采用的扰动函数方式更简洁性能更高，其他方式与JDK1.7一致。
处理哈希冲突
在 JDK1.7 中，HashMap通过链表法处理哈希冲突。当多个键的哈希值映射到同一个数组索引时，这些键值对会被存储在该索引位置的链表中。插入时，新节点会被插入到链表的头部。
在JDK1.8中，处理哈希冲突的方法有了显著改进。首先，当冲突的结点较少时(链表长度小于等于8，HashMap中存储的键值对数量小于等于64时)，则使用链表存储。链表的插入操作是尾插法，以保持插入顺序。当链表长度大于8，HashMap存储的键值对数量大于64时，会将链表的结构转换为红黑树的结构。红黑树是一种自平衡的二叉搜索树，其查找、插入和删除操作的时间复杂度为O(log2 n)，相比链表的O(n)更高效。
取值过程
在JDK1.7中，取值时，通过键计算哈希值和数组索引，然后在链表中查找对应的键值对。
在JDK1.8中，取值时，HashMap会先计算哈希值，然后找到对应的数组位置。如果该位置存储的是链表，则遍历链表查找；如果是红黑树，则在树中查找。
ConcurrentHashMap
ConcurrentHashMap 是 Java 中一种高效的线程安全哈希表，主要用于在多线程环境下进行高并发的读写操作，不允许存在null值和null键。以下是 ConcurrentHashMap 的主要原理和机制：
分段锁机制
在JDK1.7及之前的版本，ConcurrentHashMap采用了分段锁机制来实现高并发性。
分段锁：ConcurrentHashMap将整个哈希表分成了多个段(Segment)，每个段维护一个独立的哈希表和锁。这样在不同段上的操作就可以并发进行，从而提高并发度。
锁粒度：锁粒度是指一次加锁操作所覆盖的数据范围或代码范围的大小。一次加锁操作所覆盖的数据范围或代码范围的大小。
CAS和无锁操作
在JDK1.8之后，ConcurrentHashMap进行了重构，摒弃了分段锁机制，转而采用更加细粒度的锁和无锁机制（CAS操作）。
CAS操作：CAS即Compare And Swap，即比较和交换是一种无锁的原子操作，用于在不加锁情况下实现线程安全。
细粒度锁：在JDK1.8中，ConcurrentHashMap使用了更加细粒度的锁(synchronized和ReentrantLock)，只在必要时锁定特定的桶或结点，从而进一步提高并发性能。
红黑树
为了应对哈希冲突，ConcurrentHashMap在链表长度超过8且存储的键值对元素超过64时，将链表结构转换为红黑树结构以提升性能。
扩容机制
ConcurrentHashMap采用了渐进式扩容机制来避免扩容过程中长时间的全表锁定。渐进式扩容即在扩容过程中，不会一次性地将所有数据迁移到新的哈希表中，而是采用渐进式扩容的方式，在每次插入或删除操作时，逐步迁移部分数据。
读写操作
ConcurrentHashMap的读写操作大部分情况下是无锁的，因为其使用了volatile和CAS操作来保证读取的可见性和一致性。其写入操作需要在必要时使用锁或 CAS 操作来保证线程安全，读操作使用无锁的方式进行查找，性能更高。
jdk1.8的实现相较于jdk1.7实现的好处
更高的并发性能：jdk1.7采用分段锁的机制，而jdk1.8的实现采用了无锁操作和更加细粒度的锁操作，减少了锁的竞争，提高了并发性。
更好的性能：jdk1.8中读操作是无所得，相较于jdk1.7分段锁方式性能更高；而put操作采用了CAS和更加细粒度的锁，提高了插入和更新的性能。
更高效的扩容：jdk1.8的实现采用了更高效的渐进式扩容方法，通过逐步迁移节点和协同扩容机制，提高了扩容时的效率，减少了扩容过程中对性能的影响。
更高效的查找：当链表的长度超过8，存储的键值对的数量超过64时，会将链表转换为红黑树，相较于jdk1.7的实现，具有更高效的查找性能。
TreeMap
TreeMap的特点是：有序性、底层结构是红黑树、不允许null键存在、线程不安全。
· 有序性：TreeMap保证了键的自然顺序（通过Comparable接口）或通过提供的比较器（Comparator）的顺序。
· 红黑树：TreeMap底层使用红黑树来存储键值对，保证了插入、删除、查找等操作的时间复杂度为O(log2 N)。
· 不允许null键存在：TreeMap不允许键为null，但允许值为null。
· 线程不安全：TreeMap不是线程安全的，如果需要在多线程环境中使用，需要通过外部同步机制来保证线程安全。
LinkedHashMap
LinkedHashMap是java集合框架中的一个类，它继承了HashMap，具有哈希表和链表双重特性。LinkedHashMap通过维护一个双向链表来记录键值对的插入顺序或访问顺序。
· 有序性：LinkedHashMap保证了键值对的顺序，可以是插入顺序（默认）或访问顺序（可选）。
· 哈希表和链表结合：通过哈希表实现快速的键值对查找，通过双向链表维护顺序。
· 允许null值和键：允许一个null键和多个null值存在。
· 线程不安全。
不同集合类的比较
HashMap和HashTable的区别
· HashMap是线程不安全的，HashTable是线程安全的
· HashTable不允许键或值为null，HashMap允许存在一个null键和多个null值
· 在大多数情况下HashMap的性能更好，如果在并发场景下可以选择ConcurrentHashMap，效率会比HashTable高很多。
TreeMap和HashMap的区别
· TreeMap保证键的有序性，默认是升序，HashMap不保证元素顺序
· TreeMap是基于红黑树实现的，操作的时间复杂度为O(log2 N)而HashMap是基于哈希表实现的，操作的平均时间复杂度是O(1)
· TreeMap不允许null键存在，但允许null值存在，而HashMap允许存在一个null键和无数个null值
· 插入删除查找操作，TreeMap需要进行元素比较，而HashMap通过哈希函数来计算哈希地址
LinkedHashMap与HashMap的区别
· LinkedHashMap保证键值对的顺序（插入顺序或访问顺序），而HashMap不保证顺序
· LinkedHashMap通过维护链表来记录顺序，因此在插入和删除操作上可能略慢于HashMap
LinkedHashMap与TreeMap的区别
· LinkedHashMap保证插入顺序或访问顺序，而TreeMap保证键的自然顺序或比较器的顺序
· LinkedHashMap基于哈希表实现，操作的平均时间复杂度为 O(1)，而TreeMap基于红黑树实现，操作的时间复杂度为 O(log2 n)