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

• 【免费】全网独家：这是一份非常值得珍藏的Android知识体系！！！

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

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

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

一、Map接口的简单介绍

二、HashMap的初始化过程

三、HashMap的增加数据过程

一、Map接口的简单介绍

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

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

关于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的构造方法有：

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

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

此种情况首先会根据indexFor(hash, table.length)生成的bucketIndex去table中查找是否存在相同bucketIndex的value，如果有，就将旧值替换为新值，并返回旧值。否则，计数器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);
}
复制代码

该方法中，首先判断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方法中，如果表容量已经达到最大值，则直接返回Integer.MAX_VALUE。否则根据新的容量值创建新表，并执行数据迁移方法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的bucketIndex位置，并将size加1。

现在，用两个小图来表示put过程的两种状态，如下:

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

bucketIndex = indexFor(hash, table.length);
复制代码

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

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

最后，预祝你学习愉快！

• 【免费】全网独家：这是一份非常值得珍藏的Android知识体系！！！