源码分析—HashMap（JDK1.7）

引言：本文基于JDK1.7，详细分析HashMap的源码。

HashMap简介

哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表，而HashMap的实现原理就是基于此。那么什么是哈希表呢？
在讨论哈希表之前，我们先大概了解下其他数据结构在新增，查找等基础操作执行性能。

• 数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)。对应到集合实现，代表就是ArrayList。
• 线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)。对应的集合类是LinkedList。
• 二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。对应的集合类有TreeSet和TreeMap。
• 哈希表：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)。对应的集合类就是HashMap。

哈希表的主干就是数组。我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。即：

存储位置 = f(关键字)

其中，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。这会涉及到哈希冲突。

当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证计算简单和散列地址分布均匀。但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址）、再散列函数法、链地址法。而HashMap即是采用了链地址法，也就是数组+链表的方式。

简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部，急需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

HashMap的源码实现

HashMap中的几个重要属性

//最大容量，2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认的初始容量，2的4次方=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//HashMap内部的存储结构是一个数组，此处数组为空，即没有初始化之前的状态 
static final Entry<?,?>[] EMPTY_TABLE = {};

//哈希数组，默认是一个空的数组
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

//负载因子，用于计算threshold。
final float loadFactor;

//扩容的阀值，当HashMap的size达到阀值时，会发生扩容resize()。
int threshold;

//实际存储的key-value键值对的个数
transient int size;

//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
transient int modCount;

数据结构

HashMap的内部存储结构其实是数组和链表的结合。当实例化一个HashMap时，系统会创建一个长度为Capacity的Entry数组，这个长度被称为容量(Capacity)，在这个数组中可以存放元素的位置我们称之为“桶”(bucket)，每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。 每个bucket中存储一个元素，即一个Entry对象，但每一个Entry对象可以带一个引用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Entry链。 Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。 Entry是HashMap中的一个静态内部类。代码如下：

/**
 * Entry是单向链表。
 */
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
        int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

经过以上分析，HashMap的存储结构图如下：

构造方法

HashMap共有4个构造方法，但都会调用到HashMap(int initialCapacity, float loadFactor)这个构造方法。

public HashMap(int initialCapacity, float loadFactor) {
    // 初始容量不能小于0，否则报错
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity);
    // 限制初始容量的最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;

    // 填充因子不能小于或等于0，不能为非数字
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);
    // 初始化负载因子                                 
    this.loadFactor = loadFactor;

    // 初始化threshold大小
    threshold = initialCapacity;

    //init方法在HashMap中没有实际实现，不过在其子类如 linkedHashMap 中就会有对应实现
    init(); 
}


//通过扩容因子构造HashMap,容量去默认值，即16  
public HashMap(int initialCapacity) {  
    this(initialCapacity, DEFAULT_LOAD_FACTOR);  
}  

//装载因子取0.75，容量取16，构造HashMap  
public HashMap() {  
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);  
}  

//通过其他Map来初始化HashMap,容量通过其他Map的size来计算，装载因子取0.75  
public HashMap(Map<? extends K, ? extends V> m) {  
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);  
    inflateTable(threshold);//初始化HashMap底层的数组结构  
    putAllForCreate(m);//添加m中的元素  
}

从上面这段代码我们可以看出，在常规构造器中（有一个入参为指定Map的构造器例外），并没有根据传入的initialCapacity去新建一个Entry数组实例，构造方法执行完后哈希表依然是一个空表。
Entry数组的创建是在第一次执行put操作时，执行put操作会先检查当前哈希表是否是个空表，如果是空表就调用inflateTable方法进行初始化。

此外，如果创建HashMap对象时没有传入initialCapacity 和 loadFactor 这两个参数，会使用默认值。initialCapacity默认为16，loadFactor默认为0.75。

//toSize是用的threshold，而在构造方法中threshold赋值为initialCapacity
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);
}

上面贴出了inflateTable方法的代码，可以看到在这个方法中会重新计算Entry数组的容量，因为在构造HashMap时传入的初始化大小可能不是2的幂，因此先要将这个数转换成2的幂再根据新的容量新建Entry数组。并且在初始化哈希表时会再次重新设置threshold，一般就是capacity*loadFactor。
此外，在初始化哈希表时还会去初始化hashSeed，这个hashSeed用于优化哈希函数，默认为0是不使用替代哈希算法，但是也可以自己去设置hashSeed的值，以达到优化效果。

get方法

get方法相对比较简单，源码如下：

public V get(Object key) {
    // 如果key为null，调用getForNullKey方法从entry数组第一个位置获取key对应的value
    if (key == null) {
        return getForNullKey();
    }
    //如果key不为null，调用getEntry方法根据key找到对应的entry
    Entry<K, V> entry = getEntry(key);
 
    return null == entry ? null : entry.getValue();

}


