JDK7与JDK8中HashMap的实现

落日映苍穹つ 2022-05-21 23:48 181阅读 0赞

## JDK7中的HashMap ##

HashMap底层维护一个数组，数组中的每一项都是一个Entry

我们向 HashMap 中所放置的对象实际上是存储在该数组当中；

而Map中的key，value则以Entry的形式存放在数组中

而这个Entry应该放在数组的哪一个位置上（这个位置通常称为位桶或者hash桶，即hash值相同的Entry会放在同一位置，用链表相连），是通过key的hashCode来计算的。

通过hash计算出来的值将会使用indexFor方法找到它应该所在的table下标：

这个方法其实相当于对table.length取模。

当两个key通过hashCode计算相同时，则发生了hash冲突(碰撞)，HashMap解决hash冲突的方式是用链表。

当发生hash冲突时，则将存放在数组中的Entry设置为新值的next（这里要注意的是，比如A和B都hash后都映射到下标i中，之前已经有A了，当map.put(B)时，将B放到下标i中，A则为B的next，所以新值存放在数组中，旧值在新值的链表上）

示意图：

![210043_4aAJ_2243330.png][]

所以当hash冲突很多时，HashMap退化成链表。

总结一下map.put后的过程：

当向 HashMap 中 put 一对键值时，它会根据 key的 hashCode 值计算出一个位置， 该位置就是此对象准备往数组中存放的位置。

如果该位置没有对象存在，就将此对象直接放进数组当中；如果该位置已经有对象存在了，则顺着此存在的对象的链开始寻找(为了判断是否是否值相同，map不允许<key,value>键值对重复)， 如果此链上有对象的话，再去使用 equals方法进行比较，如果对此链上的每个对象的 equals 方法比较都为 false，则将该对象放到数组当中，然后将数组中该位置以前存在的那个对象链接到此对象的后面。

值得注意的是，当key为null时，都放到table\[0\]中

<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></td> 
   <td style="width:585px;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);">private</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 putForNullKey(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;&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);">for</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 = table[</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;">]; 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);">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;">; e = e.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;">&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;">(e.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;&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;">V oldValue = e.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;&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;">e.value = 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;&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;">e.recordAccess(</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);">this</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;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;">oldValue;</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;">}</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> 
     </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;min-height:auto;color:#000000;">addEntry(</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> 
      <code style="border:0px;margin:0px;padding:0px;font-family: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;">, 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;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;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></td> 
  </tr> 
 </tbody> 
</table>

当size大于threshold时，会发生扩容。 threshold等于capacity\*load factor

jdk7中resize，只有当 size>=threshold并且 table中的那个槽中已经有Entry时，才会发生resize。即有可能虽然size>=threshold，但是必须等到每个槽都至少有一个Entry时，才会扩容。还有注意每次resize都会扩大一倍容量

## JDK8中的HashMap ##

一直到JDK7为止，HashMap的结构都是这么简单，基于一个数组以及多个链表的实现，hash值冲突的时候，就将对应节点以链表的形式存储。

这样子的HashMap性能上就抱有一定疑问，如果说成百上千个节点在hash时发生碰撞，存储一个链表中，那么如果要查找其中一个节点，那就不可避免的花费O(N)的查找时间，这将是多么大的性能损失。这个问题终于在JDK8中得到了解决。再最坏的情况下，链表查找的时间复杂度为O(n),而红黑树一直是O(logn),这样会提高HashMap的效率。

JDK7中HashMap采用的是位桶+链表的方式，即我们常说的散列链表的方式，而JDK8中采用的是位桶+链表/红黑树（有关红黑树请查看[红黑树][Link 1]）的方式，也是非线程安全的。当某个位桶的链表的长度达到某个阀值(默认超过8)的时候，这个链表就将转换成红黑树。

![184438_IA5n_2243330.jpg][]JDK8中，当同一个hash值的节点数不小于8时，将不再以单链表的形式存储了，会被调整成一颗红黑树（上图中null节点没画）。这就是JDK7与JDK8中HashMap实现的最大区别。

接下来，我们来看下JDK8中HashMap的源码实现。

JDK中Entry的名字变成了Node，原因是和红黑树的实现TreeNode相关联。

当冲突节点数不小于8-1时，转换成红黑树。

以put方法在JDK8中有了很大的改变

