1. HashMap

HashMap在代码编写和面试过程中都经常用到，所以有必要总结一下其源码

1.1属性

1. 默认初始容量大小，一定为2的幂次

   //The default initial capacity - MUST be a power of two.
   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

2. 默认最大容量

   static final int MAXIMUM_CAPACITY = 1 << 30;

3. 默认加载因子大小

   //The load factor used when none specified in constructor.
   static final float DEFAULT_LOAD_FACTOR = 0.75f;

   为什么默认加载因子是0.75呢？

首先我们分析：

• 加载因子越大，填满的元素越多，空间利用率越高，但冲突概率变大了；
• 加载因子越小，填满的元素越少，冲突概率减小，但空间浪费了更多了，而且还会提高扩容rehash操作的次数。

因此，必须在“冲突概率”与“空间利用率”之间，寻找一种平衡与折衷。

4. 默认红黑树的阈值

   static final int TREEIFY_THRESHOLD = 8;

5. 默认非树形阈值

   static final int UNTREEIFY_THRESHOLD = 6;

6. 默认转红黑树时当前最小容量

   static final int MIN_TREEIFY_CAPACITY = 64;

7. hashmap中的结点

   static class Node<K,V> implements Map.Entry<K,V>{...}

8. hashmap的键值对Node数组

   transient Node<K,V>[] table;

9. 键值对的集合！

   transient Set<Map.Entry<K,V>> entrySet;

10. 当前hashmap中键值对的数量

    transient int size;

11. hashmap被修改的次数！

    transient int modCount;

    注意这个值当且仅当当前的hashmap结构发生改变的时候会加一，这些结构改变主要包括：添加或删除元素，rehash（扩容）等，主要用在迭代器使用过程中的 fail_fast机制！
    举个例子，以下代码中获取了hashmap的key集合的迭代器，并在迭代过程中通过hashmap本身删除了一个key为2的键值对，这样就会导致迭代器在迭代过程中 出现 预期modcount 不等于现在的modcount！最终 throw new ConcurrentModificationException()！注意这种情况不论在单线程多线程都会发生，即在使用迭代器的时候一定要通过迭代器本身进行修改！该同步同步！

    public static void main(String[] args){
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(1,1);
        hashMap.put(2,2);
        hashMap.put(3,3);
        hashMap.put(4,4);
        Iterator<Integer> iterator = hashMap.keySet().iterator();
        while(iterator.hasNext()){
            Integer key= iterator.next();
            if(key== 2){
                hashMap.remove(key);
            }
        }
    }

12. 下一次扩容的大小

    int threshold;// = capacity * load factor

13. 加载因子大小

    final float loadFactor;

1.2 核心方法

1. 构造函数
   通过观察以下的构造函数我们可以发现，前面三种都只是在初始化容量和加载因子，并没有真正去开辟一个node数组！即使用时创建！

   • 构造函数一，两者都指定

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

   • 构造函数二，单独指定初始值，则加载因子使用默认加载因子

     public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
     }

   • 构造函数三，空构造器

     public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
     }

   • 构造函数四，使用map作为参数

     public HashMap(Map<? extends K, ? extends V> m) {
       this.loadFactor = DEFAULT_LOAD_FACTOR;
       putMapEntries(m, false);
     }

2. 计算key的hash值——扰动函数！

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

   这个方法主要是用来和数组的长度取余找到存放的下标的！毕竟如果要存放全部的整数的话内存是放不下将近40亿的空间的。而寻找这个下标的方法就是 hash & (length -1)，这也印证数组的容量为什么是2的幂次（使用位运算能加快运算速度！）这样的结果就是截取了当前key的hash的低位！！！高位全部为零。
   但这也同样带了问题，如果插入的某些key在低位上具有某种规律性，这样会导致当前的hash冲突十分严重！所以，下面的这个hash方法采用低16位与高16位进行异或运算，混合原始哈希码的高位和低位，以此加大低位随机性，而混合后的低位掺杂了高位的信息，即高位的信息也被变相的保留下来！之后在与长度进行位运算，冲突概率就会降低！下面展示了hash方法的执行过程！

3. 将指定容量扩充至2的幂次
   通过不断地或运算将指定容量扩充至2的幂次

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

