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

深入理解 Java HashMap 的 get() 方法及其相关实现

news 2024/12/23 17:41:00

在 Java 中，HashMap 是一个非常常用的数据结构，用于存储键值对。它提供了快速的查找、插入和删除操作。HashMap 的核心功能之一是根据键获取对应的值，这主要通过 get() 方法来实现。本文将详细介绍 HashMap 的 get() 方法及其相关的辅助方法，包括 getNode()、hash()、getTreeNode()、root()、find()、comparableClassFor() 和 compareComparables()。通过这些方法的解析，您将更深入地理解 HashMap 的内部工作原理。
下面我们先来大致看一下hashMap的get()方法获取数据的大致流程，以便在看下面的源码不至于太迷茫。

在这里插入图片描述

HashMap get()方法

    //根据key获取Nodepublic V get(Object key) {Node<K,V> e;//计算key的哈希码,调用getNode方法，传入哈希码和键,获取对应的Node//如果找到的Node为null,返回null;否则返回该Node的值return (e = getNode(hash(key), key)) == null ? null : e.value;}

下面来看下hash()方法和getNode节点方法
getNode()的流程图比较复杂，我们拆分开来看
在这里插入图片描述

getNode()方法获取节点

获取节点大致分为四个步骤：

获取桶：根据哈希值计算桶的位置，并获取该桶的第一个节点。
直接匹配：检查第一个节点是否匹配，如果匹配直接返回。
深入查找：
- 如果是红黑树节点，使用红黑树的方法进行查找。
- 如果是链表节点，遍历链表查找匹配节点。
结果返回：找到匹配节点则返回该节点，否则返回 null

 //传入哈希码和keyfinal Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;//检查table是否为空且长度大于0 && 使用(n-1)&hash计算索引桶(n是table长度),并获取该桶的第一个节点firstif ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//检查first节点是否与给定的hash和key匹配,如果匹配,直接返回firstif (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;//如果不匹配，检查first的下一个节点eif ((e = first.next) != null) {//如果first是treeNode(即红黑树的根节点)，调用getTreeNode方法进行查找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;}

hash()计算哈希

根据key计算哈希=获取key的哈希码异或上h的右移

//计算哈希static final int hash(Object key) {int h;//如果键为null,则返回哈希码0。HashMap允许使用null作为键，因此需要特殊处理//如果键不为null,则调用对象的hashCode方法获取哈希码，并将结果赋值给h//然后对h进行位运算h^(h>>>16)其中>>>是无符号右移操作符，将h的高位右移到低位//最后将哈希码h和右移后的结果进行异或操作^,得到最终的哈希码并返回return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

getTreeNode()获取树节点

检查当前节点是否有父节点,如果有父节点,说明当前节点不是根节点,调用root()方法获取根据点。
调用find方法在红黑树中查找键值对

 //红黑树获取TreeNodefinal TreeNode<K,V> getTreeNode(int h, Object k) {//检查当前节点是否有父节点,如果有父节点,说明当前节点不是根节点,调用root()方法获取根据点。//调用find方法在红黑树中查找键值对//find方法是一个递归方法，用于在红黑树查找指定的键值对return ((parent != null) ? root() : this).find(h, k, null);}

root方法流程图比较简单啦，一看就懂的那种
在这里插入图片描述

root()获取红黑树的根节点

