Open xzhuz opened 6 years ago
最近从繁忙的工作中抽身，偶得一丝空闲，就来钻研钻研Java源码“大佬”HashMap。 学到老活到老，学无止境。
最近从繁忙的工作中抽身，偶得一丝空闲，就来钻研钻研Java源码“大佬”HashMap。
学到老活到老，学无止境。
HashMap是Java源码中非常优秀的源码，涉及到很多的概念，算法、红黑树、数组、链表... 之前硬着头皮去结交这位源码“大佬”，但没有掌握到方法精髓的我最终也只是和这位“大佬”成为了点头之交。那么，为了这次不也只是点头之交，先来梳理一下HashMap的一些概念。
Hash函数，可译为“散列函数”或“哈希函数”。就是把任意长度的输入，通过散列算法，映射成固定长度的输出，该输出就是散列值。这种转换一张压缩转换，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
a. 直接寻址法
取关键字或关键字的某个线性函数的值为散列地址。即H(key) = key 或 H(key) = a.key + b;
b. 数字分析法
c. 平方取中法：
d. 折叠法：
e. 随机数法：
f. 除留余数法：
散列表（Hash Table）是根据关键码值(key value)而直接进行访问的数据结构。他通过关键码值映射到表中的一个位置来访问记录，以加快查找速度。这个映射函数叫做散列函数，存放记录数组叫做
A bucket is each element in the Array you are referring to.
桶就是数组中的每个元素。
HashMap初始化时，会创建一个长度为capacity的Entry数组。数组中每个存储元素的位置就被称为桶(bucket)。每个bucket都会有指定索引，可以通过索引快速访问bucket。
桶(bucket)
无论何时，HashMap 的每个“桶”只存储一个元素（也就是一个 Entry），由于 Entry 对象可以包含一个引用变量（就是 Entry 构造器的的最后一个参数）用于指向下一个 Entry，因此可能出现的情况是：HashMap 的 bucket 中只有一个 Entry，但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链。如下图。
引用 https://blog.csdn.net/wenyiqingnianiii/article/details/52204136 扩展 https://stackoverflow.com/questions/37959941/what-exactly-is-bucket-in-hashmap
引用 https://blog.csdn.net/wenyiqingnianiii/article/details/52204136
扩展 https://stackoverflow.com/questions/37959941/what-exactly-is-bucket-in-hashmap
默认容量， 初始值为16。必须是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
最大容量，值1 << 30，2的30次方。
1 << 30
当桶的容量达到这个值的时候，就不会进行扩容。
static final int MAXIMUM_CAPACITY = 1 << 30;
默认加载因子，值为0.75f。
0.75f
static final float DEFAULT_LOAD_FACTOR = 0.75f
桶的树化阀值。默认为8。
当桶的元素个数超过这个值时，需要使用会使用红黑树来代替链表存储元素。(Java 8 新增)
static final int TREEIFY_THRESHOLD = 8;
一个树的链表还原阈值。默认为6。
当扩容时，桶中元素个数小于这个值就会把树形的桶元素 还原（切分）为链表结构。
static final int UNTREEIFY_THRESHOLD = 6;
当哈希表中的容量大于这个值时，表中的桶才能进行树形化 否则桶内元素太多时会扩容，而不是树形化 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD，即默认64.
static final int MIN_TREEIFY_CAPACITY = 64;
HashMap中的Node为一个bucket。她包含四个属
Node
bucket
分析HashMap的一些概念
HashMap是Java源码中非常优秀的源码，涉及到很多的概念，算法、红黑树、数组、链表... 之前硬着头皮去结交这位源码“大佬”，但没有掌握到方法精髓的我最终也只是和这位“大佬”成为了点头之交。那么，为了这次不也只是点头之交，先来梳理一下HashMap的一些概念。
1. 散列函数
Hash函数，可译为“散列函数”或“哈希函数”。就是把任意长度的输入，通过散列算法，映射成固定长度的输出，该输出就是散列值。这种转换一张压缩转换，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
a. 直接寻址法
取关键字或关键字的某个线性函数的值为散列地址。即H(key) = key 或 H(key) = a.key + b;
b. 数字分析法
c. 平方取中法：
d. 折叠法：
e. 随机数法：
f. 除留余数法：
（2） 散列表(哈希表)
散列表（Hash Table）是根据关键码值(key value)而直接进行访问的数据结构。他通过关键码值映射到表中的一个位置来访问记录，以加快查找速度。这个映射函数叫做散列函数，存放记录数组叫做
（3）桶
桶就是数组中的每个元素。
HashMap初始化时，会创建一个长度为capacity的Entry数组。数组中每个存储元素的位置就被称为
桶(bucket)。每个bucket都会有指定索引，可以通过索引快速访问bucket。 无论何时，HashMap 的每个“桶”只存储一个元素（也就是一个 Entry），由于 Entry 对象可以包含一个引用变量（就是 Entry 构造器的的最后一个参数）用于指向下一个 Entry，因此可能出现的情况是：HashMap 的 bucket 中只有一个 Entry，但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链。如下图。
2. 成员属性
(1) DEFAULT_INITIAL_CAPACITY
默认容量， 初始值为16。必须是2的幂
(2) MAXIMUM_CAPACITY
最大容量，值
1 << 30，2的30次方。当桶的容量达到这个值的时候，就不会进行扩容。
(3) DEFAULT_LOAD_FACTOR
默认加载因子，值为
0.75f。(4) TREEIFY_THRESHOLD
桶的树化阀值。默认为8。
当桶的元素个数超过这个值时，需要使用会使用红黑树来代替链表存储元素。(Java 8 新增)
(6) UNTREEIFY_THRESHOLD
一个树的链表还原阈值。默认为6。
当扩容时，桶中元素个数小于这个值就会把树形的桶元素 还原（切分）为链表结构。
(7) MIN_TREEIFY_CAPACITY
当哈希表中的容量大于这个值时，表中的桶才能进行树形化 否则桶内元素太多时会扩容，而不是树形化 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD，即默认64.
3. Node
HashMap中的
Node为一个bucket。她包含四个属