HashMap 1.8

结构

数组+链表+红黑树

  1. 数组：Node数组，集合元素实际存储位置
  2. 链表：哈希冲突，形成的哈希冲突链
  3. 红黑树，树上还维护着一个双向链表
    1. 哈希冲突链上的节点数量到达8，且集合中全部元素个数超过64，链表转化成红黑树
    2. 红黑树上节点个数少于6，红黑树自动转化为链表

image.png

  1.     // 默认的初始容量-必须是2的幂
  2.     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  4.     /**
  5.      * 集合的最大容量，如果两个带参数的构造函数中的任何一个隐式指定了更高的值，则使用该值
  6.      * 集合容量一定是一个小于等于1<<30的2的幂的整数
  7.      */
  8.     static final int MAXIMUM_CAPACITY = 1 << 30;
  10.     // 默认的负载因子
  11.     static final float DEFAULT_LOAD_FACTOR = 0.75f;
  13.     // 冲突链转换成红黑树的最小节点数，转树的阈值
  14.     static final int TREEIFY_THRESHOLD = 8;
  16.     // 红黑树退化成链表的阈值
  17.     static final int UNTREEIFY_THRESHOLD = 6;
  19.     /**
  20.      * 被树形化的最小表容量。(否则，如果一个bin中有太多节点，则会调整表的大小。)
  21.      * 应该至少为4 * TREEIFY_THRESHOLD，以避免调整大小和树化阈值之间的冲突。
  22.      */
  23.     static final int MIN_TREEIFY_CAPACITY = 64;
  1.     // 表在第一次使用时进行初始化，并根据需要调整大小。分配时，长度总是2的幂
  2.     transient Node<K,V>[] table;
  4.     // 保存缓存entrySet()。注意keySet()和values()使用了AbstractMap的字段
  5.     transient Set<Map.Entry<K,V>> entrySet;
  7.     // 集合中存储的key-value对的数量
  8.     transient int size;
  10.     /**
  11.      * 改变HashMap中映射的数量或以其他方式修改其内部结构(例如，rehash)的次数
  12.      * 
  13.      * 用于使HashMap的集合视图上的迭代器快速失效(见ConcurrentModificationException)
  14.      */
  15.     transient int modCount;
  17.     // 扩容阈值，集合元素数量到达这个值将要进行扩容
  18.     int threshold;
  20.     // 负载因子
  21.     final float loadFactor;
  1.     // HashMap的基本bin节点
  2.     static class Node<K,V> implements Map.Entry<K,V> {
  3.         final int hash;
  4.         final K key;
  5.         V value;
  6.         Node<K,V> next; // 链表
  7.     }
  9.     // 红黑树节点 
  10.     static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  11.         TreeNode<K,V> parent;  // red-black tree links
  12.         TreeNode<K,V> left;
  13.         TreeNode<K,V> right;
  14.         TreeNode<K,V> prev;    // needed to unlink next upon deletion
  15.         boolean red;
  16.         //……
  17.     }
  18.     static class Entry<K,V> extends HashMap.Node<K,V> {
  19.         // 双向链表
  20.         Entry<K,V> before, after;
  21.         Entry(int hash, K key, V value, Node<K,V> next) {
  22.             super(hash, key, value, next);
  23.         }
  24.     }

创建

  1. // 构造具有指定初始容量和加载因子的空HashMap
  2. public HashMap(int initialCapacity, float loadFactor) {
  3.     if (initialCapacity < 0)
  4.         throw new IllegalArgumentException("Illegal initial capacity: " +
  5.                                            initialCapacity);
  6.     if (initialCapacity > MAXIMUM_CAPACITY)
  7.         initialCapacity = MAXIMUM_CAPACITY;
  8.     if (loadFactor <= 0 || Float.isNaN(loadFactor))
  9.         throw new IllegalArgumentException("Illegal load factor: " +
  10.                                            loadFactor);
  11.     this.loadFactor = loadFactor;
  12.     // tableSizeFor方法计算出一个大于等于initialCapacity的最小的2的幂次方的整数
  13.     this.threshold = tableSizeFor(initialCapacity);
  14. }
  16. // 构造一个具有指定的初始容量和默认加载因子(0.75)的空HashMap
  17. public HashMap(int initialCapacity) {
  18.     this(initialCapacity, DEFAULT_LOAD_FACTOR);
  19. }
  21. // 构造一个具有默认初始容量(16)和默认加载因子(0.75)的空HashMap
  22. public HashMap() {
  23.     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  24. }
  26. /**
  27.  * 使用与指定Map相同的映射构造一个新的HashMap
  28.  * HashMap使用默认的装载因子(0.75)创建，初始容量足以容纳指定映射中的映射
  29.  */
  30. public HashMap(Map<? extends K, ? extends V> m) {
  31.     this.loadFactor = DEFAULT_LOAD_FACTOR;
  32.     putMapEntries(m, false);
  33. }

