本文共 6740 字，大约阅读时间需要 22 分钟。

1 概述

前面（参考）我们基于JDK1.7分析了HashMap的实现，我们知道了JDK1.7实现HashMap是基于链表和数组来实现的，而JDK1.8在数据结构上做了改了，添加进了红黑树的数据结构，红黑树的查询时间复杂度为O(log n)，所以可以使用红黑树来降低当Hash冲突比较严重，链表长度过长而导致查询效率过低的情况。

2 数据结构

上图很形象地展示了HashMap的数据结构，可以很明显地看出JDK1.8如之前的版本相比，桶中的数据结构不仅仅是链表了，还包含红黑树。

3 内部类

（1）Node

static class Node
   
     implements Map.Entry
    
      {        final int hash;        final K key;        V value;        Node
     
       next;... ...
     
    
   

我们可以看出Node内部类其实和HashMap(JDK1.7）种的Entry是相同的，所以这里就不做过多解释了。

（2）TreeNode

从这个内部类的名称我们可以猜想，这里面肯定包含了节点颜色，以及左右孩子，和父节点等属性。

static final class TreeNode
   
     extends LinkedHashMap.Entry
    
      {        TreeNode
     
       parent;  // red-black tree links        TreeNode
      
        left;        TreeNode
       
         right;        TreeNode
        
          prev; // needed to unlink next upon deletion boolean red;... ...
        
       
      
     
    
   

从上面的代码我们可以看出，和我们猜测的一致，这个内部类就是在链表转表成红黑树的时候用于在红黑树种存储数据的。

4 源码分析

4.1 类的属性

public class HashMap
   
     extends AbstractMap
    
      implements Map
     
      , Cloneable, Serializable {    // 序列号    private static final long serialVersionUID = 362498820763181265L;        // 默认的初始容量是16    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;       // 最大容量    static final int MAXIMUM_CAPACITY = 1 << 30;     // 默认的填充因子    static final float DEFAULT_LOAD_FACTOR = 0.75f;    // 当桶(bucket)上的结点数大于这个值时会转成红黑树    static final int TREEIFY_THRESHOLD = 8;     // 当桶(bucket)上的结点数小于这个值时树转链表    static final int UNTREEIFY_THRESHOLD = 6;    // 桶中结构转化为红黑树对应的table的最小大小    static final int MIN_TREEIFY_CAPACITY = 64;    // 存储元素的数组，总是2的幂次倍    transient Node
      
       [] table;     // 存放具体元素的集    transient Set
       
        
         > entrySet; // 存放元素的个数，注意这个不等于数组的长度。 transient int size; // 每次扩容和更改map结构的计数器 transient int modCount; // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容 int threshold; // 填充因子 final float loadFactor;}
        
       
      
     
    
   

4.2 类的构造函数

这里我们仅仅分析一个比较核心的构造函数。

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);    }

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;    }

4.3 核心函数分析

4.3.1 putVal函数

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {    Node
   
    [] tab; Node
    
      p; int n, i;    // table未初始化或者长度为0，进行扩容    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);    // 桶中已经存在元素    else {        Node
     
       e; K k;        // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))                // 将第一个元素赋值给e，用e来记录                e = p;        // hash值不相等，即key不相等；为红黑树结点        else if (p instanceof TreeNode)            // 放入树中            e = ((TreeNode
      
       )p).putTreeVal(this, tab, hash, key, value);        // 为链表结点        else {            // 在链表最末插入结点            for (int binCount = 0; ; ++binCount) {                // 到达链表的尾部                if ((e = p.next) == null) {                    // 在尾部插入新结点                    p.next = newNode(hash, key, value, null);                    // 结点数量达到阈值，转化为红黑树                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        treeifyBin(tab, hash);                    // 跳出循环                    break;                }                // 判断链表中结点的key值与插入的元素的key值是否相等                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    // 相等，跳出循环                    break;                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表                p = e;            }        }        // 表示在桶中找到key值、hash值与插入元素相等的结点        if (e != null) {             // 记录e的value            V oldValue = e.value;            // onlyIfAbsent为false或者旧值为null            if (!onlyIfAbsent || oldValue == null)                //用新值替换旧值                e.value = value;            // 访问后回调            afterNodeAccess(e);            // 返回旧值            return oldValue;        }    }    // 结构性修改    ++modCount;    // 实际大小大于阈值则扩容    if (++size > threshold)        resize();    // 插入后回调    afterNodeInsertion(evict);    return null;}
      
     
    
   

HashMap并没有直接提供putVal接口给用户调用，而是提供的put函数，而put函数就是通过putVal来插入元素的。

4.3.2 get函数

public V get(Object key) {        Node
   
     e;                //调用getNode函数来获取Node        return (e = getNode(hash(key), key)) == null ? null : e.value;    }
   

从上面我们可以看出get函数最终是调用getNode函数来获取到Node元素，最后获取的value。

final Node
   
     getNode(int hash, Object key) {        Node
    
     [] tab; Node
     
       first, e; int n; K k;        //数组不为空，并且对应数组位置的链表（红黑树）第一个节点的值不为空        if ((tab = table) != null && (n = tab.length) > 0 &&            (first = tab[(n - 1) & hash]) != null) {                        //如果hash和key相等，说明第一个节点就是要寻找的节点，直接进返回            if (first.hash == hash && // always check first node                ((k = first.key) == key || (key != null && key.equals(k))))                return first;            //第一个节点的后继节点不为空            if ((e = first.next) != null) {                //如果节点为红黑树节点，则调用红黑树获取节点的方法（getTreeNode）                if (first instanceof TreeNode)                    return ((TreeNode
      
       )first).getTreeNode(hash, key);                                //循换链表直到获取到节点（或者循环结束）                do {                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        return e;                } while ((e = e.next) != null);            }        }        return null;    }
      
     
    
   

从上面我们可以看出get方法相对来说比较简单。其实都是循环来获取每一个节点，然后根据节点的key和hash是否相等来判断是否获取到。

5 总结

上面我们分析了HashMap(JDK1.8)的源码，针对里面使用红黑树源码的部分这里暂不分析，后面有时间再补上。其实个人觉得，我们只需要记住红黑树的数据结构可以降低时间复杂度就行了。这里我们使用红黑树可以有效地提高查询和插入删除的效率。