2020-09-18

HashMap【源码分析-JDK1.7 版本】

字数统计: 4.2k字 | 阅读时长: 17分

一、前言

本文主要详细解释了JDK1.7版本下的HashMap的put和get过程的底层源码，并以图的形式总结了其流程。

二、源码详细讲解

（一）常量与默认值

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{
    // 默认初始容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    // 临界值
    int threshold;
    // 加载因子
    final float loadFactor;
}

HashMap中的其它方法在以下模块分别解释：

（二）构造方法

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

    // 使用指定的加载因子
    this.loadFactor = loadFactor;
    // 刚开始时将阈值设置为指定的初始容量
    threshold = initialCapacity;
    // init在HashMap中是个空方法，没有实际意义；在ConcurrentHashMap中有实现
    init();
}

public HashMap(int initialCapacity) {
    // 没有指定加载因子，则使用默认的加载因子，大小为 0.75f
	this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
    // 使用默认初始容量 16， 默认加载因子 0.75
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

（三）Put

1、put：

public V put(K key, V value) {
    // 如果当前数组为空，则会根据初始容量（默认的初始容量/用户指定的初始容量）来创建一个数组
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 如果当前key为null，则采用不同的存放数据的方法
    if (key == null)
        return putForNullKey(value);
    // 如果当前key不为null，则求当前key的hash值
    int hash = hash(key);
    // 将当前key的hash值转换为数组的index
    int i = indexFor(hash, table.length);
    
    // 查看当前hash值对应的链表中是否已经存在相同的key，如果存在，就用新的value进行覆盖，并返回旧值
    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++;
    // 如果当前key不存在，就添加新的元素
    addEntry(hash, key, value, i);
    return null;
}

2、inflateTable：

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    // 将传递进行来的参数（默认的初始容量/用户指定的初始容量）转换为 2的幂次方（为啥有这个要求后面会说）
    int capacity = roundUpToPowerOf2(toSize);
	// 选定阈值
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // 创建存放数据的数组
    table = new Entry[capacity];
    // 先不管这行代码
    initHashSeedAsNeeded(capacity);
}

3、putForNullKey：

// 如果要加入的key为null，就会调用此方法
private V putForNullKey(V value) {
    // 其实key为null时，都是存放在数组的第一个位置
    // 然后此处是如果已经存放了元素，就用新元素覆盖旧元素，并返回旧元素
    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;
}

4、hash：

// 求key的hash值的方法
final int hash(Object k) {
    int h = hashSeed;
    // 如果key为String类型，就使用特殊的求hash值的方法，求hash值的方法内部不用细究
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    // 如果不是String类型，可能为引用类型，就可以调用该对象的hashCode方法
    // 因此，如果重写类的hashCode方法，其实对hash值的获取是有影响的，从而可能会影响hashMap的效率
    // 求得hashCode之后，再和哈希种子进行异或运算
    h ^= k.hashCode();

    // 将异或运算的结果再进行多次的右移和异或运算，从而让hashCode值的高位也能参与运算，从而降低哈希冲突
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

5、indexFor：

// 将hash值转换为数组的下标
static int indexFor(int h, int length) {
    // 正因为有此操作，所以要求数组的长度必须为2的幂次方（关于具体原因，文章后面会讲解）
    return h & (length-1);
}

6、addEntry：

// 判断是否需要扩容，在添加元素
// 1) 如果需要扩容，就先扩容，然后在重新求hash，求当前元素应该在扩容后的数组中存放的index，最后在调用createEntry进行真正的存储
// 2）如果不需要扩容，就直接调用createEntry进行存储
// bucketIndex：传递过来的数组下标（索引）
void addEntry(int hash, K key, V value, int bucketIndex) {
    // 如果HashMap中当前元素个数大于等于阈值，并且数组当前要添加的位置已经有元素了，那么就会进行扩容
    // 可以通俗的理解为：当前元素个数大于等于阈值，并且发生一次哈数冲突才会触发扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 新数组的大小为旧数组大小的两倍
        resize(2 * table.length);
        // 扩容之后，需要重新求当前元素key的hash
        hash = (null != key) ? hash(key) : 0;
        // 根据新的hash，求出当前元素在新数组应该存放的index
        bucketIndex = indexFor(hash, table.length);
    }

    // 调用真正进行元素存储的方法
    createEntry(hash, key, value, bucketIndex);
}

7、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 重新指向新数组
    table = newTable;
    // 根据扩容后数组的长度来获取新的阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