put操作

将指定的值与此map中的指定键关联。如果该map先前包含了该键的映射，则旧值将被替换

  1.     public V put(K key, V value) {
  2.         return putVal(hash(key), key, value, false, true);
  3.     }

putVal

  1. // put方法的具体实现
  2. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  3.                boolean evict) {
  4.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  5.     // table为空，通过resize方法初始化table数组
  6.     if ((tab = table) == null || (n = tab.length) == 0)
  7.         n = (tab = resize()).length;
  8.     // 计算索引位置，如果该位置没有元素，直接在该位置新增一个节点
  9.     if ((p = tab[i = (n - 1) & hash]) == null)
  10.         tab[i] = newNode(hash, key, value, null);
  11.     else { // 该索引位置有元素，遍历查找位置插入新元素
  12.         Node<K,V> e; K k;
  13.         // 判断p节点的key是否和传入的key相同，相同p节点就是目标节点，就将p赋值给e
  14.         if (p.hash == hash &&
  15.             ((k = p.key) == key || (key != null && key.equals(k))))
  16.             e = p;
  17.         // 如果p节点是树节点，调用红黑树的putTreeVal方法插入节点
  18.         else if (p instanceof TreeNode)
  19.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  20.         else { // 说明是链表节点
  21.             // 遍历链表
  22.             for (int binCount = 0; ; ++binCount) {
  23.                 // 遍历到链表尾部，插入新元素节点
  24.                 if ((e = p.next) == null) {
  25.                     p.next = newNode(hash, key, value, null);
  26.                     // 链表元素个数到达转化成树的阈值时，转换成红黑树
  27.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  28.                         treeifyBin(tab, hash);
  29.                     break;
  30.                 }
  31.                 // e节点key和传入的key相同，找到目标节点e
  32.                 if (e.hash == hash &&
  33.                     ((k = e.key) == key || (key != null && key.equals(k))))
  34.                     break;
  35.                 p = e;
  36.             }
  37.         }
  38.         // 存在目标节点，使用新的value覆盖该节点旧的oldValue值，并返回oldValue
  39.         if (e != null) { // existing mapping for key
  40.             V oldValue = e.value;
  41.             // 
  42.             if (!onlyIfAbsent || oldValue == null)
  43.                 e.value = value;
  44.             afterNodeAccess(e);
  45.             return oldValue;
  46.         }
  47.     }
  48.     ++modCount;
  49.     // 如果插入节点后集合中节点数目超过扩容阈值，调用resize方法扩容
  50.     if (++size > threshold)
  51.         resize();
  52.     afterNodeInsertion(evict);
  53.     return null;
  54. }

treeifyBin

链表上节点数目到达一定值（默认8）时，链表转化成红黑树

  1.     final void treeifyBin(Node<K,V>[] tab, int hash) {
  2.         int n, index; Node<K,V> e;
  3.         // table为空或者table的长度小于最小转换成树的阈值，扩容
  4.         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
  5.             resize();
  6.         // 根据hash计算索引，从索引位置的链表头节点开始遍历链表
  7.         else if ((e = tab[index = (n - 1) & hash]) != null) {
  8.             TreeNode<K,V> hd = null, tl = null;
  9.             do {
  10.                 // 将当前链表节点e转成红黑树节点p
  11.                 TreeNode<K,V> p = replacementTreeNode(e, null);
  12.                 // tl为null，表示第一次循环
  13.                 if (tl == null)
  14.                     // 第一次循环节点赋值给头节点
  15.                     hd = p;
  16.                 else { // 不是第一次遍历，处理当前节点的prev属性和上一个节点的next属性
  17.                     p.prev = tl;
  18.                     tl.next = p;
  19.                 }
  20.                 tl = p;
  21.             } while ((e = e.next) != null);
  23.             /*将table该索引位置赋值为新转的TreeNode的头节点，
  24.               如果该节点不为空，则以头节点(hd)为根节点, 构建红黑树*/
  25.             if ((tab[index] = hd) != null)
  26.                 hd.treeify(tab);
  27.         }
  28.     }

