Java HashMap
起初，存储数据最简单的数据结构是数组，数组的优点是查找速度快，缺点是删除速度特别慢。
接下来是链表数据结构，链表的优点是删除速度快，缺点是查找速度慢。
那么，有没有一种数据结构可以结合两者的优点呢？
答案是有的，这就是常说的哈希表。如下：
640.jpg
哈希表是由数组+链表组成的混合结构，在图中纵向的0~15表示一个数组，每个数组的下标都可以含有一个链表。
当使用put方法添加元素时，首先需计算出数组的索引，再将元素插入到当前数组索引对应链表的某个位置。实际上，往往插入元素的次数比较频繁，在索引为12的位置上插入过多的元素，每次都要从头遍历当前索引所对应链表，如果key相同，则替换掉原来的value值，否则直接在链表的末尾添加元素。像这种，重复的在某索引下插入元素叫做碰撞。很明显，如果碰撞次数太多，会大大的影响hashmap的性能。那么，怎么才能减少碰撞的次数呢？请继续往下看。
这里讲解HashMap的大方向主要有以下几点：

  • 构造方法
  • 插入元素
  • 获取元素
  • 遍历

    （1）构造方法

    【方法一】

    1. /**
    2. * Constructs an empty <tt>HashMap</tt> with the default initial capacity
    3. * (16) and the default load factor (0.75).
    4. */
    5. public HashMap() {
    6.   this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    7. }
    在这个方法中，DEFAULT_LOAD_FACTOR为负载系数，源码中的定义如下：
    1. /**
    2. * The load factor used when none specified in constructor.
    3. */
    4. static final float DEFAULT_LOAD_FACTOR = 0.75f;
    负载系数默认为0.75，这个参数和HashMap的扩容有关。
    另外，HashMap是有容量的，此时HashMap的默认容量是16，源码中的定义如下：
    1. /**
    2. * The default initial capacity - MUST be a power of two.
    3. */
    4. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    【方法二】

    1. /**
    2. * Constructs an empty <tt>HashMap</tt> with the specified initial
    3. * capacity and the default load factor (0.75).
    4. *
    5. * @param  initialCapacity the initial capacity.
    6. * @throws IllegalArgumentException if the initial capacity is negative.
    7. */
    8. public HashMap(int initialCapacity) {
    9.   this(initialCapacity, DEFAULT_LOAD_FACTOR);
    10. }
    这个构造方法容量可以自定义，至于负载系数采用默认值0.75。

    【方法三】

    1. /**
    2. * Constructs an empty <tt>HashMap</tt> with the specified initial
    3. * capacity and load factor.
    4. *
    5. * @param  initialCapacity the initial capacity
    6. * @param  loadFactor      the load factor
    7. * @throws IllegalArgumentException if the initial capacity is negative
    8. *         or the load factor is nonpositive
    9. */
    10. public HashMap(int initialCapacity, float loadFactor) {
    11.   if (initialCapacity < 0)
    12.       throw new IllegalArgumentException("Illegal initial capacity: " +
    13.                                          initialCapacity);
    14.   if (initialCapacity > MAXIMUM_CAPACITY)
    15.       initialCapacity = MAXIMUM_CAPACITY;
    16.   if (loadFactor <= 0 || Float.isNaN(loadFactor))
    17.       throw new IllegalArgumentException("Illegal load factor: " +
    18.                                          loadFactor);
    19.   this.loadFactor = loadFactor;
    20.   this.threshold = tableSizeFor(initialCapacity);
    21. }
    这个方法可以任意指定HashMap的容量以及负载系数。容量的大小不能大于MAXIMUM_CAPACITY，有关MAXIMUM_CAPACITY源码中的定义代码是：
    1. /**
    2. * The maximum capacity, used if a higher value is implicitly specified
    3. * by either of the constructors with arguments.
    4. * MUST be a power of two <= 1<<30.
    5. */
    6. static final int MAXIMUM_CAPACITY = 1 << 30;
    转成十进制是：
    1. static final int MAXIMUM_CAPACITY = 1073741824;
    另外，这个方法中的tableSizeFor方法是计算当前容量的阈值，即最大容量，最大容量总是等于2的n次幂，假如HashMap的容量是9，那么数组的大小是16，2的4次幂。计算数组大小的源码如下：
    1. /**
    2. * Returns a power of two size for the given target capacity.
    3. */
    4. static final int tableSizeFor(int cap) {
    5.   int n = cap - 1;
    6.   n |= n >>> 1;
    7.   n |= n >>> 2;
    8.   n |= n >>> 4;
    9.   n |= n >>> 8;
    10.   n |= n >>> 16;
    11.   return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    12. }

    【方法四】

    1. /**
    2. * Constructs a new <tt>HashMap</tt> with the same mappings as the
    3. * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
    4. * default load factor (0.75) and an initial capacity sufficient to
    5. * hold the mappings in the specified <tt>Map</tt>.
    6. *
    7. * @param   m the map whose mappings are to be placed in this map
    8. * @throws  NullPointerException if the specified map is null
    9. */
    10. public HashMap(Map<? extends K, ? extends V> m) {
    11.   this.loadFactor = DEFAULT_LOAD_FACTOR;
    12.   putMapEntries(m, false);
    13. }
    这个方法的形参就是HashMap集合，想都不用想，肯定会遍历旧集合，并一个一个添加到新的集合中。putMapEntries方法的源码如下：
    1. /**
    2. * Implements Map.putAll and Map constructor
    3. *
    4. * @param m the map
    5. * @param evict false when initially constructing this map, else
    6. * true (relayed to method afterNodeInsertion).
    7. */
    8. final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    9.   int s = m.size();
    10.   if (s > 0) {
    11.       if (table == null) { // pre-size
    12.           float ft = ((float)s / loadFactor) + 1.0F;
    13.           int t = ((ft < (float)MAXIMUM_CAPACITY) ?
    14.                    (int)ft : MAXIMUM_CAPACITY);
    15.           if (t > threshold)
    16.               threshold = tableSizeFor(t);
    17.       }
    18.       else if (s > threshold)
    19.           resize();
    20.       for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
    21.           K key = e.getKey();
    22.           V value = e.getValue();
    23.           putVal(hash(key), key, value, false, evict);
    24.       }
    25.   }
    26. }
    其中putVal方法就是插入元素。

    （2）插入元素

    当需要添加元素时，代码实现如下：
    1. HashMap<String, String> hashMap = new HashMap<>();
    2. //添加一个元素
    3. hashMap.put("key", "value");
    那么，put方法的原理是什么呢？想要知道这个答案，必须研究下源码了。 ```java /**
    • Associates the specified value with the specified key in this map.
    • If the map previously contained a mapping for the key, the old
    • value is replaced. *
    • @param key key with which the specified value is to be associated
    • @param value value to be associated with the specified key
    • @return the previous value associated with key, or
    • null if there was no mapping for key.
    • (A null return can also indicate that the map
    • previously associated null with key.) */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

/**

  • Implements Map.put and related methods *
  • @param hash hash for key
  • @param key the key
  • @param value the value to put
  • @param onlyIfAbsent if true, don’t change existing value
  • @param evict if false, the table is in creation mode.
  • @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    1.         boolean evict) {
    Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0)
    1.  n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
    1.  tab[i] = newNode(hash, key, value, null);
    else {
    1.  Node<K,V> e; K k;
    2.  if (p.hash == hash &&
    3.      ((k = p.key) == key || (key != null && key.equals(k))))
    4.      e = p;
    5.  else if (p instanceof TreeNode)
    6.      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    7.  else {
    8.      for (int binCount = 0; ; ++binCount) {
    9.          if ((e = p.next) == null) {
    10.              p.next = newNode(hash, key, value, null);
    11.              if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    12.                  treeifyBin(tab, hash);
    13.              break;
    14.          }
    15.          if (e.hash == hash &&
    16.              ((k = e.key) == key || (key != null && key.equals(k))))
    17.              break;
    18.          p = e;
    19.      }
    20.  }
    21.  if (e != null) { // existing mapping for key
    22.      V oldValue = e.value;
    23.      if (!onlyIfAbsent || oldValue == null)
    24.          e.value = value;
    25.      afterNodeAccess(e);
    26.      return oldValue;
    27.  }
    } ++modCount; if (++size > threshold)
    1.  resize();
    afterNodeInsertion(evict); return null; }
    1. <a name="kFBzD"></a>
    2. ### 【第一步】 对Key求Hash值，然后再计算下标
    3. `putVal`的第一个参数是根据Key的`hashcode`计算一个新的`hashcode`，源码如下：
    4. ```java
    5. static final int hash(Object key) {
    6.  int h;
    7.  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    8. }
    在JDK1.8之前，重新计算hashcode源码是这样的
    1. final int hash(Object k) {
    2.  int h = 0;
    3.  if (useAltHashing) {
    4.      if (k instanceof String) {
    5.          return sun.misc.Hashing.stringHash32((String) k);
    6.      }
    7.      h = hashSeed;
    8.  }
    9.  //得到k的hashcode值
    10.  h ^= k.hashCode();
    11.  //进行计算
    12.  h ^= (h >>> 20) ^ (h >>> 12);
    13.  return h ^ (h >>> 7) ^ (h >>> 4);
    14. }
    计算数组下标代码如下：
    在JDK1.8之前的源码是：
    1. static int indexFor(int h, int length) {  
    2.  return h & (length-1);
    3. }
    在JDK1.8之后，计算数组下标的代码在putVal中，
    1. tab[i = (n - 1) & hash]
    n是数组的长度，hash的重新计算后的hashcode。
    所以，计算数组下标的算法是：
    1. index =  hashcode & (length-1)
    该算法相当于
    1. index =  hashcode % length
    那么，问题来了，为什么不直接使用key的hashcode？为什么JDK1.8前后会有差异？
    原因只有一个：为了让Hash表更加散列，减少冲突（碰撞）次数。
    如果hashcode没有重新计算，假设某对象的hashcode是3288498，那么对应的二进制是：
    1. 1100100010110110110010
    hashmap的长度默认为16，所以假设length = 16，hashcode & (length-1)的运算如下： ```java 1100100010110110110010 & 0000000000000000001111

0000000000000000000010

  1. 以上计算结果是十进制2，即数组下标为2。因此，发现的现象是：计算数组角标的计算，其实就是低位在计算，当前是在低4位上进行运算。<br />当数组长度为8时，在第3位计算出数组下标；<br />当数组长度为16时，在第4位计算出数组下标；<br />当数组长度为32时，在第5位计算出数组下标；<br />当数组长度为64时，在第6位计算出数组下标；<br />以此类推…
  2. :::info
  3. 为了让`HashMap`的存储更加散列，即低n位更加散列，需要和高m位进行异或运算，最终得出新的`hashcode`。这就是要重新计算`hashcode`的原因。JDK1.8前后重新计算`hashcode`算法的差异是因为，JDK1.8的hash算法比JDK1.8之前的`hash`算法更能让`HashMap`的存储更加散列，避免存储空间的拥挤，减少碰撞的发生。
  4. :::
  5. <a name="bfeAs"></a>
  6. ### 【第二步】 碰撞的处理
  7. Java中`HashMap`是利用“拉链法”处理`HashCode`的碰撞问题。在调用`HashMap`的`put`方法或`get`方法时，都会首先调用`hashcode`方法，去查找相关的key，当有冲突时，再调用`equals`方法。`hashMap`基于`hasing`原理，通过`put`和`get`方法存取对象。将键值对传递给`put`方法时，他调用键对象的`hashCode()`方法来计算`hashCode`，然后找到`bucket`（哈希桶）位置来存储对象。当获取对象时，通过键对象的`equals()`方法找到正确的键值对，然后返回值对象。`HashMap`使用链表来解决碰撞问题，当碰撞发生了，对象将会存储在链表的下一个节点中。hashMap在每个链表节点存储键值对对象。当两个不同的键却有相同的`hashCode`时，他们会存储在同一个`bucket`位置的链表中。
  8. <a name="t8Akz"></a>
  9. ### 【第三步】 如果链表长度超过阀值( `TREEIFY THRESHOLD==8`)，就把链表转成红黑树，链表长度低于6，就把红黑树转回链表
  10. ```java
  11. /**
  12.  * The bin count threshold for using a tree rather than list for a
  13.  * bin.  Bins are converted to trees when adding an element to a
  14.  * bin with at least this many nodes. The value must be greater
  15.  * than 2 and should be at least 8 to mesh with assumptions in
  16.  * tree removal about conversion back to plain bins upon
  17.  * shrinkage.
  18.  */
  19. static final int TREEIFY_THRESHOLD = 8;
  21. if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  22.     //红黑树
  23.     treeifyBin(tab, hash);

