（一）（ Map集合底层实现）HashMap、LinkedHashMap、Hashtable，ConcurrentHashMap，TreeMap的底层实现。

矫情吗；* 2021-09-15 03:50 364阅读 0赞

(一)HahMap：数组+链表\-->构成哈希表形式。【效率高，线程不安全-->不支持并发；put操作会引起死锁，导致CPU利用率接近100%】

1.    get（）----从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

put（）----当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部

简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry\[\] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

2.0 HashMap的resize（rehash）【扩容很消耗性能--->所以预设元素个数能有效提高HashMap性能】

3.0 遍历的方式：

# HashMap的两种遍历方式 #

## 第一种 ##

<table style="border-spacing:0px;width:620px;border:0px;margin:0px;padding:0px;font-size:12px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;min-height:auto;"> 
 <tbody style="margin:0px;padding:0px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;"> 
  <tr style="border-top:0px;margin:0px;padding:0px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;"> 
   <td style="border-width:0px;margin:0px;padding:0px;font-size:12px;vertical-align:baseline;background:none;float:none;height:auto;line-height:1.1em;width:auto;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;min-height:auto;color:rgb(175,175,175);"> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      1 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      2 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      3 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      4 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      5 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      6 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      7 
    </div></td> 
   <td style="width:592px;border-width:0px;margin:0px;padding:0px;font-size:12px;vertical-align:baseline;background:none;float:none;height:auto;line-height:1.1em;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;min-height:auto;"> 
    <div style="margin-left:-10px;width:640px;border:0px;margin-top:0px;margin-right:0px;margin-bottom:0px;padding:0px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;min-height:auto;"> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">Map map = </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">new</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">HashMap();</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">　　Iterator iter = map.entrySet().iterator();</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">　　</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">while</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(iter.hasNext()) { </code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">　　Map.Entry entry = (Map.Entry) iter.next();</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">　　Object key = entry.getKey();</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">　　Object val = entry.getValue();</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">　　}</code> 
     </div> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

效率高,以后一定要使用此种方式！

## 第二种 ##

<table style="border-spacing:0px;width:620px;border:0px;margin:0px;padding:0px;font-size:12px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;min-height:auto;"> 
 <tbody style="margin:0px;padding:0px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;"> 
  <tr style="border-top:0px;margin:0px;padding:0px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;"> 
   <td style="border-width:0px;margin:0px;padding:0px;font-size:12px;vertical-align:baseline;background:none;float:none;height:auto;line-height:1.1em;width:auto;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;min-height:auto;color:rgb(175,175,175);"> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      1 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      2 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      3 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      4 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      5 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      6 
    </div></td> 
   <td style="width:592px;border-width:0px;margin:0px;padding:0px;font-size:12px;vertical-align:baseline;background:none;float:none;height:auto;line-height:1.1em;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;min-height:auto;"> 
    <div style="margin-left:-10px;width:640px;border:0px;margin-top:0px;margin-right:0px;margin-bottom:0px;padding:0px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;min-height:auto;"> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">Map map = </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">new</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">HashMap();</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">　　Iterator iter = map.keySet().iterator();</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">　　</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">while</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(iter.hasNext()) { </code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">　　Object key = iter.next();</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">　　Object val = map.get(key);</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">　　}</code> 
     </div> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

效率低,以后尽量少使用！

（二）LinkedHashMap【继承于HashMap】---哈希表 和 双向链表   【依靠双向链表\-->保证 迭代顺序是插入顺序】

1.相比HashMap多了after  和before两个指针。

1) Entry元素：

LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了数组中保存的元素Entry，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。看源代码：

Java代码   ![收藏代码][icon_star.png]

1.  /\*\* 
2.   \* 双向链表的表头元素。 
3.   \*/  
4.  **private** **transient** Entry<K,V> header;  
5.    
6.  /\*\* 
7.   \* LinkedHashMap的Entry元素。 
8.   \* 继承HashMap的Entry元素，又保存了其上一个元素before和下一个元素after的引用。 
9.   \*/  
10. **private** **static** **class** Entry<K,V> **extends** HashMap.Entry<K,V> \{  
11.     Entry<K,V> before, after;  
12.     ……  
13. \}

