1类签名与注释

public class HashMap
     
       extends AbstractMap
      
           implements Map
       
        , Cloneable, Serializable
       
      
     

HashMap是基于哈希表实现的Map接口。 此实现提供了所有可选的地图操作，并允许null的值和null键。 （ HashMap类大致相当于Hashtable ，除了它是不同步的，并允许null）。该类不能保证map的顺序，特别是，它不能保证顺序在一段时间内保持不变（因为hash数组扩容时会重新散列）。

假设哈希函数在这些存储桶之间合理分散元素，这个实现为基本操作（ get和put ）提供了恒定的时间性能。收集视图的迭代与HashMap实例（桶数）加上其大小（键值映射数）的容量成正比 。 因此，想要好的迭代性能，不要将初始容量设置得太高（或负载因子太低）。

HashMap的一个实例有两个影响其性能的参数： 初始容量（capacity）和负载因子（load factor） 。 容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。 负载因子是在容量自动增加之前允许哈希表得到满足的度量。 当在散列表中的条目的数量超过了负载因数和当前容量的乘积，哈希表被重新散列 （即，内部数据结构被重建），使得哈希表具有桶的大约两倍。

作为一般规则，默认负载因子（0.75）提供了时间和空间成本之间的良好折中。 更高的值会降低空间开销，但会增加查找成本（反映在HashMap类的大部分操作中，包括get和put ）。 在设置其初始容量时，应考虑map中预期的条目数及其负载因子，以便最小化rehash操作的数量。 如果初始容量大于最大条目数除以负载因子，则不会发生重新排列操作。

如果有许多映射要存储在HashMap实例中，那么创建足够大的容量存储要比它自己自动扩容再rehash的效率高。注意，多个keys使用同样的hashCode会降低hash表的性能。为了改善影响，当按键是Comparable时，这个类可以使用keys之间的比较顺序来帮助打破关系。

请注意，此实现不同步。 如果多个线程同时访问哈希映射，并且至少有一个线程在结构上修改了映射，那么它必须在外部进行同步。 （结构修改是添加或删除一个或多个映射的任何操作;仅改变与实例已经包含的密钥相关联的值不是结构修改。）这可以通过同步对象来实现，如果没有同步对象，map应该使用Collections.synchronizedMap方法“包装”。 这最好在创建时完成，以防止意外的不同步访问map：

Map m = Collections.synchronizedMap(new HashMap(...));

被该类的所有集合视图方法返回的迭代器都是fail-fast的：如果映射在迭代器创建之后的任何时间被结构地修改，除了通过迭代器自己的remove方法之外，迭代器将抛出一个ConcurrentModificationException 。 因此，面对并发修改，迭代器将快速而干净地失败，而不是在未来未确定的时间冒着任意的非确定性行为。

请注意，迭代器的故障快速行为无法保证，迭代器的故障快速行为应仅用于检测错误，而不是依赖它来保证程序的正确性。

该类是Java Collections Framework的成员。

2成员变量

// 序列号private static final long serialVersionUID = 362498820763181265L;// 默认初始化容量16，要求必须是2的n次方。static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16// 最大容量，因为必须是2的n次方，int中最大只能到230static final int MAXIMUM_CAPACITY = 1 << 30;// 默认负载因子static final float DEFAULT_LOAD_FACTOR = 0.75f; //当桶中的键值对数量到达8个，且桶数量大于等于64，则将底层实现从链表转为红黑 // 如果桶中的键值对到达该阀值，则检测桶数量  static final int TREEIFY_THRESHOLD = 8;static final int UNTREEIFY_THRESHOLD = 6;//当桶数（底层数组长度）到达64个的时候，则将链表转为红黑树static final int MIN_TREEIFY_CAPACITY = 64;-------------------------------------------------------------------------------transient Node
     
      [] table;//Holds cached entrySet(). Note that AbstractMap fields are used for keySet() and values().transient Set
      
       
        > entrySet;//The number of key-value mappings contained in this map. transient int size;transient int modCount;
       
      
     

//当集合没有分配空间时，表示初始的数组容量。当分配了，则表示（capacity * load factor） //注意理解这个属性，否则后面的代码不好理解 int threshold;//The load factor for the hash table.final float loadFactor;

