当前位置： 首页 > news >正文

Java集合 HashMap 原理解读（含源码解析）

news 2024/12/18 18:33:30

目录

HashMap基本概念

什么是HashMap

HashMap的特点

HashMap类的继承和实现关系

深入了解HashMap前需要知道

hashCode()和equals()方法的关系

重写hashCode()方法的基本规则

HashMap的底层数据结构

JDK 1.8后采用数组 + 链表 + 红黑树

负载因子与扩容机制

为什么默认负载因子是0.75

链表和红黑树的转换时机

为什么链表转红黑树需要数组大于等于64

HashMap源码解析

HashMap的存储流程总览

HashMap的常量

1.默认的负载因子，默认值是0.75

2.集合最大容量

3.当链表的值超过8则会转红黑树(1.8新增)

4.当链表的值小于6则会从红黑树转回链表

5.转化为红黑树对应的数组长度最小的值

HashMap的构造方法

1.构造一个空的 HashMap ，默认初始容量（16）和默认负载因子（0.75）。 

2.构造一个具有指定的初始容量和默认负载因子（0.75） HashMap。

3.构造一个具有指定的初始容量和负载因子的 HashMap。

HashMap的成员方法

1.put存储方法

2.resize扩容方法

3.remove删除方法

4.get查找元素方法

5.getTreeNode查找树形节点方法

HashMap基本概念

什么是HashMap

HashMap是Java中基于哈希表实现的Map接口的一个非同步实现类，是以key-value存储形式存在，即主要用来存放键值对。它的key、value都可以为null。HashMap 的实现不是同步的，这意味着它不是线程安全的。此外，HashMap中的映射不是有序的。

HashMap的特点

下面是HashMap的一些基本特点，具有这些特点的原因会在后面详细解读：

  • 存取无序：元素的存储和访问不保证任何顺序。

  • 键和值：可以存储空值（null），但只能有一个空键。

  • 键的唯一性：底层数据结构确保键的唯一性。

  • 数据结构演变：在JDK 1.8之前，HashMap使用链表和数组来存储数据。JDK 1.8之后，引入了红黑树以优化性能。

  • 转换为红黑树：当链表长度超过一定阈值（默认为8）且数组长度大于64时，链表会转换为红黑树，以提高查询效率。这一转换是为了在面对大量数据时，保持HashMap操作的高效性。

HashMap类的继承和实现关系


 

HashMap在Java集合框架中的继承和实现关系如下：

  • HashMap继承自AbstractMap类，这个抽象类提供了Map接口的大部分实现。

  • AbstractMap实现了Map接口，该接口定义了映射表的基本操作。

  • HashMap实现了Cloneable接口，允许HashMap对象被克隆。

  • HashMap同样实现了Serializable接口，使得HashMap对象可以被序列化。

这种设计使得HashMap具备了Map接口的功能，并且能够进行对象克隆和序列化操作。

深入了解HashMap前需要知道

hashCode()和equals()方法的关系

在Java中，hashCode()和equals()方法在集合类（例如HashMap、HashSet）中扮演着至关重要的角色，它们共同决定了对象的逻辑相等性以及在哈希存储结构中的处理方式：

  • equals()方法：用于确定两个对象是否逻辑相等。默认实现是比较对象的内存地址。开发者可以根据需要重写此方法，以实现自定义的相等性逻辑。

  • hashCode()方法：返回一个整数哈希值，这个值在对象的生命周期中应保持不变，且对于逻辑上相等的对象，必须返回相同的哈希值。哈希值主要用于快速定位基于哈希的集合中的对象。

如果重写了equals()方法，那么通常也需要重写hashCode()方法，以确保在哈希集合中对象的正确存储和检索。这是因为哈希集合依赖于哈希码来快速访问对象，如果两个逻辑上相等的对象具有不同的哈希码，它们将被存储在不同的哈希桶中，这可能导致集合的行为异常

重写hashCode()方法的基本规则

  • 在相同的应用程序执行过程中，对于同一个对象多次调用hashCode()必须返回相同的值。

  • 如果两个对象根据equals()方法相等，则它们的hashCode()值必须相等。

  • 但是如果两个对象equals()不相等，则它们的hashCode()值不必不同，但不同的hashCode()值可以提高哈希表的性能。 