获取当前节点所在的红黑树的根节点

    final TreeNode<K,V> root() {//使用无限循环来遍历父节点，直到找到没有父节点的节点(即根节点)//初始化r为当前节点this，初始化p为null//每次循环中,将r的父节点赋值给pfor (TreeNode<K,V> r = this, p;;) {//如果p为null,说明r已经是根节点，返回rif ((p = r.parent) == null)return r;//否则将p赋值给r,继续循环r = p;}}

find()查找方法

find方法大致逻辑如下：

初始化：将当前节点 p 设置为 this。
遍历树：
- 获取当前节点的左右子节点。
- 根据哈希值和键进行比较，决定向左或向右子树搜索。
- 如果当前节点的键与目标键匹配，返回当前节点。
- 如果左右子节点之一为空，选择另一个子节点进行搜索。
- 如果键实现了 Comparable 接口，根据比较结果决定搜索方向。
- 递归地在右子树中查找，如果找到匹配节点，返回该节点。
- 否则，继续向左子树搜索。
未找到时返回：如果遍历完整棵树后仍未找到匹配节点，返回 null。

//h要查找的键的哈希码;k要查找的键的对象;kc键的可比较类(Comparable类型),用于优化比较过程//用于在红黑树中查找指定哈希码和键的节点final TreeNode<K,V> find(int h, Object k, Class<?> kc) {//初始化p为当前节点thisTreeNode<K,V> p = this;//do-while循环遍历树，直到找到匹配的节点或遍历结束do {int ph, dir; K pk;//获取当前节点p的左节点pl和右子节点prTreeNode<K,V> pl = p.left, pr = p.right, q;//比较当前节点的哈希码ph和目标哈希码h//如果ph大于h,向左子树搜索(p=pl)if ((ph = p.hash) > h)p = pl;//如果ph小于h,向右子树搜索(p=pr)else if (ph < h)p = pr;//如果ph等于h，进一步比较//如果键相等(pk==k或k.equals(pk))返回当前节点pelse if ((pk = p.key) == k || (k != null && k.equals(pk)))return p;//如果左子节点为空,向右子树搜索(p=pr)else if (pl == null)p = pr;//如果右子节点为空,向左子树搜索(p=pl)else if (pr == null)p = pl;//如果键实现了Comparable接口(通过comparableClassFor方法检查）//使用compareComparables方法比较键，决定向左还是向右搜搜else if ((kc != null ||(kc = comparableClassFor(k)) != null) &&(dir = compareComparables(kc, k, pk)) != 0)p = (dir < 0) ? pl : pr;//如果上述条件都不满足，递归地在右子树中查找(p=pr.find(h,k,kc),如果找到返回qelse if ((q = pr.find(h, k, kc)) != null)return q;//否则向左子树搜索(p=pl)elsep = pl;} while (p != null);//如果遍历结束后没有找到匹配的节点，返回nullreturn null;}

comparableClassFor()方法

目的：确定对象 x 是否实现了 Comparable 接口，并返回其具体的类型。
步骤：

检查 x 是否是 Comparable 的实例。
如果 x 是 String 类型，直接返回 String.class。
获取 x 的类及其泛型接口。
遍历泛型接口，检查是否是 Comparable 接口的具体实现。
如果找到匹配的类型，返回该类型；否则返回 null。

  //用于确定一个对象x是否实现了Comparable接口，并且如果实现了，返回其具体的类型static Class<?> comparableClassFor(Object x) {//检查x是否是Comparable的实例if (x instanceof Comparable) {Class<?> c; Type[] ts, as; Type t; ParameterizedType p;//如果x是String类型,直接返回String.class，因为String实现了Comparable<String>if ((c = x.getClass()) == String.class) // bypass checksreturn c;//获取x的类c及其泛型接口tsif ((ts = c.getGenericInterfaces()) != null) {//遍历ts数组，检查每个接口是否是ParameterizedType类型for (int i = 0; i < ts.length; ++i) {//如果接口的原始类型(getRawType)是Comparable,并且其实际类型参数(getActualTypeArguments)是一个长度为1的数组//且这个参数就是c,则返回cif (((t = ts[i]) instanceof ParameterizedType) &&((p = (ParameterizedType)t).getRawType() ==Comparable.class) &&(as = p.getActualTypeArguments()) != null &&as.length == 1 && as[0] == c) // type arg is creturn c;}}}//如果没有找到匹配的类型，返回nullreturn null;}

compareComparables()

比较两个对象 k 和 x，前提是 k 实现了 Comparable 接口，并且 x 的类型与 k 的类型相同。
步骤：

检查 x 是否为空或类型不匹配，如果是，返回 0。
将 k 强制转换为 Comparable 类型，并使用 compareTo 方法与 x 进行比较，返回比较结果。

//比较两个对象k和xstatic int compareComparables(Class<?> kc, Object k, Object x) {//如果x为null或者x的类不是kc,返回0//否则,将k强制转换为Comparable类型，并调用compareTo方法与x进行比较，返回比较结果return (x == null || x.getClass() != kc ? 0 :((Comparable)k).compareTo(x));}

通过本文的详细解析，我们了解了 HashMap 的 get() 方法及其相关辅助方法的工作原理。get() 方法通过计算哈希码和调用 getNode() 方法来查找指定键的节点。getNode() 方法根据哈希值定位桶，并通过直接匹配或深入查找（链表或红黑树）来获取节点。hash() 方法提高了哈希分布的均匀性。getTreeNode() 和 find() 方法处理红黑树中的节点查找。comparableClassFor() 和 compareComparables() 方法则用于优化键的比较过程。
掌握这些方法的实现细节，可以帮助开发者更好地理解和使用 HashMap，并在实际开发中做出更高效的设计和优化。
更多内容请关注以下公众号
在这里插入图片描述