转载

Hashmap源码解析-构造函数

#### 构造函数

构造函数:

默认构造函数什么都不做，只是将加载因子设为默认加载因子。

有初始值大小的构造函数，

会将threshold设置为大于输入参数且最近的2的整数次幂的数,比如10，设置阈值16.

即使有initialCapacity参数的构造，也是设置threshold，不会现在设置cap，如要设置cap就需要new资源了，而原理是在等真的插入的时候才去通过resize操作申请内存资源, 见resize.md,put.md

重点:

1.参数最大容量,默认的加载因子,加载因子,阈值

2.哈希桶, Node [] table, 是Node数组, 存放链表, 长度初始化时为0, 之后是2的N次方

3.loadFactor和threshold的关系

4.tableSizeFor函数的原理, 见下面解析

默认参数和构造函数源码:

//最大容量 2的30次方

static final int MAXIMUM_CAPACITY = 1 << 30;

//默认的加载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

//哈希桶，存放链表。 长度是2的N次方，或者初始化时为0.

transient Node<K,V>[] table;

//加载因子，用于计算哈希表元素数量的阈值。  threshold = 哈希桶.length * loadFactor;

final float loadFactor;

//哈希表内元素数量的阈值，当哈希表内元素数量超过阈值时，会发生扩容resize()。

int threshold;

public HashMap() {

    //默认构造函数，赋值加载因子为默认的0.75f

    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

}

public HashMap(int initialCapacity) {

    //指定初始化容量的构造函数

    this(initialCapacity, DEFAULT_LOAD_FACTOR);

}

//同时指定初始化容量 以及 加载因子， 用的很少，一般不会修改loadFactor

public HashMap(int initialCapacity, float loadFactor) {

    //边界处理

    if (initialCapacity < 0)

        throw new IllegalArgumentException("Illegal initial capacity: " +

                                            initialCapacity);

    //初始容量最大不能超过2的30次方

    if (initialCapacity > MAXIMUM_CAPACITY)

        initialCapacity = MAXIMUM_CAPACITY;

    //显然加载因子不能为负数

    if (loadFactor <= 0 || Float.isNaN(loadFactor))

        throw new IllegalArgumentException("Illegal load factor: " +

                                            loadFactor);

    this.loadFactor = loadFactor;

    //设置阈值为  >= 初始化容量的最近的2的n次方的值

    this.threshold = tableSizeFor(initialCapacity);

}

//新建一个哈希表，同时将另一个map m 里的所有元素加入表中

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

    this.loadFactor = DEFAULT_LOAD_FACTOR;

    putMapEntries(m, false);

}

##### tableSizeFor函数的原理

tableSizeFor的功能（不考虑大于最大容量的情况）是返回大于输入参数且最近的2的整数次幂的数。比如10，则返回16.

static final int tableSizeFor(int cap) {

    int n = cap - 1;

    n |= n >>> 1;

    n |= n >>> 2;

    n |= n >>> 4;

    n |= n >>> 8;

    n |= n >>> 16;

    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

}

先来分析有关n位操作部分：先来假设n的二进制为01xxx…xxx。接着

对n右移1位：001xx…xxx，再位或：011xx…xxx

对n右移2为：00011…xxx，再位或：01111…xxx

此时前面已经有四个1了，再右移4位且位或可得8个1

同理，有8个1，右移8位肯定会让后八位也为1。

综上可得，该算法让最高位的1后面的位全变为1。

最后再让结果n+1，即得到了2的整数次幂的值了。

现在回来看看第一条语句：

int n = cap - 1;

让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000，十进制数值为8。如果不对它减1而直接操作，将得到答案10000，即16。显然不是结果。减1后二进制为111，再进行操作则会得到原来的数值1000，即8。

##### loadFactor和threshold的关系?

HashMap中size表示当前共有多少个KV对，capacity表示当前HashMap的容量是多少，默认值是16，每次扩容都是成倍的。loadFactor是装载因子，当Map中元素个数超过loadFactor capacity的值时，会触发扩容。loadFactor capacity可以用threshold表示。

好多地方都说threshold = loadFactor capacity, 但有初始值的初始化的时候，threadshold由tableSizeFor函数获得，这个地方之后 threshold 是什么时间进行的调整，应该是之后调整是根据loadFactor capacity。

原文 https://techwei.cn/2019/05/26/hashmap/构造函数/

正文到此结束