HashMap实现原理学习

HashMap源码来自：android-25/java/util/HashMap

一、构造方法

static final int MAXIMUM_CAPACITY = 1 << 30;
static final int DEFAULT_INITIAL_CAPACITY = 4;
static final float DEFAULT_LOAD_FACTOR = 0.75f;

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 参数默认为 4,0.75f
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 4 < MAXIMUM_CAPACITY
        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        }
        // 4 = DEFAULT_INITIAL_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();
}

ps：

init()为空方法；构造方法中只是做了HashMap数组容量字段的一个简单限制，最大为MAXIMUM_CAPACITY，最小为DEFAULT_INITIAL_CAPACITY

二、添加元素 put(K key, V value)

添加数据时，若出现冲突。

Java是通过 数组+链表 的形式解决冲突。效果如下图所示：

• HashMap中有一个默认长度为16的table数组，当数组的容量达到默认长度的0.75倍时，则扩容两倍；
• 其中table数组的每一项数据结构如下：

static class HashMapEntry<K,V> implements Map.Entry<K,V> {
    final K key; // key
    V value;     // value
    HashMapEntry<K,V> next; // 链表的下一项
    int hash;    // key 的hash值
}

下面通过跟中源码查看：

table数组初始化

介绍put(K key, V value)方法前，先简单介绍table数组初始化

// 添加key value
public V put(K key, V value) {
    // 如果table列表为null，则用过inflateTable方法初始化
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    ...
    return null;
}
// 初始化table数组
private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        // 这里计算一个2的n次方的数组容量，默认为2的4次方，为16
        int capacity = roundUpToPowerOf2(toSize);
        // 计算数组容量的0.75倍，超过数组容量0.75倍时，数组需要扩容
        float thresholdFloat = capacity * loadFactor;
        if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
            thresholdFloat = MAXIMUM_CAPACITY + 1;
        }
        // 数组容量的0.75倍
        threshold = (int) thresholdFloat;
        // 初始化数组,默认容量capacity为16
        table = new HashMapEntry[capacity];
}

ps：

这里默认初始化了一个数组容量为16的table数组，其中关于roundUpToPowerOf2(toSize)为什么为2的n次方的问题，在下边进行介绍

put(K key, V value)

// 添加key value
public V put(K key, V value) {
        // 如果table列表为null，则用过inflateTable方法初始化
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        // key 为null，则添加key为null的value
        if (key == null)
            return putForNullKey(value);
        // 根据key获取hash值
        // Jenkins hash算法，可参考以下链接：
        // https://en.wikipedia.org/wiki/Jenkins_hash_function
        int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
        //  h & (length-1) 取余太消耗性能，这里通过位运算达到同样的效果
        // 获取该key在table 数组的index
        int i = indexFor(hash, table.length);
        // 循环table[i]对应的链表
        // 如果 hash值相同 && key相同，则替换对应value，并返回老的value值
        // 注：这里只是循环table[i]位置的链表，对于table数组未做循环
        for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            // 如果 hash值相同 && key相同，则替换对应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;
            }
        }

        modCount++;
        // 以下两种情况，则需要通过createEntry方法来看了
        // hash相同 && key不同
        // hash不同 && key不同 
        addEntry(hash, key, value, i);
        return null;
}

ps：

以上介绍了添加数据时，“如果 hash值相同 && key相同，则替换对应value，并返回老的value值”，但对于“hash相同 && key不同”与“hash不同 && key不同”情况，则需要在createEntry中进行说明

void addEntry(int hash, K key, V value, int bucketIndex) {
        // 当数组的占用量，达到数组长度的0.75倍时，则需要扩容，扩展后的容量为原容量的2倍
        // 数组扩容首先创建一个长度为原数组两倍的数组，然后将老的数组数据赋值给新数组的对应项项目
        // 数组扩容的代码，这里不再说明
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        // hash相同 && key不同
        // hash不同 && key不同 
        createEntry(hash, key, value, bucketIndex);
}
// hash相同 && key不同
// hash不同 && key不同 
void createEntry(int hash, K key, V value, int bucketIndex) {
        // 取出table[bucketIndex]数组的原有值，可能为null，可能为HashMapEntry
        // 若为null,则直接将value放在table[bucketIndex]位置就ok了
        // 若不为null,则将新数组放到table[bucketIndex]位置，老数组放到新数据链表的next字段
        // hash冲突就是这样解决了，可以看到确实与上图一致，为数组+链表的方式解决冲突
        HashMapEntry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
        size++;
}

ps：

通过createEntry方法，我们看到HashMap中通过数组+链表方式解决了Hash冲突，呼应了上图

roundUpToPowerOf2(toSize)为什么为2的n次方

打个比方：

• 当数组长度为15时，添加数组时 h & (length-1) 计算成为 hash&14（0x1110） ,那么最后一位永远是0，从而造成table数组中 1（0x0001），3（0x0011），5（0x0101），7（0x0111），9（0x1001），11（0x1011）等位置永远不可以存放数据，从而造成空间浪费；
• 更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率。

========== THE END ==========