HashMap

HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。HashMap是一个散列表，它是通过“拉链法”实现的。在初始创建的hashMap对象中Node[] table 为空null，只有在第一次存放元素时table数组会初始化。
重要的成员变量有 table, size, threshold, loadFactor, modCount

• table：是一个Node[]数组类型，而Node实际上就是一个单向链表。
• size： 是HashMap的大小，它是HashMap保存的键值对的数量。
• threshold [ˈθreʃhəʊld]：HashMap的阈值，threshold的值=”容量*加载因子”，当 size > threshold时，HashMap扩容。
• loadFactor： 加载因子。
• modCount：是用来实现fail-fast机制。
  

影响HashMap性能的有两个参数：初始容量(initialCapacity) 和加载因子(loadFactor)。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行扩容操作（即重建内部数据结构），即将哈希表的桶数(buckets)调整为当前的2倍。

HashMap的属性

HashMap中静态属性和实例属性

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{
    // 默认的初始容量是16，必须是2的幂。
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  
    // 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 一个桶中链表的树化阈值，当桶中元素个数超过这个值时，需要使用红黑树节点替换链表节点
    static final int TREEIFY_THRESHOLD = 8;
    // 一个桶中红黑树链表化的阈值 当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原为链表结构
    static final int UNTREEIFY_THRESHOLD = 6;
    // 哈希表的最小树形化的桶的容量，当哈希表中的容量大于这个值时，表中的桶才能进行树形化，否则只会扩容，而不进行树化
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储数据的Node数组，长度是2的幂。
     transient Node[] table;
    // HashMap的大小，它是HashMap保存的键值对的数量
    transient int size;
    // HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子）
    int threshold;
    // 加载因子实际大小
    final float loadFactor;
    // HashMap被改变的次数
    transient volatile int modCount;
}

数据节点Node的数据结构

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; //key的hash值（高16和低16异或）
    final K key;
    V value;
    Node<K,V> next;  // 指向下一个节点

   Node(int hash, K key, V value, Node<K,V> 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;
    }
}

其中Node是一个单向链表，Node实现了Map.Entry 接口，并实现了getKey()，getValue()，setValue(V value)， equals(Object o)，hashCode()这些函数。这些都是基本的读取/修改key、value值的函数。
红黑树结构

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;    // 树化后的节点的父节点
    TreeNode<K,V> left;      // 树的左子节点
    TreeNode<K,V> right;     // 树的右子节点
    TreeNode<K,V> prev;      // 在由链表树化时节点的前驱节点
    boolean red;             //节点颜色
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

由于它继承自 LinkedHashMap.Entry ，而 LinkedHashMap.Entry 继承自 HashMap.Node ，所以它也拥有Node类中属性（hash、key、value、next）以及LinkedHashMap.Entry 的（before、after）属性

public class LinkedHashMap<K,V>  extends HashMap<K,V>  implements Map<K,V>{
    //内部类Entry
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
}

tableSizeFor(int)
调用tableSizeFor(int)，该方法用来返回大于等于cap的最小2^次幂值；假如你传入的是 7，返回的初始容量为 8

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

说明 在调用此方法的地方将方法返回值赋值给了threshold。是因为在构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。

HashMap的主要函数

确定哈希桶数组索引位置
不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些（避免hash碰撞），尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能。

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

以及put、get、remove方法中的计算桶的位置的代码

tab[i = (n - 1) & hash]

对于任意给定的对象，只要它的hashCode()返回值相同，那么调用方法一所计算得到的Hash码值总是相同的。在HashMap中 通过hash & (table.length -1)来得到该对象的保存位置，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，**hash **& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

put方法

代码

