HashMap源码阅读

HashMap是什么想必大家都是知道的，日常开发中经常使用，而且常驻于笔试题目及面试中，那么今天将从源码的角度来深入理解一下HashMap。

PS:本文以下分析基于jdk1.7，1.8的改动会在文后总结。

1.什么是HashMap？

HashMap是基于哈希表的Map接口实现，是一个key-value型的数据结构。他在性能良好的情况下，存取的时间复杂度皆为O(1).

要知道数组的获取时间复杂度为O(1),但是他的插入时间复杂度为O(n).

那么HashMap是怎么做到的呢？

看一下HashMap的属性：

//内部数组的默认初始容量，作为hashmap的初始容量，是2的4次方，2的n次方的作用是减少hash冲突
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

 //默认的最大容量
 static final int MAXIMUM_CAPACITY = 1 << 30;

 //默认负载因子，当容器使用率达到这个75%的时候就扩容
 static final float DEFAULT_LOAD_FACTOR = 0.75f;

 /**
  *当数组表还没扩容的时候，一个共享的空表对象
  */
 static final Entry<?,?>[] EMPTY_TABLE = {};

 //内部数组表，用来装entry，大小只能是2的n次方。
 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

 //存储的键值对的个数
 transient int size;

 /**
  * 扩容的临界点，如果当前容量达到该值，则需要扩容了。
  * 如果当前数组容量为0时（空数组），则该值作为初始化内部数组的初始容量
  */
 int threshold;

 //由构造函数传入的指定负载因子
 final float loadFactor;

 //Hash的修改次数
 transient int modCount;

 //threshold的最大值
 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

 //计算hash值时候用，初始是0
 transient int hashSeed = 0;

 //含有所有entry节点的一个set集合
 private transient Set<Map.Entry<K,V>> entrySet = null;

 private static final long serialVersionUID = 362498820763181265L;
复制代码

注释已经比较完备，便不再做过多的说明。

由里面的

可以看出，HashMap的主体其实是个数组，是Entry这个内部类的数组。

Entry内部类是啥呢？

这是Entry内部类的属性，可以看出这是个单链表的节点，因为它内部有指向下一个节点的next。

那么就相当明了了，HashMap内部是一个数组，数组的每一个节点是一个链表的头结点，也就是拉链式。

2.HashMap具体是怎么做到的

对于HashMap来说，日常使用的就是两个方法， get() , put() .

我们首先看 put .

public V put(K key, V value) {

    //判断当前HashMap是否为空，为空则初始化
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    //判断传入的key是否为null，为null则放到table[0]的位置或者其链表上
    if (key == null)
        return putForNullKey(value);

     //计算key的hash值      
    int hash = hash(key);
    //计算key存放在数组中的下标
    int i = indexFor(hash, table.length);
    //遍历该位置上的链表，如果存在key值和传入的key值相等，则替换掉旧值
    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++;
    //如果没有这个值，则添加一个Entry
    addEntry(hash, key, value, i);
    return null;
}
/**
 * Offloaded version of put for null keys
 */
private V putForNullKey(V value) {
    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;
}

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);
    }
    //新建一个Entry
    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    //将传入的key-value放在链表的头部，并且指向原链表的头。
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

复制代码

代码中添加了一些注释，大概是可以看懂的，那么这里总结一下流程。

1. 判断当前hashMap是否为空，为空则初始化。
2. 判断传入的key是否为null，为null的话直接放到数组的0位置或者0位置的链表上。
3. key不为空，计算key的hash值。
4. 计算key在数组中应该存储的下标
5. 遍历数组在该下标的链表，如果找到已经存在的key和传入的key相等，则用新的value替换旧的value。
6. 没找到，则在数组的i位置添加一个Entry。
7. 添加Entry时，先判断是否需要扩容，需要的话扩容，不需要的话下一步。
8. 创建一个Entry，创建的方法是将新传入的key-value放在数组i位置的链表头结点，并且指向原链表头结点。

接下来是 get() 方法。

public V get(Object key) {
    //key为null，则在数组0位置寻找值
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

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

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

final Entry<K,V> getEntry(Object key) {
    //如果hashMap中存的值数量为0，则返回null
    if (size == 0) {
        return null;
    }
    //计算key的hash值
    int hash = (key == null) ? 0 : hash(key);

    //用indexof函数算出数组下标
    //在该下标位置上的链表中遍历，寻找与传入key相等的key，否则返回null
    for (Entry<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;
}

复制代码

同样这里总结一下流程：

1. 判断key==null，如果为null，在数组0位置寻找。
2. key！=null，判断hashMap中存的值数量是否为0，如果为0直接返回null。
3. 计算key的hash值。
4. 计算key应该在数组中的下标。
5. 遍历Entry数组在该位置的链表，寻找与传入key相等的key，并返回值，如果遍历结束找不到，则返回null。

hash()方法和indexOf()方法

大家可能注意到了，在 get() 和 put() 方法的实现中，都使用到了这两个方法，那么这里看一下源码：

//通过一系列复杂的计算拿到一个int类型的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);
}

/**
* Returns index for hash code h.
*/
//将hash值和数组长度与，结果等同于hash%length，拿到数组下标
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);
}

复制代码

这里重点是：indexOf()方法，将hash值和数组长度 与 ，结果等同于hash%length，拿到数组下标。