存储桶table是用Node型的数组表示的，Node是一个静态内部类，实现了Map.Entry接口。这里将每个Entity封装成一个链表的节点，每个节点指向下一个节点（如果有的话）。

所以hashMap是用数组和链表实现的。（当当达到一定条件后，由“数组/链表”变为“数组/红黑树”实现）

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

 

3构造函数

//（1）指定初始容量initialCapacity与负载因子loadFactor public HashMap(int initialCapacity, float loadFactor) {        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal initial capacity: " +                                               initialCapacity);        if (initialCapacity > MAXIMUM_CAPACITY) //初始容量最大值            initialCapacity = MAXIMUM_CAPACITY;        if (loadFactor <= 0 || Float.isNaN(loadFactor))            throw new IllegalArgumentException("Illegal load factor: " +                                               loadFactor);        this.loadFactor = loadFactor;        this.threshold = tableSizeFor(initialCapacity);    }  //该方法可以将参数cap值改为2n，2n-1
     
      >> 1;        n |= n >>> 2;        n |= n >>> 4;        n |= n >>> 8;        n |= n >>> 16;        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;    } //（2）指定初始容量，负载因子默认0.75 public HashMap(int initialCapacity) {        this(initialCapacity, DEFAULT_LOAD_FACTOR);    } //（3）默认初始容量16（在put时会检查扩容），负载因子默认0.75 public HashMap() {        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted    }  public HashMap(Map
       m) {        this.loadFactor = DEFAULT_LOAD_FACTOR;        putMapEntries(m, false);    } final void putMapEntries(Map
       m, boolean evict) {        int s = m.size();        if (s > 0) {            if (table == null) { // pre-size                float ft = ((float)s / loadFactor) + 1.0F;                int t = ((ft < (float)MAXIMUM_CAPACITY) ?                         (int)ft : MAXIMUM_CAPACITY);                if (t > threshold)                    threshold = tableSizeFor(t);            }            else if (s > threshold)                resize();            for (Map.Entry
       e : m.entrySet()) {                K key = e.getKey();                V value = e.getValue();                putVal(hash(key), key, value, false, evict);            }        }    }
     

tableSizeFor(int cap)方法使用无符号右移和或运算，实现了将cap参数转为2ⁿ的整数。思路如下：以00001000（8）为例，从左往右找到第一个1，先>>>1得（00000100）然后或操作原数(00001000)得（00001100），将原数第一个1的下一位变成1。下一次>>>2或之后得15（00001111），也就是把最高位1开始之后的所有位都变成1，最后加1就变成了2ⁿ。因为int是32位得所以最多移16位即可。为什么要先加1，最后再减1？这样可以保证2^n-1<cap≤2ⁿ，否则当cap=8时，返回得结果为16都是2的n次方，没有什么意义。

也可以通过1个map类型的参数构造HashMap，构造函数通过调用putMapEntries实现。putMapEntries先检查一下容量，然后通过putVal插入元素。关于putVal方法，在后面小节详细说明。

4查找

1 public V get(Object key) { 2         Node
     
       e; 3         return (e = getNode(hash(key), key)) == null ? null : e.value; 4     } 5  6     final Node
      
        getNode(int hash, Object key) { 7         Node
       
        [] tab; Node
        
          first, e; int n; K k; 8         if ((tab = table) != null && (n = tab.length) > 0 && 9             (first = tab[(n - 1) & hash]) != null) {10             if (first.hash == hash && // always check first node11                 ((k = first.key) == key || (key != null && key.equals(k))))12                 return first;13             if ((e = first.next) != null) {14                 if (first instanceof TreeNode)15                     return ((TreeNode
         
          )first).getTreeNode(hash, key);16                 do {17                     if (e.hash == hash &&18                         ((k = e.key) == key || (key != null && key.equals(k))))19                         return e;20                 } while ((e = e.next) != null);21             }22         }23         return null;24     }25 26     public boolean containsKey(Object key) {27         return getNode(hash(key), key) != null;28     }
         
        
       
      
     

