Android HashMap 1.7 源码分析

作者: 是刘航啊 | 来源:发表于2021-04-01 11:55 被阅读0次

前言

HashMap 的数据结构是什么样子的？
hash 碰撞是怎么产生的？HashMap 是如何处理 hash 碰撞？
HashMap 的长度为什么必须是 2 的整数次幂？

下面的流程会分析以上的问题。在了解 HashMap 结构前需要了解 2 种基本的数据结构「数组」「链表」

1、数组

数组是线性结构，会使用一组连续的内存空间来存储相同类型的数据，所以可能会导致内存浪费。这种特性有利有弊：好处是数组支持根据下标随机访问；坏处是插入和删除需要做数据搬移。

2、链表

链表和数组刚好相反，不需要连续的内存空间。链表的插入和删除非常方便，因为链表的空间不是连续的，所以链表不支持随机访问，因此在链表中查询某个位置的元素需要从第一个元素开始依次便利。

3、HashMap

HashMap 通过 key 获取 value，数组通过 index 获取 value，那么是不是可以把 HashMap 想象成特殊的数组。

3.1 hash 和 hashCode

由于 key 不一定会为数字，因此需要将对象转换为数字，所以会使用到 hash 方法，而 hashCode 用于存储对应的 hash 值。

通过这种方式存储数据还有一个好处，因为 key 相同时得到的 hashCode 是相同的，相同的 key 是不会重复存储的，这样达到一个替换的作用。

3.2 hash 碰撞

不同的 key，它们的 hash 值有可能是相同的，因此导致了 hash 碰撞，所以 HashMap 采用了数组 + 链表的数据结构。

不同的 key 值，当 hash 值相同时，会通过链表的方式将数据链接起来，这样就避免了 hash 碰撞时错误的覆盖。以上是对 HashMap 数据结构的分析，下面具体对 HashMap 的源码进行分析

4、HashMap 使用

HashMap map = new HashMap();
map.put("key","value");
map.get("key");

后面会依次从「HashMap 创建」「put 方法」「get 方法」来分析 HashMap 原理。

5、HashMap 创建

//数组大小，默认16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//可以理解成扩容率
static final float DEFAULT_LOAD_FACTOR = 0.75f;

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

public HashMap(int initialCapacity, float loadFactor) {
    //判断传入的数组大小是否小于0，如果小于0则抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
    //判断数组的大小是否大于最大值「2的30次方」，如果大于则设置成最大值
    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 = initialCapacity;
    init();
}

经过上面的分析可以了解 HashMap 也有多个构造方法，只是我们平时使用无参数的构造方法比较多。HashMap 在创建时可以自定义数组大小以及扩容率。

6、HashMap -> put

public V put(K key, V value) {
    //当集合为空时，创建一个集合，并设置长度
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    //如果key为空，直接添加value
    if (key == null)
        return putForNullKey(value);
    //2次hash
    int hash = hash(key);
    //通过hash值和集合的长度来获取下表
    int i = indexFor(hash, table.length);
    //根据索引拿到数组的链表，然后进行便利
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //如果 hash 值相等且 key 相同就重新赋值
        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;
}

6.1 inflateTable

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);
    //扩容临界再次赋值
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    //创建数组
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

private static int roundUpToPowerOf2(int number) {
    return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

inflateTable 方法会找到大于或等于当前长度的值且是 2 的整数次幂，然后进行赋值、临界值的运算以及数组的创建

6.2 putForNullKey

private V putForNullKey(V value) {
    //便利数组下标为0的第一个位置
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        //如果查找到key为null的键值对对象则更新value
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //添加元素
    addEntry(0, null, value, 0);
    return null;
}

putForNullKey 方法说明 HashMap 是支持处理 null 为 key 的。putForNullKey 方法会便利数组的第一个位置，从链表中去查找key 为 null 的对象，如果存在就更新 value，如果不存在就添加一条数据。

6.3 indexFor

static int indexFor(int h, int length) {  
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

indexFor 通过 hash 值和数组长度来获取数组索引

HashMap 将长度为 2 的整数次幂，长度减去 1 得到的 2 进制后面的数都为1。这样的做法是无论 hash 值为多少，得到的索引长度会在 0 到 length - 1 之间，更直观点理解成这样处理可以防止索引越界

6.4 hash

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

虽然说产生的 hashCode 不一样，但是经过运算不同的 hash 值也会被分配到相同的索引，而 2 次 hash 的作用就是减少产生碰撞的几率

6.5 addEntry

void addEntry(int hash, K key, V value, int bucketIndex) {
    //当集合大小大于等于扩容临界值并且数组当前索引存在对象才进行扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        //更新数组的长度
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        //更新索引
        bucketIndex = indexFor(hash, table.length);
    }
    //第一次添加会执行这个方法
    createEntry(hash, key, value, bucketIndex);
}

第一次添加数据，肯定不会执行条件判断，所以分析 createEntry 方法

6.5.1 createEntry

void createEntry(int hash, K key, V value, int bucketIndex) {
    //1:获取当前数组索引对应的链表结点
    Entry<K,V> e = table[bucketIndex];
    //2:创建新的结点，并将 next 指向获取的 e 结点，如果为空则 next = null 
    //3:将创建的结点赋值给当前索引
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

6.5.2 resize

void resize(int newCapacity) {
    //获取原来的数组
    Entry[] oldTable = table;
    //获取原数组的长度
    int oldCapacity = oldTable.length;
    //如果原长度已经达到最大值，那么会将扩容临界值设置成最大值并返回
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    //如果没有达到最大值，会创建一个 2 倍大的新数组
    Entry[] newTable = new Entry[newCapacity];
    //扩容
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    //更新 table
    table = newTable;
    //更新扩容临界值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

6.5.3 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) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //通过新的长度计算索引
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[I];
            newTable[i] = e;
            e = next;
        }
    }
}

在扩容中，原数组索引的链表元素有 50% 的几率还在原索引处，这个取决于 hash 值

以上就是 HashMap 的 put 流程

7、HashMap -> get

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);
        return null == entry ? null : entry.getValue();
}

7.1 getForNullKey

private V getForNullKey() {
    //集合为空时返回 null
    if (size == 0) {
        return null;
    }
    //便利数组第 0 个位置
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

put 流程中分析到会将 null 放到数组的第 0 个位置，如果存在返回 value，不存在则返回 null

7.2 getEntry

final Entry<K,V> getEntry(Object key) {
    //集合为空返回 null
    if (size == 0) {
        return null;
    }
    //2次 hash
    int hash = (key == null) ? 0 : hash(key);
    //通过 hash 值和数组长度获取索引，通过索引找到数组中对应的链表，便利链表
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
        e != null;
        e = e.next) {
        Object k;
        if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
    }
    return null;
}

对于 put 流程来说，get 流程非常简单

开篇疑问解答

HashMap 的数据结构是什么样子的？
HashMap 的结构是由数组和链表组成的
hash 碰撞是怎么产生的？HashMap 是如何处理 hash 碰撞？
不同的 key 可能会产生相同的 hash 值，因此产生了 hash 碰撞；HashMap 使用链表来处理 hash 碰撞，同时内部使用了 2次 hash 来减少 hash 碰撞
HashMap 的长度为什么必须是 2 的整数次幂？
HashMap 将长度为 2 的整数次幂，长度减去 1 得到的 2 进制后面的数都为1，在进行索引计算时会将索引的范围限制在 0 至 length - 1 之间，这样也可以防止索引越界

HashMap 1.7 源码分析大致就介绍到这里了，如果有什么写得不对的，可以在下方评论留言，我会第一时间改正。