resize

  2. /**
  3.  * 初始化或扩容
  4.  *     1、如果table为null，则按照threshold中保留的初始容量进行分配
  5.  *         i、构造方法执行后Threshold中保存的是table数组的大小，初始化后这个字段存储的是扩容阈值
  6.  *     2、扩容，使用2的幂展开，每个bin中的元素必须保持在相同的索引位置，或者在新表中以2的幂偏移量移动
  7.  */
  8. final Node<K,V>[] resize() {
  9.     Node<K,V>[] oldTab = table;
  10.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  11.     int oldThr = threshold;
  12.     int newCap, newThr = 0;
  13.     // table数组容量>0,将要进行扩容操作
  14.     if (oldCap > 0) {
  15.         // table容量超过集合最大容量，使用最大容量
  16.         if (oldCap >= MAXIMUM_CAPACITY) {
  17.             threshold = Integer.MAX_VALUE;
  18.             return oldTab;
  19.         }
  20.         // 扩容2倍，如果table容量大于等于默认初始容量，扩容阈值直接也扩大2倍
  21.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  22.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  23.             newThr = oldThr << 1; // 扩容阈值翻倍
  24.     }
  25.     // table数组容量<=0且指定table将要初始化的容量>0,将要使用这个oldThr初始化table数组
  26.     else if (oldThr > 0) // initial capacity was placed in threshold
  27.         newCap = oldThr;
  28.     else {               // 没有指定table要初始化的容量，使用默认值
  29.         newCap = DEFAULT_INITIAL_CAPACITY;
  30.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  31.     }
  32.     // 设置扩容阈值
  33.     if (newThr == 0) {
  34.         float ft = (float)newCap * loadFactor;
  35.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  36.                   (int)ft : Integer.MAX_VALUE);
  37.     }
  38.     threshold = newThr;
  40.     // 创建一个容量为原来2倍的Node数组,table指向新的数组
  41.     @SuppressWarnings({"rawtypes","unchecked"})
  42.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  43.     table = newTab;
  44.     // 将集合中的元素迁移到新的Node数组中
  45.     if (oldTab != null) {
  46.         for (int j = 0; j < oldCap; ++j) {
  47.             Node<K,V> e;
  48.             // 原先table数组该索引位置存在元素
  49.             if ((e = oldTab[j]) != null) {
  50.                 oldTab[j] = null;
  51.                 // 原先table数组中的索引位置只有一个元素
  52.                 if (e.next == null)
  53.                     newTab[e.hash & (newCap - 1)] = e;
  54.                 else if (e instanceof TreeNode) // 红黑树
  55.                     // 
  56.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  57.                 else { // 链表
  58.                     // 存储索引位置为“原索引位置”的节点
  59.                     Node<K,V> loHead = null, loTail = null;
  60.                     // 存储索引位置为“原索引位置 + oldCap”的节点
  61.                     Node<K,V> hiHead = null, hiTail = null;
  62.                     Node<K,V> next;
  64.                     // 先组成两个链表（索引位置不变、索引位置=原索引位置+oldCap）
  65.                     do {
  66.                         next = e.next;
  67.                         // 该节点在新表索引位置和在老表索引位置相同
  68.                         if ((e.hash & oldCap) == 0) {
  69.                             // 是链表的第一个节点
  70.                             if (loTail == null)
  71.                                 loHead = e;
  72.                             else // 不是第一个节点，追加到链表尾部
  73.                                 loTail.next = e;
  74.                             loTail = e;
  75.                         }
  76.                         else { // 该节点在新表索引位置 = 在老表索引位置 + oldCap
  77.                             // 是链表的第一个节点
  78.                             if (hiTail == null)
  79.                                 hiHead = e;
  80.                             else  // 不是第一个节点，追加到链表尾部
  81.                                 hiTail.next = e;
  82.                             hiTail = e;
  83.                         }
  84.                     } while ((e = next) != null);// 遍历结束条件
  86.                     // 索引位置相同的链表，表头放入新Node数组newTab的对应索引位置
  87.                     if (loTail != null) {
  88.                         loTail.next = null;
  89.                         newTab[j] = loHead;
  90.                     }
  91.                     // 索引位置=原索引位置+oldCap的链表，newTab的对应索引位置存储表头hiHead
  92.                     if (hiTail != null) {
  93.                         hiTail.next = null;
  94.                         newTab[j + oldCap] = hiHead;
  95.                     }
  96.                 }
  97.             }
  98.         }
  99.     }
  100.     return newTab;
  101. }

