什么是HashMap，文章内HashMap源码主要来自Android 7.0

HashMap是开发中常用的一个类，那么他究竟是什么呢？

HashMap是一个存储key-value的集合，底层实现的是数组，所以可以看作HashMap是对数组的一种封装。

构造方法

HashMap构造函数.png

不管调用的是哪一个方法，最终都会回调两个参数的这个构造函数，第一个参数是容量，第二个参数是阈值（用于扩容的时候计算容量）

先看看HashMap主要的成员变量

  /**
     * HashMap默认容量
     */
    static final int DEFAULT_INITIAL_CAPACITY = 4;

    /**
     * HashMap最大可存储的容量值  1<<30
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 加载因子（阈值）如果put进来的元素数量>=总数量*0.75的时候， 就会进行扩容了
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * EMPTY_TABLE 看了一下，好像没啥用。。。
     */
    static final HashMapEntry<?,?>[] EMPTY_TABLE = {};
    transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;

    /**
     * 这个size表示容量值，put了几次，这个size就是几，所以我们方法中用的size() 就是返回的这个值
     */
    transient int size;

因为HashMap常用的就是get和put，所以主要分析一下这两个方法，在讲这个之前，先看一下HashMapEntry这个类吧

HashMapEntry

HashMapEntry继承自Map.Entry

static class HashMapEntry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        HashMapEntry<K,V> next;
        int hash;
        ...
}

HashMapEntry的结构是链表(在api25之前是链表,在api26开始引入了红黑树, 当节点>8个的时候会转为红黑树, 节点<6个的时候又会转回为链表, 红黑树跳这里HashMap在Api26后的应用---红黑树篇)，所以存储数据的时候是这样的

存储结构.png

关于链表可参考其他文章

现在来讲一讲HashMap的put和get

put

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
        int i = indexFor(hash, table.length);
        for (HashMapEntry<K,V> 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;
    }

整个put的方法并不长，首次进来时会判断table是不是EMPTY_TABLE，就是上面那两数组，然后会执行inflatetable方法，这个方法就不看了。。。只有第一次put时候才会进入，因为只有那个时候table==EMPTY_TABLE，在inflatetable里，table就会被重新赋值
接下来看第二个判断 key==null
看看这个方法putForNullKey()

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

如果已经有了一个 key为null的元素，那么就会替换他的value值，所以HashMap只能由一个空key。
sun.misc.Hashing.singleWordWangJenkinsHash(key);这个方法就是根据key计算hash值，然后通过indexFor方法算出key在table中的下标。由于数组的存储方式大概是这样的

image.png

但是由于下标是根据key的hash和数组长度计算来的，所以有可能下标会一样，这个时候HashMapEntry这个链表的用处就体现出来了，如果下标一样的时候，那么就会比对HashMapEntry的key值是否一致，如果一致，就替换原key-value，如果没有与新添加的key一致的值，就会在HashMapEntry中新加一个节点，所以现在的存储方式变成了这样

hashmap存储方式.png

如果是替换就value，会直接吧旧的value返回回去，如果不是的话就会走addEntry方法，这个方法有三个作用

扩容
拷贝数据
插入新数据
跟进一下addEntry方法

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

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

首先判断的是size是否大于阈值（总容量*0.75），并且table[bucketIndex]！=null, 所以只有两个条件成立的时候才会进行扩容

resize（）

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

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

newCapacity的大小等于就数组长度*2，所以下方构建的newTable的长度就是原数组的长度两倍，到这里，就进行扩容完毕了，但是新数组是有了，但是没数据啊！不急，看transfer方法

transfer（）

void transfer(HashMapEntry[] newTable) {
        int newCapacity = newTable.length;
        for (HashMapEntry<K,V> e : table) {
            while(null != e) {
                HashMapEntry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

看到了吧，或进行一个双层循环，先循环数组，然后在循环里面节点，直到next==null的时候，会跳出当前循环，进行下一次循环，直到循环完毕，也就是新数据赋值完毕
再回到resize方法，再看下面的代码，把新数组newTable又给了table，threshold又得到了扩容后新的阈值，到这一步，扩容和拷贝数据就已经完成了。
再回看addEntry方法，又会更具新数组的大小和key的hash值重新计算下标，传递给createEntry（hash, key, value, bucketIndex）方法中，

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

到此，hashmap的put就结束了，回头看看。。。其实还算蛮简单的哈

毛骨悚然.png

那么get方法呢？

get

final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
        for (HashMapEntry<K,V> 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;
    }

get方法最终会调用这个getEntry方法，看看里面的方法是不是很眼熟，计算hash，比对key。

对！就是这么简单，同样也是根据hash和数组长度获取下标，然后就是这么一个循环，只要hash值一样并且key有一样的就会返回这个元素，否则就是返回null

总结一下：
put添加元素的操作为：

计算key的hash ==> 根据hash和数组长度计算对应的数组下标 ==> 如果当前下标内容为null，就直接添加，否则的话会进入一个循环，在这个循环中去寻找链表内有没有当前key值，有的话替换原value，没有的话插入到最后一个节点

put步骤.png

get获取元素

计算key的hash ==> 根据hash和数组长度计算对应的数组下标 ==> 如果当前下标元素不为null，进入循环，在这个循环中去寻找链表内有没有当前key值，有的话返回，没有的话就返回null
get就不画了啊自行体会

话说你们画图都用啥啊。。。我这大晚上的用截图工具扣扣画画好累，win10自带的画图工具感觉用不来

图解HashMap