<table style="border-spacing:0px;width:672px;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> 
    <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;">
      56 
    </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;">
      57 
    </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;">
      58 
    </div></td> 
   <td style="width:637px;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;&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;">putVal(hash(key), 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);">false</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);">true</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;</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;">
       &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);">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;">V putVal(</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;">hash, K key, V 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);">boolean</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;">onlyIfAbsent,</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;&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);">boolean</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;">evict) { </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;">Node&lt;K,V&gt;[] tab;</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;">Node&lt;K,V&gt; 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;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;">n, i;</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);">//如果当前map中无数据，执行resize方法。并且返回n</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;">((tab = table) == </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;">|| (n = tab.length) == </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;">n = (tab = resize()).length;</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;</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);">//如果要插入的键值对要存放的这个位置刚好没有元素，那么把他封装成Node对象，放在这个位置上就完事了</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;">((p = tab[i = (n - </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;">) &amp; hash]) == </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;min-height:auto;color:#000000;">tab[i] = newNode(hash, 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;</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;&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;&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;">Node&lt;K,V&gt; e; K k;</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);">//如果这个元素的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;">(p.hash == hash &amp;&amp;</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;">((k = p.key) == 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;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;">&amp;&amp; key.equals(k))))</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;">e = 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;&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);">//1.如果当前节点是TreeNode类型的数据，执行putTreeVal方法</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;">(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);">instanceof</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;">TreeNode)</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;">e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(</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);">this</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;">, tab, hash, key, 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;&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;min-height:auto;color:rgb(0,130,0);">//还是遍历这条链子上的数据，跟jdk7没什么区别</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);">for</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);">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;">binCount = </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;">; ; ++binCount) { </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;&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;">((e = p.next) == </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;&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.next = newNode(hash, 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;&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);">//2.完成了操作后多做了一件事情，判断，并且可能执行treeifyBin方法</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;&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;">(binCount &gt;= TREEIFY_THRESHOLD - </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> 
      <code style="border:0px;margin:0px;padding:0px;font-family: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);">// -1 for 1st</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;&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;">treeifyBin(tab, hash);</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;&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);">break</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;&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;&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;">(e.hash == hash &amp;&amp;</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;&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;">((k = e.key) == 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;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;">&amp;&amp; key.equals(k))))</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;&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);">break</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;&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 = 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;&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> 
     </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;">}</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;">(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);">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;min-height:auto;color:rgb(0,130,0);">// existing mapping for 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;&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;">V oldValue = e.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;&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;">(!onlyIfAbsent || oldValue == </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;min-height:auto;color:rgb(0,130,0);">//true || --</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;&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;">e.value = 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;&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);">//3.</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;">afterNodeAccess(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;&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;">oldValue;</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;">}</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> 
     </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;</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;&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;">(++size &gt; threshold)</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;">resize();</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);">//4.</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;">afterNodeInsertion(evict);</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></td> 
  </tr> 
 </tbody> 
</table>

treeifyBin()就是将链表转换成红黑树。

之前的indefFor()方法消失 了，直接用(tab.length-1)&hash，所以看到这个，代表的就是数组的下角标。

<table style="width:620px;border-spacing:0px;margin:0px;border-width: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;background:none;margin:0px;padding:0px;float:none;height:auto;line-height:1.1em;vertical-align:baseline;width:auto;min-height:auto;"> 
   <td style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;font-size:12px;border-width:0px;color:rgb(175,175,175);line-height:1.1em;padding:0px;margin:0px;vertical-align:baseline;background:none;float:none;height:auto;width:auto;min-height:auto;"> 
    <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></td> 
   <td style="width:592px;font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;font-size:12px;border-width:0px;line-height:1.1em;padding:0px;margin:0px;vertical-align:baseline;background:none;float:none;height:auto;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="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:rgb(0,102,153);background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;">static</code> 
      <code style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:rgb(0,102,153);background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;">final</code> 
      <code style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:rgb(0,102,153);background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;">int</code> 
      <code style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:#000000;background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;min-height:auto;">hash(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="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:rgb(0,102,153);background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;">int</code> 
      <code style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:#000000;background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;min-height:auto;">h;</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="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:rgb(0,102,153);background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;">return</code> 
      <code style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:#000000;background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;min-height:auto;">(key ==&nbsp;</code> 
      <code style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:rgb(0,102,153);background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;font-weight:bold;min-height:auto;">null</code> 
      <code style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:#000000;background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;min-height:auto;">) ?&nbsp;</code> 
      <code style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:rgb(0,153,0);background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;min-height:auto;">0</code> 
      <code style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:#000000;background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;min-height:auto;">: (h = key.hashCode()) ^ (h &gt;&gt;&gt;&nbsp;</code> 
      <code style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:rgb(0,153,0);background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;min-height:auto;">16</code> 
      <code style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:#000000;background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;min-height:auto;">);</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="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;min-height:auto;">&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code style="font-family:Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace;line-height:1.1em;color:#000000;background:none;border:0px;margin:0px;padding:0px;float:none;height:auto;vertical-align:baseline;width:auto;min-height:auto;">}</code> 
     </div> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

性能提升有什么用处？例如说恶意的程序，假设它知道我们用的是哈希算法。它可能会发送大量的请求，导致产生严重的哈希碰撞。然后不停的訪问这些 key就能显著的影响server的性能。这样就形成了一次拒绝服务攻击（DoS）。

JDK 8中从O(n)到O(logn)的飞跃，能够有效地防止类似的攻击，同一时候也让HashMap性能的可预測性略微增强了一些

JDK7即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。

当插入新元素时，对于红黑树的判断如下：

判断table\[i\] 是否为treeNode，即table\[i\] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向下面；

遍历table\[i\]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

文章来源：[http://www.importnew.com/23164.html][http_www.importnew.com_23164.html]

[210043_4aAJ_2243330.png]: /images/20220522/c34534cfea0e4e02927fcf2f6b2ac13c.png
[Link 1]: http://my.oschina.net/hosee/blog/618828
[184438_IA5n_2243330.jpg]: /images/20220522/43af42cae8d04af5adce2e1c7492f495.png
[http_www.importnew.com_23164.html]: http://www.importnew.com/23164.html