split

将原红黑树拆分为两棵树，如果树节点太小退化成链表（该方法只在resize方法中使用）

原树节点重新拆分到新table中后只可能在两个位置

  1. 原索引位置
  2. 原索引位置 + oldCap

前置知识

  1. 转为红黑树节点后，链表的结构还存在，通过 next 属性维持，红黑树节点在进行操作时都会维护链表的结构，并不是转为红黑树节点，链表结构就不存在了
  2. 源码中进行红黑树的查找时，会反复用到以下两条规则 【红黑树的特性（左节点 < 根节点 < 右节点）】
    1. 如果目标节点的 hash 值小于 p 节点的 hash 值，则向 p 节点的左边遍历；否则向 p 节点的右边遍历
    2. 如果目标节点的 key 值小于 p 节点的 key 值，则向 p 节点的左边遍历；否则向 p 节点的右边遍历
  1. /**
  2.  * 将原红黑树拆分为两棵树，如果树节点太小退化成链表（该方法只在resize方法中使用）
  3.  *    map——this、tab——newTab、index——原tab数组指定索引位置、bit——oldCap
  4.  */
  5. final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
  6.     TreeNode<K,V> b = this;
  7.     // 原索引位置不变
  8.     TreeNode<K,V> loHead = null, loTail = null;
  9.     // 原索引位置+oldCap
  10.     TreeNode<K,V> hiHead = null, hiTail = null;
  11.     // 迁移到指定位置的节点个数
  12.     int lc = 0, hc = 0;
  13.     // 红黑树本身也维护了一个链表，可以按照链表方式遍历每个节点
  14.     for (TreeNode<K,V> e = b, next; e != null; e = next) {
  15.         // 下一个节点
  16.         next = (TreeNode<K,V>)e.next;
  17.         // 释放节点，方便垃圾回收
  18.         e.next = null;
  19.         // 迁移到新数组后索引位置不变
  20.         if ((e.hash & bit) == 0) {
  21.             // 该节点为第一个节点
  22.             if ((e.prev = loTail) == null)
  23.                 loHead = e;
  24.             else // 该节点不是第一个节点，追加到链表尾部
  25.                 loTail.next = e;
  26.             // loTail赋值为新增的节点
  27.             loTail = e;
  28.             // 记录该索引位置链表的节点个数
  29.             ++lc;
  30.         }
  31.         // 迁移到新数组后索引位置 = 原索引位置 + oldCap
  32.         else {
  33.             if ((e.prev = hiTail) == null)
  34.                 hiHead = e;
  35.             else
  36.                 hiTail.next = e;
  37.             hiTail = e;
  38.             ++hc;
  39.         }
  40.     }
  42.     // 索引位置不变的情况，该索引位置中存在元素
  43.     if (loHead != null) {
  44.         // 元素个数较小，红黑树退化为链表
  45.         if (lc <= UNTREEIFY_THRESHOLD)
  46.             tab[index] = loHead.untreeify(map);
  47.         else {  // 树化
  48.             tab[index] = loHead;
  49.             if (hiHead != null) // (else is already treeified)
  50.                 loHead.treeify(tab);
  51.         }
  52.     }
  53.     if (hiHead != null) {
  54.         if (hc <= UNTREEIFY_THRESHOLD)
  55.             tab[index + bit] = hiHead.untreeify(map);
  56.         else {
  57.             tab[index + bit] = hiHead;
  58.             if (loHead != null)
  59.                 hiHead.treeify(tab);
  60.         }
  61.     }
  62. }

