从根源揭秘HashMap的数据存储过程

类型	描述	用时
选题	silencezwm	0.1小时
写作时间	2017年12月3日	5小时
审稿	silencezwm	0.5小时
校对上线	silencezwm	0.1小时

Tips:4个环节，共计约5.7小时的精心打磨完成上线。

原文链接：
https://juejin.im/post/5a24fc8451882561a20a4ea8

---

在我们日常的开发过程中，HashMap的使用率还是非常高的，本文将首先对Map接口的基本属性做一个简单的介绍，然后从HashMap的初始化、增加数据两方面来进行探讨。

通过本文的学习，你可以了解到：

一、Map接口的简单介绍

二、HashMap的初始化过程

三、HashMap的增加数据过程

---

一、Map接口的简单介绍

我们查看Map源码，可知道其是以key-value(键值对)形式存在的接口，由其衍生出来的接口和类也是相当多的，比如HashMap、TreeMap、Hashtable、SortedMap等等。

其常用的方法以及描述如下：

方法	描述
V put(K key, V value)	往Map中存入一个键值对数据，并返回一个Value
void putAll (Map<? extends K, ? extends V> map)	往Map中存入一个Map数据
V remove (Object key)	根据key删除该数据，并返回一个Value
void clear ()	清空Map现有数据
V get (Object key)	根据key查询对应的Value
boolean isEmpty ()	判断Map是否为空
int size ()	返回Map存有数据的个数
boolean containsKey (Object key)	判断Map是否包含该key
boolean containsValue (Object value)	判断Map是否包含该value

关于Map的更多介绍，可参阅Api文档

---

二、HashMap的初始化过程

首先我们来看下HashMap的继承以及接口实现关系：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

AbstractMap同样也实现了Map接口。所以，HashMap拥有所有Map的特征也是毋庸置疑的。并且HashMap的静态内部类HashMapEntry<K,V>也实现了Map.Entry<K,V>接口，如下：

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

    HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
    
    ......
}

HashMap的表中存放的每一个数据都是HashMapEntry<K,V>的一个对象，其包含key、value、指向下一个对象的引用对象next以及该key生成的哈希码值。

我们先来看看HashMap几个重要的全局变量

// HashMap的初始容量
static final int DEFAULT_INITIAL_CAPACITY = 4;

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

// 在构造函数中没有指定的加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// HashMap未初始化时的数组空表
static final HashMapEntry<?,?>[] EMPTY_TABLE = {};

// 该反序列化数组table在HashMap需要调整容量时使用，默认为空表
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;

// HashMap的大小
transient int size;

// 该值用于HashMap需要调整容量时使用
int threshold;

// 加载因子，默认为0.75f
final float loadFactor = DEFAULT_LOAD_FACTOR;

// 计数器
transient int modCount;

HashMap的构造方法有：

方法	描述
HashMap()	得到一个新的空HashMap实例
HashMap(int capacity)	根据传入的容量实例化空HashMap
HashMap(int capacity, float loadFactor)	根据传入的容量、加载因子实例化空HashMap
HashMap(Map<? extends K, ? extends V> map)	传入已有Map对象实例化新的HashMap

这里就选择第一个构造方法来探讨，其代码如下：

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY) {
        initialCapacity = MAXIMUM_CAPACITY;
    } else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
        initialCapacity = DEFAULT_INITIAL_CAPACITY;
    }

    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    
    threshold = initialCapacity;
    init();
}

从默认的构造方法中可以看出，有 initialCapacity(初始容量) 和 loadFactor(加载因子) 这两个参数。如果我们并没有通过其他构造方法传入这两个参数，所以其就会使用默认值。

该构造方法使用流程图表示如下：

构造方法流程图

所以，整个初始化过程仅仅就是对参数的合理性进行判断以及确定几个变量的初始值。

三、HashMap的增加数据过程

既然我们有了HashMap的实例，那就可以往里存放数据了，而其存放数据用到的方法是：

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return =;
    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方法的整个流程解析如下：

1、表的初始化：我们刚在构造方法中，并没有对table进行初始化，所以inflateTable方法会执行；

private void inflateTable(int toSize) {
    int capacity = roundUpToPowerOf2(toSize);

    float thresholdFloat = capacity * loadFactor;
    if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
        thresholdFloat = MAXIMUM_CAPACITY + 1;
    }

    threshold = (int) thresholdFloat;
    table = new HashMapEntry[capacity];
}

private static int roundUpToPowerOf2(int number) {
    int rounded = number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (rounded = Integer.highestOneBit(number)) != 0
                ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
                : 1;

    return rounded;
}

roundUpToPowerOf2方法的作用是用来返回大于等于最接近number的2的冪数，最后对table进行初始化。

2、根据key存放数据：这里分 key为null 和 key不为null 两种情况处理。

情况一：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;
}

首先对数组table从头到尾遍历，当找到有key为null的地方，就将旧值替换为新值，并返回旧值。否则，计数器modCount加1，调用addEntry方法，并返回null。

情况二：key不为null

此种情况首先会根据key以及key的哈希码值和现有table数组中的数据作对比，如果有key相等并且key的哈希码值也相等的数据，就将旧值替换为新值，并返回旧值。否则，计数器modCount加1，调用addEntry方法，并返回null。

分析了以上两种情况后，并且都指向了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);
}

addEntry方法中，首先判断table是否需要扩容，如果需要扩容，则resize方法被执行，传入的参数为现有table长度的两倍。

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

resize方法中，如果表容量已经达到最大值，则直接返回。否则根据新的容量值创建新表，并执行数据迁移方法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;
        }
    }
}

transfer方法的作用就是将老表的数据全部迁移到新表中。

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

最后将需要添加的数据存入到table中，并将size加1。

最后，用个小图表示一下整个put过程，如下:

put方法情况一
put方法情况二

其中数据存放的位置bucketIndex是由 key 和 表的长度 共同决定的。在addEntry方法中计算得到：

bucketIndex = indexFor(hash, table.length);

所以有可能会出现bucketIndex相同的情况，也称之为bucketIndex碰撞，当碰撞发生时，相同bucketIndex的value会通过单链的形式连接在一起，此时HashMapEntry<K,V>中的next就会指向下一个元素。也就印证了以下这句话：

如果hashCode不同，equals一定为false；如果hashCode相同，equals不一定为true。

---

最后，预祝你学习愉快！

把文章分享出去吧