接下来会从以下几个方面介绍 HashMap 源码相关知识：

　　1、HashMap 存储结构

　　2、HashMap 各常量、成员变量作用

　　3、HashMap 几种构造方法

　　4、HashMap put 及其相关方法

　　5、HashMap get 及其相关方法

　　6、HashMap remove 及其相关方法

　　7、HashMap 扩容方法　resize()

　　介绍方法时会包含方法实现相关细节。

　　先来看一下 HashMap 的继承图：

HashMap 根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null ，允许多条记录的值为 null 。HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap 方法使 HashMap 具有线程安全的能力，或者使用ConcurrentHashMap。

一、HashMap 存储结构

　　HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下图所示：

　源码中具体实现如下：　　

1 　// Node
    
      类用来实现数组及链表的数据结构 2 　 static class Node
     
       implements Map.Entry
      
        { 3         final int hash; //保存节点的 hash　值 4         final K key; //保存节点的　key　值 5         V value;　//保存节点的　value 值 6         Node
       
         next;　//指向链表结构下的当前节点的　next 节点，红黑树　TreeNode　节点中也有用到 7  8         Node(int hash, K key, V value, Node
        
          next) { 9             this.hash = hash;10             this.key = key;11             this.value = value;12             this.next = next;13         }14 15         public final K getKey()        { }16         public final V getValue()      {  }17         public final String toString() { }18 19         public final int hashCode() {           20         }21 22         public final V setValue(V newValue) {          23         }24 25         public final boolean equals(Object o) {            26         }27     }28     29     public class LinkedHashMap
         
           {30 static class Entry
          
            extends HashMap.Node
           
             {31 Entry
            
              before, after;32 Entry(int hash, K key, V value, Node
             
               next) {33 super(hash, key, value, next);34 } 35 }36 } 37 38 　// TreeNode
              
                继承 LinkedHashMap.Entry
               
                ，用来实现红黑树相关的存储结构39 static final class TreeNode
                
                  extends LinkedHashMap.Entry
                 
                   {40 TreeNode
                  
                    parent; // 存储当前节点的父节点41 TreeNode
                   
                     left;　//存储当前节点的左孩子42 TreeNode
                    
                      right;　//存储当前节点的右孩子43 TreeNode
                     
                       prev; // 存储当前节点的前一个节点44 boolean red;　// 存储当前节点的颜色（红、黑）45 TreeNode(int hash, K key, V val, Node
                      
                        next) {46 super(hash, key, val, next);47 }48 }
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

二、HashMap 各常量、成员变量作用　　

1 　//创建 HashMap 时未指定初始容量情况下的默认容量    2     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  3  4 　//HashMap 的最大容量 5     static final int MAXIMUM_CAPACITY = 1 << 30; 6  7     //HashMap 默认的装载因子,当 HashMap 中元素数量超过 容量*装载因子 时，进行　resize()　操作 8     static final float DEFAULT_LOAD_FACTOR = 0.75f; 9 10     //用来确定何时将解决 hash 冲突的链表转变为红黑树11     static final int TREEIFY_THRESHOLD = 8;12 13     // 用来确定何时将解决 hash 冲突的红黑树转变为链表14     static final int UNTREEIFY_THRESHOLD = 6;15  16     /* 当需要将解决 hash 冲突的链表转变为红黑树时，需要判断下此时数组容量，若是由于数组容量太小（小于　MIN_TREEIFY_CAPACITY　）导致的 hash 冲突太多，则不进行链表转变为红黑树操作，转为利用　resize() 函数对　hashMap 扩容　*/17     static final int MIN_TREEIFY_CAPACITY = 64;

1 //保存Node
    
     节点的数组 2  transient Node
     
      [] table; 3  4 //由　hashMap 中 Node
      
       　节点构成的 set 5 transient Set
       
        
         > entrySet; 6  7 //记录 hashMap 当前存储的元素的数量 8 transient int size; 9 10 //记录　hashMap 发生结构性变化的次数（注意　value 的覆盖不属于结构性变化）11 transient int modCount;12 13 //threshold的值应等于 table.length * loadFactor, size 超过这个值时进行　resize()扩容14 int threshold;15 16 //记录 hashMap 装载因子17 final float loadFactor;
        
       
      
     
    

　　三、HashMap 几种构造方法