HashMap的底层数据结构

JDK 1.8后采用数组 + 链表 + 红黑树

在JDK 1.8中，HashMap 结合了数组和链表来管理哈希冲突，采用"拉链法"在数组索引处使用链表。当链表长度超过阈值（默认8）且数组长度超过64时，会转为红黑树以提升搜索效率。此改进相较于JDK 1.8之前的仅使用数组和链表，显著提高了面对大量哈希冲突时的性能。红黑树的O(log n)查找效率优于链表的O(n)。

转换决策基于链表长度和数组大小：若链表长度超标但数组不足64，会扩容数组而非转换为红黑树，以避免小数组中红黑树操作的低效。当两者条件满足时，treeifyBin 方法触发链表向红黑树的转换，从而在大规模数据和冲突中保持 HashMap 的高性能。

负载因子与扩容机制

HashMap中的扩容是基于负载因子(load factor)来决定的。

默认情况下,HashMap的负载因子为0.75,这意味着当HashMap的已存储元素数量超过当前容量的75%时,就会触发扩容操作。

例如,初始容量为16,负载洇子为0.75,则扩容阈值为16x0.75=12。当存入第13个元素时,HashMap就会触发扩容。当触发扩容时,HashMap的容量会扩大为当前容量的两倍。例如,容量从16增加到32,从32增加到64等。

扩容时,HashMap需要重新计算所有元素的哈希值,并将它们重新分配到新的哈希桶中,这个过程称为rehashing。每个元素的存储位置会根据新容量的大小重新计算哈希值,并移动到新的数组中。

为什么默认负载因子是0.75

HashMap 的默认负载因子设定为0.75，这一设计旨在平衡时间复杂度和空间复杂度。

当负载因子保持在0.75时，HashMap 能够在避免频繁扩容和减少哈希冲突之间找到一个折中点，这样的设定确保了数据结构在保持较低存储成本的同时，也优化了查找和插入操作的效率，从而维持整体性能。

在面对特定业务需求时，对 HashMap 的负载因子进行调整能够实现性能优化。例如，在高并发读取的场景中，通过降低负载因子至0.5，可以显著减少哈希冲突，进而提升读取效率。相反，在内存资源受限的环境中，提高负载因子至0.85或更高，虽然可能会对写入和查询性能造成一定影响，但能够有效减少哈希表的扩容次数，降低内存消耗。

链表和红黑树的转换时机

在Java的 HashMap 实现中，链表和红黑树的转换时机是为了保证哈希表的性能和效率。具体转换规则如下：

  • 链表转换为红黑树：当单个桶中的链表长度达到8，并且 HashMap 的容量（桶数组大小）大于等于64时，链表会转换为红黑树。这种转换的目的是为了提高查找、插入和删除操作的性能，因为红黑树的这些操作的时间复杂度为O(log n)，而链表的为O(n)。

  • 红黑树转换回链表：当红黑树的节点数量少于等于6时，会将红黑树重新转化为链表，这是为了避免在少量节点的情况下，红黑树的平衡操作（如旋转和变色）带来的性能开销。

这种机制使得 HashMap 能够在不同的数据规模和负载条件下保持高效的性能。

为什么链表转红黑树需要数组大于等于64

  • 减少不必要的树化开销：当数组容量较小时，即使发生哈希冲突，通过扩容HashMap也能有效地降低冲突。如果在小数组上过早地将链表转换为红黑树，一旦发生扩容，之前为树化所付出的努力可能会变得不必要，因为扩容后冲突自然减少。

  • 节省内存：红黑树相较于链表需要更多的内存，特别是在节点数量较少的情况下。红黑树的额外指针和结构会占用更多的内存空间。为了在小规模数据集中避免不必要的内存消耗，HashMap设计为仅在数组容量达到一定规模（至少64）后才允许链表转为红黑树，这样可以在保证性能的同时，有效控制内存使用。

换句话说就是减少在小容量数组中因扩容而引发的不必要树化开销，并在节点较少时节省内存，以此在性能和内存使用之间实现平衡。

