摘要

HashMap是在日常开发中使用比较频繁的一个数据结构，随着Jdk的升级，HashMap的底层也发生了比较大的变化。对于Jdk1.8来说，HashMap基于数组加链表的基础上，又增加了红黑树来进行优化，在分析JDK1.8的HashMap前，本文先分析jdk1.7版本的HashMap。

HashMap uml类图

实现原理

HashMap采用数组来作为hash桶，采用链表来记录冲突的元素，也就是采用链地址法来解决hashCode冲突。

成员变量

//hashMp的默认容量，1<<4=2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//hashMap的最大容量 2^30 也就是比Integer.MAX_VALUE少一点
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//空的hash桶
static final Entry<?,?>[] EMPTY_TABLE = {};
//存储元素的hash桶，默认指向空的hash桶
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//记录hashMap存储元素的个数
transient int size;
//阈值，可用于标识下次扩容的阈值
int threshold;
//加载因子
final float loadFactor;
//hashMap结构变更的次数
transient int modCount;
//hash种子，可对key的hash进行扰乱，使hash值更加随机
transient int hashSeed = 0;
复制代码

由于HashMap采用数组+链表来实现哈希表，那么对于哈希表的实现，需要解决以下几个问题：

好的哈希函数如何设计
如何解决哈希冲突
哈希表的大小如何确定
什么是加载因子，如何确定加载因子

那么，我们结合问题，来逐个进行分析。

什么是加载因子，如何确定加载因子？

加载因子=阈值/哈希表长度，加载因子可以作为HashMap空间与时间的一个衡量指标，通过以上源码可知，hashMap的默认容量是16，那么根据加载因子的算法，我们分析下加载因子变化对HashMap的影响：

当加载因子越大，哈希表长度固定的情况下，说明扩容的阈值越高，HashMap的空间利用率高，但是增加了HashMap冲突的概率，从而导致链表来保存更多的冲突元素，导致时间利用率降低。
当加载因子越小，哈希表长度固定的情况下，说明扩容的阈值低，HashMap的空间利用率低，会导致频繁扩容，会对性能造成极大的影响。

HashMap之所以选用0.75，是在提高空间利用率和减少查询成本之间折中的一个方案，因此我们如果没有特殊的要求，一般都不建议自定义加载因子。

哈希表的大小如何确定？

哈希表设置的越大，会使用更多空间，若存储元素少，则会造成空间浪费。哈希表设置的越小，会使用更小的空间，则会造成大概率的hash冲突，对性能会有一定的影响。

好的哈希函数如何设计？

好的哈希函数具有两个特点：碰撞概念低、分散均匀。那么以上源码中的hashSeed主要就是用于对key的hash值进行扰乱，从而使计算出来的hash值更加随机，使得hash碰撞概率低，分散也比较均匀。

如何解决哈希冲突？

HashMap采用链地址法来解决哈希冲突，HashMap采用了Entry结构来实现链表，源码如下：

    static class Entry<K,V> implements Map.Entry<K,V> {
        //存储key
        final K key;
        //存储value
        V value;
        //指向下一个节点
        Entry<K,V> next;
        //key的hash值
        int hash;
   }
复制代码

通过以上的源码，可以看出链表是通过next来维护起来的。

功能实现

构造函数

hashMap核心的构造函数源码如下：

    /**
     * @param initialCapacity 初始容量
     * @param loadFactor 加载因子
     */
    public HashMap(int initialCapacity, float loadFactor) {
        //1. 初始容量
        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;
        threshold = initialCapacity;
        init();
    }
复制代码

构造函数处理逻辑如下：

初始容量值的边界校验，规定初始容量的值需要在【0，2^30】之间。
加载因子边界确认，规定加载因子需要大于0，并且不能是无效的数字。
设置加载因子。
将初始容量作为阈值（threshold）。

创建哈希桶

源码如下：

    /**
     * 创建哈希桶
     */
    private void inflateTable(int toSize) {
        //计算toSize最接近的2^n数，作为数组的容量
        int capacity = roundUpToPowerOf2(toSize);
        //根据容量*加载因子，计算阈值
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        //创建哈希桶
        table = new Entry[capacity];
        //初始化hashSeed
        initHashSeedAsNeeded(capacity);
    }
复制代码

以上源码保证了HashMap的容量为2的幂次方。

存放空值

源码如下：

    private V putForNullKey(V value) {
        //获取索引为0的元素，e作为首节点
        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++;
        addEntry(0, null, value, 0);
        return null;
    }
复制代码

通过以上源码，可以看出key为null的主要都是存放在索引为0的哈希桶中，然后遍历链表，若发现链表中存在key为null的值就进行替换，并且返回旧值。

当以上遍历找不到key为null的值，就会在索引为0的哈希桶进行存放。

添加元素

源码如下:

    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);
    }
复制代码

以上函数的主要功能是，创建一个新的Entry, 并添加进哈希桶中。当然，在添加元素前，需要校验下当前哈希桶存放元素的个数是否已经达到了扩容阈值，并且当前索引对应的哈希桶位置存放这元素，那么就会触发扩容、rehash处理（下面会针对扩容进行分析）。

创建Entry实际还是调用了createEntry方法，这个方法比较简单，源码如下：

    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中。

扩容处理

源码如下：

    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);
    }
    
    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;
            }
        }
    }
复制代码

通过addEntry方法中，我们可以看到这一行代码：

resize(2 * table.length);
复制代码

这一行代码，通过对哈希桶当前数量乘以2，再调用resize方法。

那么resize方法处理原理也是比较简单的，流程如下：

使用oldTable变量来缓存扩容前的哈希桶。
校验当前哈希桶容量是否已经超过了2^30, 如果超过了，那么阈值设置为Integer的最大值，最后返回。如果没有超过，则进行下一步。
根据新容量创建一个新的哈希桶，此时哈希桶中没有任何数据。
调用transfer方法来讲扩容前的哈希桶迁移到新的哈希桶中。
重新计算下次扩容的阈值。

关于第二步的校验，会直接返回，主要原因是容量已经达到最大值了，不允许再进行扩容了，因此干脆把阈值也设置为最大值，以保证下次减少触发扩容的操作。

transfer方法主要是用于元素的迁移，流程如下：

遍历扩容前的哈希桶，获取当前遍历节点。
遍历当前节点的冲突链，根据当前遍历节点e的hash以及新的哈希桶容量，来计算当前遍历节点在新的哈希桶上对应的索引。
将当前遍历节点存放到新的哈希桶中。

以上transfer中调用了indexFor方法来获取节点在哈希桶中对应的索引，源码如下：

    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }
复制代码

以上源码，采用的取余法来计算索引，也就是h % length, 但由于%运算性能低，因此使用与运算来进行优化，也就是h & length = h & (length – 1), 此算法成立的前提是，length=2^n。

计算hash

源码如下:

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

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
复制代码

hash函数的处理流程如下：

获取hashSeed, 已进行hash扰乱处理。
当hashSeed不为0，并且key的类型是String，就采用sun下stringHash32方法来获取字符串的hash值。
当key是其他类型时，先采用hashSeed来与key的hashCode进行异或处理，最后再对计算处理的hash值进行多次扰动，以此来获取key的hash值。

哈希桶添加元素

源码如下：

    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<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;
    }
复制代码