1 //构造方法１，指定初始容量及装载因子 2 public HashMap(int initialCapacity, float loadFactor) { 3         if (initialCapacity < 0) 4             throw new IllegalArgumentException("Illegal initial capacity: " + 5                                                initialCapacity); 6         if (initialCapacity > MAXIMUM_CAPACITY) 7             initialCapacity = MAXIMUM_CAPACITY; 8         if (loadFactor <= 0 || Float.isNaN(loadFactor)) 9             throw new IllegalArgumentException("Illegal load factor: " +10                                                loadFactor);11         this.loadFactor = loadFactor;12     　/* tableSizeFor(initialCapacity)　方法返回的值是最接近 initialCapacity 的2的幂，若指定初始容量为９，则实际 hashMap 容量为16*/13     　//注意此种方法创建的 hashMap 初始容量的值存在　threshold 中14         this.threshold = tableSizeFor(initialCapacity);15 }16 //tableSizeFor(initialCapacity)　方法返回的值是最接近 initialCapacity 的2的幂17 static final int tableSizeFor(int cap) {18         int n = cap - 1;19         n |= n >>> 1;// >>> 代表无符号右移20         n |= n >>> 2;21         n |= n >>> 4;22         n |= n >>> 8;23         n |= n >>> 16;24         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;25 }26 //构造方法２，仅指定初始容量，装载因子的值采用默认的　0.7527 public HashMap(int initialCapacity) {28         this(initialCapacity, DEFAULT_LOAD_FACTOR);29 }30 //构造方法３，所有参数均采用默认值31 public HashMap() {32         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted33 }

　　四、HashMap put 及其相关方法

　　这部分我觉得是　hashMap 中比较重要的代码，介绍如下：　　

