一、先来熟悉一下我们常用的HashMap:

hashing(散列法或哈希法)的概念

散列法（Hashing）是一种将字符组成的字符串转换为固定长度的数值来取索引值的方法，称为散列法，也叫哈希法。由于通过更短的哈希值比用原始值进行数据库搜索更快，这种方法一般用来在数据库中建立索引并进行搜索，同时还用在各种解密算法中。

概述

1、HashMap继承AbstractMap实现Map，Cloneable，Serializable接口，
2、HashMap的底层基于哈希表(散列表)，数据结构是“链表散列”，也就是数组+链表 ：通过对元素hash算法计算出元素的索引存放位置，遇到多个元素的hash值相同就产生了hash冲突，也叫做哈希碰撞，HashMap即是采用了链地址法，也就是数组+链表的方式将多个元素的地址关联起来，JDK7对链表头部插入方法，JDK8对链表尾部插入方法。
3、允许使用null 建和null值，因为key不允许重复，因此只能有一个键为null,当键为null时会存到数组的第一个位置。
4、HashMap插入是无序的，线程不安全，效率高；

• HashMap 的优化
  HashMap 在java7和java8上有所区别，当然java8的效率要更好一些，主要是java8的HashMap在java7的基础上增加了红黑树这种数据结构，降低在桶里面查找数据的复杂度，当然还有一些其他的优化，比如resize的优化等。

哈希表

数组：一段连续控件存储数据，指定下标的查找，时间复杂度O(1),通过给定值查找，需要遍历数组，自已对比复杂度为O（n） 二分查找插值查找，复杂度为O(logn)
线性链表：增 删除仅处理结点，时间复杂度O(1)查找需要遍历也就是O(n)
二叉树：对一颗相对平衡的有序二叉树，对其进行插入，查找，删除，平均复杂度O(logn)
哈希表：哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)哈希表的主干就是数组

hash冲突

如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式

链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好

继承关系

public class HashMap<K,V>extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

基本属性

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, 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)上的结点数大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8; 
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储元素的数组，总是2的幂次倍
    transient Node<k,v>[] table; 
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数，注意这个不等于数组的长度。
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;   
    // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
    int threshold;
    // 加载因子
    final float loadFactor;
} 

loadFactor加载因子

• loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor越小，也就是趋近于0，数组中存放的数据(entry)也就越少，也就越稀疏。
• loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。
• 给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

threshold

• threshold = capacity * loadFactor，当Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。
• HashMap的初始桶的数量为16，loadFact为0.75,当桶里面的数据记录超过阈值的时候，HashMap将会进行扩容则操作，每次都会变为原来大小的2倍，直到设定的最大值之后就无法再resize了。

HashMap的扩容操作是一项很耗时的任务，所以如果能估算Map的容量，最好给它一个默认初始值，避免进行多次扩容。HashMap的线程是不安全的，多线程环境中推荐是ConcurrentHashMap。

HashMap数据结构

HashMap的底层就是一个数组，数组中每一项有事一个链表，当新建一个HashMap时候，就会初始化一个数组，查看源码如下，直接看重点，table = new Entry[capacity]; 创建一个Entry数组，也就是上面的table ,这个Entry结构就是static的包含key value 还有一个next的指针，指向下一个元素的引用，也就构成了链表

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

    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;

    this.loadFactor = loadFactor;
    threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    init();
}

Node节点类源码

// 继承自 Map.Entry<K,V>
static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;// 哈希值，存放元素到hashmap中时用来与其他元素hash值比较
       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; }
        // 重写hashCode()方法
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        // 重写 equals() 方法
        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<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // 父
        TreeNode<K,V> left;    // 左
        TreeNode<K,V> right;   // 右
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;           // 判断颜色
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
        // 返回根节点
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
       }

构造方法

// 默认构造函数。
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all   other fields defaulted
     }
     
     // //指定初始容量的构造方法
     public HashMap(int initialCapacity) {
         this(initialCapacity, DEFAULT_LOAD_FACTOR);
     }
     
     // //指定初始容量和负载因子
     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);
     }

     // 指定集合，转化为HashMap
     public HashMap(Map<? extends K, ? extends V> m) {
         this.loadFactor = DEFAULT_LOAD_FACTOR;
         putMapEntries(m, false);
        //下面会分析到这个方法
     }

