1. 导读

本章节面相的是对红黑树有了解的读者, 因为JAVA引入了黑红树, 所以后面的内容中主要围绕着红黑树来展开;

.1 get

.2 find

2. get

HashMap::get返回一个数据节点, 如果不存在则返回空;

 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) { if (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); } } return null; }

HashMap::getNode的流程是:

.1 通过 hash & (table.length - 1)获取该key对应的数据节点的hash槽;

.2 判断首节点是否为空, 为空则直接返回空;

.3 再判断首节点.key 是否和目标值相同, 相同则直接返回(首节点不用区分链表还是红黑树);

.4 首节点.next为空, 则直接返回空;

.5 首节点是树形节点, 则进入红黑树数的取值流程, 并返回结果;

.6 进入链表的取值流程, 并返回结果;

我们先来看简单的链表取值流程:

我们再来看相对复杂的红黑树的取值流程(JAVA8引入):

 final TreeNode<K,V> getTreeNode(int h, Object k) {			return ((parent != null) ? root() : this).find(h, k, null);		}

HashMap.TreeNode::getTreeNode返回的是key对应的红黑树节点, 看代码可知他是从根节点开始遍历寻找key相对应的节点, 我们接着来看获取红黑树节点的核心方法: HashMap.TreedNode::find:

 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; 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; else p = pl; } while (p != null); return null; }

HashMap.TreeNode::find的源码逻辑还是比较清晰的:

.1 获取当前节点, 第一次进入是根节点;

.2 通过一个循环去遍历节点, 当下一个遍历节点为空时退出, 返回null;

.3 先比较每个节点的hash值, 目标节点的hash小于当前节点时, 位于当前节点的左子树, 将当前节点的左子节点赋值给p, 进行下一次循环;

.4 目标节点的hash大于当前节点时, 位于当前节点的右子树, 将当前节点的右子节点赋值给p, 进行下一次循环;

.5 如果目标节点的hash等于当前节点的hash值, 再比较key是否相同, 如果相同则返回节点;

.6 左节点为空时, 将右节点赋值给p, 进行下一轮循环;

.7 右节点为空时, 将左节点赋值给p, 进行下一轮循环;

.8 如果key不相等, 再次判断能否通过key::compareTo(key是否实现Comparable接口)比出大小, 如果小, 则将左子节点赋值给p, 如果大则将右子节点赋值给p, 进行下一轮循环;

.9 如果无法通过key::compareTo比较出大小, 右子节点递归调用find, 如果结果不为空, 则返回结果(第8步已经保证pr不为空了);

.10 如果右子节点的递归无法得出结果, 只能将左子节点赋值给p, 进行下一轮循环;

经过上面的分析, 我们可以发现红黑树获取节点与链表获取节点有个很大的不同:

.1 红黑树需要通过hash与key的比较来判断节点的位置, 这是为什么呢?

.2 因为红黑树的特性要求了每个节点必须是有序的, 也就是左子树的父节点必定小于任一子节点的, 那么当hash相同时, 就必须借助于key来实现大小有序了(右子树同理), 所以在查找时, 我们就需要先通过hash来判断, 如果hash相同时, 就需要借助key来判断大小了;

3. HashMap::comparableClassFor

 static Class<?> comparableClassFor(Object x) { if (x instanceof Comparable) { Class<?> c; Type[] ts, as; Type t; ParameterizedType p; if ((c = x.getClass()) == String.class) // bypass checks return c; if ((ts = c.getGenericInterfaces()) != null) { for (int i = 0; i < ts.length; ++i) { if (((t = ts[i]) instanceof ParameterizedType) && ((p = (ParameterizedType)t).getRawType() == Comparable.class) && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) // type arg is c return c; } } } return null; }

HashMap::get在红黑树获取节点时, 是通过key是否实现Comparable接口来判断是否有序的;HashMap::comparableClassFor就是获取key是否实现Comparable接口的方法:

HashMap::comparableClassFor就是需要找到Comparable接口且泛型有且只有目标类的结果, 如果不存在就返回空;

今天关于HashMap::get的分享就到这里了, 虽然JAVA8中引入了红黑树, 但是经过上面的分析, 理解了红黑树的寻值比较了hash值和key, 你会发现红黑树的寻值和链表的寻值一样简单;

如果看了上面的内容对你有所帮助, 烦请点赞转发, 感谢;