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

1、HashMap结构

Node是HashMap的一个内部类，实现了Map.Entry接口，本质上是一个映射（键值对）。上图中每一个黄框就是一个Node对象。具体代码如下：

/** * Node是单向链表，它实现了Map.Entry接口 */static class Node
   
     implements Map.Entry
    
      {    final int hash;    final K key;    V value;    Node
     
       next;    Node(int hash, K key, V value, Node
      
        next) {        this.hash = hash;        this.key = key;        this.value = value;        this.next = next;    }     public final K getKey()        { return key; }    public final V getValue()      { return value; }    public final String toString() { return key + = + value; }     public final int hashCode() {        return Objects.hashCode(key) ^ Objects.hashCode(value);    }     public final V setValue(V newValue) {        V oldValue = value;        value = newValue;        return oldValue;    }    //判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true    public final boolean equals(Object o) {        if (o == this)            return true;        if (o instanceof Map.Entry) {            Map.Entry
        e = (Map.Entry
       )o;            if (Objects.equals(key, e.getKey()) &&                Objects.equals(value, e.getValue()))                return true;        }        return false;    }}/** * 红黑树 */static final class TreeNode
       
         extends LinkedHashMap.Entry
        
          { TreeNode
         
           parent; // 父节点 TreeNode
          
            left; //左子树 TreeNode
           
             right;//右子树 TreeNode
            
              prev; // needed to unlink next upon deletion boolean red; //颜色属性 TreeNode(int hash, K key, V val, Node
             
               next) { super(hash, key, val, next); } //返回当前节点的根节点 final TreeNode
              
                root() { for (TreeNode
               
                 r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } }}transient Node
                
                 [] table;//存储（位桶）的数组
                
               
              
             
            
           
          
         
        
       
      
     
    
   

2、类属性

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)上的结点数大于这个值时会转成红黑树;+对应的table的最小大小为64，即MIN_TREEIFY_CAPACITY ；这两个条件都满足，会链表会转红黑树    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;}
        
       
      
     
    
   

3、重要方法分析

3.1 hash方法

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

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

3.2 putVal方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {        Node
   
    [] tab; Node
    
      p; int n, i;        // 步骤1：tab为空则创建         // table未初始化或者长度为0，进行扩容        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;        // 步骤2：计算index，并对null做处理          // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)        if ((p = tab[i = (n - 1) & hash]) == null)            tab[i] = newNode(hash, key, value, null);        else {            Node
     
       e; K k;            // 步骤3：节点key存在，直接覆盖value             // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p;            // 步骤4：判断该链为红黑树             // hash值不相等，即key不相等；为红黑树结点            else if (p instanceof TreeNode)                e = ((TreeNode
      
       )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);                        // 结点数量达到阈值，转化为红黑树                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                            treeifyBin(tab, hash);                        break;                    }                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        break;                    // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表                    p = e;                }            }            // 表示在桶中找到key值、hash值与插入元素相等的结点            if (e != null) { // existing mapping for key                V oldValue = e.value;                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeAccess(e);                return oldValue;            }        }        ++modCount;        // 步骤6：超过最大容量就扩容         // 实际大小大于阈值则扩容        if (++size > threshold)            resize();        afterNodeInsertion(evict);        return null;    }
      
     
    
   

putVal方法执行过程可以通过下图来理解：

• 1)判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
• 2)根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转到6)，如果table[i]不为空，转向3)；
• 3)判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4)，这里的相同指的是hashCode以及equals；
• 4)判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向15)；
• 5)遍历table[i]，判断链表长度是否大于8（且），大于8的话（且Node数组的数量大于64）把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
• 6)插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

3.3 getNode方法

public V get(Object key) {    Node
   
     e;    return (e = getNode(hash(key), key)) == null ? null : e.value;}final Node
    
      getNode(int hash, Object key) {    Node
     
      [] tab; Node
      
        first, e; int n; K k;    // table已经初始化，长度大于0，根据hash寻找table中的项也不为空    if ((tab = table) != null && (n = tab.length) > 0 &&        (first = tab[(n - 1) & hash]) != null) {        // 桶中第一项(数组元素)相等        if (first.hash == hash && // always check first node            ((k = first.key) == key || (key != null && key.equals(k))))            return first;        // 桶中不止一个结点        if ((e = first.next) != null) {            // 为红黑树结点            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;}
       
      
     
    
   

3.4 resize方法

resize方法是在hashmap中的键值对大于阈值时或者初始化时，就调用resize方法进行扩容；每次都是扩展2倍。

final Node
   
    [] resize() {    Node
    
     [] oldTab = table;    int oldCap = (oldTab == null) ? 0 : oldTab.length;    int oldThr = threshold;    int newCap, newThr = 0;    if (oldCap > 0) {//如果oldCap不为空的话，就是hash桶数组不为空        if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了，就赋值为整数最大的阀值            threshold = Integer.MAX_VALUE;            return oldTab;        }//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                 oldCap >= DEFAULT_INITIAL_CAPACITY)            newThr = oldThr << 1; // double threshold 双倍扩容阀值threshold    }    else if (oldThr > 0) // initial capacity was placed in threshold        newCap = oldThr;    else {               // zero initial threshold signifies using defaults        newCap = DEFAULT_INITIAL_CAPACITY;        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);    }    if (newThr == 0) {        float ft = (float)newCap * loadFactor;        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                  (int)ft : Integer.MAX_VALUE);    }    threshold = newThr;    @SuppressWarnings({"rawtypes","unchecked"})        Node
     
      [] newTab = (Node
      
       [])new Node[newCap];    table = newTab;//将新数组的值复制给旧的hash桶数组    if (oldTab != null) {//进行扩容操作，复制Node对象值到新的hash桶数组        for (int j = 0; j < oldCap; ++j) {            Node
       
         e;            if ((e = oldTab[j]) != null) {//如果旧的hash桶数组在j结点处不为空，复制给e                oldTab[j] = null;//将旧的hash桶数组在j结点处设置为空，方便gc                if (e.next == null)//如果e后面没有Node结点                    newTab[e.hash & (newCap - 1)] = e;//直接对e的hash值对新的数组长度求模获得存储位置                else if (e instanceof TreeNode)//如果e是红黑树的类型，那么添加到红黑树中                    ((TreeNode
        
         )e).split(this, newTab, j, oldCap); else { // preserve order Node
         
           loHead = null, loTail = null; Node
          
            hiHead = null, hiTail = null; Node
           
             next; do { next = e.next;//将Node结点的next赋值给next if ((e.hash & oldCap) == 0) {//如果结点e的hash值与原hash桶数组的长度作与运算为0 if (loTail == null)//如果loTail为null loHead = e;//将e结点赋值给loHead else loTail.next = e;//否则将e赋值给loTail.next loTail = e;//然后将e复制给loTail } else {//如果结点e的hash值与原hash桶数组的长度作与运算不为0 if (hiTail == null)//如果hiTail为null hiHead = e;//将e赋值给hiHead else hiTail.next = e;//如果hiTail不为空，将e复制给hiTail.next hiTail = e;//将e复制个hiTail } } while ((e = next) != null);//直到e为空 if (loTail != null) {//如果loTail不为空 loTail.next = null;//将loTail.next设置为空 newTab[j] = loHead;//将loHead赋值给新的hash桶数组[j]处 } if (hiTail != null) {//如果hiTail不为空 hiTail.next = null;//将hiTail.next赋值为空 newTab[j + oldCap] = hiHead;//将hiHead赋值给新的hash桶数组[j+旧hash桶数组长度] } } } } } return newTab;}