untreeify

从红黑树退化到链表

  1. // 这里的this是红黑树
  2. final Node<K,V> untreeify(HashMap<K,V> map) {
  3.     Node<K,V> hd = null, tl = null;
  4.     // 遍历红黑树自身维护的链表
  5.     for (Node<K,V> q = this; q != null; q = q.next) {
  6.         // 将红黑树节点转换为普通的Node节点
  7.         Node<K,V> p = map.replacementNode(q, null);
  8.         // 第一次遍历，这个节点作为头节点
  9.         if (tl == null)
  10.             hd = p;
  11.         else
  12.             tl.next = p;
  13.         tl = p;
  14.     }
  15.     return hd;
  16. }
  18. // 用于从树节点到普通节点的转换
  19. Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
  20.     return new Node<>(p.hash, p.key, p.value, next);
  21. }

treeify

从链表转化为红黑树

  1. // 形成从该节点链接的节点树
  2. final void treeify(Node<K,V>[] tab) {
  3.     TreeNode<K,V> root = null;
  4.     // 从调用该方法的节点开始，遍历这个链表
  5.     for (TreeNode<K,V> x = this, next; x != null; x = next) {
  6.         // 下一个节点
  7.         next = (TreeNode<K,V>)x.next;
  8.         // 左右节点先设置为null
  9.         x.left = x.right = null;
  10.         // 还没有根节点，当前节点设置为根节点
  11.         if (root == null) {
  12.             // 根节点没有父节点
  13.             x.parent = null;
  14.             // 根节点必须是黑色的
  15.             x.red = false;
  16.             // 设置当前节点为根节点
  17.             root = x;
  18.         }
  19.         // 已经存在根节点
  20.         else {
  21.             // 当前节点的key值
  22.             K k = x.key;
  23.             // 当前节点的hash值
  24.             int h = x.hash;
  25.             Class<?> kc = null;
  26.             // 从根节点开始遍历红黑树，x作为目标节点，遍历插入符合条件的位置
  27.             for (TreeNode<K,V> p = root;;) {
  28.                 int dir, ph;
  29.                 // 目前遍历到的节点p的key值
  30.                 K pk = p.key;
  31.                 // 节点p的hash值大于目标节点x的hash值，dir设置为-1，表示向p节点的左边遍历
  32.                 if ((ph = p.hash) > h)
  33.                     dir = -1;
  34.                 // 节点p的hash值小于目标节点x的hash值，dir设置为1，表示向p节点的右边遍历
  35.                 else if (ph < h)
  36.                     dir = 1;
  37.                 // p、x节点key的hash值相同，开始比较key的值
  38.                 else if ((kc == null &&
  39.                           // k没有实现Compareable接口
  40.                           (kc = comparableClassFor(k)) == null) ||
  41.                          // x节点和p节点的key值相同
  42.                          (dir = compareComparables(kc, k, pk)) == 0)
  43.                     // 使用自定义的规则比较x、p节点的大小，决定向左还是向右遍历
  44.                     dir = tieBreakOrder(k, pk);
  46.                 // 设置当前节点p为x节点的父节点
  47.                 TreeNode<K,V> xp = p;
  48.                 // dir<=0向左查找，dir>0向右查找；如果p为null，表示找到最后，这个位置插入x
  49.                 if ((p = (dir <= 0) ? p.left : p.right) == null) {
  50.                     // x节点的父节点为最后一次遍历的p节点
  51.                     x.parent = xp;
  52.                     // 向左查找，且p为null，表示x节点为父节点的左节点
  53.                     if (dir <= 0)
  54.                         xp.left = x;
  55.                     // 向右查找，且p为null，表示x节点为父节点的右节点
  56.                     else
  57.                         xp.right = x;
  58.                     /* 进行红黑树的插入平衡
  59.                         (通过左旋、右旋和改变节点颜色来保证当前树符合红黑树的要求) */
  60.                     root = balanceInsertion(root, x);
  61.                     break;
  62.                 }
  63.             }
  64.         }
  65.     }
  66.     // 确保root节点是table索引位置的头节点
  67.     moveRootToFront(tab, root);
  68. }