2) 初始化：

通过源代码可以看出，在LinkedHashMap的构造方法中，实际调用了父类HashMap的相关构造方法来构造一个底层存放的table数组。如：

Java代码   ![收藏代码][icon_star.png]

1.  **public** LinkedHashMap(**int** initialCapacity, **float** loadFactor) \{  
2.      **super**(initialCapacity, loadFactor);  
3.      accessOrder = **false**;  
4.  \}

3) 存储：

LinkedHashMap并未重写父类HashMap的put方法，而是重写了父类HashMap的put方法调用的子方法void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现。

Java代码   ![收藏代码][icon_star.png]

1.  **void** addEntry(**int** hash, K key, V value, **int** bucketIndex) \{  
2.      // 调用create方法，将新元素以双向链表的的形式加入到映射中。  
3.      createEntry(hash, key, value, bucketIndex);  
4.    
5.      // 删除最近最少使用元素的策略定义  
6.      Entry<K,V> eldest = header.after;  
7.      **if** (removeEldestEntry(eldest)) \{  
8.          removeEntryForKey(eldest.key);  
9.      \} **else** \{  
10.         **if** (size >= threshold)  
11.             resize(2 \* table.length);  
12.     \}  
13. \}

Java代码   ![收藏代码][icon_star.png]

1.  **void** createEntry(**int** hash, K key, V value, **int** bucketIndex) \{  
2.      HashMap.Entry<K,V> old = table\[bucketIndex\];  
3.      Entry<K,V> e = **new** Entry<K,V>(hash, key, value, old);  
4.      table\[bucketIndex\] = e;  
5.      // 调用元素的addBrefore方法，将元素加入到哈希、双向链接列表。  
6.      e.addBefore(header);  
7.      size++;  
8.  \}

Java代码   ![收藏代码][icon_star.png]

1.  **private** **void** addBefore(Entry<K,V> existingEntry) \{  
2.      after  = existingEntry;  
3.      before = existingEntry.before;  
4.      before.after = **this**;  
5.      after.before = **this**;  
6.  \}

4) 读取：

LinkedHashMap重写了父类HashMap的get方法，实际在调用父类getEntry()方法取得查找的元素后，再判断当排序模式accessOrder为true时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。

Java代码   ![收藏代码][icon_star.png]

1.  **public** V get(Object key) \{  
2.      // 调用父类HashMap的getEntry()方法，取得要查找的元素。  
3.      Entry<K,V> e = (Entry<K,V>)getEntry(key);  
4.      **if** (e == **null**)  
5.          **return** **null**;  
6.      // 记录访问顺序。  
7.      e.recordAccess(**this**);  
8.      **return** e.value;  
9.  \}

Java代码   ![收藏代码][icon_star.png]

1.  **void** recordAccess(HashMap<K,V> m) \{  
2.      LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  
3.      // 如果定义了LinkedHashMap的迭代顺序为访问顺序，  
4.      // 则删除以前位置上的元素，并将最新访问的元素添加到链表表头。  
5.      **if** (lm.accessOrder) \{  
6.          lm.modCount++;  
7.          remove();  
8.          addBefore(lm.header);  
9.      \}  
10. \}

5) 排序模式：

LinkedHashMap定义了排序模式accessOrder，该属性为boolean型变量，对于访问顺序，为true；对于插入顺序，则为false。

Java代码   ![收藏代码][icon_star.png]

1.  **private** **final** **boolean** accessOrder;

一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。看LinkedHashMap的构造方法，如：

Java代码   ![收藏代码][icon_star.png]

1.  **public** LinkedHashMap(**int** initialCapacity, **float** loadFactor) \{  
2.      **super**(initialCapacity, loadFactor);  
3.      accessOrder = **false**;  
4.  \}

