Java教程

JDK1.8 HashMap源码解读

本文主要是介绍JDK1.8 HashMap源码解读,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

JDK1.8 HashMap源码解读

  • 写作目的
  • 问题合集
    • HashMap的继承与实现
    • HashMap的关键参数
    • HashMap的构造方法
    • HashMap的常见方法

写作目的

本文旨在探究HashMap的源码设计思路,仅供学习交流之用.

问题合集

HashMap的继承与实现

1.:在JDK1.8中,HashMap的继承与实现的关系如何?

:
源码如下:

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

HashMap继承了AbstractMap,实现了Map,Cloneable, Serializable。

利用IDEA的yFiles得效果图如下:
在这里插入图片描述
2.:接第一问,为何这么设计

: 首先关于AbstractMap,其实现了Map接口,继承此abstract类可以避免重复造轮子,提高代码的重用率;其次关于Cloneable,查看它的源码后可以发现其并没有声明任何的方法,实现 Cloneable是来表示该对象能被克隆,能使用Object.clone()方法。如果没有实现 Cloneable的类对象调用clone()就会抛出CloneNotSupportedException;最后关于Serializable,与Cloneable类似,内部也没有方法,实现Serializable也是为了确保HashMap类本身能够实现序列化。

HashMap的关键参数

1.描述 DEFAULT_INITIAL_CAPACITY

     /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

HashMap的初始容量,左移4位即是1*2^4 = 16,

那为什么要设置为16,可以初始化是指定么?

其实是可以的,并且是推荐的 [阿里巴巴开发手册]:
alibaba开发手册
在这里插入图片描述
具体见 HashMap容量为什么设置初始值为16

2.描述 MAXIMUM_CAPACITY

     /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

HashMap的最大容量,如需指定,必须为2的n次幂,且小于初始的2^30

3.描述 DEFAULT_LOAD_FACTOR
:默认的负载因子, 当元素的总个数>当前数组的长度 * 负载因子。数组会进行扩容,扩容为原来的两倍。

至于为什么设置为0.75,是因为负载因子太小了浪费空间并且会发生更多次数的resize,太大了哈希冲突增加会导致性能不好,所以0.75只是一个折中的选择,和泊松分布没有什么关系,本质上就是trade off–(权衡之后的折中方案)。具体见
HashMap defaultLoadFactor = 0.75和泊松分布没有关系.

为什么每次扩容都是原来的两倍?
JDK8因为巧妙的设计,性能有了大大的提升:由于数组的容量是以2的幂次方扩容的,那么一个Entity在扩容时,新的位置要么在原位置,要么在原长度+原位置的位置。原因如下图:
在这里插入图片描述
数组长度变为原来的2倍,表现在二进制上就是多了一个高位参与数组下标确定。此时,一个元素通过hash转换坐标的方法计算后,恰好出现一个现象:最高位是0则坐标不变,最高位是1则坐标变为“10000+原坐标”,即“原长度+原坐标”。如下图:
在这里插入图片描述
详见HashMap的扩容机制

4.描述 TREEIFY_THRESHOLD

 /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
    static final int TREEIFY_THRESHOLD = 8;

TREEIFY,即树形化。TREEIFY_THRESHOLD,表树化域值: 默认值为 8 。表示在一个node(Table)节点下的值的个数大于8(链表的长度大于8)时候,会将链表转换成为红黑树。

那为什么是8呢?
首先需要明确的是treeify不是一个廉价的操作,因此需要避免频繁的树形化,其次,链表太长也会影响查找效率,所以我们需要找到一个合适的值。
TREEIFY_THRESHOLD的寻找过程和泊松分布有关。记住结论:8个键值对同时存在于同一个桶(bin)的概率只有 0.00000006,具体见源码中的如下片段

 /* Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million
     * /

因此认为8是一个比较合理的值

5.描述 UNTREEIFY_THRESHOLD

/**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
    static final int UNTREEIFY_THRESHOLD = 6;

桶的链表还原阈值:即 红黑树转为链表的阈值,当在扩容(resize())时(此时HashMap的数据存储位置会重新计算),在重新计算存储位置后,当原有的红黑树内数量 < 6时,则将 红黑树转换成链表

6.描述 MIN_TREEIFY_CAPACITY

 /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

最小树形化容量阈值:即 当哈希表中的容量 > 该值时,才允许树形化链表 (即 将链表 转换成红黑树)
否则,若桶内元素太多时,则直接扩容,而不是树形化

为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD

HashMap的构造方法

1.初始化容量和负载因子,原16和0.75

 public HashMap(int initialCapacity, float loadFactor)

2.仅初始化容量

public HashMap(int initialCapacity)

3.无参构造函数

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

4.指定K,V类型

public HashMap(Map<? extends K, ? extends V> m)

HashMap的常见方法

方法名返回值作用
put(k,v)void插入一个k,v键值对
get(k)v提供k,计算hash值后获取v或返回空
entrySet()Set<Map.Entry<K,V>>返回entrySet的存储值
containsKey(k)boolean是否含有k
keySet()Set < k >返回ket的集合
clear()void清空hashmap
containsValue(v)boolean是否含有value
isEmpty()boolean是否为空
size()int容量
values()Collection返回v的集合(不会去重!)
cloneObject浅拷贝
compute(K key, BiFunction remappingFunction)V对 hashMap 中指定 key 的值进行重新计算
computeIfAbsent(K key, BiFunction remappingFunction)V如果k不存在就重新计算,如果存在就当无事发生
computeIfPresent(K key, BiFunction remappingFunction)k对 hashMap 中指定 key 的值进行重新计算,前提是该 key 存在于 hashMap 中。
putAll(Map<? extends K, ? extends V> m)void将所有键/值对添加到 hashMap 中(将一个hashmap中的值填入本map中,重复的key会被忽略而不是覆盖)
merge(K key, V value,BiFunction<? super V, ? super V, ? extends V> remappingFunction)V1.key不存在,则插入新值。2.key存在,value不存在,则插入指定的value.3.value如果存在,则返回经过计算后的值
这篇关于JDK1.8 HashMap源码解读的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!