HashMap提供了四个构造方法，构造方法中 ，依靠第三个方法来执行的，但是前三个方法都没有进行数组的初始化操作，即使调用了构造方法此时存放HaspMap中数组元素的table表长度依旧为0 。在第四个构造方法中调用了inflateTable()方法完成了table的初始化操作，并将m中的元素添加到HashMap中。

• putMapEntries方法：

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 判断table是否已经初始化
        if (table == null) { // pre-size
            // 未初始化，s为m的实际元素个数
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                    (int)ft : MAXIMUM_CAPACITY);
            // 计算得到的t大于阈值，则初始化阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 已初始化，并且m元素个数大于阈值，进行扩容处理
        else if (s > threshold)
            resize();
        // 将m中的所有元素添加至HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

主要方法

HashMap的put方法流程

下图展示了java8中put方法的处理逻辑，比java7多了红黑树部分，以及在一些细节上的优化，put逻辑和java7中是一致的。

image.png

HashMap只提供了put用于添加元素，putVal方法只是给put方法调用的一个方法，并没有提供给用户使用。

• 对putVal方法添加元素的分析如下：
  ①如果定位到的数组位置没有元素 就直接插入。
  ②如果定位到的数组位置有元素就和要插入的key比较，如果key相同就直接覆盖，如果key不相同，就判断p是否是一个树节点，如果是就调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)。

JDK1.8 put方法的代码