这些构造方法都会默认指定排序模式为插入顺序。如果你想构造一个LinkedHashMap，并打算按从近期访问最少到近期访问最多的顺序（即访问顺序）来保存元素，那么请使用下面的构造方法构造LinkedHashMap：

Java代码   ![收藏代码][icon_star.png]

1.  **public** LinkedHashMap(**int** initialCapacity,  
2.           **float** loadFactor,  
3.                       **boolean** accessOrder) \{  
4.      **super**(initialCapacity, loadFactor);  
5.      **this**.accessOrder = accessOrder;  
6.  \}

该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建LRU缓存。LinkedHashMap提供了removeEldestEntry(Map.Entry<K,V> eldest)方法，在将新条目插入到映射后，put和 putAll将调用此方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。

Java代码   ![收藏代码][icon_star.png]

1.  **protected** **boolean** removeEldestEntry(Map.Entry<K,V> eldest) \{  
2.      **return** **false**;  
3.  \}

此方法通常不以任何方式修改映射，相反允许映射在其返回值的指引下进行自我修改。如果用此映射构建LRU缓存，则非常方便，它允许映射通过删除旧条目来减少内存损耗。  
   例如：重写此方法，维持此映射只保存100个条目的稳定状态，在每次添加新条目时删除最旧的条目。

Java代码   ![收藏代码][icon_star.png]

1.  **private** **static** **final** **int** MAX\_ENTRIES = 100;  
2.  **protected** **boolean** removeEldestEntry(Map.Entry eldest) \{  
3.      **return** size() > MAX\_ENTRIES;  
4.  \}

（三）**效率低下**HashTable的**容器【底层实现：【拉链法实现的】哈希表。线程安全，synchronized关键字，锁住整个哈希表】**

**   1.继承自Dictionary ；**

**     实现了 Map接口       **

**   2.  **HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时，其他线程访问HashTable的同步方法时，可能会进入阻塞或轮询状态。如线程1使用put进行添加元素，线程2不但不能使用put方法添加元素，并且也不能使用get方法来获取元素，所以竞争越激烈效率越低

（四）ConcurrentHashMap：【高并发，高吞吐量的HashMap。线程安全的，高效的，支持并发（因为用了segment锁分段技术）】

1. 它使用了多个锁来控制对hash表的不同部分进行的修改。ConcurrentHashMap内部使用段(Segment结构)来表示这些不同的部分，【每个段其实就是一个小的hashtable】，它们有自己的锁。只要多个修改操作发生在 不同的段上，它们就可以并发进行。

2.ConcurrentHashMap的结构：【Segment数组结构和HashEntry数组结构组成】

![70][]

3.put（）方法：

前面的所有的介绍其实都为这个方法做铺垫。ConcurrentHashMap最常用的就是put和get两个方法。现在来介绍put方法，这个put方法依然沿用HashMap的put方法的思想，根据hash值计算这个新插入的点在table中的位置i，如果i位置是空的，直接放进去，否则进行判断，如果i位置是树节点，按照树的方式插入新的节点，否则把i插入到链表的末尾。ConcurrentHashMap中依然沿用这个思想，有一个最重要的不同点就是ConcurrentHashMap不允许key或value为null值。另外由于涉及到多线程，put方法就要复杂一点。在多线程中可能有以下两个情况

①如果一个或多个线程正在对ConcurrentHashMap进行扩容操作，当前线程也要进入扩容的操作中。这个扩容的操作之所以能被检测到，是因为transfer方法中在空结点上插入forward节点，如果检测到需要插入的位置被forward节点占有，就帮助进行扩容；

②如果检测到要插入的节点是非空且不是forward节点，就对这个节点加锁，这样就保证了线程安全。尽管这个有一些影响效率，但是还是会比hashTable的synchronized要好得多。

整体流程就是首先定义不允许key或value为null的情况放入  对于每一个放入的值，首先利用spread方法对key的hashcode进行一次hash计算，由此来确定这个值在table中的位置。

如果这个位置是空的，那么直接放入，而且不需要加锁操作。