private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    //HashMap将“key为null”的元素存储在table[0]位置，但不一定是该链表的第一个位置！所以也要遍历链表
    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) {
    if (size == 0) {
        return null;
    }
    
    // 计算hash值
    int hash = (key == null) ? 0 : hash(key);
    // 通过hash值和数组长度计算出Entry数组的指定槽位
    for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        //遍历链表，在hash值相等的条件下，如果key是同一个或者key用equals方法判断为真，则返回对应的entry
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { return e; }
    }
    return null;
}

put方法

put方法稍微复杂些，代码如下：

public V put(K key, V value) {
    //如果哈希表没有初始化就进行初始化
    if (table == EMPTY_TABLE) {
        //根据HashMap的构造器，threshold的初始值是initialCapacity;
        inflateTable(threshold);
    }
    // 若key为null，则将该键值对添加到table[0]中。
    if (key == null)
        return putForNullKey(value);
   // 若key不为null， 则根据key的hash值和数组的长度，计算出一个哈希数组槽位值i，该键值对将被添加到table[i]处的链表上
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 通过key的hashCode和equals方法判断，key是否存在，如果存在则用新的value取代旧的value，并返回旧的value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    // 修改次数增加1，保证并发访问时，若HashMap内部结构发生变化，快速响应失败
    modCount++;

    // 如果table[i]处链表是空的，或者遍历完链表后，发现key不存在，则创建一个新的Entry，并添加到哈希表中
    addEntry(hash, key, value, i);
    return null;
}


// putForNullKey()的作用是将“key为null”键值对添加到table[0]位置  
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;  
        }  
    }  
    // 如果没有存在key为null的键值对，则直接题阿见到table[0]处
    modCount++;  
    addEntry(0, null, value, 0);  
    return null;  
}

indexFor方法中，用h & (length-1)保证获取的index一定在数组范围内。

//返回数组下标
static int indexFor(int h, int length) {
    return h & (length-1);
}

比如，默认容量16，length-1=15，h=18,转换成二进制计算为

最终计算出的index=2。有些版本的对于此处的计算会使用 取模运算，也能保证index一定在数组范围内，不过位运算对计算机来说，性能更高一些（HashMap中有大量位运算）。
通过以上分析，我们看到，要得到一个元素的存储位置，需要如下几步：
1、获取该元素的key值
2、通过hash方法得到key的散列值，这其中需要用到key的hashcode值。
3、通过indexFor计算得到存储的下标位置。

最后，得到存储的下标位置后，我们就可以将元素放入HashMap中，具体通过addEntry实现：

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容，新容量为旧容量的2倍
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);//扩容后重新计算插入的位置下标
    }

    //把元素放入HashMap的桶的对应位置
    createEntry(hash, key, value, bucketIndex);
}

//创建元素  
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++;//元素个数+1  
}

通过以上代码能够得知，当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。

扩容（resize）

扩容操作通过resize操作实现：

//按新的容量扩容Hash表  
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;//修改HashMap的底层数组  
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改阀值  
}

如果数组进行扩容，数组长度发生变化，而存储位置 index = h&(length-1),index也可能会发生变化，需要重新计算index，我们先来看看transfer这个方法：

//将老的表中的数据拷贝到新的结构中  
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) {//如果是重新Hash，则需要重新计算hash值  
                e.hash = null == e.key ? 0 : hash(e.key);  
            }  
            int i = indexFor(e.hash, newCapacity);//定位Hash桶  
            e.next = newTable[i];//元素连接到桶中,这里相当于单链表的插入，总是插入在最前面
            newTable[i] = e;//newTable[i]的值总是最新插入的值
            e = next;//继续下一个元素  
        }  
    }  
}

这个方法将老数组中的数据逐个链表地遍历，重新计算后放入新的扩容后的数组中，我们的数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后，再通过和 length-1进行位运算得到最终数组索引位置。
注意：HashMap数组元素长度的设计
通过源码可以发现，hashMap的数组长度一定保持2的次幂，这样做有什么好处呢？

//根据Hash值和Hash表的大小选择合适的槽位
static int indexFor(int h, int length) {  
    return h & (length-1);  
}

如果length为2的次幂，其二进制表示就是100….0000；则length-1 转化为二进制必定是0111….11的形式，在于h的二进制与操作效率会非常的快，而且空间不浪费；如果length不是2的次幂，比如length为15，则length-1为14，对应的二进制为1110，再于h与操作，
最后一位都为0，所以0001，0011，0101，1001，1011，0111，1101这几个位置永远都不会存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。

几个注意点

• HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变（发生扩容时，元素位置会重新分配）。
• 迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。
• HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。
  如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。