8、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) {
                // 求出旧哈希表中每一个元素key的新的hash值
                e.hash = null == e.key ? 0 : hash(e.key);
            }
             // 求出旧哈希表中每一个元素key的新的hash值所对应的数组下标
            int i = indexFor(e.hash, newCapacity);
            // 仍然采用头插法将旧哈希表中的元素迁移到新哈希表
            e.next = newTable[i];
            newTable[i] = e;
            
            // 继续遍历旧的哈希表中的元素
            e = next;
        }
    }
}

9、createEntry：

// 采用头插法将元素插入到链表中
/* 整体思路：先将新元素插入到链表的头部，在将链表整体下移一个位置
1）先获取数组中要插入位置的元素 e ；
2）创建put进来的元素，并将该元素的next指向获取到的元素 e ；
3）将put进来的元素存放到数组中的index位置
*/
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++;
}

（四）Get

1、get：

public V get(Object key) {
    // 如果当前key为null，则调用专门的方法
    if (key == null)
        return getForNullKey();
    
    // 如果非null，则调用getEntr获取该key所对应的元素
    Entry<K,V> entry = getEntry(key);

    // 判断当前获取到的元素是否为null，如果为null，说明该key不存在（元素不存在），否则返回该元素的value
    return null == entry ? null : entry.getValue();
}

2、getEntry：

final Entry<K,V> getEntry(Object key) {
    // 如果当前哈希表中没有元素，则直接返回null
    if (size == 0) {
        return null;
    }

    // 如果key为null，则直接将hash赋值为0，之后转为index也为0（因为key为null，存储在数组的第一个位置）
    // 如果不为null，则计算该key对应的hash
    int hash = (key == null) ? 0 : hash(key);
    
    // 将hash转换为index后，获取该数组对应index位置的元素，然后遍历index位置所对应的链表中的元素
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        // 判断每一个元素是否和要获取的key所对应的元素相同，找到后返回这个元素
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

3、hash：

// 求key的hash值的方法
final int hash(Object k) {
    int h = hashSeed;
    // 如果key为String类型，就使用特殊的求hash值的方法，求hash值的方法内部不用细究
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    // 如果不是String类型，可能为引用类型，就可以调用该对象的hashCode方法
    // 因此，如果重写类的hashCode方法，其实对hash值的获取是有影响的，从而可能会影响hashMap的效率
    // 求得hashCode之后，再和哈希种子进行异或运算
    h ^= k.hashCode();

    // 将异或运算的结果再进行多次的右移和异或运算，从而让hashCode值的高位也能参与运算，从而降低哈希冲突
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

4、indexFor：

// 将hash值转换为数组的下标
static int indexFor(int h, int length) {
    // 正因为有此操作，所以要求数组的长度必须为2的幂次方（关于具体原因，文章后面会讲解）
    return h & (length-1);
}

5、getForNullKey：

private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    // 遍历数组中第一个位置所对应的链表，如果当前元素 e 的key为null，则返回该元素的value
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

三、整体结构流程图

（一）Put过程

![Put方法流程图](HashMap[源码分析-JDK1.7 版本]/Put方法流程图.png)
若图片不清晰，请点击在线查看

（二）Get过程

![Get方法流程图](HashMap[源码分析-JDK1.7 版本]/Get方法流程图.png)
若图片不清晰，请点击在线查看

四、补充知识点

1、为什么要使用头插法而不是尾插法？

如果使用尾插法还需要遍历找到链表的最后一个节点，效率低。

但是如果使用头插法就只需要将新的节点的next指向当前数组中index位置的元素，然后再将链表往下移动一个位置即可，通俗的理解为：每次都将新的头结点存放在数组中对应的index位置（因为如果不将链表往下移动的话，单链表是没有办法向上遍历的）

具体体现这个思想的代码为createEntry中的如下代码：
1
2
>Entry<K,V> e = table[bucketIndex];
>table[bucketIndex] = new Entry<>(hash, key, value, e);

2、关于在创建HashMap时，使用指定容量大小：

当在创建hashmap时指定容量大小，并不会直接是创建指定大小的hashmap，它会进行判断，判断指定的数是否为2的幂次方。如果不为2的幂次方就会将这个容量修改为大于指定的容量的2的幂次方数（如：指定hashmap大小为10，但是底层会将这个大小修改为16）

具体体现这个操作的代码为inflateTable中的如下代码：
1
2
//将传递进行来的参数（默认的初始容量/用户指定的初始容量）转换为 2的幂次方
int capacity = roundUpToPowerOf2(toSize);

3、数组长度为什么要设置为2的幂次方？

在弄懂这个问题之前，先看一段代码：
1
2
3
static int indexFor(int h, int length) {
    return h & (length-1);
}
这个indexFor方法就是将key的hash值转换为数组索引的一个方法。

我们都知道求出来的hash的数值可能会非常大，一般都是会超出数组的索引的，那为什么只需要将hash值和数组长度-1进行一次与操作之后就能确保索引不会越界呢（或者说能转换为数组的索引呢）？

让我们带着这个问题，先看下面这个案例：

1）假设当前哈希表的数组length为 16，那么将其转换为2进制之后就是：0001 0000（此处假设只有8位）

2）那么 length-1 为：0000 1111

3）假设当前hash值为：0101 0101（此处只是假设只有8位）

4）执行 hash & (length-1) 操作，会发现结果是：0000 0101

当我们看完这个案例之后，大概就能想到，原来将 length 规定为2的幂次方是为了确保在执行 length-1 的操作后，其低位都是1，高位仍然保持为0，这样在和hash值进行与操作之后，结果只会小于等于 length-1而 length-1 正好是数组的最大索引，从而确保不会发生索引越界。

小结：

将数组长度设置为2的幂次方是为了保证与运算后的结果在【0，length-1】的范围内，对应为数组的索引，并且不会发生索引越界。

4、关于如何求key的hash值（hash方法）：

会先获取哈希种子，然后调用要存储的对象的hashCode方法（因此可以重写对象的hashCode方法）获取到对象的哈希值，将哈希种子和对象的哈希值进行异或运算，最后将异或运算的结果再进行移位和异或运算（为什么需要这么多步操作呢？其实是为了让高位也参与运算，从而减少哈希冲突，让其散列性更好）

具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
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);
}