结果等同于取模法，但是运算过程更加快速。这里有一个重要的知识点，后续会说噢。

resize()方法

在 put() 方法及其调用的方法中，当在数组上新添加一个节点时，会判断当前是否需要扩容，怎么判断的呢？

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

可以看到，当当前已经存储值得size大于阀值，则将数组扩容为原来的两倍。

阀值threshold怎么计算呢？容量 * 负载因子。即 capacity * loadFactory

扩容的方法为：

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];
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        transfer(newTable, rehash);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    /**
     * Transfers all entries from current table to newTable.
     */
    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;
            }
        }
    }

复制代码

新建一个容量为原来两倍的数组，然后将旧数组中的值，rehash之后重新放入新数组，以保证散列均匀。

rehash这个操作是比较费时间的，总的来说扩容操作就比较费时间，因为需要将旧的值移动到新的数组中，因此如果在使用前能预估数量，尽量使用带有参数的构造方法，指定初始容量，尽量避免过多的扩容操作

remove()方法

差点忘记remove()方法了。。

public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

    /**
     * Removes and returns the entry associated with the specified key
     * in the HashMap.  Returns null if the HashMap contains no mapping
     * for this key.
     */
    final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
        //计算hash
        int hash = (key == null) ? 0 : hash(key);
        //计算下标
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

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

复制代码

具体的实现思路也是一样的：首先计算hash继而计算下标，然后遍历数组在该位置的链表，找到该key-value然后将其移除掉。

3.HashMap的一些为什么？

3.1.为什么扩容的阀值在 capacity * loadFactory ?

首先了解一下

1. capacity是指容量，数组最大的容量
2. loadfactory是指负载因子，是形容当前数组装的有多满的一个值。默认为0.75.也就是如果初始capacity为16，那么当不发生hash碰撞，也就是没有用到链表结构时，写入12个元素即会扩容了。
3. 数组在性能上是比链表优秀的(在HashMap中，数组可以存null，不用进行值的移位)。
4. HashMap的数据结构，导致即使容量只有16，也可以存储32(还可以更多)个值，只需要每个位置上的链表多链几个节点就好了。

因此可以发现，HashMap的性能问题又来到了时间和空间的取舍上，当你不扩容，仍然可以存储，只是由于链表的变长，性能下降。当你进行太多的扩容，hash碰撞减少，链表长度统一减少，性能提高了但是浪费的空间又多了。0.75这个值是开发者定义的一个对时间空间的折中值。

3.2.性能极限的情况

当存入的值越来越多，却不扩容，HashMap性能就会下降，那么我们极限一点。

HashMap的容量只有1，存入了100个值。由上面的分析可知，这时候HashMap退化成了单链表，存取得时间复杂度都是O(n)。

HashMap的容量为16，存入一个值，在存入第二个值，立即扩容，这样可以尽量的避免hash碰撞，避免产生链表，存取时间复杂度都为O(1).

因此，当你对存取速度要求很高，可以适当调低loadfactory，当你当前对速度无所谓，但是内存很小，可是调大loadfactory，当然大部分时候默认值0.75都是一个不错的选择。

loadfactory的值为：0.75，2，4等数字都是合法值

3.3.为什么HashMap的容量永远是2的次幂？

看过上面的代码我们可以发现，HashMap的初始容量为16，扩容为原容量乘以2。

也就是说，HashMap的容量永远是2的次幂，这是为什么呢？

想一想哪里使用到了容量这个参数呢？

在拿到key的hash值，计算当前key在数组中的下标的时候，运用了如下的方法进行计算：

真实的length为16，我们假设一个假的lengthWrong = 15；

同时我们有两个key，hash之后拿到的hash=8，和hash=9；

可以看到当长度为15时，当h = 8,h =9 h & length - 1 拿到的结果一样都为8，也就是这两个key都存在数组中下标为8的链表上。这是为什么呢？

当length为偶数时，length- 1位奇数，奇数的二进制最后一位必然为1，而当length = 奇数时，length - 1位偶数，偶数的二进制最后一位为0.

二进制与运算有如下规则：

1 & 任意 = 任意；
0 & 任意 = 0；
复制代码

也就是说，当length = 16时，计算的下标可以为1-16任意数字，而当length=15时，计算的下标只能为2，4，6，8 等等偶数，这样就浪费了一般的存储空间，同时还增大了hash碰撞的概率，使得HashMap的性能变差。

因此length必须为偶数，而length为2的次幂不仅能保证为偶数，还可以实现 h & length - 1 = h % length ,可谓是一举两得了。666啊。

扩展(Java8 的hashMap有哪些改进？）

在3.2中提到，当极限情况下HashMap会退化成链表，存取时间复杂度变为O(n)，这显然是不能接受的，因此在java8中对这一点做了优化。

在java7中，存储在数组上的是一个链表的头结点，当哈希碰撞之后，不断的增长链表的长度，这会导致性能下降。在java8中，引入了红黑树数据结构，当链表长度小于8时，仍然使用链表存储，而当长度大于8时，会将链表转化为红黑树。同时，当树的节点数小于6时，会从红黑树变成链表。

这样改进之后，即使在性能最差的情况下，hashMap的存取时间复杂仍为O(logn).

而红黑树的具体实现，这里不再详细叙述，这属于数据结构的范围了，在HashMap中展开不合适。

ChangeLog

2018-10-17 完成

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客------>呼延十