get方法和containsKey都是通过getNode实现。

（1）如何通过key的hash值找到key在数组中的位置？

注意代码line9，first = tab[(n - 1) & hash]，前面我们知道HashMap的容量是2的指数倍的，所以n-1可以保证低位全部都是1，例如n=16，n-1=1（00001111）。而(n - 1) & hash可以将hash值得高位置0，相当于hash%n，但计算速度比后者要快。

（2）找到该位置的对应节点

first表示该位置的第一个节点，当找到该位置时，总是要先检查一下first节点是不是查找的元素（line10-12）。若不是则往后遍历链表。（为什么要判断TreeNode？）

（3）hash(key)实现的原理

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

若非空，则高16位不变，低16位变成高16位和低16位的异或。为什么要这么做？前面我们知道定位是通过(length - 1) & hash，当length不够大时（也就是hashMap容量不够大），一直是hash值的低位起作用，这样容易造成碰撞（不同的hash值定位的结果相同），所以要提高高位的影响。然后就有了该操作。

注意key为null的情况，hashMap是允许key为null的，key为null的entry（键值对）存储在存储数组的0号位。

也可以查找value是否在集合中

public boolean containsValue(Object value) {        Node
     
      [] tab; V v;        if ((tab = table) != null && size > 0) {            for (int i = 0; i < tab.length; ++i) {                for (Node
      
        e = tab[i]; e != null; e = e.next) {                    if ((v = e.value) == value ||                        (value != null && value.equals(v)))                        return true;                }            }        }        return false;    }
      
     

这里总结两个源码实现的小技巧：

（1）在遍历数组前先检查数组是否为空。((tab = table) != null && size > 0)

（2）判断对象是否相等的方式。((v = e.value) == value || (value != null && value.equals(v)))

 

5扩容

resize方法