5、关于将hash值转换为数组的index（indexFor方法）：

就是第3点中的 indexFor 方法：
1
2
3
static int indexFor(int h, int length) {
    return h & (length-1);
}
前面已详细解释，具体操作此处不再赘述.

补充一点：其实%操作也能将其转换为数组的index，那么为什么要采用与运算而不是%运算呢？

这是因为与运算是属于位操作，其速度要比%运算快。

6、关于JDK 1.7 中的扩容机制：

先扩容在添加元素

扩容条件：size大于等于阈值并且当前元素要存放的位置已经有元素了才会扩容，如果只是size大于等于阈值是不会进行扩容的。

体现这个操作的代码为 addEntry 中的如下代码:
1
2
3
4
5
6
// 如果HashMap中当前元素个数大于等于阈值，并且数组当前要添加的位置已经有元素了，那么就会进行扩容
// 可以通俗的理解为：当前元素个数大于等于阈值，并且发生一次哈数冲突才会触发扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
    // 新数组的大小为旧数组大小的两倍
    resize(2 * table.length);
}

7、扩容前后，元素在数组中index的变化（分析新旧index之间的规律）：

还是通过一个小案例来找规律：

1）首先，我们已经知道了扩容后新数组的大小为旧数组大小的两倍，假设扩容前数组大小为16，那么扩容后数组大小就变为32：二进制代码表示为: 0001 0000 –> 0010 0000

length-1之后的值用二进制代码表示为：0000 1111 –> 0001 1111

2）假设 key1 的hash值为：0001 0101

3）那么分别用旧的长度和新的长度求出key1所对应的index值为：0000 0101 –> 0001 0101

我们会发现，key1 所对应的index在扩容前后发生了变化，并且新的index和旧的index之间相差了16，即相差了旧数组的长度。

接下来，我们再看另外一个key，是不是也会发生变化并且有这个规律呢？

4）假设 key2 的hash值为：0000 0101

5）那么分别用旧的长度和新的长度求出key2所对应的index值为：0000 0101 –> 0000 0101

这个时候我们又发现，key2 所对应的index在扩容前后没有发生变化。

于是就有以下结论：

在JDK 7 中，元素在数组中的index在扩容前后，可能发生变化，也可能不会发生变化，并且如果有变化，那么新的index和旧的index之间，其实相差了一个旧数组的长度。

（可能有的小伙伴担心，这不是只举了一个栗子嘛，怎么就能这么确定呢。其实大家也可以使用更多的栗子来验证，会发现这个结论是成立的，因为这是由位操作的特点得出的结论）

Java新手，若有错误，欢迎指正！

| 阅读量次