HashMap之treeifyBin

前提作用业务逻辑整理源码分析getTreeNodefind

前提

jdk1.8之前HashMap的存储方式：链表+hashjdk1.8以后中HashMap的存储方式：链表+hash+红黑树算法

作用

根据key查找树结构中与之一致的对象

业务逻辑整理

1，获取根节点2，从根节点开始循环 2.1，如果当前对象的key与查询的key一致，则返回，否则判断下一个循环节点是右子节点还是左子节点2.2，继续循环，直到找到对象，或者为空

源码分析

getTreeNode

/** * Calls find for root node. */ final TreeNode<K,V> getTreeNode(int h, Object k) { //root()获取根节点 //find遍历树结构，查找对象 return ((parent != null) ? root() : this).find(h, k, null); }

find

/** * Finds the node starting at root p with the given hash and key. * The kc argument caches comparableClassFor(key) upon first use * comparing keys. */ 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; //根据hash值判断，p=左子节点，或右子节点 if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; //p的key与之key对比，如果相同，则返回当前对象 else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; //如果左子节点为空，则p=右子节点 else if (pl == null) p = pr; //如果右子节点为空，则p=左子节点 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; }