public V put(K key, V value) {
    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;
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素
    else {
        Node<K,V> e; K k;
        // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 将第一个元素赋值给e，用e来记录
                e = p;
        // hash值不相等，即key不相等；为红黑树结点
        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;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) { 
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
} 

JDK1.7 put方法的代码

对于put方法的分析如下：
①如果定位到的数组位置没有元素 就直接插入。
②如果定位到的数组位置有元素，遍历以这个元素为头结点的链表，依次和插入的key比较，如果key相同就直接覆盖，不同就采用头插法插入元素。

 //先看put方法
    public V put(K key, V value) {
    //table为空，就先初始化
        if (table == EMPTY_TABLE) {
        //这个方法上面已经分析过了，主要是在初始化HashMap,包括创建HashMap保存的元素的数组等操作
            inflateTable(threshold);
        }
    
    //key 为null的情况， 只允许有一个为null的key
        if (key == null)
            return putForNullKey(value);
    //计算hash
        int hash = hash(key);
    //根据指定hash，找出在table中的位置
        int i = indexFor(hash, table.length);
    //table中，同一个位置（也就是同一个hash）可能出现多个元素（链表实现），故此处需要循环
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
         //如果key已经存在，那么直接设置新值
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
    //key 不存在，就在table指定位置之处新增Entry
        addEntry(hash, key, value, i);
        return null;
    }

在该方法中，添加键值对时，首先进行table是否初始化的判断，如果没有进行初始化（分配空间，Entry[]数组的长度）。然后进行key是否为null的判断，如果key==null ,放置在Entry[]的0号位置。计算在Entry[]数组的存储位置，判断该位置上是否已有元素，如果已经有元素存在，则遍历该Entry[]数组位置上的单链表。判断key是否存在，如果key已经存在，则用新的value值，替换点旧的value值，并将旧的value值返回。如果key不存在于HashMap中，程序继续向下执行。将key-vlaue, 生成Entry实体，添加到HashMap中的Entry[]数组中。

putForNullKey() :当key为null 的处理情况

 //当key为null 的处理情况
    private V putForNullKey(V value) {
    //先看有没有key为null, 有就直接设置新值
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;、
    //当前没有为null的key就新创建一个entry,其在table的位置为0（也就是第一个）
        addEntry(0, null, value, 0);
        return null;
    }

addEntry():在table指定位置新增Entry

 /*
*在table指定位置新增Entry, 这个方法很重要    
*/
    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
        //table容量不够, 该扩容了（两倍table），重点来了，下面将会详细分析
            resize(2 * table.length);
             //扩容操作，将数据元素重新计算位置后放入newTable中，链表的顺序与之前的顺序相反

        //计算hash, null为0
            hash = (null != key) ? hash(key) : 0;
        //找出指定hash在table中的位置
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }
    }


    /**
     * 在链表中添加一个新的Entry对象在链表的表头
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

添加到方法的具体操作，在添加之前先进行容量的判断，如果当前容量达到了阈值，并且需要存储到Entry[]数组中，先进性扩容操作，空充的容量为table长度的2倍。重新计算hash值，和数组存储的位置，扩容后的链表顺序与扩容前的链表顺序相反。然后将新添加的Entry实体存放到当前Entry[]位置链表的头部。在1.8之前，新插入的元素都是放在了链表的头部位置，但是这种操作在高并发的环境下容易导致死锁，所以1.8之后，新插入的元素都放在了链表的尾部。

HashMap在扩容的时候，会重新计算hash值，并对hash的位置进行重新排列， 因此，为了效率，尽量给HashMap指定合适的容量，避免多次扩容

什么时候扩容：

当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值(知道这个阈字怎么念吗？不念fa值，念yu值四声)---即当前数组的长度乘以加载因子的值的时候，就要自动扩容啦。

扩容(resize)介绍：

当HashMapde的长度超出了加载因子与当前容量的乘积（默认16*0.75=12）时，通过调用resize方法重新创建一个原来HashMap大小的两倍的newTable数组，最大扩容到2^30+1，并transfer()方法，重新计算hash值，然后再重新根据hash分配位置，将原先table的元素全部移到newTable里面。

分析下resize的源码

鉴于JDK1.8融入了红黑树，较复杂，为了便于理解我们仍然使用JDK1.7的代码，好理解一些，本质上区别不大，具体区别后文再说。

//扩容之后，重新计算hash，然后再重新根据hash分配位置，
//由此可见，为了保证效率，如果能指定合适的HashMap的容量，会更合适
void resize(int newCapacity) {   //传入新的容量
        Entry[] oldTable = table;    //引用扩容前的Entry数组
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了，那么就将临界值threshold设置为最大的int值
            threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
            return;
        }
 
        Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
        transfer(newTable);                         //！！，重新计算hash，然后再重新根据hash分配位置，将原先table的元素全部移到newTable里面
        table = newTable;                           //再将newTable赋值给table
        threshold = (int) (newCapacity * loadFactor);
// 重新计算临界值，扩容公式在这儿（newCapacity * loadFactor）

这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

void transfer(Entry[] newTable) {
        Entry[] src = table;                   //src引用了旧的Entry数组
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
            Entry<K, V> e = src[j];             //取得旧Entry数组的每个元素
            if (e != null) {
                src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
                do {
                    Entry<K, V> next = e.next;
                    int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                    e.next = newTable[i]; //标记[1]
                    newTable[i] = e;      //将元素放在数组上
                    e = next;             //访问下一个Entry链上的元素
                } while (e != null);
            }
        }
}

详细介绍for循环内部这个转存的过程和怎么进行头插入

Entry<K, V> e = src[j];
这句话，就把原来数组上的那个链表的引用就给接手了，所以下面src[j] = null;可以放心大胆的置空，释放空间。告诉gc这个地方可以回收啦。
继续到do while 循环里面，
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity);计算出元素在新数组中的位置
下面就是单链表的头插入方式转存元素啦

扩容问题：

数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这个操作是极其消耗性能的。所以如果我们已经预知HashMap中元素的个数，那么预设初始容量能够有效的提高HashMap的性能。

重新调整HashMap大小，当多线程的情况下可能产生条件竞争。因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。

newTable[i]的引用赋给了e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话），这一点和Jdk1.8有区别，下文详解。在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。

死链过程分析

首先假设在扩容时，hash表中有一个单链表，单链表中有两个元素：元素1和元素2

如果该HashMap为单线程操作时

执行过程：
首先 e = 元素1
执行到 next = e.next 的时候 next =元素2
从 1 到 3 的过程会将 元素1 按照头插法插入到newtable[i]所引用的单链表中
然后 e = next 会将 next 赋值给 e，所以就有 e = 元素2
判断后 e != null，继续循环，然后以同样方式插入元素2
因为 元素2 的 next 为 null 所以最后 e = null
这时候循环就结束了，原链表的顺序由 元素1—>元素2 变成了 元素2—>元素1（结果如图所示）。

image.png

如果该HashMap为多线程操作时（假设有T1、T2两个线程）

执行过程：
T1执行到 next = e.next；时挂起
T2开始执行并且执行完了整个流程，也就是说T2把所有元素都插入了新数组之后，原来
的table引用现在指向了 newtable，即 table = newtable；
这时T1回归继续执行，这时就会有如下场景

image.png

当元素1正常插入后 next 是 元素2，e = next = 元素2，继续执行插入
此时，由于原表中 元素2 的 next 已经被T2所修改，不再是T1挂起时的 next = null了，所以T1就会碰到如下情况，因为 next 永远都不为空，所以就会一直循环执行插入操作，造成死循环。（图中这种状态的链表称为死链）

image.png

避免死循环

第一种方式：使用HashTable

HashTable和HashMap一样都实现了Map接口，但是HashTable是一个线程安全的类，所以不会出现死循环问题。

第二种方式：使用Collections.synchronizeMap(hashMap)

该方法是Collections类中的静态方法，返回的是一个线程安全的HashMap

第三种方式：使用concurrentHashMap

concurrentHashMap也是一个线程安全类，他比HashTable更为高效。在HashTable中，使用的是同一个锁，所以当一个线程操作某一个功能时，其他线程想要操作另外的功能就要等待锁被让出来。而concurrentHashMap采用了【锁分段】技术，不同的地方使用了不同的锁，功能之间的锁不一样，操作不同功能时就不再需要等待，这样就大大提高了执行效率。

关于什么时候resize（）的说明：

• JDK1.7的是：
  if ((size >= threshold) && (null != table[bucketIndex])) {。。。}
  其中
  size表示当前hashmap里面已经包含的元素的个数。
  threshold：threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  一般是容量值X加载因子。
• JDK1.8的是：
  if (++size > threshold){}
  其中
  size：The number of key-value mappings contained in this map.和上面的是一样的
  threshold：newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

remove移除方法

 //上面看了put方法，接下来就看看remove
    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

    //这就是remove的核心方法
    final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
    //老规矩，先计算hash,然后通过hash寻找在table中的位置
        int hash = (key == null) ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
    
    //这儿又神奇地回到了怎么删除链表的问题（上次介绍linkedList的时候，介绍过）
    //李四左手牵着张三，右手牵着王五，要删除李四，那么直接让张三牵着王五的手就OK
        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

get方法

如果两个不同的key的hashcode相同，两个值对象储存在同一个bucket位置，要获取value，我们调用get()方法，HashMap会使用key的hashcode找到bucket位置，因为HashMap在链表中存储的是Entry键值对，所以找到bucket位置之后，会调用key的equals()方法，按顺序遍历链表的每个 Entry，直到找到想获取的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那HashMap必须循环到最后才能找到该元素。
get()方法源码如下：

public V get(Object key) {
        // 若key为null，遍历table[0]处的链表（实际上要么没有元素，要么只有一个Entry对象），取出key为null的value
        if (key == null)
            return getForNullKey();
        // 若key不为null，用key获取Entry对象
        Entry<K,V> entry = getEntry(key);
        // 若链表中找到的Entry不为null，返回该Entry中的value
        return null == entry ? null : entry.getValue();
    }

    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
        // 计算key的hash值
        int hash = (key == null) ? 0 : hash(key);
        // 计算key在数组中对应位置，遍历该位置的链表
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            // 若key完全相同，返回链表中对应的Entry对象
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        // 链表中没找到对应的key，返回null
        return null;
    }

二、HashMap的数据存储结构

1、HashMap由数组和链表来实现对数据的存储

HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，以此来解决Hash冲突的问题。

数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；

链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易。

image.png

从上图我们可以发现数据结构由数组+链表组成，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key.hashCode())%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。
HashMap里面实现一个静态内部类Entry，其重要的属性有 hash，key，value，next。

HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。打个比方， 第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止，HashMap的大致实现，我们应该已经清楚了。

根据key的hashCode来决定应该将该记录放在哪个桶里面，无论是插入、查找还是删除，这都是第一步，计算桶的位置。因为HashMap的length总是2的n次幂，所以可以使用下面的方法来做模运算：h&(length-1)
h是key的hashCode值，计算好hashCode之后，使用上面的方法来对桶的数量取模，将这个数据记录落到某一个桶里面。当然取模是java7中的做法，java8进行了优化，做得更加巧妙，因为我们的length总是2的n次幂，所以在一次resize之后，当前位置的记录要么保持当前位置不变，要么就向前移动length就可以了。所以java8中的HashMap的resize不需要重新计算hashCode。

为什么HashMap线程不安全

HashMap会进行resize操作，在resize操作的时候会造成线程不安全。下面将举两个可能出现线程不安全的地方。
1、put的时候导致的多线程数据不一致。
这个问题比较好想象，比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。

2、另外一个比较明显的线程不安全的问题是HashMap的get操作可能因为resize而引起死循环（cpu100%），具体分析如下：
下面的代码是resize的核心内容：

void transfer(Entry[] newTable, boolean rehash) {  
        int newCapacity = newTable.length;  
        for (Entry<K,V> e : table) {  
  
            while(null != e) {  
                Entry<K,V> next = e.next;           
                if (rehash) {  
                    e.hash = null == e.key ? 0 : hash(e.key);  
                }  
                int i = indexFor(e.hash, newCapacity);   
                e.next = newTable[i];  
                newTable[i] = e;  
                e = next;  
            } 
        }  
    }  

这个方法的功能是将原来的记录重新计算在新桶的位置，然后迁移过去。

image.png

我们假设有两个线程同时需要执行resize操作，我们原来的桶数量为2，记录数为3，需要resize桶到4，原来的记录分别为：[3,A],[7,B],[5,C]，在原来的map里面，我们发现这三个entry都落到了第二个桶里面。
假设线程thread1执行到了transfer方法的Entry next = e.next这一句，然后时间片用完了，此时的e = [3,A], next = [7,B]。线程thread2被调度执行并且顺利完成了resize操作，需要注意的是，此时的[7,B]的next为[3,A]。此时线程thread1重新被调度运行，此时的thread1持有的引用是已经被thread2 resize之后的结果。线程thread1首先将[3,A]迁移到新的数组上，然后再处理[7,B]，而[7,B]被链接到了[3,A]的后面，处理完[7,B]之后，就需要处理[7,B]的next了啊，而通过thread2的resize之后，[7,B]的next变为了[3,A]，此时，[3,A]和[7,B]形成了环形链表，在get的时候，如果get的key的桶索引和[3,A]和[7,B]一样，那么就会陷入死循环。

如果在取链表的时候从头开始取（现在是从尾部开始取）的话，则可以保证节点之间的顺序，那样就不存在这样的问题了。

最后总结一下：

就是这个map里面包含的元素，也就是size的值，大于等于这个阈值的时候，才会resize（）；
具体到实际情况就是：假设现在阈值是4；在添加下一个假设是第5个元素的时候，这个时候的size还是原来的，还没加1，size=4，那么阈值也是4的时候，
当执行put方法，添加第5个的时候，这个时候，4 >= 4。元素个数等于阈值。就要resize（）啦。添加第4的时候，还是3 >= 4不成立，不需要resize（）。
经过这番解释，可以发现下面的这个例子，不应该是在添加第二个的时候resize（），而是在添加第三个的时候，才resize（）的。
这个也是我后来再细看的时候，发现的。当然，这个咱可以先忽略，重点看如何resize（），以及如何将旧数据移动到新数组的

image.png

下面我们讲解下JDK1.8做了哪些优化。经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，

经过rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。对应的就是下方的resize的注释。

/** 
 * Initializes or doubles table size.  If null, allocates in 
 * accord with initial capacity target held in field threshold. 
 * Otherwise, because we are using power-of-two expansion, the 
 * elements from each bin must either stay at same index, or move 
 * with a power of two offset in the new table. 
 * 
 * @return the table 
 */  