在JDK1.8之后，HashMap的存储引入了红黑树数据结构。

【第四步】 如果节点已经存在就替换旧值

代码如下：

  1. if (p.hash == hash &&
  2.     ((k = p.key) == key || (key != null && key.equals(k))))
  3.     e = p;

【第五步】 扩容

代码如下：

  1. /**
  2.  * Initializes or doubles table size.  If null, allocates in
  3.  * accord with initial capacity target held in field threshold.
  4.  * Otherwise, because we are using power-of-two expansion, the
  5.  * elements from each bin must either stay at same index, or move
  6.  * with a power of two offset in the new table.
  7.  *
  8.  * @return the table
  9.  */
  10. final Node<K,V>[] resize() {
  11.     Node<K,V>[] oldTab = table;
  12.     //当前容量
  13.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  14.     //阈值，最大容量
  15.     int oldThr = threshold;
  16.     //定义新容量和阈值
  17.     int newCap, newThr = 0;
  18.     if (oldCap > 0) {//如果当前容量>0
  19.         if (oldCap >= MAXIMUM_CAPACITY) {
  20.             threshold = Integer.MAX_VALUE;
  21.             return oldTab;
  22.         }
  23.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  24.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  25.             //计算新的阈值，在老阈值的基础上乘以2
  26.             newThr = oldThr << 1; // double threshold
  27.     }
  28.     else if (oldThr > 0) // initial capacity was placed in threshold
  29.         newCap = oldThr;
  30.     else {               // zero initial threshold signifies using defaults
  31.         newCap = DEFAULT_INITIAL_CAPACITY;
  32.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  33.     }
  34.     if (newThr == 0) {
  35.         float ft = (float)newCap * loadFactor;
  36.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  37.                   (int)ft : Integer.MAX_VALUE);
  38.     }
  39.     threshold = newThr;
  40.     @SuppressWarnings({"rawtypes","unchecked"})
  42.     //计算完容量和阈值之后，开始新建一个数组，扩容
  43.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  44.     table = newTab;
  45.     if (oldTab != null) {
  46.         //赋值操作
  47.         for (int j = 0; j < oldCap; ++j) {
  48.             Node<K,V> e;
  49.             if ((e = oldTab[j]) != null) {
  50.                 oldTab[j] = null;
  51.                 if (e.next == null)
  52.                     newTab[e.hash & (newCap - 1)] = e;
  53.                 else if (e instanceof TreeNode)
  54.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  55.                 else { // preserve order
  56.                     Node<K,V> loHead = null, loTail = null;
  57.                     Node<K,V> hiHead = null, hiTail = null;
  58.                     Node<K,V> next;
  59.                     do {
  60.                         next = e.next;
  61.                         if ((e.hash & oldCap) == 0) {
  62.                             if (loTail == null)
  63.                                 loHead = e;
  64.                             else
  65.                                 loTail.next = e;
  66.                             loTail = e;
  67.                         }
  68.                         else {
  69.                             if (hiTail == null)
  70.                                 hiHead = e;
  71.                             else
  72.                                 hiTail.next = e;
  73.                             hiTail = e;
  74.                         }
  75.                     } while ((e = next) != null);
  76.                     if (loTail != null) {
  77.                         loTail.next = null;
  78.                         newTab[j] = loHead;
  79.                     }
  80.                     if (hiTail != null) {
  81.                         hiTail.next = null;
  82.                         newTab[j + oldCap] = hiHead;
  83.                     }
  84.                 }
  85.             }
  86.         }
  87.     }
  88.     return newTab;
  89. }

