Java集合系列之HashMap

1,535 阅读7分钟

Java集合系列之HashMap

Hello,大家好,喜欢看我文章的小伙伴应该都知道作者正在写Java并发编程系列的文章,但是今天要插播一些Java集合系列的文章,之后也会一直并行的写Java并发编程系列文章和Java集合系列的文章,因为一直写一个系列的文章实在是比较枯燥。而且这两个系列其实是有关联的,希望大家喜欢。好了,废话少说,今天给大家讲一讲HashMap底层的实现,结构如下:

  1. HashMap底层数据结构
  2. 核心API
  3. 扩容相互(容量,负载因子,2的倍数)
  4. 非线程安全

1. HashMap底层数据结构

HashMap底层是数组加上链表的数据结构,每一个数组的元素通过指针又引出一个链表,链表的尾部指针指向NULL,这个元素的结构如下:

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

可以看到,存储了K和V,然后一个next指针指向下一个元素。

2. 核心API

知道了存储结构是不够的,元素怎么入到这个集合里面呢?下面来看下核心的API,put和get.

put()讲解:

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
        //key为null时,直接丢到table[0]这个数组位置上
            return putForNullKey(value);
        //自己封装的hash方法,对key做完hash后加了高位运算,尽量避免Hash碰撞
        int hash = hash(key);
        //根据hash值`对数组长度取模`,算出应该放入索引为几的数组格子里
        int i = indexFor(hash, table.length);
        //如果这个格子里已经有元素了,那么就遍历执行equals方法,如果equals也一样,就用value替换掉oldValue。返回oldValue
        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;
            }
        }
        //如果这个数组隔离里没有equals一样的,把这个元素加入到链表的头部。
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

当我们往 HashMap 中 put 元素的时候,先根据 key 的 hashCode 重新计算 hash 值,根据 hash 值得到这个元素在数组中的位置(即下标),如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。 还可以看到,当key-value 对时,完全没有考虑 Entry 中的 value,仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。我们完全可以把 Map 集合中的 value 当成 key 的附属,当系统决定了 key 的存储位置之后,value(可以为NULL) 随之保存在那里即可。

这里再顺带提一下,为什么HashMap在扩容时数组的长度必须是2的倍数(默认16),其实这和indexFor()这个方法有关系的,这个方法是根据key的hash值算出在数组对应的索引,大家可能会想到,直接用hash%数组长度不就可以保证元素尽量平均的分配到数组里,避免少的碰撞吗?但是取模的效率是比较低下的,所以这个API的实现如下:

static int indexFor(int h, int length) {  
    return h & (length-1);
}

h & (length-1)要和h%length的效果一样就必须保证length的长度是2的倍数,至于为什么,小弟也不知道,这是算法这块的东西了。而&符号可比%符号效率高的多了。所以大家知道了吧。数组长度为什么必须是2的倍数。 整体上看,当数组长度为 2 的 n 次幂的时候,不同的 key 算得得 index 相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。

稍微总结下put(): 当程序试图将一个key-value对放入HashMap中时,程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value,但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部.

get()讲解:

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

        return null == entry ? null : entry.getValue();
    }
    
    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        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;
    }

其实大家应该自己都可以看懂了,比较easy,从 HashMap 中 get 元素时,首先计算 key 的 hashCode,找到数组中对应位置的某一元素,然后通过 key 的 equals 方法在对应位置的链表中找到需要的元素。

好,存储元素和读取元素来一个总结: 简单地说,HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据 hash 算法来决定其在数组中的存储位置,在根据 equals 方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry 时,也会根据 hash 算法找到其在数组中的存储位置,再根据 equals 方法从该位置上的链表中取出该Entry.

3. 扩容相关(容量,负载因子,2的倍数)

当 HashMap 中的元素越来越多的时候,hash 冲突的几率也就越来越高,因为数组的默认长度是16。所以为了提高查询的效率,就要对 HashMap 的数组进行扩容,数组扩容这个操作也会出现在 ArrayList 中,这是一个常用的操作,而在 HashMap 数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是 resize。

那么 HashMap 什么时候进行扩容呢?当 HashMap 中的元素个数超过(数组大小 XloadFactor)时,就会进行数组扩容,loadFactor的默认值为 0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为 16,那么当 HashMap 中元素个数超过 16X0.75=12 的时候,就把数组的大小扩展为 2X16=32,即扩大一倍(想想前面讲过的2的倍数),然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知 HashMap 中元素的个数,那么预设元素的个数能够有效的提高 HashMap 的性能。

然后顺带提下几个HashMap的构造方法:

  • HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap。
  • HashMap(int initialCapacity):构建一个初始容量为initialCapacity,负载因子为 0.75 的 HashMap。
  • HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap。

负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。默认的0.75其实是一个比较折中的方案了。

4. 非线程安全

稍微提一下,HashMap是非线程安全的,在多线程并发访问的时候,扩容时有可能造成数组的某个元素后的链表形成闭环,所以查询的时候就一直死循环,造成100%利用率。所以,在多线程环境下应该使用ConcurrentHashMap替代之。后面会专门讲解ConcurrentHashMap.此外,关于HashMap为什么会造成这种死循环,因为网上文章比较多我就不多余了,给大家几个传送门:

结语

好了,HashMap算是给大家说完了,后续会继续给大家分享Java集合的相关底层知识。Over,Have a good day!