//添加指定的键值对到 Map 中，如果已经存在，就替换
public V put(K key, V value) {
    //先调用 hash() 方法计算key的hash值（高低位异或）
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {

　　Node<K,V>[] tab; Node<K,V> p; int n, i;
   // 步骤①：tab为空则创建
   if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
   // 步骤②：计算index，并对null做处理 
   if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
   else {
        // 步骤③：节点key存在，直接覆盖value
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
        //p 指向要插入的桶第一个元素的位置，如果 p 的哈希值、键和要添加的一样，就停止找，e 指向 p
            e = p;
        else if (p instanceof TreeNode) // 步骤④：判断该链为红黑树
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {// 步骤⑤：该链为链表
             for (int binCount = 0; ; ++binCount) {
                //如果要put的元素在链表中不存在，则将元素插到链表后面
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //链表长度大于8转换为红黑树进行处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
               // key已经存在直接覆盖value
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //如果要put的元素在链表中存在
        if (e != null) {
            V oldValue = e.value;
            //替换，返回
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
  // 步骤⑥：超过最大容量 就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

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

扩容机制

当put时，如果发现目前的bucket占用程度已经超过了Load Factor所希望的比例，那么就会发生resize。在resize的过程，简单的说就是把bucket扩充为2倍，之后重新计算index，而Java里的数组是无法自动扩容的，则使用一个新的数组代替已有的容量小的数组 然后再把旧bucket中元素放到新的bucket中 。

final Node<K,V>[] resize() {
     Node<K,V>[] oldTab = table;
     int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) { 
        if (oldCap >= MAXIMUM_CAPACITY) { //如果oldCap超过最大值，则只调整threshold，返回原来的hash表
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //新的容量为旧的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //如果旧容量小于等于 16，新的阈值就是旧阈值的两倍
            newThr = oldThr << 1; // double threshold
    }
    //如果旧容量为 0 ，并且旧阈值>0，说明之前创建了哈希表但没有添加元素，初始化容量等于阈值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //旧容量、旧阈值都是0，说明还没创建哈希表，容量为默认容量，阈值为 容量*加载因子
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //如果新的阈值为 0 ，就得用 新容量*加载因子 重计算一次
    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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //遍历:把每个bucket都移动到新的buckets中
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                //旧的桶置为空，便于GC回收
                oldTab[j] = null;
                //当前 桶只有一个元素，直接赋值给对应位置
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    //如果旧哈希表中这个位置的桶是树形结构，就要把新哈希表里当前桶也变成树形结构
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { //保留旧哈希表桶中链表的顺序
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    //do-while 循环赋值给新哈希表
                    do {
                        next = e.next;
                        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);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                   // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

get

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    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) {
            // 在树中get
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 在链表中get
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

1. bucket里的第一个节点，直接命中；
   2. 如果有冲突，则通过key.equals(k)去查找对应的entry，若为树，则在树中通过key.equals(k)查找，O(logn)；若为链表，则在链表中通过key.equals(k)查找，O(n)。

   remove

   ```java public V remove(Object key) {

    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
   

   }

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

<a name="pne9H"></a>
## **HashMap实现的Cloneable接口**
HashMap实现了Cloneable接口，即实现了clone()方法。clone()方法的作用很简单，就是克隆一个HashMap对象并返回。
```java
public Object clone() {
    HashMap<K,V> result;
    try {
        result = (HashMap<K,V>)super.clone();
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
    result.reinitialize();
    result.putMapEntries(this, false);
    return result;
 }

HashMap实现的Serializable接口

HashMap实现java.io.Serializable，分别实现了串行读取、写入功能。
串行写入函数是writeObject()，它的作用是将HashMap的“总的容量，实际容量，所有的Entry”都写入到输出流中。
而串行读取函数是readObject()，它的作用是将HashMap的“总的容量，实际容量，所有的Entry”依次读出。

private void writeObject(java.io.ObjectOutputStream s) throws IOException {
    int buckets = capacity();
    // Write out the threshold, loadfactor, and any hidden stuff
    s.defaultWriteObject();
    s.writeInt(buckets);
    s.writeInt(size);
    internalWriteEntries(s);
}

/**
 * Reconstitute the {@code HashMap} instance from a stream (i.e.,
 * deserialize it).
 */
private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException {
    // Read in the threshold (ignored), loadfactor, and any hidden stuff
    s.defaultReadObject();
    reinitialize();
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new InvalidObjectException("Illegal load factor: " + loadFactor);
    s.readInt();                // Read and ignore number of buckets
    int mappings = s.readInt(); // Read number of mappings (size)
    if (mappings < 0)
        throw new InvalidObjectException("Illegal mappings count: " + mappings);
    else if (mappings > 0) { // (if zero, use defaults)
        // Size the table using given load factor only if within
        // range of 0.25...4.0
        float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
        float fc = (float)mappings / lf + 1.0f;
        int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
                   DEFAULT_INITIAL_CAPACITY :
                   (fc >= MAXIMUM_CAPACITY) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor((int)fc));
        float ft = (float)cap * lf;
        threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
                     (int)ft : Integer.MAX_VALUE);
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
        table = tab;

        // Read the keys and values, and put the mappings in the HashMap
        for (int i = 0; i < mappings; i++) {
            @SuppressWarnings("unchecked")
                K key = (K) s.readObject();
            @SuppressWarnings("unchecked")
                V value = (V) s.readObject();
            putVal(hash(key), key, value, false, false);
        }
    }
}

通过实现readObject/writeObject两个方法自定义了序列化的内容
在HashMap中table 被变量用transient 所修饰，所以该变量不会被默认的序列化机制序列化，而自定义序列化方法的原因：
1. table 多数情况下是无法被存满的，序列化未使用的部分，浪费空间
2. 同一个键值对在不同 JVM 下，所处的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能会发生错误。
以上两个问题中，第一个问题比较好理解，第二个问题解释一下。HashMap 的get/put/remove等方法第一步就是根据 hash 找到键所在的桶位置，但如果键没有覆写 hashCode 方法，计算 hash 时最终调用 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是 native 型的，不同的 JVM 下，可能会有不同的实现，产生的 hash 可能也是不一样的。也就是说同一个键在不同平台下可能会产生不同的 hash，此时再对在同一个 table 继续操作，就会出现问题。

HashMap的线程安全

在多线程环境下，1.7 会产生死循环、数据丢失、数据覆盖的问题，1.8 中会有数据覆盖的问题。
以1.8为例，当A线程执行到下面代码第6行判断index位置为空后正好挂起，B线程开始执行第7 行，往index位置的写入节点数据，这时A线程恢复现场，执行赋值操作，就把A线程的数据给覆盖了；
还有第38行++size这个地方也会造成多线程同时扩容等问题。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  if ((p = tab[i = (n - 1) & hash]) == null)  //多线程执行到这里
    tab[i] = newNode(hash, key, value, null);
  else {
    Node<K,V> e; K k;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    else if (p instanceof TreeNode)
      e = ((TreeNode<K,V>)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;
        }
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e;
      }
    }
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  ++modCount;
  if (++size > threshold) // 多个线程走到这，可能重复resize()
    resize();
  afterNodeInsertion(evict);
  return null;
}

面试官: 那你平常怎么解决这个线程不安全的问题？
安琪拉: Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。

1. HashTable是直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大；
   
2. Collections.synchronizedMap是使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现；
   
3. ConcurrentHashMap使用分段锁，降低了锁粒度，让并发度大大提高。