1 　//指定节点 key,value，向 hashMap 中插入节点 2 　public V put(K key, V value) { 3     　//注意待插入节点　hash 值的计算，调用了　hash(key) 函数 4 　　//实际调用 putVal（）进行节点的插入 5         return putVal(hash(key), key, value, false, true); 6     } 7 　static final int hash(Object key) { 8         int h; 9 　　/*key 的 hash　值的计算是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销*/10         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);11     }12 13 　public void putAll(Map
     m) {14         putMapEntries(m, true);15     }16 　17 　/*把Map
     m 中的元素插入到　hashMap 中,若 evict 为 false,代表是在创建 hashMap 时调用了这个函数，例如利用上述构造函数３创建 hashMap;若 evict　为true,代表是在创建　hashMap 后才调用这个函数，例如上述的　putAll 函数。*/18 19 　final void putMapEntries(Map
     m, boolean evict) {20         int s = m.size();21         if (s > 0) {22             /*如果是在创建 hashMap 时调用的这个函数则 table 一定为空*/23             if (table == null) { 24 　　　　  //根据待插入的map 的 size 计算要创建的　hashMap 的容量。25                 float ft = ((float)s / loadFactor) + 1.0F;26                 int t = ((ft < (float)MAXIMUM_CAPACITY) ?27                          (int)ft : MAXIMUM_CAPACITY);28 　　　　  //把要创建的　hashMap 的容量存在　threshold　中29                 if (t > threshold)30                     threshold = tableSizeFor(t);31             }32 　　　 //判断待插入的　map 的 size,若　size 大于　threshold，则先进行　resize()33             else if (s > threshold)34                 resize();35             for (Map.Entry
     e : m.entrySet()) {36                 K key = e.getKey();37                 V value = e.getValue();38                 //实际也是调用　putVal　函数进行元素的插入39                 putVal(hash(key), key, value, false, evict);40             }41         }42     }43 　44     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,45                    boolean evict) {46         Node
    
     [] tab; Node
     
       p; int n, i;47         if ((tab = table) == null || (n = tab.length) == 0)48             n = (tab = resize()).length;49 　　 /*根据 hash 值确定节点在数组中的插入位置，若此位置没有元素则进行插入，注意确定插入位置所用的计算方法为　(n - 1) & hash,由于　n 一定是２的幂次，这个操作相当于50 　hash % n */51         if ((p = tab[i = (n - 1) & hash]) == null)52             tab[i] = newNode(hash, key, value, null);53         else {//说明待插入位置存在元素54             Node
      
        e; K k;55 　　　 　　　　//比较原来元素与待插入元素的　hash 值和　key 值56             if (p.hash == hash &&57                 ((k = p.key) == key || (key != null && key.equals(k))))58                 e = p;59 　　　 　　　　//若原来元素是红黑树节点，调用红黑树的插入方法:putTreeVal60             else if (p instanceof TreeNode)61                 e = ((TreeNode
       
        )p).putTreeVal(this, tab, hash, key, value);62             else {//证明原来的元素是链表的头结点，从此节点开始向后寻找合适插入位置63                 for (int binCount = 0; ; ++binCount) {64                     if ((e = p.next) == null) {65 　　　　　　　//找到插入位置后，新建节点插入66                         p.next = newNode(hash, key, value, null);67 　　　　　　　//若链表上节点超过TREEIFY_THRESHOLD - 1，将链表变为红黑树68                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st69                             treeifyBin(tab, hash);70                         break;71                     }72                     if (e.hash == hash &&73                         ((k = e.key) == key || (key != null && key.equals(k))))74                         break;75                     p = e;76                 }77             }//end else78             if (e != null) { // 待插入元素在　hashMap 中已存在79                 V oldValue = e.value;80                 if (!onlyIfAbsent || oldValue == null)81                     e.value = value;82                 afterNodeAccess(e);83                 return oldValue;84             }85         }//end else86         ++modCount;87         if (++size > threshold)88             resize();89         afterNodeInsertion(evict);90         return null;91     }//end putval
       
      
     
    

1        /*读懂这个函数要注意理解 hash 冲突发生的几种情况 2          １、两节点　key 值相同（hash值一定相同），导致冲突 3          ２、两节点　key 值不同，由于 hash 函数的局限性导致hash 值相同，冲突 4 　　 　　 ３、两节点　key 值不同，hash 值不同，但 hash 值对数组长度取模后相同，冲突 5       */ 6         final TreeNode
    
      putTreeVal(HashMap
     
       map, Node
      
       [] tab, 7                                        int h, K k, V v) { 8             Class
        kc = null; 9             boolean searched = false;10             TreeNode
       
         root = (parent != null) ? root() : this;11 　　　　　　　 //从根节点开始查找合适的插入位置（与二叉搜索树查找过程相同）12             for (TreeNode
        
          p = root;;) {13                 int dir, ph; K pk;14                 if ((ph = p.hash) > h)15                     dir = -1;　//　dir小于０，接下来查找当前节点左孩子16                 else if (ph < h)17                     dir = 1;　//　dir大于０，接下来查找当前节点右孩子18                 else if ((pk = p.key) == k || (pk != null && k.equals(pk)))19 　　　　　　　　　　　　//进入这个else if 代表　hash 值相同，key　相同20                     return p;21 　　　　 　　　　 /*要进入下面这个else if,代表有以下几个含义:22                   1、当前节点与待插入节点　key　不同,　hash 值相同23     　　　　　　　　2、ｋ是不可比较的，即ｋ并未实现　comparable
         
          　接口　　　　　　　　　　　　　　（若 k 实现了comparable
          
           　接口，comparableClassFor（k）返回的是ｋ的　class,而不是　null）24 　　或者　compareComparables(kc, k, pk)　返回值为 0　　　　　　　　　　　　　　(pk 为空　或者　按照 k.compareTo(pk) 返回值为０，　　　　　　　　　　　　　　返回值为０可能是由于　ｋ的compareTo 方法实现不当引起的，compareTo 判定相等，而上个 else if　中　equals 判定不等)*/25 else if ((kc == null &&26 (kc = comparableClassFor(k)) == null) ||27 (dir = compareComparables(kc, k, pk)) == 0) {28 //在以当前节点为根的整个树上搜索是否存在待插入节点（只会搜索一次）29 if (!searched) {30 TreeNode
           
             q, ch;31 searched = true;32 if (((ch = p.left) != null &&33 (q = ch.find(h, k, kc)) != null) ||34 ((ch = p.right) != null &&35 (q = ch.find(h, k, kc)) != null))36 　　　　　　　　　　　　　　　　　//若树中存在待插入节点，直接返回37 return q;38 }39 　　　　　 　　　　　　 // 既然ｋ是不可比较的，那我自己指定一个比较方式40 dir = tieBreakOrder(k, pk);41 }//end else if42 43 TreeNode
            
              xp = p;44 if ((p = (dir <= 0) ? p.left : p.right) == null) {45 　　　　　　　　　　　　//找到了待插入的位置，xp 为待插入节点的父节点46 　　　　　　　　　　　　//注意TreeNode节点中既存在树状关系，也存在链式关系，并且是双端链表47 Node
             
               xpn = xp.next;48 TreeNode
              
                x = map.newTreeNode(h, k, v, xpn);49 if (dir <= 0)50 xp.left = x;51 else52 xp.right = x;53 xp.next = x;54 x.parent = x.prev = xp;55 if (xpn != null)56 ((TreeNode
               
                )xpn).prev = x;57 　　　　　　　　　　　　//插入节点后进行二叉树的平衡操作58 moveRootToFront(tab, balanceInsertion(root, x));59 return null;60 }61 }//end for62 }//end putTreeVal 　63 　　64 　　 　　static int tieBreakOrder(Object a, Object b) {65 int d;66 //System.identityHashCode()实际是利用对象 a,b 的内存地址进行比较67 if (a == null || b == null ||68 (d = a.getClass().getName().69 compareTo(b.getClass().getName())) == 0)70 d = (System.identityHashCode(a) <= System.identityHashCode(b) ?71 -1 : 1);72 return d;73 }
               
              
             
            
           
          
         
        
       
      
     
    

五、HashMap get 及其相关方法　　

1  　public V get(Object key) { 2         Node
    
      e; 3 　　//实际上是根据输入节点的 hash 值和 key 值利用getNode 方法进行查找 4         return (e = getNode(hash(key), key)) == null ? null : e.value; 5     } 6 　 7 　final Node
     
       getNode(int hash, Object key) { 8         Node
      
       [] tab; Node
       
         first, e; int n; K k; 9         if ((tab = table) != null && (n = tab.length) > 0 &&10             (first = tab[(n - 1) & hash]) != null) {11             if (first.hash == hash && // always check first node12                 ((k = first.key) == key || (key != null && key.equals(k))))13                 return first;14             if ((e = first.next) != null) {15                 if (first instanceof TreeNode)16 　　　　　　　　　　　　//若定位到的节点是　TreeNode 节点，则在树中进行查找17                     return ((TreeNode
        
         )first).getTreeNode(hash, key);18                 do {//否则在链表中进行查找19                     if (e.hash == hash &&20                         ((k = e.key) == key || (key != null && key.equals(k))))21                         return e;22                 } while ((e = e.next) != null);23             }24         }25         return null;26     }
        
       
      
     
    

1         final TreeNode
    
      getTreeNode(int h, Object k) { 2 　　　　　　　　//从根节点开始，调用 find 方法进行查找 3             return ((parent != null) ? root() : this).find(h, k, null); 4         } 5 　 6         final TreeNode
     
       find(int h, Object k, Class
       kc) { 7             TreeNode
      
        p = this; 8             do { 9                 int ph, dir; K pk;10                 TreeNode
       
         pl = p.left, pr = p.right, q;11 　　　　　　　　　//首先进行hash 值的比较，若不同令当前节点变为它的左孩子或者右孩子12                 if ((ph = p.hash) > h)13                     p = pl;14                 else if (ph < h)15                     p = pr;16 　　　　　　　　　//hash 值相同，进行 key　值的比较 17                 else if ((pk = p.key) == k || (k != null && k.equals(pk)))18                     return p;19                 else if (pl == null)20                     p = pr;21                 else if (pr == null)22                     p = pl;23 　　　　　　　　　//执行到这儿，意味着hash 值相同，key 值不同 24    　　　　　　　　//若k 是可比较的并且k.compareTo(pk) 返回结果不为０可进入下面elseif   25                 else if ((kc != null ||26                           (kc = comparableClassFor(k)) != null) &&27                          (dir = compareComparables(kc, k, pk)) != 0)28                     p = (dir < 0) ? pl : pr;29                 /*若 k 是不可比较的　或者　k.compareTo(pk) 返回结果为０则在整棵树中进行查找，先找右子树，右子树没有再找左子树*/30                 else if ((q = pr.find(h, k, kc)) != null)31                     return q;32                 else33                     p = pl;34             } while (p != null);35             return null;36         }
       
      
     
    

七、HashMap 扩容方法　resize()

　　resize()　方法中比较重要的是链表和红黑树的 rehash 操作，先来说下 rehash 的实现原理：

　　我们在扩容的时候，一般是把长度扩为原来2倍，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

　　元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

　　因此，我们在扩充HashMap的时候，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：

　　 这个算法很巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的槽中了。

　　具体源码介绍：

　final Node
    
     [] resize() {        Node
     
      [] oldTab = table;        int oldCap = (oldTab == null) ? 0 : oldTab.length;        int oldThr = threshold;        int newCap, newThr = 0;　　/*        1、resize（）函数在size　> threshold时被调用。            oldCap大于 0 代表原来的 table 表非空， oldCap 为原表的大小，            oldThr（threshold） 为 oldCap × load_factor    　*/        if (oldCap > 0) {            if (oldCap >= MAXIMUM_CAPACITY) {                threshold = Integer.MAX_VALUE;                return oldTab;            }            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                     oldCap >= DEFAULT_INITIAL_CAPACITY)                newThr = oldThr << 1; // double threshold        }　　　　/*        2、resize（）函数在table为空被调用。        oldCap 小于等于 0 且 oldThr 大于0，代表用户创建了一个 HashMap，但是使用的构造函数为        HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)        或 HashMap(Map
       m)，导致 oldTab 为 null，oldCap 为0，        oldThr 为用户指定的 HashMap的初始容量。    　　*/        else if (oldThr > 0) // initial capacity was placed in threshold            newCap = oldThr;　　　　　/*            3、resize（）函数在table为空被调用。            oldCap 小于等于 0 且 oldThr 等于0，用户调用 HashMap()构造函数创建的　HashMap，所有值均采用默认值，       　　 oldTab（Table）表为空，oldCap为0，oldThr等于0，    　　*/        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;                Node
      
       [] newTab = (Node
       
        [])new Node[newCap];        table = newTab;        if (oldTab != null) {　　　　　　　//把　oldTab 中的节点　reHash 到　newTab 中去            for (int j = 0; j < oldCap; ++j) {                Node
        
          e;                if ((e = oldTab[j]) != null) {                    oldTab[j] = null;　　　　　　　　　　　　//若节点是单个节点，直接在 newTab　中进行重定位                    if (e.next == null)                        newTab[e.hash & (newCap - 1)] = e;　　　　　　　　　　　　//若节点是　TreeNode 节点，要进行 红黑树的 rehash　操作                    else if (e instanceof TreeNode)                        ((TreeNode
         
          )e).split(this, newTab, j, oldCap);　　　　　　　　　　　　//若是链表，进行链表的 rehash　操作 else { // preserve order Node
          
            loHead = null, loTail = null; Node
           
             hiHead = null, hiTail = null; Node
            
              next; do { 　　 next = e.next;　　　　　　　　　　　　　　　　　　//根据算法　e.hash & oldCap　判断节点位置　rehash　后是否发生改变 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null;　　　　　　　　　　　　　　　　// rehash　后节点新的位置一定为原来基础上加上　oldCap newTab[j + oldCap] = hiHead; } } } } } return newTab; }
            
           
          
         
        
       
      
     
    

1      //这个函数的功能是对红黑树进行　rehash 操作 2     final void split(HashMap
    
      map, Node
     
      [] tab, int index, int bit) { 3             TreeNode
      
        b = this; 4             // Relink into lo and hi lists, preserving order 5             TreeNode
       
         loHead = null, loTail = null; 6             TreeNode
        
          hiHead = null, hiTail = null; 7             int lc = 0, hc = 0; 8     　　　　　//由于　TreeNode 节点之间存在双端链表的关系，可以利用链表关系进行 rehash 9             for (TreeNode
         
           e = b, next; e != null; e = next) {10 next = (TreeNode
          
           )e.next;11 e.next = null;12 if ((e.hash & bit) == 0) {13 if ((e.prev = loTail) == null)14 loHead = e;15 else16 loTail.next = e;17 loTail = e;18 ++lc;19 }20 else {21 if ((e.prev = hiTail) == null)22 hiHead = e;23 else24 hiTail.next = e;25 hiTail = e;26 ++hc;27 }28 }29 30 //rehash 操作之后注意对根据链表长度进行　untreeify　或　treeify　操作31 if (loHead != null) {32 if (lc <= UNTREEIFY_THRESHOLD)33 tab[index] = loHead.untreeify(map);34 else {35 tab[index] = loHead;36 if (hiHead != null) // (else is already treeified)37 loHead.treeify(tab);38 }39 }40 if (hiHead != null) {41 if (hc <= UNTREEIFY_THRESHOLD)42 tab[index + bit] = hiHead.untreeify(map);43 else {44 tab[index + bit] = hiHead;45 if (loHead != null)46 hiHead.treeify(tab);47 }48 }//end if49 }//end split50
          
         
        
       
      
     
    

关于　HashMap 源码阅读的相关知识就先介绍到这里，有一些地方还需要更深入理解透彻（例如红黑树的插入节点之后的平衡操作，删除节点操作），后期会继续补充。