HashMap源码解析

HashMap的存储流程总览

我们先来看一下HashMap的存储流程，然后再看具体的源码：

（注：本图来源于黑马程序员，画的真的很清楚）

HashMap的常量

1.默认的负载因子，默认值是0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
2.集合最大容量
//集合最大容量的上限是：2的30次幂
static final int MAXIMUM_CAPACITY = 1 << 30;
3.当链表的值超过8则会转红黑树(1.8新增)
static final int TREEIFY_THRESHOLD = 8;
4.当链表的值小于6则会从红黑树转回链表
 //当桶(bucket)上的结点数小于这个值时树转链表static final int UNTREEIFY_THRESHOLD = 6;
5.转化为红黑树对应的数组长度最小的值
//桶中结构转化为红黑树对应的数组长度最小的值 
static final int MIN_TREEIFY_CAPACITY = 64;

HashMap的构造方法

1.构造一个空的 HashMap ，默认初始容量（16）和默认负载因子（0.75）。 
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // 将默认的加载因子0.75赋值给loadFactor，并没有创建数组
}
2.构造一个具有指定的初始容量和默认负载因子（0.75） HashMap。
 // 指定“容量大小”的构造函数public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}
3.构造一个具有指定的初始容量和负载因子的 HashMap。
public HashMap(int initialCapacity, float loadFactor) {// 检查初始容量是否小于 0if (initialCapacity < 0)// 如果初始容量小于 0，抛出 IllegalArgumentException 异常throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);// 检查初始容量是否大于最大容量（MAXIMUM_CAPACITY）if (initialCapacity > MAXIMUM_CAPACITY)// 如果初始容量大于最大容量，将初始容量设置为最大容量initialCapacity = MAXIMUM_CAPACITY;// 检查加载因子是否小于等于 0 或者是 NaN（非数字）if (loadFactor <= 0 || Float.isNaN(loadFactor))// 如果加载因子不合法，抛出 IllegalArgumentException 异常throw new IllegalArgumentException("Illegal load factor: " + loadFactor);// 将传入的加载因子赋值给实例变量 loadFactorthis.loadFactor = loadFactor;// 计算并设置阈值（threshold），使用 tableSizeFor 方法确定合适的容量this.threshold = tableSizeFor(initialCapacity);
}/*** Returns a power of two size for the given target capacity.返回比指定初始化容量大的最小的2的n次幂*/
static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

初始容量校验：

  • 检查 initialCapacity 是否小于 0。如果是，抛出 IllegalArgumentException 异常，提示非法的初始容量。

  • 检查 initialCapacity 是否大于 MAXIMUM_CAPACITY。如果是，将 initialCapacity 设置为 MAXIMUM_CAPACITY。

加载因子校验：

  • 检查 loadFactor 是否小于等于 0 或者是 NaN。如果是，抛出 IllegalArgumentException 异常，提示非法的加载因子。

初始化成员变量：

  • 将传入的 loadFactor 赋值给实例变量 this.loadFactor。

  • 使用 tableSizeFor(initialCapacity) 方法计算并设置 this.threshold，确保 HashMap 的容量是合适的。

HashMap的成员方法

1.put存储方法
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}

