面试必问之HashMap源码解析

面试一般都会涉及JDK中1.7及1.8的HashMap相关问题，所以专门写此博客用于分享与学习！！！

首先先来看看JDK1.7中的源码！

1.7中底层存储结构为数组+链表

首先先看下源码中的构造方法：

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


    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

 DEFAULT_INITIAL_CAPACITY： 表示默认初始化大小 默认为16

​​​​
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

DEFAULT_LOAD_FACTOR： 表示装载因子的默认值  0.75f

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

具体看看构造方法：

 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);
             //上面的if是用作筛选条件的

        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }

底层数组：

 static final Entry[] EMPTY_TABLE = {};

   
 transient Entry[] table = (Entry[]) EMPTY_TABLE;

接下来看看存储数据对应的类 ——Entry

 static class Entry implements Map.Entry {
        final K key;       
        V value;
        Entry next;   //发生哈希碰撞后用来指向下一个结点
        int hash;         //哈希值 根据哈希值计算出在数组中对应的下标

        //构造方法
        Entry(int h, K k, V v, Entry n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

这些了解后我们再看看最常用的put方法的底层

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

 threshold 为扩容阈值 

如果key的值为null

put方法里面包含的方法 inflateTable(int toSize) ：

作用：判断是否初始化长度大于MAXIMUM_CAPACITY，然后做相应处理

private void inflateTable(int toSize) {
   // roundUpToPowerOf2()这个方法实现数组的长度是2的幂次方，具体为什么要为2的幂次方，下面会揭晓
        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

点进去看看putForNullKey()方法：

private V putForNullKey(V value) {
        for (Entry 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++;
        addEntry(0, null, value, 0);
        return null;
    }

容易分析出key为null的entry放在数组第一个位置，也就是下标为0的位置 

再点进去看看addEntry()方法的源码

​
   void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

​

​
  void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

​

createEntry采用的是头插法 从上面代码不难分析出来  

addEntry()内部有个resize()方法是在满足一定条件下，会执行的扩容方法！

​
 void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

​

  里面有个核心方法：transfer()，作用是：将老数组的元素转移到新数组当中 

​
 void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry e : table) {
            while(null != e) {
                Entry 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;
            }
        }
    }

​

老数组链表元素转移过程中，要不下标相等，要不就是下标+16；

理由如下：

32:      0010 0000

h:        0100 0101

31:      0001 1111

&运算后 结果不变，那要是 h本身是： 0101 0101 那与0001 1111进行&运算后就会＋16

类似下面的图这样！！！

下面来分析下这段代码：

 for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

来个例子：

 HashMap map = new HashMap<>();
       map.put("1","2");
        String put = map.put("1", "3");

 这个put会输出“2”；原因就是上面那个代码段啦！！！

private V putForNullKey(V value) {
        for (Entry 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++;
        addEntry(0, null, value, 0);
        return null;
    }

根据key计算哈希值  （如此多的位运算和^运算是为了让高位也参与运算 ，提高散列性）

 final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();
    
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

返回下标值

  static int indexFor(int h, int length) {
        return h & (length-1);
    }

为什么会返回0-15之间的数呢？

举个例子：

16:      0001 0000

h:        0101 0101

15:      0000 1111

对两者进行&运算一定是小于15的！！！（因为高四位都是0）

趁热打铁，再抛出一个问题为什么数组长度一定是2的n次幂？

假设数组长度为17，

对应的二进制数：     0001 0001

h对应的二进制数      0001 0101

16对应的二进制数：0001 0000

&运算符后： 只能返回0或者16，中间的下标就用不到了。

 还有一个问题？为什么用&不用^呢？ 原因：效率高

下面来看看get()方法

 public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

方法内部的两个核心方法：

getForNullKey()：

  private V getForNullKey() {
        if (size == 0) {
            return null;
        }
        for (Entry e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

getEntry(Object key)：

  final Entry getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

好了，1.7中的hashmap我们就先分析到这里！！！接下来去探究探究1.8中的hashmap中的方法吧！！！

1.8中底层是数组＋链表+红黑树实现的

为什么要使用红黑树？

原因是：当某个下标对应的链表太长，会影响get()方法的效率，因此需要使用红黑树将其查找效率提高！！！

 构造方法：

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

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

可以看到构造方法并没有什么大的改动

jdk1.8多加了两个全局常量： 

 static final int TREEIFY_THRESHOLD = 8;    树化阈值


  static final int UNTREEIFY_THRESHOLD = 6;  链化阈值  当一颗红黑树只有6个结点

为什么是8呢？因为当链表的长度达到8后，查询效率就变得很低了！！！因此需要树化，这个8也是个经验值！！

为什么是6呢？而不是7,8呢？

防止频繁的插入和删除，防止转化效率过低！！！

友情提示：树化条件满足是指，链表长度到达8并且数组长度大于等于64。具体源码如下（这里只截取一部分源码）

 treeifyBin(Node[] tab, int hash)方法里面：

final void treeifyBin(Node[] tab, int hash) {
        int n, index; Node e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)  
     //数组长度不足64，就扩容   MIN_TREEIFY_CAPACITY=64
            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);
        }
    }     

put()方法

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

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

 1.8中的hash(Object key)简化了一点，因为红黑树也能提高数组的散列性！！！

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node 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 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)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();
        afterNodeInsertion(evict);
        return null;
    }

  for (int binCount = 0; ; ++binCount) {     //遍历链表
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // //判断是否要树化
                            treeifyBin(tab, hash);    //树化
                        break;
                    }

从上面这段代码可以看出 因为加了红黑树，所以要去数链表长度，所以要遍历链表，那既然都遍历了，就顺便把新节点插入到链表末尾，也就是说1.8中的put()方法采用的是尾插法！！！！ 上面的方法很多逻辑在1.7中都是有的。

final Node[] resize() {
        Node[] 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[] newTab = (Node[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        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);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }