JDK源码分析之hashmap就这么简单理解

 public V put(K key, V value) {　　　　　//(1)        if (table == EMPTY_TABLE) {            inflateTable(threshold);        }　　　　　//（2）        if (key == null)            return putForNullKey(value);　　　　　//(3)        int hash = hash(key);　　　　　//(4)        int i = indexFor(hash, table.length);　　　　　//(5)        for (Entry<K,V> e = table[i]; e != null; e = e.next) {              k;　　　　　　　//(6)            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {                V oldValue = e.value;                e.value = value;                e.recordAccess(this);                return oldValue;            }        }　　　　　//(7)        modCount++;　　　　　//(8)        addEntry(hash, key, value, i);        return null;    }

代码（1）如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(=16)。、

代码（2）若“key为null”，则将该键值对添加到table[0]处，遍历该链表，如果有存在key为null的entry，则将value替换。没有就创建新Entry对象放在链表表头，所以table[0]的位置上，永远最多存储1个Entry对象，形成不了链表。key为null的Entry存在这里。

代码（3）若key不为null，则计算该key的hash值，然后将其添加到该哈希值对应的数组索引处的链表中。

代码（4）根据hash值计算桶号。

代码（5）遍历该桶中的链表。

代码（6）如果其hash值相等且键也相等，将新值替换旧值，并返回旧值。

代码（7）保证并发访问时，若HashMap内部结构发生变化，快速响应失败。即修改次数+1

代码（8）如果桶是空的，说明当前位置没有数据存入；新增一个 Entry 对象写入当前位置。

接下来我们进入到代码（1）中的数组空间分配的方法 inflateTable(threshold)，源码如下：

private void inflateTable(int toSize) {        int capacity = roundUpToPowerOf2(toSize);//（1）        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//（2）        table = new Entry[capacity];//（3）        initHashSeedAsNeeded(capacity);//（4）    }

代码（1）capacity一定是2的次幂

代码（2）此处为threshold赋值，取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值，capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1。

代码（3）分配空间。

代码（4）选择合适的Hash因子。

inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16；to_size=16，capacity=16；to_size=17,capacity=32。roundUpToPowerOf2(toSize)源码如下所示：

　　private static int roundUpToPowerOf2(int number) {        // assert number >= 0 : "number must be non-negative";        return number >= MAXIMUM_CAPACITY                ? MAXIMUM_CAPACITY                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;    }

roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂，Integer.highestOneBit是用来获取最左边的bit（其他bit位为0）所代表的数值。

接下来我们看看put方法中的hash方法的计算，源码如下：

//(1)　　final int hash(  k) { 　　　　　//(2)        int h = hashSeed;　　　　　//(3)        if (0 != h && k instanceof String) {//这里针对String优化了Hash函数，是否使用新的Hash函数和Hash因子有关              return sun.misc.Hashing.stringHash32((String) k);        }　　　　　//(4)        h ^= k.hashCode();　　　　　//(5)        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }h ^= k.hashCode(): 0101 1101 0010 1111 1100 0110 0011 0101------------------------------------------------------------h >>> 20：       : 0000 0000 0000 0000 0000 0101 1101 0010h >>> 12         : 0000 0000 0000 0101 1101 0010 1111 1100 ------------------------------------------------------------(h >>> 20) ^ (h >>> 12)                 : 0000 0000 0000 0101 1101 0111 0010 1110-----------------------------------------------------------h ^= (h >>> 20) ^ (h >>> 12)                 : 0101 1101 0010 1010 0001 0001 0001 1011-----------------------------------------------------------(h >>> 7)        : 0000 0000 1011 1010 0101 0100 0010 0010(h >>> 4)        : 0000 0101 1101 0010 1010 0001 0001 0001 -----------------------------------------------------------(h >>> 7) ^ (h >>> 4)                 ：0000 0101 0110 1000 1111 0101 0011 0011-----------------------------------------------------------h ^ (h >>> 7) ^ (h >>> 4)                 ：0101 1000 0100 0010 1110 0100 0010 1000-----------------------------------------------------------h & (length-1)   ：0000 0000 0000 0000 0000 0000 0000 1000   = 8

代码（1）判断k的数据类型选择不同的hash计算方式。用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀。

代码（2）随机种子,用来降低冲突发生的几率

代码（3）这里针对String优化了Hash函数，是否使用新的Hash函数和Hash因子有关。

代码（5）这个函数确保哈希码在每个位的倍数不变的情况下只会发生有限数量的碰撞(默认负载系数大约为8)。

从上面的操作看以看出，影响HashMap元素的存储位置的只有key的值，与value值无关。

就这样，通过高低位之间进行异或用来加大低位的随机性，以减少冲突的几率。

通过hash函数得到散列值后，再通过indexFor进一步处理来获取实际的存储位置，其实现如下：

　//返回数组下标    static int indexFor(int h, int length) {　　　　//(1)        return h & (length-1);    }

代码（1）把hash值和数组的长度进行“与”操作。

该方法用于确定元素存放于数组的位置，但是参数h是一个由hash方法计算而来的int类型数据，如果直接拿h作为下标访问HashMap主数组的话，考虑到2进制32位带符号的int值范围从-2147483648到2147483648，该值可能会很大，所以这个值不能直接使用，要用它对数组的长度进行取模运算，得到的余数才能用来当做数组的下标，这就是indexFor方法做的事情。（因为length总是为2的N次方，所以h & (length-1)操作等价于hash % length操作， 但&操作性能更优）。

该方法也是HashMap的数组长度为什么总是2的N次方的原因。2的N次方 - 1的二进制码是一个“低位掩码”，“与”操作后会把hash值的高位置零，只保留低位的值，使用这种方法使值缩小。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。例子如下：

    10100101 11000100 00100101&   00000000 00000000 00001111----------------------------------    00000000 00000000 00000101 //高位全部归零，只保留末四位

这样，就算差距很大的两个数，只要低位相同，那么就会产生冲突，会对性能造成很大的影响，于是，hash方法的作用就体现出来了。

接着我们再看看普通方法中调用的addEntry方法，如下：

void addEntry(int hash, K key, V value, int bucketIndex) {　　　　　//(1)        if ((size >= threshold) && (null != table[bucketIndex])) {　　　　　　　//(2)            resize(2 * table.length);　　　　　　　//(3)            hash = (null != key) ? hash(key) : 0;　　　　　　　//(4)            bucketIndex = indexFor(hash, table.length);        }　　　　　//（5）        createEntry(hash, key, value, bucketIndex);    }        void createEntry(int hash, K key, V value, int bucketIndex) {　　　　　//(6)        Entry<K,V> e = table[bucketIndex];　　　　　//(7)        table[bucketIndex] = new Entry<>(hash, key, value, e);　　　　　//元素个数加1        size++;    }

代码（1）当调用 addEntry 写入 Entry 时需要判断是否需要扩容。

代码（2）当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容，新容量为旧容量的2倍。

代码（3）扩容后，重新计算哈希值。

代码（4）扩容后重新计算插入的位置下标，即重新计算桶号。

代码（5）createEntry 中会将当前位置的桶传入到新建的桶中，如果当前桶有值就会在位置形成链表。

代码（6）获取待插入位置元素

代码（7）这里执行链接操作，使得新插入的元素指向原有元素。这保证了新插入的元素总是在链表的头。

发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。接下来让我们看看resize（2 * table.length）的扩容方法，源码如下：

//按新的容量扩容Hash表      void resize(int newCapacity) {　　　　　//(1)          Entry[] oldTable = table;　　　　　//(2)          int oldCapacity = oldTable.length;　　　　　//(3)          if (oldCapacity == MAXIMUM_CAPACITY) {　　　　　　　//(4)              threshold = Integer.MAX_VALUE;//修改扩容阀值              return;          }          //(5)        Entry[] newTable = new Entry[newCapacity];　　　　 boolean oldAltHashing = useAltHashing; 　　　　 //(6)计算是否需要对键重新进行哈希码的计算　　　　 useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);　　　　 boolean rehash = oldAltHashing ^ useAltHashing;　　　　　//（7）          transfer(newTable, rehash);　　　　　//(8)          table = newTable;　　　　　//(9)          threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);    } 

代码（1）先获取老的数据

代码（2）获取老的容量值。

代码（3）如果老的容量值已经到了最大容量值，则修改扩容阙值

代码（5）创建新的结构

代码（6）计算是否需要对键重新进行哈希码的计算

代码（7）将老的表中的数据拷贝到新的结构中。将原有所有的桶迁移至新的桶数组中 ，在迁移时，桶在桶数组中的绝对位置可能会发生变化 *，这就是为什么HashMap不能保证存储条目的顺序不能恒久不变的原因

代码（8）修改HashMap的底层数组

代码（9）修改阀值 

接下来让我们进入到tranfer方法中，看看是如何进行桶迁移至新的桶数组中的，源码如下：

void transfer(Entry[] newTable, boolean rehash) {        int newCapacity = newTable.length;        //（1）        for (Entry<K,V> e : table) {            while(null != e) {                Entry<K,V> next = e.next;　　　　　　　　　　//（2）                if (rehash) {                    //(3)                    e.hash = null == e.key ? 0 : hash(e.key);                }                //（4）                int i = indexFor(e.hash, newCapacity);                //（5）                e.next = newTable[i];                //（6）                newTable[i] = e;　　　　　　　　　 //(7)                e = next;            }        }    }

代码（1）遍历当前的table，将里面的元素添加到新的newTable中。

代码（2）如果是重新Hash

代码（3）重新计算hash值。

代码（4）计算桶号

代码（5）元素连接到桶中,这里相当于单链表的插入，总是插入在最前面

代码（6）存放在数组下标i中,所以扩容后链表的顺序与原来相反。

代码（7）继续下一个元素。

接着，让我们看看HashMap的put方法，源码如下：

　 //(1)　　 public V get(  key) {　　　　　//(2）        if (key == null)            return getForNullKey();　　　　　//(3)        Entry<K,V> entry = getEntry(key);　　　　　//(4)        return null == entry ? null : entry.getValue();    }        final Entry<K,V> getEntry(  key) {　　　　　//(5)        if (size == 0) {            return null;        }　　　　　//（6）        int hash = (key == null) ? 0 : hash(key);　　　　　//(7)        for (Entry<K,V> e = table[indexFor(hash, table.length)];             e != null;             e = e.next) {              k;　　　　　　　//(8)            if (e.hash == hash &&                ((k = e.key) == key || (key != null && key.equals(k))))                return e;        }　　　　　//(9)        return null;    }　　 //获取key为null的实体      private V getForNullKey() {          if (size == 0) {//如果元素个数为0，则直接返回null              return null;          }          //key为null的元素存储在table的第0个位置          for (Entry<K,V> e = table[0]; e != null; e = e.next) {              if (e.key == null)//判断是否为null                  return e.value;//返回其值          }          return null;      } 

代码（1）获取key值为key的元素值。

代码（2）如果Key值为空，则获取对应的值，这里也可以看到，HashMap允许null的key，其内部针对null的key有特殊的逻辑。

代码（3）如果建不为null，获取Entry实体。

代码（4）判断是否为空，不为空，则获取对应的值。

代码（5）元素个数为 0 ，直接返回null。

代码（6）计算key的hash值。

代码（7）根据key和表的长度，定位到Hash桶。

代码（8）遍历直到 key 及 hashcode 相等时候就返回值。

代码（9）啥也没取到直返回null。

接着让我们看最后一个HashMap的方法，remove方法，源码如下：

final Entry<K,V> removeEntryForKey(  key) {        //计算键的hash值        int hash = (key == null) ? 0 : hash(key);        //计算桶号        int i = indexFor(hash, table.length);        //记录待删除节点的上一个节点        Entry<K,V> prev = table[i];        //待删除节点        Entry<K,V> e = prev;        while (e != null) {            Entry<K,V> next = e.next;              k;            //是否是将要删除的节点            if (e.hash == hash &&                ((k = e.key) == key || (key != null && key.equals(k)))) {                modCount++;                size--;                //将要删除的节点是否为链表的头部                if (prev == e)                    //链表的头部指向下一节点                    table[i] = next;                else                    //上一节点的NEXT为将要删除节点的下一节点                    prev.next = next;                e.recordRemoval(this);                return e;            }            prev = e;            e = next;        }        return e;    }

JDK1.8中，HashMap的变化。

　　到目前为止，不知道大家有没有发现JDK1.7中需要优化的地方？

正如开篇提到的当 Hash 冲突严重时，在桶上形成的链表会变的越来越长，这样在查询时的效率就会越来越低；时间复杂度为 O(N)。

因此JDK1.8中中采用的是位桶+链表/红黑树的结构实现，而在JDK1.8中的时候链表长度达到一个阙值(通常节点数量  > 8 )的时候就会转换成红黑树结构，至于红黑树，自己去了解后再来看此篇文章，众所周知红黑树的时间复杂度为 log n ，这无疑是对性能的一次大提升。相对于JDK1.7的位桶+链表的实现方式来说，性能谁优谁劣，可想而知。

JDK1.8中的HashMap的结构图如下：

接着让我们看看JDK1.8中的HashMap的成员变量。源码如下：

//（1） 默认的初始容量是16    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;       //（2） 桶最大容量    static final int MAXIMUM_CAPACITY = 1 << 30;     //（3） 默认的负载因子    static final float DEFAULT_LOAD_FACTOR = 0.75f;    //（4） 当桶(bucket)上的结点数大于这个值时会转成红黑树    static final int TREEIFY_THRESHOLD = 8;     //（5） 当桶(bucket)上的结点数小于这个值时树转链表    static final int UNTREEIFY_THRESHOLD = 6;    //（6） 桶中结构转化为红黑树对应的table的最小大小    static final int MIN_TREEIFY_CAPACITY = 64;    //（7） 存储元素的数组，总是2的幂次倍    transient Node<k,v>[] table;     //（8） 存放具体元素的集    transient Set<map.entry<k,v>> entrySet;    //（9） 存放元素的个数，注意这个不等于数组的长度。    transient int size;    //（10） 每次扩容和更改map结构的计数器    transient int modCount;       //（11） 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容    int threshold;    //（12） 负载因子    final float loadFactor;

代码（1）初始化桶大小，因为底层是数组，所以这是数组默认的大小。即16。

代码（2）桶最大值。即2的30次方

代码（3）默认的负载因子（0.75），负载因子越小，hash冲突机率越低 。

代码（4）用于判断是否需要将链表转换为红黑树的阈值。当桶(bucket)上的结点数大于这个值时会转成红黑树

代码（5）当桶(bucket)上的结点数小于这个值时树转链表

代码（6）桶中结构转化为红黑树对应的table的最小大小

代码（7）存储元素的数组，总是2的幂次倍。当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold。

代码（8）存放具体元素的集。

代码（9）存放元素的个数，注意这个不等于数组的长度。

代码（10）HashMap的结构被修改的次数，用于迭代器。用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException。

代码（11）临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容。、

代码（12）负载因子。

可以看到JDK1.8中HashMap的成员变量和 1.7 大体上都差不多。

构造函数稍微有点变化，JDK1.8的构造函数源码如下：

public HashMap(int initialCapacity, float loadFactor) {    // 桶初始容量不能小于0，否则报错    if (initialCapacity < 0)        throw new IllegalArgumentException("Illegal initial capacity: " +                                            initialCapacity);    // 桶初始容量不能大于最大值，否则为最大值    if (initialCapacity > MAXIMUM_CAPACITY)        initialCapacity = MAXIMUM_CAPACITY;    //校验负载因子 负载因子不能小于或等于0，不能为非数字    if (loadFactor <= 0 || Float.isNaN(loadFactor))        throw new IllegalArgumentException("Illegal load factor: " +                                            loadFactor);    // 初始化负载因子                                            this.loadFactor = loadFactor;    // 初始化threshold大小    this.threshold = tableSizeFor(initialCapacity);    }public HashMap(int initialCapacity) {    // 调用HashMap(int, float)型构造函数,通过扩容因子构造HashMap,容量取默认值，即16 。    this(initialCapacity, DEFAULT_LOAD_FACTOR);}public HashMap() {    // 初始化负载因子，装载因子取0.75，容量取16，构造HashMap     this.loadFactor = DEFAULT_LOAD_FACTOR; }//通过其他Map来初始化HashMap,容量通过其他Map的size来计算，装载因子取0.75public HashMap(Map<? extends K, ? extends V> m) {    // 初始化负载因子    this.loadFactor = DEFAULT_LOAD_FACTOR;    // 将m中的所有元素添加至HashMap中    putMapEntries(m, false);}

不同在于：

　　1.初始化threshold大小 this.threshold = tableSizeFor(initialCapacity);有所不同，tableSizeFor(initialCapacity)返回大于initialCapacity的最小的二次幂数值。源码如下：

static final int tableSizeFor(int cap) {    int n = cap - 1;    n |= n >>> 1;    n |= n >>> 2;    n |= n >>> 4;    n |= n >>> 8;    n |= n >>> 16;    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}

>>> 操作符表示无符号右移，高位取0。

　　2.通过其他Map来初始化HashMap，putMapEntries(Map<? extends K, ? extends V> m, boolean evict)函数将m的所有元素存入本HashMap实例中。源码如下：

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {    int s = m.size();    if (s > 0) {        // 判断table是否已经初始化        if (table == null) { // pre-size            // 未初始化，s为m的实际元素个数            float ft = ((float)s / loadFactor) + 1.0F;            int t = ((ft < (float)MAXIMUM_CAPACITY) ?                    (int)ft : MAXIMUM_CAPACITY);            // 计算得到的t大于阈值，则初始化阈值            if (t > threshold)                threshold = tableSizeFor(t);        }        // 已初始化，并且m元素个数大于阈值，进行扩容处理        else if (s > threshold)            resize();        // 将m中的所有元素添加至HashMap中        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {            K key = e.getKey();            V value = e.getValue();            putVal(hash(key), key, value, false, evict);        }    }}

static final int hash(  key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

首先获取对象的hashCode()值，然后将hashCode值右移16位，然后将右移后的值与原来的hashCode做异或运算，返回结果。（其中h>>>16，在JDK1.8中，优化了高位运算的算法，使用了零扩展，无论正数还是负数，都在高位插入0）。

接着再看看JDK1.8中的put方法和get方法中的变化。

先看put方法，如下：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {    Node<K,V>[] tab; Node<K,V> p; int n, i;    // （1）    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    // （2）    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);    // 桶中已经存在元素    else {        Node<K,V> e; K k;        // （3）        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))                // 将第一个元素赋值给e，用e来记录                e = p;        // （4）        else if (p instanceof TreeNode)            // 放入树中            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);        // 该链为链表         // 为链表结点        else {            //（5）            for (int binCount = 0; ; ++binCount) {                // 到达链表的尾部                if ((e = p.next) == null) {                    // 在尾部插入新结点                    p.next = newNode(hash, key, value, null);                    // （6）                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        treeifyBin(tab, hash);                    // 跳出循环                    break;                }                // （7）                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    // 相等，跳出循环                    break;                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表                p = e;            }        }        // （8）        if (e != null) {             // 记录e的value            V oldValue = e.value;            // onlyIfAbsent为false或者旧值为null            if (!onlyIfAbsent || oldValue == null)                //用新值替换旧值                e.value = value;            // 访问后回调            afterNodeAccess(e);            // 返回旧值            return oldValue;        }    }    // 结构性修改    ++modCount;    // （9）    if (++size > threshold)        resize();    // 插入后回调    afterNodeInsertion(evict);    return null;}

看似要比 1.7 的复杂，我们一步步拆解：

代码（1）判断当前桶是否为空，空的就需要初始化（resize 中会判断是否进行初始化）。

代码（2）根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空，为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。

代码（3）如果当前桶有值（ Hash 冲突），那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等，相等就赋值给 e,在第 8 步的时候会统一进行赋值及返回。

代码（4）如果当前桶为红黑树，那就要按照红黑树的方式写入数据。

代码（5）如果是个链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面（形成链表）。

代码（6）接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。

代码（7）判断链表中结点的key值与插入的元素的key值是否相等

代码（8）接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。

代码（9）最后判断是否需要进行扩容。超过最大容量就扩容，实际大小大于阈值则扩容。

HashMap的数据存储实现原理

流程：

1. 根据key计算得到key.hash = (h = k.hashCode()) ^ (h >>> 16)；

2. 根据key.hash计算得到桶数组的索引index = key.hash & (table.length - 1)，这样就找到该key的存放位置了：

① 如果该位置没有数据，用该数据新生成一个节点保存新数据，返回null；

② 如果该位置有数据是一个红黑树，那么执行相应的插入 / 更新操作；

③ 如果该位置有数据是一个链表，分两种情况一是该链表没有这个节点，另一个是该链表上有这个节点，注意这里判断的依据是key.hash是否一样：

如果该链表没有这个节点，那么采用尾插法新增节点保存新数据，返回null；如果该链表已经有这个节点了，那么找到该节点并更新新数据，返回老数据。

注意：

HashMap的put会返回key的上一次保存的数据，比如：

HashMap<String, String> map = new HashMap<String, String>();
System.out.println(map.put("a", "A")); // 打印null
System.out.println(map.put("a", "AA")); // 打印A
System.out.println(map.put("a", "AB")); // 打印AA

接着看红黑树如何插入数据的， putTreeVal(this, tab, hash, key, value) 源码如下：

/** * Tree version of putVal. * 红黑树插入会同时维护原来的链表属性, 即原来的next属性 */final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,                               int h, K k, V v) {    Class<?> kc = null;    boolean searched = false;    // 查找根节点, 索引位置的头节点并不一定为红黑树的根结点    TreeNode<K,V> root = (parent != null) ? root() : this;      for (TreeNode<K,V> p = root;;) {    // 将根节点赋值给p, 开始遍历        int dir, ph; K pk;        if ((ph = p.hash) > h)  // 如果传入的hash值小于p节点的hash值             dir = -1;    // 则将dir赋值为-1, 代表向p的左边查找树        else if (ph < h)    // 如果传入的hash值大于p节点的hash值,            dir = 1;    // 则将dir赋值为1, 代表向p的右边查找树        // 如果传入的hash值和key值等于p节点的hash值和key值, 则p节点即为目标节点, 返回p节点        else if ((pk = p.key) == k || (k != null && k.equals(pk)))              return p;        // 如果k所属的类没有实现Comparable接口 或者 k和p节点的key相等        else if ((kc == null &&                  (kc = comparableClassFor(k)) == null) ||                 (dir = compareComparables(kc, k, pk)) == 0) {             if (!searched) {    // 第一次符合条件, 该方法只有第一次才执行                TreeNode<K,V> q, ch;                searched = true;                // 从p节点的左节点和右节点分别调用find方法进行查找, 如果查找到目标节点则返回                if (((ch = p.left) != null &&                     (q = ch.find(h, k, kc)) != null) ||                    ((ch = p.right) != null &&                     (q = ch.find(h, k, kc)) != null))                      return q;            }            // 否则使用定义的一套规则来比较k和p节点的key的大小, 用来决定向左还是向右查找            dir = tieBreakOrder(k, pk); // dir<0则代表k<pk，则向p左边查找；反之亦然        }         TreeNode<K,V> xp = p;   // xp赋值为x的父节点,中间变量,用于下面给x的父节点赋值        // dir<=0则向p左边查找,否则向p右边查找,如果为null,则代表该位置即为x的目标位置        if ((p = (dir <= 0) ? p.left : p.right) == null) {              // 走进来代表已经找到x的位置，只需将x放到该位置即可            Node<K,V> xpn = xp.next;    // xp的next节点                  // 创建新的节点, 其中x的next节点为xpn, 即将x节点插入xp与xpn之间            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);               if (dir <= 0)   // 如果时dir <= 0, 则代表x节点为xp的左节点                xp.left = x;            else        // 如果时dir> 0, 则代表x节点为xp的右节点                xp.right = x;            xp.next = x;    // 将xp的next节点设置为x            x.parent = x.prev = xp; // 将x的parent和prev节点设置为xp            // 如果xpn不为空,则将xpn的prev节点设置为x节点,与上文的x节点的next节点对应            if (xpn != null)                    ((TreeNode<K,V>)xpn).prev = x;            moveRootToFront(tab, balanceInsertion(root, x)); // 进行红黑树的插入平衡调整            return null;        }    }}

1.查找当前红黑树的根结点，将根结点赋值给p节点，开始进行查找

2.如果传入的hash值小于p节点的hash值，将dir赋值为-1，代表向p的左边查找树

3.如果传入的hash值大于p节点的hash值， 将dir赋值为1，代表向p的右边查找树

4.如果传入的hash值等于p节点的hash值，并且传入的key值跟p节点的key值相等, 则该p节点即为目标节点，返回p节点

5.如果k所属的类没有实现Comparable接口，或者k和p节点的key使用compareTo方法比较相等：第一次会从p节点的左节点和右节点分别调用find方法（见上文代码块2）进行查找，如果查找到目标节点则返回；如果不是第一次或者调用find方法没有找到目标节点，则调用tieBreakOrder方法（见下文代码块5）比较k和p节点的key值的大小，以决定向树的左节点还是右节点查找。

6.如果dir <= 0则向左节点查找（p赋值为p.left，并进行下一次循环），否则向右节点查找，如果已经无法继续查找（p赋值后为null），则代表该位置即为x的目标位置，另外变量xp用来记录查找的最后一个节点，即下文新增的x节点的父节点。

7.以传入的hash、key、value参数和xp节点的next节点为参数，构建x节点（注意：xp节点在此处可能是叶子节点、没有左节点的节点、没有右节点的节点三种情况，即使它是叶子节点，它也可能有next节点，红黑树的结构跟链表的结构是互不影响的，不会因为某个节点是叶子节点就说它没有next节点，红黑树在进行操作时会同时维护红黑树结构和链表结构，next属性就是用来维护链表结构的），根据dir的值决定x决定放在xp节点的左节点还是右节点，将xp的next节点设为x，将x的parent和prev节点设为xp，如果原xp的next节点（xpn）不为空, 则将该节点的prev节点设置为x节点, 与上面的将x节点的next节点设置为xpn对应。

8.进行红黑树的插入平衡调整，

接下来让我们看看链表如何转红黑树，treeifyBin(tab, hash)，源码如下：

final void treeifyBin(Node<K,V>[] tab, int hash) {    int n, index; Node<K,V> e;    // table为空或者table的长度小于64, 进行扩容    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)         resize();    // 根据hash值计算索引值, 遍历该索引位置的链表    else if ((e = tab[index = (n - 1) & hash]) != null) {           TreeNode<K,V> hd = null, tl = null;        do {            TreeNode<K,V> p = replacementTreeNode(e, null); // 链表节点转红黑树节点            if (tl == null)    // tl为空代表为第一次循环                hd = p; // 头结点            else {                p.prev = tl;    // 当前节点的prev属性设为上一个节点                tl.next = p;    // 上一个节点的next属性设置为当前节点            }            tl = p; // tl赋值为p, 在下一次循环中作为上一个节点        } while ((e = e.next) != null);    // e指向下一个节点        // 将table该索引位置赋值为新转的TreeNode的头节点        if ((tab[index] = hd) != null)             hd.treeify(tab);    // 以头结点为根结点, 构建红黑树    }

1.校验table是否为空，如果长度小于64，则调用resize方法（见下文resize方法）进行扩容。

2.根据hash值计算索引值，将该索引位置的节点赋值给e节点，从e节点开始遍历该索引位置的链表。

3.调用replacementTreeNode方法（该方法就一行代码，直接返回一个新建的TreeNode）将链表节点转为红黑树节点，将头结点赋值给hd节点，每次遍历结束将p节点赋值给tl，用于在下一次循环中作为上一个节点进行一些链表的关联操作（p.prev = tl 和 tl.next = p）。

4.将table该索引位置赋值为新转的TreeNode的头节点hd，如果该节点不为空，则以hd为根结点，调用treeify方法（见下文代码块7）构建红黑树。

接着看如何构建红黑树treeify(Node<K,V>[] tab)，源码如下：

final void treeify(Node<K,V>[] tab) {   // 构建红黑树    TreeNode<K,V> root = null;    for (TreeNode<K,V> x = this, next; x != null; x = next) {// this即为调用此方法的TreeNode        next = (TreeNode<K,V>)x.next;   // next赋值为x的下个节点        x.left = x.right = null;    // 将x的左右节点设置为空        if (root == null) { // 如果还没有根结点, 则将x设置为根结点            x.parent = null;    // 根结点没有父节点            x.red = false;  // 根结点必须为黑色            root = x;   // 将x设置为根结点        }        else {            K k = x.key;    // k赋值为x的key            int h = x.hash;    // h赋值为x的hash值            Class<?> kc = null;            // 如果当前节点x不是根结点, 则从根节点开始查找属于该节点的位置            for (TreeNode<K,V> p = root;;) {                    int dir, ph;                K pk = p.key;                   if ((ph = p.hash) > h)  // 如果x节点的hash值小于p节点的hash值                    dir = -1;   // 则将dir赋值为-1, 代表向p的左边查找                else if (ph < h)    // 与上面相反, 如果x节点的hash值大于p节点的hash值                    dir = 1;    // 则将dir赋值为1, 代表向p的右边查找                // 走到这代表x的hash值和p的hash值相等，则比较key值                else if ((kc == null && // 如果k没有实现Comparable接口 或者 x节点的key和p节点的key相等                          (kc = comparableClassFor(k)) == null) ||                         (dir = compareComparables(kc, k, pk)) == 0)                    // 使用定义的一套规则来比较x节点和p节点的大小，用来决定向左还是向右查找                    dir = tieBreakOrder(k, pk);                  TreeNode<K,V> xp = p;   // xp赋值为x的父节点,中间变量用于下面给x的父节点赋值                // dir<=0则向p左边查找,否则向p右边查找,如果为null,则代表该位置即为x的目标位置                if ((p = (dir <= 0) ? p.left : p.right) == null) {                     x.parent = xp;  // x的父节点即为最后一次遍历的p节点                    if (dir <= 0)   // 如果时dir <= 0, 则代表x节点为父节点的左节点                        xp.left = x;                    else    // 如果时dir > 0, 则代表x节点为父节点的右节点                        xp.right = x;                    // 进行红黑树的插入平衡(通过左旋、右旋和改变节点颜色来保证当前树符合红黑树的要求)                    root = balanceInsertion(root, x);                       break;                }            }        }    }    moveRootToFront(tab, root); // 如果root节点不在table索引位置的头结点, 则将其调整为头结点}

1.从调用此方法的节点作为起点，开始进行遍历，并将此节点设为root节点，标记为黑色（x.red = false）。

2.如果当前节点不是根结点，则从根节点开始查找属于该节点的位置（该段代码跟之前的代码块2和代码块4的查找代码类似）。

3.如果x节点(将要插入红黑树的节点)的hash值小于p节点(当前遍历到的红黑树节点)的hash值，则向p节点的左边查找。

4.与3相反，如果x节点的hash值大于p节点的hash值，则向p节点的右边查找。

5.如果x的key没有实现Comparable接口，或者x节点的key和p节点的key相等，使用tieBreakOrder方法（见上文代码块5）来比较x节点和p节点的大小，以决定向左还是向右查找（dir <= 0向左，否则向右）。

6.如果dir <= 0则向左节点查找（p赋值为p.left，并进行下一次循环），否则向右节点查找，如果已经无法继续查找（p赋值后为null），则代表该位置即为x的目标位置，另外变量xp用来记录最后一个节点，即为下文新增的x节点的父节点。

7.将x的父节点设置为xp，根据dir的值决定x决定放在xp节点的左节点还是右节点，最后进行红黑树的插入平衡调整。

8.调用moveRootToFront方法（如下：）将root节点调整到索引位置的头结点。

/** * 如果当前索引位置的头节点不是root节点, 则将root的上一个节点和下一个节点进行关联,  * 将root放到头节点的位置, 原头节点放在root的next节点上 */static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {    int n;    if (root != null && tab != null && (n = tab.length) > 0) {        int index = (n - 1) & root.hash;        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];        if (root != first) {    // 如果root节点不是该索引位置的头节点            Node<K,V> rn;            tab[index] = root;  // 将该索引位置的头节点赋值为root节点            TreeNode<K,V> rp = root.prev;   // root节点的上一个节点            // 如果root节点的下一个节点不为空,             // 则将root节点的下一个节点的prev属性设置为root节点的上一个节点            if ((rn = root.next) != null)                   ((TreeNode<K,V>)rn).prev = rp;             // 如果root节点的上一个节点不为空,             // 则将root节点的上一个节点的next属性设置为root节点的下一个节点            if (rp != null)                 rp.next = rn;            if (first != null)  // 如果原头节点不为空, 则将原头节点的prev属性设置为root节点                first.prev = root;            root.next = first;  // 将root节点的next属性设置为原头节点            root.prev = null;        }        assert checkInvariants(root);   // 检查树是否正常    }