我们可以看出HashMap只提供了put用于添加元素，put的本质是putVal方法，所以我们重点来看看putVal方法，而putVal首先调用了hash方法，下面先看看hash方法。

 static final int hash(Object key) {int h;/*1）如果key等于null：可以看到当key等于null的时候也是有哈希值的，返回的是0.2）如果key不等于null：首先计算出key的hashCode赋值给h,然后与h无符号右移16位后的二进制进行按位异或得到最后的					hash值*/return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

这个方法解释了为什么HashMap是支持Key为空的，Key如果为null会被赋值为0。

下面我们来看看putVal方法：

/*** 将指定的键值对插入到HashMap中* * @param hash 键的哈希值，用于计算存储位置* @param key 插入的键，不为null* @param value 插入的值，可以为null* @param onlyIfAbsent 如果为true，则只有在当前键不存在时才插入* @param evict 如果为true，则在插入后可能移除某些条目（用于TreeMap）* @return 如果插入的键已经存在，则返回旧值；否则返回null*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 检查表是否初始化或为空，如果是，则进行初始化或扩容if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 计算插入位置，如果该位置没有元素，则直接插入if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;// 如果当前位置的元素与插入的键相同，则替换旧值if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 如果当前位置是红黑树节点，则调用红黑树的插入方法else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// 遍历链表，直到找到空的位置或相同的键for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 如果链表长度达到阈值，则将链表转换为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 如果找到相同的键，则替换旧值if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 如果找到了相同的键，则处理值的替换if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}// 更新modCount，表示HashMap已被修改++modCount;// 如果大小超过阈值，则进行扩容if (++size > threshold)resize();// 插入后的一些处理，例如在TreeMap中可能需要移除某些条目afterNodeInsertion(evict);return null;
}

putVal 方法的主要功能是在 HashMap 中插入一个新的键值对。具体步骤如下：

1. 检查哈希表是否为空：如果哈希表为空或长度为0，则调用 resize 方法初始化或扩容哈希表。

2. 插入新节点：

   2.1 如果目标位置 tab[i] 为空，则直接插入新节点。

   2.2 如果目标位置已有节点：

        2.2.1 检查是否存在相同键的节点，如果存在则更新值。

        2.2.2 如果目标位置的节点是树节点，则调用 putTreeVal 方法插入。

        2.2.3 否则，遍历链表找到合适的位置插入新节点，如果链表长度超过阈值则进行树化。

3. 更新计数：增加 modCount 和 size，如果 size 超过阈值则调用 resize 方法扩容。

4. 回调方法：调用 afterNodeAccess 和 afterNodeInsertion 方法。

上述put操作里面调用了resize 扩容方法，我们下面来看看resize方法。

2.resize扩容方法
/*** 扩容哈希表，这是一个复杂且关键的方法* 它负责在哈希表容量达到阈值时，自动扩容以保持哈希表的性能* 此方法涉及重新计算新的容量和阈值，并重新分配所有的键值对到新的哈希表中* 整个过程包括：* 1. 检查当前哈希表是否为空，如果不为空，判断是否需要扩容* 2. 计算新的哈希表容量和阈值* 3. 创建新的哈希表* 4. 将所有键值对重新分配到新的哈希表中，这个过程包括处理链表和红黑树* 5. 更新引用，使新的哈希表成为当前哈希表* * @return 新的哈希表数组*/
final Node<K,V>[] resize() {// 当前哈希表Node<K,V>[] oldTab = table;// 当前哈希表容量，如果哈希表为空，则容量为0int oldCap = (oldTab == null) ? 0 : oldTab.length;// 当前阈值int oldThr = threshold;// 新的哈希表容量和新的阈值，初始设为0int newCap, newThr = 0;// 如果当前哈希表容量大于0if (oldCap > 0) {// 如果当前容量已经达到或超过最大容量，则将阈值设为Integer.MAX_VALUE，不再扩容if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 否则，如果新容量小于最大容量且当前容量大于等于默认初始容量，则新容量为当前容量的两倍，新阈值也为当前阈值的两倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}// 如果当前哈希表为空，但阈值大于0，说明初始容量被放在了阈值中，将新容量设为当前阈值else if (oldThr > 0)newCap = oldThr;// 如果当前哈希表为空且阈值也为0，则使用默认的初始容量和负载因子来计算新容量和新阈值else {newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 如果新阈值为0，通过新容量和负载因子来计算新阈值if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 更新阈值为新计算出的阈值threshold = newThr;// 创建新的哈希表数组，由于泛型数组不能直接创建，所以使用类型转换@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];// 将新的哈希表数组设为当前哈希表table = newTab;// 如果旧的哈希表不为空，则需要将所有键值对重新分配到新的哈希表中if (oldTab != null) {// 遍历旧的哈希表数组for (int j = 0; j < oldCap; ++j) {Node<K,V> e;// 如果当前位置的节点不为空if ((e = oldTab[j]) != null) {oldTab[j] = null;// 如果当前节点没有下一个节点，直接将当前节点放入新的哈希表中对应的位置if (e.next == null)newTab[e.hash & (newCap - 1)] = e;// 如果当前节点是TreeNode类型，说明当前位置的节点形成了红黑树，调用split方法来处理红黑树的分割else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 如果当前节点有下一个节点且不是TreeNode类型，说明当前位置的节点形成了链表，需要将链表分割成两个链表else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;// 遍历链表，根据节点的hash值决定节点应该放入新的哈希表中的位置do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 如果低位链表不为空，将低位链表放入原位置if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 如果高位链表不为空，将高位链表放入新位置if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}// 返回新的哈希表数组return newTab;
}

1. 检查旧容量：

   1.1 如果旧容量大于等于最大容量 MAXIMUM_CAPACITY，则将阈值设为 Integer.MAX_VALUE 并返回旧表。

   1.2 否则，计算新容量 newCap 和新阈值 newThr。

2. 创建新表：根据新容量创建新的 Node 数组 newTab 并更新 table。

3. 迁移数据：遍历旧表，将每个节点重新插入到新表中。对于链表节点，根据哈希值决定其在新表 中的位置；对于树节点，调用 split 方法进行拆分.

3.remove删除方法

删除的话就是首先先找到元素的位置，如果是链表就遍历链表找到元素之后删除。如果是用红黑树就遍历树然后找到之后做删除，树小于6的时候要转链表。

public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;}