如果这个位置存在结点，说明发生了hash碰撞，首先判断这个节点的类型。

如果是链表节点（fh>0）,则得到的结点就是hash值相同的节点组成的链表的头节点。需要依次向后遍历确定这个新加入的值所在位置。如果遇到hash值与key值都与新加入节点是一致的情况，则只需要更新value值即可。否则依次向后遍历，直到链表尾插入这个结点。

如果加入这个节点以后链表长度大于8，就把这个链表转换成红黑树。

如果这个节点的类型已经是树节点的话，直接调用树节点的插入方法进行插入新的值。

4.get方法（）

get方法比较简单，给定一个key来确定value的时候，必须满足两个条件  key相同  hash值相同，对于节点可能在链表或树上的情况，需要分别去查找.

5. treeifyBin（）方法

这个方法用于将过长的链表转换为TreeBin对象。但是他并不是直接转换，而是进行一次容量判断，如果容量没有达到转换的要求，直接进行扩容操作并返回；如果满足条件才链表的结构抓换为TreeBin ，这与HashMap不同的是，它并没有把TreeNode直接放入红黑树，而是利用了TreeBin这个小容器来封装所有的TreeNode.

（五）TreeMap：【基于红黑树（一种自平衡的二叉树）实现-->】

1.什么是平衡二叉树：

平衡二叉树必须具备如下特性：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个等等子节点，其左右子树的高度都相近。

![SouthEast][]

2.put方法（）：

如果存在的话，old value被替换；如果不存在的话，则新添一个节点，然后对做红黑树的平衡操作。