get操作

  1. // 返回指定key在集合中映射的value值，如果集合中不包含该key的映射就返回null
  2. public V get(Object key) {
  3.     Node<K,V> e;
  4.     return (e = getNode(hash(key), key)) == null ? null : e.value;
  5. }
  7. // get方法的具体实现
  8. final Node<K,V> getNode(int hash, Object key) {
  9.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  10.     // key找到索引位置，table索引位置中的元素不为空，找到第一个节点
  11.     if ((tab = table) != null && (n = tab.length) > 0 &&
  12.         (first = tab[(n - 1) & hash]) != null) {
  13.         // 如果第一个节点就是我们要找的，直接返回
  14.         if (first.hash == hash && // always check first node
  15.             ((k = first.key) == key || (key != null && key.equals(k))))
  16.             return first;
  17.         // 遍历冲突链或者红黑树
  18.         if ((e = first.next) != null) {
  19.             // 节点为树节点，表示该索引位置中的是一颗红黑树
  20.             if (first instanceof TreeNode)
  21.                 // 调用树的遍历方法查找目标
  22.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  23.             do {
  24.                 // 到达这里，说明索引位置中的是普通冲突链表，遍历查找目标
  25.                 if (e.hash == hash &&
  26.                     ((k = e.key) == key || (key != null && key.equals(k))))
  27.                     return e;
  28.             } while ((e = e.next) != null);
  29.         }
  30.     }
  31.     return null;
  32. }

getTreeNode

  1. 找到根节点
  2. 从根节点开始遍历树
    1. 如果当前对象的key与查询的key一致，则返回，否则判断下一个节点是右子节点还是左子节点
    2. 继续遍历，直到找到对象，找不到返回null
  1. // 从根节点开始遍历树查找
  2. final TreeNode<K,V> getTreeNode(int h, Object k) {
  3.     return ((parent != null) ? root() : this).find(h, k, null);
  4. }
  5. // 从调用该方法的节点开始遍历树，根据hash和key进行比较，规则：左节点 < 父节点 < 右节点
  6. final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
  7.     // 将调用该方法的节点赋值给p，就是红黑树的根节点
  8.     TreeNode<K,V> p = this;
  9.     // 从p节点开始向下遍历
  10.     do {
  11.         int ph, dir; K pk;
  12.         TreeNode<K,V> pl = p.left, pr = p.right, q;
  13.         // 目标hash值小于p的hash值，说明目标在p的左子树上
  14.         if ((ph = p.hash) > h)
  15.             p = pl;
  16.         // 目标hash值大于p的hash值，说明目标在p的右子树上
  17.         else if (ph < h)
  18.             p = pr;
  19.         // 目标hash值等于p的hash值，且key相同，说明该节点就是目标节点，直接返回该节点
  20.         else if ((pk = p.key) == k || (k != null && k.equals(pk)))
  21.             return p;
  22.         // 左子树为空，遍历右子树
  23.         else if (pl == null)
  24.             p = pr;
  25.         // 右子树为空，遍历左子树
  26.         else if (pr == null)
  27.             p = pl;
  28.         // 比较p节点和k节点
  29.         else if ((kc != null ||
  30.                   (kc = comparableClassFor(k)) != null) &&
  31.                  // k<pk,dir<0向左遍历;k>pk,dir>0向右遍历
  32.                  (dir = compareComparables(kc, k, pk)) != 0)
  33.             p = (dir < 0) ? pl : pr;
  34.         // 右子树上找到了目标节点，返回该节点
  35.         else if ((q = pr.find(h, k, kc)) != null)
  36.             return q;
  37.         // 右子树上没找到目标节点，遍历左子树
  38.         else
  39.             p = pl;
  40.     } while (p != null);
  41.     return null;
  42. }