final Node<K,V>[] resize() {  }

看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希值(也就是根据key1算出来的hashcode值)与高位与运算的结果。

image.png

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

image.png

JDK8的HashMap实现。

还需要能理解红黑树这种数据结构

image.png

上面的图片展示了我们的描述，其中有一个非常重要的数据结构Node<K,V>，这就是实际保存我们的key-value对的数据结构，下面是这个数据结构的主要内容：

final int hash;    
        final K key;
        V value;
        Node<K,V> next;

一个Node就是一个链表节点，也就是我们插入的一条记录，明白了HashMap使用链地址方法来解决哈希冲突之后，我们就不难理解上面的数据结构，hash字段用来定位桶的索引位置，key和value就是我们的数据内容，需要注意的是，我们的key是final的，也就是不允许更改，这也好理解，因为HashMap使用key的hashCode来寻找桶的索引位置，一旦key被改变了，那么key的hashCode很可能就会改变了，所以随意改变key会使得我们丢失记录（无法找到记录）。next字段指向链表的下一个节点。

小结
(1) 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
(2) 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
(3) HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。
(4) JDK1.8引入红黑树大程度优化了HashMap的性能。
(5) 还没升级JDK1.8的，现在开始升级吧。HashMap的性能提升仅仅是JDK1.8的冰山