以上扩容相关代码是基于JDK1.8的，和JDK1.8之前存在差异。

（3）获取元素

  1. /**
  2.  * Returns the value to which the specified key is mapped,
  3.  * or {@code null} if this map contains no mapping for the key.
  4.  *
  5.  * <p>More formally, if this map contains a mapping from a key
  6.  * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
  7.  * key.equals(k))}, then this method returns {@code v}; otherwise
  8.  * it returns {@code null}.  (There can be at most one such mapping.)
  9.  *
  10.  * <p>A return value of {@code null} does not <i>necessarily</i>
  11.  * indicate that the map contains no mapping for the key; it's also
  12.  * possible that the map explicitly maps the key to {@code null}.
  13.  * The {@link #containsKey containsKey} operation may be used to
  14.  * distinguish these two cases.
  15.  *
  16.  * @see #put(Object, Object)
  17.  */
  18. public V get(Object key) {
  19.     Node<K,V> e;
  20.     return (e = getNode(hash(key), key)) == null ? null : e.value;
  21. }
  23. /**
  24.  * Implements Map.get and related methods
  25.  *
  26.  * @param hash hash for key
  27.  * @param key the key
  28.  * @return the node, or null if none
  29.  */
  30. final Node<K,V> getNode(int hash, Object key) {
  31.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  32.     if ((tab = table) != null && (n = tab.length) > 0 &&
  33.         (first = tab[(n - 1) & hash]) != null) {
  34.         if (first.hash == hash && // always check first node
  35.             ((k = first.key) == key || (key != null && key.equals(k))))
  36.             return first;
  37.         if ((e = first.next) != null) {
  38.             if (first instanceof TreeNode)
  39.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  40.             do {
  41.                 if (e.hash == hash &&
  42.                     ((k = e.key) == key || (key != null && key.equals(k))))
  43.                     return e;
  44.             } while ((e = e.next) != null);
  45.         }
  46.     }
  47.     return null;
  48. }