4. 核心方法——put方法

   public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
        //onlyIfAbsent默认为false，即覆盖已存在的key的value
    }

   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) 
        //首先进行node数组的判断，如果为空或者长度为0则通过resize方法创建，印证了上面构造函数中使用才创建!
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
        //如果要添加的对应下标为空，ok，则说明没有冲突，可以添加
            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))))
                //在这判断两者的key是否是等价的！！！
                //注意这里就是为什么自己创建的对象需要重写hashcode和equals方法！！！
                //如果两者不重写，会导致hashmap将等价对象判定为不同对象！！！！或者说插入重复对象！
                e = p;//两个对象等价！！！
            else if (p instanceof TreeNode)
            //两者不等价，需要在此节点往后插，先判断当前节点是否是树结点！是的话采用树结点的插入方式
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
            //不是树结点，ok ，在这个链表上不断寻找与待插入结点等价的结点
                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); //如果说链表结点达到了8，需要转红黑树！
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        //找到这个链表中与待插入结点等价的结点！！直接break
                        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;//添加之后导致map数量增加，即修改次数加一！
        if (++size > threshold)//如果添加后的容量等于扩容容量，即需要扩容！
            resize();
        afterNodeInsertion(evict);
        return null; 
    }

5. resize方法
   注意jdk1.8之前采用的是头插法，容易造成链表死循环！之后改成尾插法，解除隐患！

   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) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && //两倍扩容！！！
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        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;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        /--------------------/
        //以上到这，是在进行使用时初始化的过程！
        table = newTab;
        //从这开始，才是真正的resize！！！即扩容！
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) { //迭代遍历旧的数组！
                Node<K,V> e;
                if ((e = oldTab[j]) != null) { //如果当前下标有结点
                    oldTab[j] = null; //先将原始的数组对应位置置空
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e; //即当前下标只有一个结点,直接rehash过去就好了
                    else if (e instanceof TreeNode) //如果说是树结点，执行对应方法
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order //说明此时是长度至少为2的链表
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do { //这个dowhile在做旧结点往新节点的移动！并且采用尾插法
                            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);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead; //旧结点hash小于oldcap的不需要移动！
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead; //大于hash的直接放到当前下标 + oldcap位置即可!
                        }
                    }
                }
            }
        }
        return newTab;
    }

3.为什么采用头插法容易造成链表死循环呢？

先看下旧版本的扩容方法

void transfer(Entry[] newTable){　　//复制一个原数组src，Entry是一个静态内部类，有K，V，next三个成员变量
    Entry[] src = table;　　//数组新容量
    int newCapacity = newTable.length;：
    //  从OldTable里摘一个元素出来，然后放到NewTable中
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];//取出原数组一个元素
        if (e != null) {//判断原数组该位置有元素
            src[j] = null;//原数组位置置为空
            do {//对原数组某一位置下的一串元素进行操作
                Entry<K,V> next = e.next;//next是当前元素下一个
                int i = indexFor(e.hash, newCapacity);//i是元素在新数组的位置
                e.next = newTable[i];//此处体现了头插法，当前元素的下一个是新数组的头元素
                newTable[i] = e;//将原数组元素加入新数组
                e = next;//遍历到原数组某一位置下的一串元素的下一个　　　　　　
            } while (e != null); 　　　　
        } 　            
    }
}

接下来图示单线程情况下，do循环内的情况：

　　初始：当前数组容量为2，有三个元素3、7、5，此处的hash算法是简化处理（对容量取模）。因此，3、7、5都在数组索引1对应的链表上。

　　扩容新容量为2*2=4。

　　第一步：当前Entry e对应3，next对应7，新位置i为3，然后将3插入新数组对应位置。

　　第二步：当前Entry e对应7，next对应5，新位置i为3，然后将新数组对应索引处的元素3添加到7的尾巴后（头插），然后将7插入新数组对应位置。

　　第三步：当前Entry e对应5，next对应null，新位置i为1, 然后将5插入新数组对应位置。

　　接下来图示多线程情况下死循环场景：初始条件相同。如果有两个线程：

• 线程一执行到 Entry<K,V> next = e.next; 便挂起了，即此时Entry e是3，next是7，3是在7前面的。

• 线程二执行完成。

　　此时如下图所示，线程一的3的next是7，而线程二的7的next是3。（此处是Entry里的next成员变量，在多个线程中相同Entry不冲突）。此时可以看出出现了死循环问题。

本作品采用《CC 协议》，转载必须注明作者和本文链接