在Java编程中，我们经常需要在一个数据集合中查找特定的元素。如果数据集合很小，这个过程可能很简单，我们可以使用传统的查找方法，例如线性查找或二分查找。但是，如果数据集合很大，这些传统的查找方法可能变得非常耗时，效率很低。
那么有没有一种更快速、更高效的方法来查找元素呢？答案是肯定的，这就是这个数据结构。在本文中，我们将深入探讨的底层原理，了解它是如何工作的，以及为什么它是如此强大和高效的。
目录
1.哈希表
1.1哈希值
1.2哈希表的结构
2.HashMap对哈希表的实现
2.1HashMap的内部类
2.1.1Node类
2.1.2TreeNode类
2.2HashMap的put方法
2.2.1源码
2.3HashMap的get方法
2.3.1源码
2.3.2get方法的时间复杂度
2.4HashMap中的红黑树结构
2.4.1红黑树
2.4.2为什么HashMap不直接使用红黑树
2.4.3为什么选择红黑树而不是二叉搜索树
3.HashMap中的内部机制
3.1哈希冲突的解决
3.2扩容机制
3.2.1为什么HashMap的默认加载因子是0.75
3.2.2为什么采用2倍扩容
3.2.3扩容时元素重新分布的过程
4.HashMap的线程安全问题
4.1HashMap并发环境下的平替：ConcurrentHashMap
4.1.1ConcurrentHashMap的底层实现原理
4.1.2为什么使用synchronized关键字而不是ReentrantLock
4.3为什么ConcurrentHashMap不常见？
5.HashMap的一些相似类
5.1linkedHashMap
5.2HashTable
5.2.1HashTable 和 HashMap的区别
5.2.2HashTable的线程安全
5.2.3ConcurrentHashMap和Hashtable的区别
首先我们要知道HashMap是一种基于哈希表的Map接口的实现，用于存储键值对。在JDK8以前，哈希表是是通过数组加链表来实现的。而在JDK8以及之后，哈希表是是通过数组加链表加红黑树来实现的。 内部维护了一个数组 ，这个数组的每个元素称为桶（bucket）。每个桶中存储一个链表，用于解决哈希冲突。当需要添加一个键值对时，首先计算键的哈希值，然后将这个键值对插入到对应的桶中的链表的末尾。当需要查找一个键值对时，首先计算键的哈希值，然后在对应的桶中的链表中查找该键值对。那么我们的键值对应该放入哪个桶中？数组的下角标如何确定？这里就要引入一个概念叫做哈希值。
哈希值可以理解为对象的整数表现形式，是用hashCode()方法算出来的int类型的整数，该方法定义在Object类中，所有对象都可以调用，默认使用地址值进行计算。然而，一般情况下我们会重写hashCode()方法，利用对象内部的属性来计算哈希值。
注意：
1.如果没有重写hashCode()方法，那么不同对象计算出的哈希值是不同的
2.如果已经重写hashCode()方法，那么不同对象只要属性值相同，计算出的哈希值就是一样的
3.在小部分情况下，不同属性值或者不同地址值计算出来的哈希值也有可能一样，这种情况我们称之为哈希碰撞（也叫哈希冲突）
为什么会有哈希碰撞？我们举个例子，对于int整型变量，它的数据范围从-2^31到2^31+1，合在一起int的值可以有四十多亿种，那么如果我定义五十亿个对象，即使把所有的整型数都用上，也会有哈希值一样的对象，虽然这是个很极端的情况，但也同样说明哈希碰撞是有可能发生的。
对于哈希值的计算过程，
不同数据类型的哈希值的计算方法是不一样的。不同的数据类型可能有不同的属性，因此它们的哈希值的计算方法也会有所不同。
在 Java 中，每个数据类型都有一个默认的 方法，用于计算对象的哈希值。例如，对于整数类型 ，它的 方法直接返回该整数的值。对于字符串类型 ，它的 方法会根据字符串的内容计算哈希值。
对于自定义类，如果没有重写 方法，则会继承 类的默认实现，该实现返回对象的内存地址，这通常不是一个好的哈希值，因为它无法保证不同的对象有不同的哈希值。
因此，对于自定义类，通常需要重写 方法，以便根据对象的内容计算哈希值。常用的做法是将对象的属性组合起来计算哈希值，例如使用乘法散列、除法散列、FNV 哈希等算法。这样可以保证相同的对象有相同的哈希值，不同的对象有不同的哈希值，从而提高哈希表的性能。
如果我们构建一个哈希表并向表中存入数据
1.当哈希表初始化时，会创建一个默认长度16，默认加载因子为0.75的数组，数组名为table。（加载因子后面会讲）
2.根据 数组下角标：int index=(数组长度-1）&哈希值 的公式将数据存入哈希表中。
3.判断数组中当前位置是否是null，如果是null直接存入
4.如果当前计算位置不是null就代表已经有元素了，会调用equals方法来比较二者的属性值
5.如果属性值一样，就认为是重复的元素，不存。如果属性值不一样将元素存入数组，形成链表
从这里开始，新老版本的哈希表就有所不同了，对于将新元素填入已有元素的bucket中的情况，在JDK8以前，会将新的元素添加到数组当中，会把老的元素挂在新元素的下面。JDK8之后会将新元素直接挂在老元素下面，形成链表。
当我们在HashMap中添加键值对时，根据键的哈希值计算出对应的桶的索引，然后将键值对插入到该桶中，如果桶中已经有元素，则遍历链表，查找键是否已经存在。如果键已经存在，则更新对应的值。如果键不存在，则将新的键值对插入到链表的末尾。
注意：
1.当数组中存了数组长度*加载因子个元素时，数组就会扩容成原来的两倍
2.当链表长度>8且数组长度>=64时，当前的列表会自动转化为红黑树，从而提高查找效率（JDK8之后）
3.如果存储的是自定义对象，必须要重写hashCode和equals方法，否则在底层都是用地址值来进行比较和计算，达不到比较属性值的目的。
HashMap 与哈希表最大的区别在于，HashMap 是存储键值对的，用键来判断插入位置，用值来做比较。当向 HashMap 中添加键值对时，首先根据键的哈希值计算出键所在的桶的位置，然后将键值对添加到该桶对应的链表（或红黑树）中。当查询一个键时，也是根据该键的哈希值计算出它所在的桶的位置，然后在该桶对应的链表（或红黑树）中查找该键。
2.1.1Node类
在 中，Node类是HashMap中最重要的内部类之一，它用于表示键值对。每个Node对象包含了一个键、一个值和一个指向下一个Node对象的引用。当HashMap中发生哈希冲突时，会将相同哈希值的键值对存储在同一个位置上，形成一个链表，Node类就是用于表示这个链表中的每个节点的。 类的源码如下：
其中， 字段是键的哈希码， 字段是键， 字段是值， 字段是指向下一个节点的指针。 类实现了 接口，这意味着它可以作为 的键值对来使用。
2.1.2TreeNode类
TreeNode类是Java 8中HashMap中新增的内部类，它用于表示红黑树中的节点。当链表中的元素个数超过8个时，链表就会转换成红黑树，以提高HashMap的效率。
接下来我们来讲解HashMap的put方法的原理。其实与上述哈希表中大致相同，过程如下：
- 根据键的哈希值计算出键在数组中的位置。
- 遍历该位置上的链表（或红黑树），查找是否已经存在该键。
- 如果已经存在该键，用新的值替换旧的值。
- 如果不存在该键，将该键值对添加到链表（或红黑树）的末尾。
- 当链表中的元素个数超过8个且数组长度>=64时，当前链表就会转换成红黑树，以提高put方法的效率。（当元素个数少于6，红黑树又会还原为链表）
2.2.1源码
我们来看看put方法的源码
方法接收一个键和值作为输入，并将其添加到映射中。如果该键已经存在于映射中，则将其关联的值替换为新值，并返回旧值。如果该键不存在于映射中，则将其添加到映射中，并返回 。
方法是 方法的辅助方法，它实际上执行了将键值对添加到映射中的操作。该方法首先检查 数组是否为空，如果为空，则调用 方法创建一个新的数组。然后，该方法计算键的哈希值，并找到与之相关联的节点。如果该节点为空，则将新节点插入到该位置。如果该节点不为空，则遍历链表，直到找到匹配的节点或到达链表的末尾。如果找到匹配的节点，则替换其值。如果找不到匹配的节点，则将新节点添加到链表的末尾。
2.3.1源码
方法接受一个 类型的键作为输入，并返回与之关联的值，如果在映射中找不到该键，则返回 。
方法是一个辅助方法，用于通过给定的键检索与之关联的节点。它首先检查 数组不为 null 且长度大于 0。然后计算键的哈希值，并检索与哈希关联的链表中的第一个节点。如果第一个节点与键匹配，则返回该节点。否则，它会遍历链表，直到找到匹配的节点或到达链表的末尾。如果找不到匹配的节点，则返回 null
2.3.2get方法的时间复杂度
get方法根据key查询的时间复杂度要看key是否发生了哈希冲突，如果没有哈希冲突那么时间复杂度就是O(1)。如果key发生了哈希冲突，且底层采用链表进行存放，此时时间复杂度为O(n)，也就是从链表头部查询到尾部；如果采用红黑树的形式进行存放，时间复杂度为O(logn)
2.4.1红黑树
红黑树（Red-Black Tree）是一种自平衡二叉查找树，它是在计算机科学中使用的一种数据结构，通常用于实现关联数组（Associative Array）和集合（Set）等抽象数据类型。
红黑树的特点是：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色的。
- 每个叶子节点（NIL节点，空节点）是黑色的。
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
通过这些特点，红黑树可以保证在最坏情况下，插入、删除、查找等操作的时间复杂度都是O(log n)，其中n是树中元素的数量。因此，红黑树是一种高效的数据结构，被广泛应用于各种算法和数据处理的场合。
2.4.2为什么HashMap不直接使用红黑树
时间和空间的折中考虑：
在哈希冲突比较小的时候，即使转化为红黑树，在时间复杂度上产生的效果其实也并不是特别大，而且在put的时候效率会降低，因为每次put都要进行红黑树复杂的旋转操作，在空间上每个结点都需要维护更多的一个指针，这就显得有一些得不偿失了。
2.4.3为什么选择红黑树而不是二叉搜索树
二叉树在极端的情况下会变成一个倾斜的结构，像这样：
此时二叉树的查找效率就退化为了和链表一样的O(n)，而红黑树是一种平衡树，可以防止这种退化，而且也没有像其他的完全的平衡二叉树那样有严格的平衡条件，所以插入效率也会更高，所以HashMap选择红黑树既可以避免极端情况下的退化也可以兼顾查询和查找的效率
Hash冲突是由于哈希算法，被计算的数据是无限的，而计算后的结果的范围是有限的，总会存在不同的数据，经过计算之后得到值是一样，那么这个情况下就会出现所谓的哈希冲突。
常见的处理hash冲突的方法有四种：
-
链地址法：在哈希表的每个槽位上，使用链表来存储多个键值对，如果发生哈希冲突，就将新的键值对插入到链表的末尾。这种方法需要额外的空间来存储链表，但可以避免数据丢失。
-
开放地址法：在哈希表的每个槽位上，存储一个键值对，如果发生哈希冲突，就在其他槽位上寻找空闲的槽位来存储键值对。常见的开放地址法有线性探测、二次探测和双重哈希等方法。
-
再哈希法：使用多个哈希函数来计算键值的哈希值，如果第一个哈希函数计算得到的槽位已经被占用，就使用第二个哈希函数来计算槽位，以此类推，直到找到一个空闲的槽位为止。
-
建立公共溢出区：将哈希表中所有的冲突的元素都存储在一个公共的溢出区中，这样就可以避免哈希表的大小限制，但需要额外的空间来存储溢出区。
在HashMap当中我们使用的就是链地址法，使用链表来存储多个键值对，如果发生哈希冲突，就将新的键值对插入到链表的末尾。
HashMap 的扩容机制是在 HashMap 中维护了一个加载因子（load factor），当 HashMap 中元素数量达到数组长度与加载因子的乘积时，就需要对数组进行扩容。默认情况下，HashMap 的装载因子为 0.75，这是一个比较理想的值，可以在时间和空间上取得一个平衡。在 HashMap 中，当元素数量达到一定阈值时，就需要进行扩容操作，以保证 HashMap 的性能。
HashMap 的扩容机制如下：
-
当 HashMap 中的元素数量达到加载因子（load factor）与容量（capacity）的乘积时，就需要进行扩容操作。
-
扩容操作会将 HashMap 的容量翻倍，并重新计算每个元素在新的哈希表中的位置。这个过程需要重新计算每个元素的哈希值，并将它们重新插入到新的哈希表中。如果多个元素的哈希值相同，那么它们会被放置在同一个桶中，形成一个链表。
-
扩容操作会导致 HashMap 中的所有元素重新分布，因此它需要对每个元素进行重新哈希和插入操作，这个过程的时间复杂度是 O(n)，其中 n 是 HashMap 中的元素数量。
-
扩容操作会消耗一定的时间和空间，因此在实际应用中，需要根据具体的场景来选择合适的负载因子和容量，以平衡性能和空间的需求。
3.2.1为什么HashMap的默认加载因子是0.75
的加载因子默认值是0.75，这是因为经验表明，在哈希表中元素的数量达到哈希表大小的3/4时，哈希表的性能最优。具体来说，当加载因子为0.75时，哈希表的性能最优，即：
-
哈希表中元素的数量和哈希表大小之比接近0.75时，哈希表的冲突数量最少，哈希表的性能最优。这是因为当哈希表的装载因子为 0.75 时，哈希表的空间利用率比较高，同时哈希冲突的概率也比较低。这样就可以在不频繁扩容的情况下，保证哈希表的性能和空间利用率都比较好。
-
当哈希表中元素的数量达到哈希表大小的3/4时，哈希表需要进行扩容，这时候扩容后的哈希表大小仍然是2的幂次方，这样可以保证哈希函数的计算仍然可以通过位运算来实现，从而提高哈希表的性能。
因此，的加载因子为0.75是经过实验和优化得出的最优值，可以在大多数情况下提供最佳的性能。
3.2.2为什么采用2倍扩容
当哈希表中元素的数量达到哈希表大小的3/4时，哈希表需要进行扩容，这时候扩容后的哈希表大小仍然是2的幂次方，这样可以保证哈希函数的计算仍然可以通过位运算来实现，从而提高哈希表的性能。
当HashMap的容量是2的n次幂时，(n-1)的2进制也就是1111111***111这样形式的，这样与添加元素的hash值进行位运算时，能够充分的散列，使得添加的元素均匀分布在HashMap的每个位置上，减少hash碰撞。
3.2.3扩容时元素重新分布的过程
在 HashMap 进行扩容操作后，所有元素都需要重新计算哈希值，并重新插入到新的哈希表中。具体来说，元素重新分布的过程如下：
-
创建一个新的哈希表，容量是原来的两倍。
-
遍历原来的哈希表中的每个桶，将桶中的元素重新计算哈希值，并插入到新的哈希表中。
-
如果多个元素的哈希值相同，那么它们会被放置在同一个桶中，形成一个链表。
-
重复步骤 2 和步骤 3，直到遍历完原来的哈希表中的所有桶。
需要注意的是，扩容操作会导致 HashMap 中的所有元素重新分布，因此它需要对每个元素进行重新哈希和插入操作，这个过程的时间复杂度是 O(n)，其中 n 是 HashMap 中的元素数量。因此，在实际应用中，需要根据具体的场景来选择合适的负载因子和容量，以平衡性能和空间的需求。
HashMap在设计的时候是针对单线程环境来设计的，所以HashMap不是线程安全的，这意味着如果多个线程同时访问HashMap，可能会导致不一致的结果或抛出异常。例如，当一个线程正在修改HashMap的结构（例如插入、删除元素）时，另一个线程可能会同时访问HashMap，这可能会导致HashMap的结构发生变化，从而导致不一致的结果或抛出ConcurrentModificationException异常。
是 Java 中的一个线程安全的哈希表实现，它与 类似，但是可以被多个线程同时访问而不需要额外的同步措施。
4.1.1ConcurrentHashMap的底层实现原理
在JDK7，ConcurrentHashMap使用了一种分段锁来保证线程安全，它是将数组分成了16段，也就是给每个segment配一把锁，在读取每个segment的时候就要先获取对应的锁，最多可以有16个线程并发操作。默认情况下， 的段数是 16，可以通过构造函数指定。
在JDK8之后，ConcurrentHashMap也引入了红黑树的结构，在并发处理方面不再使用并发处理方式，而是使用CAS加synchronized关键字，来实现了一种更加细粒度的锁。在写入键值对的时候，可以所著哈希桶的头节点，不会影响其他哈希桶的写入。
CAS 操作是一种无锁算法，它利用了硬件的原子性操作来实现对共享变量的原子操作。在 中，当多个线程同时对同一个元素进行操作时，它们会先获取对应段的锁，然后使用 CAS 操作来保证对元素的原子操作。这样，即使多个线程同时对同一个元素进行操作，也不会出现线程安全问题。
4.1.2为什么使用synchronized关键字而不是ReentrantLock
理论上来讲使用ReentrantLock也是可以的，但是synchronized会更好一点
1.在JDK1.6之后synchronized进行了一些优化，引入了偏向锁，轻量级锁以及重量级锁，这些在ReentrantLock中是没有的。
2. 是 Java 中的内置锁，它的实现非常高效，而且在 Java 中使用广泛，所以使用 可以避免引入额外的依赖。
3.虽然 提供了更多的功能，比如可重入性、公平性等，但是在实现上，它比 更加复杂，而且需要手动释放锁，容易出现死锁等问题。
ps：
-
偏向锁：偏向锁是一种针对加锁操作的优化，它的目标是降低无竞争情况下的锁操作的代价。偏向锁的核心思想是，如果一个线程获得了锁，那么在接下来的一段时间内，它很可能会再次获得该锁。因此，为了避免每次都需要重新竞争锁，JVM 会将这个线程对锁的访问记录下来，称之为偏向。当这个线程再次请求锁时，JVM 会快速判断该线程是否已经获得了锁，如果是，则直接进入临界区，否则再进行锁的竞争。偏向锁只有在无竞争的情况下才会生效。
-
轻量级锁：轻量级锁是一种针对短时间内的加锁操作的优化，它的目标是避免线程的上下文切换和操作系统内核态和用户态之间的切换，从而提高加锁的效率。轻量级锁的核心思想是，当一个线程请求锁时，JVM 会将对象头中的标志位设置为轻量级锁，并将锁对象的指针保存在线程的栈帧中。此时，如果另外一个线程也请求同一个锁，那么它会进入自旋状态，不断尝试获取锁，直到获取到锁或者自旋次数达到一定的阈值。如果自旋成功，那么该线程就可以进入临界区，否则就会进入重量级锁的状态。
-
重量级锁：重量级锁是一种针对长时间占用锁的优化，它的目标是避免线程一直占用 CPU 资源，从而降低系统的整体性能。重量级锁的核心思想是，当一个线程请求锁时，JVM 会将对象头中的标志位设置为重量级锁，并在操作系统层面上挂起该线程，直到锁被释放。当锁被释放时，JVM 会唤醒所有等待该锁的线程，并重新进行锁的竞争。重量级锁的代价比较高，因此只在长时间占用锁的情况下使用。
可重入性（Reentrancy）是指一个线程在持有锁的情况下，可以再次获取同一个锁，而不会被自己所持有的锁所阻塞。也就是说，如果一个线程已经获得了某个锁，那么它可以再次获取该锁，而不必担心自己会被阻塞。
公平性（Fairness）是指多个线程竞争同一个锁时，这些线程被获取到锁的顺序是按照它们发出请求的顺序来进行的。如果一个锁是公平的，那么当多个线程同时请求该锁时，这些线程将按照它们发出请求的顺序来获取到该锁。
既然HashMap是线程不安全的，那为什么我们还在大量的使用HashMap而不使用ConcurrentHashMap呢？
这是因为我们的HashMap的声明基本都是在方法体的内部，而每一个方法体被调用的时候，都属于一个单独的线程，线程不共享变量，就不用考虑线程安全问题，所以并不存在并发问题。只有当我们把HashMap用static关键字修饰，让它变成一个全局的静态变量，在多线程环境里面调用put方法的时候，才有可能出现并发问题，我们使用ConcurrentHashMap才有意义。而声明一个static的map，大部分情况下是当作一个JVM的缓存来用，因为现在有分布式缓存Redis，JVM缓存有caffeine这种中间件，所以不太会用map。
是Java编程语言中的一个类，它扩展了类，并且维护了一个双向链表。与类似，也使用哈希表来存储键值对，但是它还维护了一个双向链表，该链表按照插入顺序存储了所有的键值对。
相比于，的优点和缺点如下：
优点：
-
有序性：维护了一个双向链表，因此可以按照插入顺序或访问顺序迭代元素。这个特性可以用于实现LRU缓存等场景。
-
迭代性能：由于维护了一个双向链表，因此按照插入顺序或访问顺序迭代元素时，性能比更好。
缺点：
-
空间占用：由于维护了一个双向链表，因此它的空间占用比更大。
-
插入和删除性能：由于需要维护双向链表，因此在插入和删除元素时，性能比略差。
综上所述，的主要优点是有序性和迭代性能，缺点是空间占用和插入删除性能略差。因此，在需要有序性和迭代性能优先的场景下，可以选择使用。如果对空间占用和插入删除性能有更高的要求，则可以选择使用。
HashTable 和 HashMap 都是基于哈希表实现的数据结构，它们的基本原理和使用方法都很相似。不过它们之间还是有一些区别的。
5.2.1HashTable 和 HashMap的区别
主要包括以下几点：
-
线程安全性：HashTable 是线程安全的，即多个线程可以同时访问一个 HashTable 实例并进行读写操作，而不会出现数据不一致的情况。HashMap 则不是线程安全的，如果多个线程同时访问一个 HashMap 实例并进行写操作，可能会导致数据不一致的情况。
-
null 值支持：HashTable 不支持 null 的 key 和 value，即插入 null 值会抛出 NullPointerException 异常。而 HashMap 则可以插入 null 的 key 和 value。
-
性能：在多线程环境下，HashTable 的性能可能会受到锁的影响而变得较低。而 HashMap 则可以通过一些技巧来提高多线程环境下的性能。
综上所述，如果需要在多线程环境下使用哈希表，并且不需要支持 null 的 key 和 value，可以选择使用 HashTable。否则，可以选择使用 HashMap。
5.2.2HashTable的线程安全
HashTable 的线程安全是通过使用 synchronized 关键字来实现的。具体来说，HashTable 中的每个方法都是被 synchronized 关键字修饰的，这意味着在同一时刻只有一个线程可以访问 HashTable 中的方法，其他线程需要等待当前线程执行完毕后才能继续执行。
由于 synchronized 关键字会对方法进行加锁，因此在多线程环境下，HashTable 的性能可能会受到锁的影响而变得较低。另外，由于所有的方法都是同步的，因此多个线程不能同时读取 HashTable 中的数据，这可能会导致一些性能问题。