获取元素其实，没什么好讲的，但是需要知道的是，不管是插入元素还是获取元素，都是围绕节点(Node)来操作的。Node实现了Map.Entry<K,V>接口。

（4）遍历元素

【方法一】

如果只需要获取所有的key，最佳方案如下：

  1. for (Integer key : map.keySet()) {//在for-each循环中遍历keys
  2.     System.out.println(String.valueOf(key));
  3. }

优点：比entrySet遍历要快，代码简洁。

【方法二】

如果只需要获取所有的value，最佳方案如下：

  1. for (String value : map.values()) {//在for-each循环中遍历value
  2.     System.out.println(value);
  3. }

优点：比entrySet遍历要快，代码简洁。

【方法三】

通过键找值遍历

  1. for (Integer key : map.keySet()) {//在for-each循环中遍历keys
  2.     String value = map.get(key);
  3.     System.out.println(key+"========"+value);
  4. }

缺点：根据键取值是耗时操作，效率非常的慢， 所以不推荐。

【方法四】

通过Map.entrySet遍历key和value

  1. for (Map.Entry<Integer, String> entry : map.entrySet()) {
  2.     System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
  3. }

优点：代码简洁，效率高，推荐使用。

【方法五】

使用Iterator遍历

  1. Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
  2. while (iterator.hasNext()) {
  3.     Map.Entry<Integer, String> entry = iterator.next();
  4.     System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
  5. }

缺点：代码比起前面几个方法并不简洁。
优点：当遍历的时候，如果涉及到删除操作，建议使用Iterator的remove方法，因为如果使用foreach的话会报错。