我们可以看出HashMap只提供了remove用于删除元素，remove的本质是removeNode方法，所以我们重点来看看removeNode方法：

/*** 根据指定的键、值和其他条件从哈希表中移除节点。* 此方法用于从哈希表中移除符合特定条件的映射。* * @param hash 键的哈希值，用于定位存储节点的桶。* @param key 要移除的节点的键。* @param value 要移除的节点的值，当 matchValue 为 true 时用于验证节点是否应被移除。* @param matchValue 布尔值，表示是否需要匹配值才能移除节点。* @param movable 布尔值，表示桶中的剩余节点是否可以重新组织。* @return 返回被移除的节点，如果没有找到匹配的节点则返回 null。*/
final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {// 本地变量，包括表、节点、索引等Node<K,V>[] tab; Node<K,V> p; int n, index;// 检查表是否已初始化且不为空，以及对应索引的桶是否不为空if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {// 遍历桶中的链表或树以找到要移除的节点Node<K,V> node = null, e; K k; V v;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;else if ((e = p.next) != null) {if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}// 如果找到了要移除的节点，并且（如果 matchValue 为 true，还需验证值）if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {// 根据节点的类型和位置移除节点if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);else if (node == p)tab[index] = node.next;elsep.next = node.next;// 更新修改计数和大小，并执行移除后的处理++modCount;--size;afterNodeRemoval(node);return node;}}// 如果未找到节点或移除条件不满足，返回 nullreturn null;
}

1. 检查表是否为空：如果 table 为空或长度为 0，则直接返回 null。

2. 查找节点：

    2.1 检查当前节点 p 是否为目标节点。

    2.2 如果不是目标节点且存在下一个节点 e，则继续查找。

    2.3 如果当前节点是 TreeNode 类型，则调用 getTreeNode 方法查找目标节点。

    2.4 否则，遍历链表查找目标节点。

3. 验证节点值：如果找到的目标节点的值与传入的值匹配（或不需要匹配值），则进行删除操作。

4. 删除节点：

    4.1 如果目标节点是 TreeNode，则调用 removeTreeNode 方法删除节点。

    4.2 否则，调整链表指针删除节点。

5. 更新状态：增加 modCount，减少 size，并调用 afterNodeRemoval 方法。

6. 返回结果：返回被删除的节点，如果没有找到目标节点则返回 null。

4.get查找元素方法

查找方法，通过元素的 Key 找到 Value。

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}

可以看出 get 方法主要调用的是 getNode 方法，代码如下：