1 final Node
     
      [] resize() { 2         Node
      
       [] oldTab = table; 3         int oldCap = (oldTab == null) ? 0 : oldTab.length; 4         int oldThr = threshold; 5         int newCap, newThr = 0; 6         if (oldCap > 0) { // 容量不为空（已分配内存空间） 7             if (oldCap >= MAXIMUM_CAPACITY) { 8                 threshold = Integer.MAX_VALUE; 9                 return oldTab; //已到最大值，没法继续扩容10             }11             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&12                      oldCap >= DEFAULT_INITIAL_CAPACITY) //容量增为2倍，并检查13                 newThr = oldThr << 1; // 将阈值也扩为2倍14         }15         else if (oldThr > 0) // 若容量为0，old阈值大于0。容量用阈值表示（见构造函数1）16             newCap = oldThr;17         else {               // 若容量为0，old阈值也为0。使用默认值初始化（见构造函数3）18             newCap = DEFAULT_INITIAL_CAPACITY;19             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);20         }21         if (newThr == 0) { //计算阈值的合理值22             float ft = (float)newCap * loadFactor;23             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?24                       (int)ft : Integer.MAX_VALUE);25         }26         threshold = newThr;27         @SuppressWarnings({"rawtypes","unchecked"})28             Node
       
        [] newTab = (Node
        
         [])new Node[newCap];29         table = newTab;30         if (oldTab != null) { //将旧的值复制到新的存储桶里面31             for (int j = 0; j < oldCap; ++j) {32                 Node
         
           e;33                 if ((e = oldTab[j]) != null) {34                     oldTab[j] = null;35                     if (e.next == null) //如果该位置只有1个元素，直接插如到新的位置（从新计算位置）36                         newTab[e.hash & (newCap - 1)] = e;37                     else if (e instanceof TreeNode)38                         ((TreeNode
          
           )e).split(this, newTab, j, oldCap);39 else { // preserve order40 Node
           
             loHead = null, loTail = null;41 Node
            
              hiHead = null, hiTail = null;42 Node
             
               next;43 do {44 next = e.next;45 if ((e.hash & oldCap) == 0) {46 if (loTail == null)47 loHead = e; // 头节点指向第一个元素48 else49 loTail.next = e; // 当前个元素的next指向下一个元素50 loTail = e; //尾节点移向下一个个元素51 }52 else {53 if (hiTail == null)54 hiHead = e;55 else56 hiTail.next = e;57 hiTail = e;58 }59 } while ((e = next) != null);60 if (loTail != null) {61 loTail.next = null;62 newTab[j] = loHead;63 }64 if (hiTail != null) {65 hiTail.next = null;66 newTab[j + oldCap] = hiHead;67 }68 }69 }70 }71 }72 return newTab;73 }
             
            
           
          
         
        
       
      
     

下面重点分析line40-66，这里的任务是处理oldTab[j]位置的值不是单个元素，而是由多个元素组成链表的情况。

原理是通过头节点Head定位第一个元素，通过尾节点Tail的不断后移组装链表。但是为什么这里要使用两组头尾节点呢？（loHead+loTail、hiHead+hiTail）

这里是定位用的。举个例子原集合容量为16（0001 0000），(e.hash & oldCap) == 0表示hash值的第5位（从右往左）为0，这样扩容后定位为e.hash & （newCap-1）= e.hash &31（0001 1111），计算后第5位也为0，与旧集合的位置一样。所以line62直接将链表存在和同样的位置上。否则hash值的第5位为1，定位计算后第5位也为0，与原来相比大了2^（5-1）=16，正好是大了旧集合的容量，所以line66定位用j+oldCap。可以把容量为32的新集合简单理解为高16位和低16位，结合取模计算就很好理解了。

line37-38在后面讨论红黑树的时候解释。

6添加元素

通过调用put方法向hashMap中添加1个元素

1 public V put(K key, V value) { 2         return putVal(hash(key), key, value, false, true); 3     } 4  5     /** 6      * @param hash hash for key 7      * @param key the key 8      * @param value the value to put 9      * @param onlyIfAbsent if true, don't change existing value10      * @param evict if false, the table is in creation mode.11      * @return previous value, or null if none12      */13     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,14                    boolean evict) {15         Node
     
      [] tab; Node
      
        p; int n, i;16         if ((tab = table) == null || (n = tab.length) == 0)17             n = (tab = resize()).length;18         if ((p = tab[i = (n - 1) & hash]) == null)19             tab[i] = newNode(hash, key, value, null);20         else {21             Node
       
         e; K k;22             if (p.hash == hash &&23                 ((k = p.key) == key || (key != null && key.equals(k))))24                 e = p;25             else if (p instanceof TreeNode)26                 e = ((TreeNode
        
         )p).putTreeVal(this, tab, hash, key, value);27             else {28                 for (int binCount = 0; ; ++binCount) {29                     if ((e = p.next) == null) {30                         p.next = newNode(hash, key, value, null);31                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st32                             treeifyBin(tab, hash);33                         break;34                     }35                     if (e.hash == hash &&36                         ((k = e.key) == key || (key != null && key.equals(k))))37                         break;38                     p = e;39                 }40             }41             if (e != null) { // existing mapping for key42                 V oldValue = e.value;43                 if (!onlyIfAbsent || oldValue == null)44                     e.value = value;45                 afterNodeAccess(e);46                 return oldValue;47             }48         }49         ++modCount;50         if (++size > threshold)51             resize();52         afterNodeInsertion(evict);53         return null;54     }
        
       
      
     

line16-17检查集合是否为空，若是则分配初始容量。

line18-19根据hash值进行定位，检查存储桶在该位置i是否为空。若是则直接放入新的值。（newNode方法新建1个Node类型的对象）。

若存储桶在i位置有元素

（1）首先判断key值是否和链表的第一个元素相等（line22）

（2）若相等则如果参数onlyIfAbsent为false或者该位置的值为null，将value赋值为新值，并返回旧值（line41-47）。

（3）若1步不相等，则检查是否是TreeNode类型（红黑树实现）

（4）在链表的尾部插入新的元素（Node类型）

line25-26中的treeNode后面再研究。

最后判断当前容量是否超过阈值，若超过就要进行扩容。line50-51

afterNodeInsertion是一个post-actions，为了方便LinkedHashMap插入节点后的行为。但是在HashMap里面是该方法没有任何行为。

 注意：line31检查桶中的节点数量（链表的长度），大于阀值则调用treeifyBin方法，treeifyBin中检查桶数量，大于64则需要将底层实现由链表改为红黑树，  如果桶数量不到64则重构一下链表 。 （jdk8中做的优化）

//当桶的数量太多的时候，底层则改为红黑树实现  final void treeifyBin(Node
     
      [] tab, int hash) {      int n, index; Node
      
        e;      //当桶的数量有 MIN_TREEIFY_CAPACITY （64）个时才将链表改为红黑树      if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)          //节点太少则resize()          resize();      else if ((e = tab[index = (n - 1) & hash]) != null) {          //将链接的结点转为二叉树结构          TreeNode
       
         hd = null, tl = null;          do {              TreeNode
        
          p = replacementTreeNode(e, null);              if (tl == null)                  hd = p;              else {                  p.prev = tl;                  tl.next = p;              }              tl = p;          } while ((e = e.next) != null);          if ((tab[index] = hd) != null)              hd.treeify(tab);      }  }
        
       
      
     

 

7删除元素

public V remove(Object key) {        Node
     
       e;        return (e = removeNode(hash(key), key, null, false, true)) == null ?            null : e.value;    }    /**     * @param hash hash for key     * @param key the key     * @param value the value to match if matchValue, else ignored     * @param matchValue if true only remove if value is equal     * @param movable if false do not move other nodes while removing     * @return the node, or null if none     */    final Node
      
        removeNode(int hash, Object key, Object value,                               boolean matchValue, boolean movable) {        Node
       
        [] tab; Node
        
          p; int n, index;        if ((tab = table) != null && (n = tab.length) > 0 &&            (p = tab[index = (n - 1) & hash]) != null) {            Node
         
           node = null, e; K k; V v;            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                node = p;            else if ((e = p.next) != null) {                if (p instanceof TreeNode)                    node = ((TreeNode
          
           )p).getTreeNode(hash, key); else { do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { if (node instanceof TreeNode) ((TreeNode
           
            )node).removeTreeNode(this, tab, movable); else if (node == p) tab[index] = node.next; else p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }
           
          
         
        
       
      
     

删除所有元素

public void clear() {        Node
     
      [] tab;        modCount++;        if ((tab = table) != null && size > 0) {            size = 0;            for (int i = 0; i < tab.length; ++i)                tab[i] = null;        }    }
     

 8迭代器

hashMap内部实现了四个迭代器，分别是HashIterator，KeyIterator，ValueIterator，EntryIterator。其中HashIterator是其他迭代器的父类。

HashIterator实现如下：

abstract class HashIterator {        Node
     
       next;        // next entry to return        Node
      
        current;     // current entry        int expectedModCount;  // for fast-fail        int index;             // current slot        HashIterator() {            expectedModCount = modCount;            Node
       
        [] t = table;            current = next = null;            index = 0;            if (t != null && size > 0) { // 找到数组第一个不为null的位置                do {} while (index < t.length && (next = t[index++]) == null);            }        }        public final boolean hasNext() {            return next != null;        }        final Node
        
          nextNode() {            Node
         
          [] t;            Node
          
            e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); if ((next = (current = e).next) == null && (t = table) != null) { // 这里不仅判断，而且将next节点后移。 do {} while (index < t.length && (next = t[index++]) == null); // 找到数组下一个不为null的位置 } return e; } public final void remove() { Node
           
             p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; //要求remove之前的操作是nextNode K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } }
           
          
         
        
       
      
     

KeyIterator是keySet的迭代器实现

ValueIterator是valuse的迭代器实现

EntryIterator是Entry的迭代器实现

final class KeyIterator extends HashIterator        implements Iterator
     
       {        public final K next() { return nextNode().key; }    }    final class ValueIterator extends HashIterator        implements Iterator
      
        {        public final V next() { return nextNode().value; }    }    final class EntryIterator extends HashIterator        implements Iterator
       
        
         > {        public final Map.Entry
         
           next() { return nextNode(); }    }
         
        
       
      
     

本文只分析了hashMap的一些基本操作的实现，其他的方法（包括函数编程内容，红黑树的实现等）后续会深入学习。