<table style="border-spacing:0px;width:620px;border:0px;margin:0px;padding:0px;font-size:12px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;min-height:auto;"> 
 <tbody style="margin:0px;padding:0px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;"> 
  <tr style="border-top:0px;margin:0px;padding:0px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;"> 
   <td style="border-width:0px;margin:0px;padding:0px;font-size:12px;vertical-align:baseline;background:none;float:none;height:auto;line-height:1.1em;width:auto;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;min-height:auto;color:rgb(175,175,175);"> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      1 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      2 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      3 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      4 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      5 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      6 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      7 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      8 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      9 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      10 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      11 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      12 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      13 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      14 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      15 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      16 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      17 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      18 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      19 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      20 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      21 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      22 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      23 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      24 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      25 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      26 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      27 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      28 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      29 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      30 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      31 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      32 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      33 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      34 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      35 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      36 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      37 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      38 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      39 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      40 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      41 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      42 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      43 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      44 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      45 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      46 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      47 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      48 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      49 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      50 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      51 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      52 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      53 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      54 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      55 
    </div></td> 
   <td style="width:585.6px;border-width:0px;margin:0px;padding:0px;font-size:12px;vertical-align:baseline;background:none;float:none;height:auto;line-height:1.1em;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;min-height:auto;"> 
    <div style="margin-left:-10px;width:640px;border:0px;margin-top:0px;margin-right:0px;margin-bottom:0px;padding:0px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;min-height:auto;"> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">public</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">V put(K key, V value) { </code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">Entry&lt;K,V&gt; t = root;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">if</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(t == </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">null</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">) { </code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">compare(key, key); </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,130,0);">// type (and possibly null) check</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
       &nbsp; 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">root = </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">new</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">Entry&lt;&gt;(key, value, </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">null</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">);</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">size = </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,153,0);">1</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">modCount++;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">return</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">null</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">}</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">int</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">cmp;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">Entry&lt;K,V&gt; parent;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,130,0);">// split comparator and comparable paths</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">Comparator&lt;? </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">super</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">K&gt; cpr = comparator;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,130,0);">// 如果该节点存在，则替换值直接返回</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">if</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(cpr != </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">null</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">) { </code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">do</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">{ </code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">parent = t;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">cmp = cpr.compare(key, t.key);</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">if</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(cmp &lt; </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,153,0);">0</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">)</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">t = t.left;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">else</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">if</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(cmp &gt; </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,153,0);">0</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">)</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">t = t.right;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">else</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">return</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">t.setValue(value);</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">} </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">while</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(t != </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">null</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">);</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">}</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">else</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">{ </code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">if</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(key == </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">null</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">)</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">throw</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">new</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">NullPointerException();</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#808080;">@SuppressWarnings</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#0000FF;">"unchecked"</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">)</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">Comparable&lt;? </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">super</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">K&gt; k = (Comparable&lt;? </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">super</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">K&gt;) key;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">do</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">{ </code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">parent = t;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">cmp = k.compareTo(t.key);</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">if</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(cmp &lt; </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,153,0);">0</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">)</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">t = t.left;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">else</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">if</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(cmp &gt; </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,153,0);">0</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">)</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">t = t.right;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">else</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">return</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">t.setValue(value);</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">} </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">while</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(t != </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">null</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">);</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">}</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,130,0);">// 如果该节点未存在，则新建</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">Entry&lt;K,V&gt; e = </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">new</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">Entry&lt;&gt;(key, value, parent);</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">if</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(cmp &lt; </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,153,0);">0</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">)</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">parent.left = e;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">else</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">parent.right = e;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,130,0);">// 红黑树平衡调整</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">fixAfterInsertion(e);</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">size++;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">modCount++;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">return</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">null</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">}</code> 
     </div> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

### 3. get（）函数 ###

get函数则相对来说比较简单，以log(n)的复杂度进行get

<table style="border-spacing:0px;width:620px;border:0px;margin:0px;padding:0px;font-size:12px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;min-height:auto;"> 
 <tbody style="margin:0px;padding:0px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;"> 
  <tr style="border-top:0px;margin:0px;padding:0px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;"> 
   <td style="border-width:0px;margin:0px;padding:0px;font-size:12px;vertical-align:baseline;background:none;float:none;height:auto;line-height:1.1em;width:auto;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;min-height:auto;color:rgb(175,175,175);"> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      1 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      2 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      3 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      4 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      5 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      6 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      7 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      8 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      9 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      10 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      11 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      12 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      13 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      14 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      15 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      16 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      17 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      18 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      19 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      20 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      21 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      22 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      23 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      24 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      25 
    </div> 
    <div style="border-width:0px 3px 0px 0px;border-right-style:solid;border-right-color:rgb(108,226,108);margin:0px;padding:0px .5em 0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;text-align:right;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
      26 
    </div></td> 
   <td style="width:585.6px;border-width:0px;margin:0px;padding:0px;font-size:12px;vertical-align:baseline;background:none;float:none;height:auto;line-height:1.1em;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;min-height:auto;"> 
    <div style="margin-left:-10px;width:640px;border:0px;margin-top:0px;margin-right:0px;margin-bottom:0px;padding:0px;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;min-height:auto;"> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">final</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">Entry&lt;K,V&gt; getEntry(Object key) { </code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,130,0);">// Offload comparator-based version for sake of performance</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">if</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(comparator != </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">null</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">)</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">return</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">getEntryUsingComparator(key);</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">if</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(key == </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">null</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">)</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">throw</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">new</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">NullPointerException();</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#808080;">@SuppressWarnings</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#0000FF;">"unchecked"</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">)</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">Comparable&lt;? </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">super</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">K&gt; k = (Comparable&lt;? </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">super</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">K&gt;) key;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">Entry&lt;K,V&gt; p = root;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,130,0);">// 按照二叉树搜索的方式进行搜索，搜到返回</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">while</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(p != </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">null</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">) { </code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">int</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">cmp = k.compareTo(p.key);</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">if</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(cmp &lt; </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,153,0);">0</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">)</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">p = p.left;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">else</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">if</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(cmp &gt; </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:rgb(0,153,0);">0</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">)</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">p = p.right;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">else</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">return</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">p;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">}</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">return</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">null</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">;</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">}</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;">
       &nbsp; 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">public</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">V get(Object key) { </code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">Entry&lt;K,V&gt; p = getEntry(key);</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">return</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">(p==</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">null</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">? </code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;color:rgb(0,102,153);">null</code> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">: p.value);</code> 
     </div> 
     <div style="border:0px;margin:0px;padding:0px 1em;background-image:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;white-space:pre;"> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;">}</code> 
     </div> 
     <div> 
      <code style="border:0px;margin:0px;padding:0px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;background:none;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;color:#000000;"><br></code> 
     </div> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

[icon_star.png]: /images/20210811/27580aa0d5b04b618fcefa212efac59b.png
[70]: /images/20210811/cd53670e173540a4820c058a3e455bf1.png
[SouthEast]: /images/20210811/c33594c3240c475e8fd8eeb94cd323fa.png

发表评论取消回复

表情：

评论列表（有 0 条评论，364人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java 集合、HashMap 底层实现原理

一、Java 集合概述 Java 集合可分为 Collection 和 Map 两种体系 Collection接口：单列数据，定义了存取一组对象的方法的集合

青旅半醒/ 2024年04月01日 15:43/ 0 赞/ 78 阅读

相关 java集合的底层原理（Map的底层原理（WeakHashMap）四）

一、概念相关 WeakHashMap ，从名字上看，直接翻译就知道，这是一种弱的HashMap,那这个弱字表面看起来有点不好理解，其实这是跟对象引用相关的，

「爱情、让人受尽委屈。」/ 2023年02月17日 03:15/ 0 赞/ 21 阅读

相关底层实现_死磕synchronized底层实现

![d8f9aa82ef5f34a8c10d3a824bf2126b.png][] > 点赞再看，养成习惯，微信搜索【三太子敖丙】第一时间阅读。 > 本文 GitHub

客官°小女子只卖身不卖艺/ 2023年01月06日 04:21/ 0 赞/ 226 阅读

相关 java集合的底层实现_java-集合学习-底层实现

Collection类关系图 ![2ffc3f3aa7b1a206b6761576ea2b277a.png][] 单向链表由若干个节点组成，每个节点除了数据域之外还保存

水深无声/ 2022年11月05日 03:24/ 0 赞/ 18 阅读

相关 Docker 底层实现

Docker 底层实现简介基本架构命名空间 pid 命名空间 net 命名空间

素颜马尾好姑娘i/ 2022年06月04日 00:05/ 0 赞/ 244 阅读

相关集合各实现类的底层实现原理

ArrayList实现原理要点概括参考文献： [http://zhangshixi.iteye.com/blog/674856l][http_zhangshixi

雨点打透心脏的1/2处/ 2022年05月24日 07:06/ 0 赞/ 184 阅读

相关 Synchronzied底层实现

synchronized的底层是使用操作系统的mutex lock实现； Mutex Lock 监视器锁（Monitor）本质是依赖于底层操作系统的Mutex Lock

你的名字/ 2022年05月23日 13:16/ 0 赞/ 236 阅读

相关 HashMap底层实现

HashMap发布于jdk1.2，发布HashMap的主要原因在于弥补Hashtable的效率问题，因为Hashtable是同步式实现，所以性能比较差。其实就是优化版Hasht

Myth丶恋晨/ 2022年05月15日 03:24/ 0 赞/ 312 阅读

相关 Dubbo底层实现

1.Dubbo的底层实现（1）协议支持 Dubbo支持多种协议，如下所示： Dubbo协议 Hessian协议 HTTP协议 RMI协议 WebServic

朴灿烈づ我的快乐病毒、/ 2022年04月22日 02:00/ 0 赞/ 227 阅读

相关（一）（ Map集合底层实现）HashMap、LinkedHashMap、Hashtable，ConcurrentHashMap，TreeMap的底层实现。

(一)HahMap：数组+链表\-->构成哈希表形式。【效率高，线程不安全-->不支持并发；put操作会引起死锁，导致CPU利用率接近100%】 1. get（）-

矫情吗；*/ 2021年09月15日 03:50/ 0 赞/ 365 阅读