/*** 根据给定的hash和key获取对应的节点* 此方法用于在哈希表中查找特定的节点，首先计算数组中的索引位置，然后遍历链表或红黑树来查找节点* * @param hash 键的哈希值，用于计算在数组中的索引位置* @param key 要查找的键，用于比较以找到正确的节点* @return 返回找到的节点，如果未找到则返回null*/
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 检查表是否初始化且不为空，然后获取第一个节点if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 检查第一个节点是否匹配给定的hash和keyif (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;// 如果存在下一个节点，准备遍历链表或红黑树if ((e = first.next) != null) {// 如果第一个节点是树节点，说明此处是红黑树if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 遍历链表中的节点，直到找到匹配的节点或到达链表末尾do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}// 如果未找到匹配的节点，返回nullreturn null;
}

1. 通过hash值获取该key映射到的桶

2. 桶上的key就是要查找的key,则直接找到并返回

3. 桶上的key不是要找的key,则查看后续的节点：

    3.1 如果后续节点是红黑树节点，通过调用红黑树的方法根据key获取value

​    3.2 如果后续节点是链表节点，则通过循环遍历链表根据key获取value

上述关于红黑树节点都是调用的 getTreeNode 方法通过树形节点的 find 方法进行查找，我们最后来看看这两个方法。

5.getTreeNode查找树形节点方法

最后补充一下查找树形节点的 getTreeNode 和 find 方法，getTreeNode 调用 find 方法。

        final TreeNode<K,V> getTreeNode(int h, Object k) {return ((parent != null) ? root() : this).find(h, k, null);}
/*** 在树中查找指定键的节点* * @param h 散列值，用于比较节点的散列值* @param k 键，要查找的目标键* @param kc 键的类类型，用于比较节点键值时确定是否可以进行比较* @return 返回找到的节点，如果未找到则返回null*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {TreeNode<K,V> p = this;do {int ph, dir; K pk;TreeNode<K,V> pl = p.left, pr = p.right, q;// 比较当前节点散列值与目标散列值，决定搜索方向if ((ph = p.hash) > h)p = pl;else if (ph < h)p = pr;// 散列值相等时，进一步比较键值else if ((pk = p.key) == k || (k != null && k.equals(pk)))return p;// 根据子节点情况决定搜索方向else if (pl == null)p = pr;else if (pr == null)p = pl;// 如果键值可以比较，且比较结果不为0，则根据比较结果决定搜索方向else if ((kc != null ||(kc = comparableClassFor(k)) != null) &&(dir = compareComparables(kc, k, pk)) != 0)p = (dir < 0) ? pl : pr;// 在右子树中继续查找else if ((q = pr.find(h, k, kc)) != null)return q;// 默认向左子树搜索elsep = pl;} while (p != null);return null;
}


http://www.mrgr.cn/news/80588.html

相关文章：

  • 【C++】小乐乐求和问题的高效求解与算法对比分析
  • Cherno C++学习笔记 P40 隐式转换与explicit关键字
  • C# opencvsharp 流程化-脚本化-（2）ROI
  • 基于Qwen2-VL模型针对LaTeX OCR任务进行微调训练 - 训练
  • 【Redis篇】Hash的认识以及相关命令操作
  • 计算机网络-传输层 UDP协议
  • 灵当crm pdf.php存在任意文件读取漏洞
  • C#速成（GID+图形编程）
  • C++之二：类和对象
  • 基于STM32设计的粮食仓库(粮仓)环境监测系统_284
  • GIN
  • Latex 转换为 Word（使用GrindEQ ）（英文转中文，毕业论文）
  • ubuntu升级python版本
  • 15.初始接口1.0 C#
  • Windows环境 (Ubuntu 24.04.1 LTS ) 国内镜像，用apt-get命令安装RabbitMQ，java代码样例
  • Yolo中OBB的角度范围和角度损失设计思路
  • flink SQL实现mysql source sink
  • 面试题整理2---Nginx 性能优化全方案
  • next.js 存在缓存中毒漏洞(CVE-2024-46982)
  • Qt之修改窗口标题、图标以及自定义标题栏（九）
  • 登陆harbor发现证书是错误的, 那么如何更新harbor的证书呢
  • day4：tomcat—maven-jdk
  • SQL server学习07-查询数据表中的数据（下）
  • 24-12 空间转录组数据分析之分子niche与细胞niche
  • 【信息系统项目管理师-论文真题】2015下半年论文详解（包括解题思路和写作要点）
  • window.getSelection() 获取划线内容并实现 dom 追随功能