01.HashMap原理
0.什么是Hash
哈希：英文是Hash，也称为散列 基本原理就是把任意长度输入，转化为固定长度输出 这个映射的规则就是Hash算法，而原始数据映射的二进制串就是Hash值 Hash的特点 1.从Hash值不可以反向推导出原始数据 2.输入数据的微小变化会得到完全不同的Hash值，相同的数据一定可以得到相同的值 3.哈希算法的执行效率要高效，长的文本也能快速计算Hash值 4.Hash算法的冲突概率要小 由于Hash原理就是将输入空间映射成Hash空间，而Hash空间远远小于输入空间，根据抽屉原理，一定存在不同输出有相同的映射 抽屉原理- 桌子上有10个苹果，将其放在9个抽屉里面，那必有一个抽屉不少于2个苹果
1.HashMap 集合简介
HashMap 基于哈希表的 Map 接口实现，是以 key-value 存储形式存在，即主要用来存放键值对。HashMap 的实现不是同步的，这意味着它不是线程安全的。它的 key、value 都可以为 null，此外，HashMap 中的映射不是有序的。 jdk1.8 之前 HashMap 由 数组 + 链表 组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突（两个对象调用的 hashCode 方法计算的哈希值经哈希函数算出来的地址被别的元素占用）而存在的（“拉链法”解决冲突）。 jdk1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8 ）并且当前数组的长度大于 64 时，此时此索引位置上的所有数据改为使用红黑树存储。 补充：将链表转换成红黑树前会判断，即便阈值大于 8，但是数组长度小于 64，此时并不会将链表变为红黑树，而是选择逬行数组扩容。 这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率，因为红黑树需要逬行左旋， 右旋，变色这些操作来保持平衡。同时数组长度小于64时，搜索时间相对要快些。所以结上所述为了提高性能和减少搜索时间，底层 阈值大于8并且数组长度大于64时，链表才转换为红黑树，具体可以参考 treeifyBin() 方法。 当然虽然增了红黑树作为底层数据结构，结构变得复杂了，但是阈值大于 8 并且数组长度大于 64 时，链表转换为红黑树时，效率也变 的更高效。 小结： HashMap 特点：- 存储无序的。
- 键和值位置都可以是 null，但是键位置只能存在一个 null。
- 键位置是唯一的，是底层的数据结构控制的。
- jdk1.8 前数据结构是链表+数组，jdk1.8 之后是链表+数组+红黑树。
- 阈值（边界值）> 8 并且数组长度大于 64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。
2.HashMap的原理
put方法原理-简单版
put方法原理-详细版
说明：- size 表示 HashMap 中键值对的实时数量，注意这个不等于数组的长度。
- threshold（临界值）= capacity（容量）* loadFactor（负载因子）。这个值是当前已占用数组长度的最大值。size 超过这个值就重新 resize（扩容），扩容后的 HashMap 容量是之前容量的两倍
- 相等：将后添加的数据的 value 覆盖之前的 value。
- 不相等：继续向下和其他的数据的 key 进行比较，如果都不相等，则划出一个结点存储数据，如果结点长度即链表长度大于阈值 8 并且数组长度大于 64 则将链表变为红黑树。
什么是Hash碰撞
只要两个元素的 key，通过hash算法， 计算的哈希码值相同就会发生哈希碰撞解决Hash碰撞的方法
a. 链地址法：将哈希表的每个单元作为链表的头结点，所有哈希地址为 i 的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。原理就是发生冲突，新加进来的，就放在链表的尾部 HashMap 就是使用链地址法来解决冲突的- jdk8 之前使用链表解决哈希碰撞
- jdk8之后使用链表 + 红黑树解决哈希碰撞
hashmap的hash算法
先调用hashcode,拿到hashcode,再经过扰乱算法，重新得到hashcode，然后再跟 （length - 1）按位与，找到存储的桶 计算索引的算法表达式 hashCode & （length - 1） length是数组的长度扰乱算法(重新计算hash值)
引入红黑树的原因
1.提高查询效率 2.假如单链表有n个元素，遍历的时间复杂度就是O(n)，完全失去了它的优势。 针对这种情况，jdk1.8 中引入了红黑树（最坏查找时间复杂度为 O(logn)）来优化这个问题。当链表长度很小的时候，即使遍历，速度 也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。扩容原理
为什么需要扩容？ 当元素越来越多的时候，hashMap的查找速度就从O(1)升到O(n)，导致链化严重， 为了解决冲突带来的查询效率的下降，因此需要扩容[扩容是一个很不好的动作] 什么时候才需要扩容？ 当 HashMap 中的元素个数超过数组大小(数组长度)*loadFactor(负载因子)时，就会进行数组扩容，loadFactor 的默认值是 0.75。 HashMap 的扩容是什么？ 进行扩容，会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。 HashMap 在进行扩容时，使用的 rehash 方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n - 1) & hash 的结果相比， 只是多了一个 bit 位，所以结点要么就在原来的位置，要么就被分配到 “原位置 + 旧容量” 这个位置。 扩容之后所以结点要么就在原来的位置，要么就被分配到 “原位置 + 旧容量” 这个位置。 因此，我们在扩充 HashMap 的时候，不需要重新计算 hash，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就可以了，- 是 0 的话索引没变
- 是 1 的话索引变成 “原位置 + 旧容量”
3.HashMap的继承关系
HashMap继承关系如下图所示： 说明：- Cloneable 空接口，表示可以克隆。创建并返回 HashMap 对象的一个副本。
- Serializable 序列化接口。属于标记性接口。HashMap 对象可以被序列化和反序列化。
- AbstractMap 父类提供了 Map 实现接口。以最大限度地减少实现此接口所需的工作。
通过上述继承关系我们发现一个很奇怪的现象，
就是 HashMap 已经继承了AbstractMap 而 AbstractMap 类实现了Map 接口
那为什么 HashMap 还要在实现 Map 接口呢？同样在 ArrayList 中 LinkedLis 中都是这种结构。
据 Java 集合框架的创始人 Josh Bloch 描述，这样的写法是一个失误。
在 Java 集合框架中，类似这样的写法很多，最开始写 Java 集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。
显然的，jdk 的维护者，后来不认为这个小小的失误值得去修改，所以就这样保留下来了。4.HashMap 集合类的成员
成员变量
1.DEFAULT_INITIAL_CAPACITY 集合的初始化容量（必须是 2 的 n 次幂）// 默认的初始容量是16 1 << 4 相当于 1*2的4次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;为什么必须是 2 的 n 次幂？
当向 HashMap 中添加一个元素的时候，需要根据 key 的 hash 值，去确定其在数组中的具体位置。HashMap 为了存取高效，减少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现的关键就在把数据存到哪个链表中的算法。 这个算法实际就是取模，hash % length，计算机中直接求余效率不如位移运算。 所以源码中做了优化，使用 hash & (length - 1)，而实际上 hash % length 等于 hash & ( length - 1) 的前提是- length 是 2 的 n 次幂
如果输入值不是 2 的幂比如 10 会怎么样?
当在实例化 HashMap 实例时，如果给定了 initialCapacity，由于 HashMap 的 capacity 必须都是 2 的幂- 因此这个方法(tableSizeFor)用于找到大于等于 initialCapacity 的最小的 2 的幂
- 例如 传入 10，得到16，传入 30，得到32
// 构造一个带指定初始容量和默认负载因子（0.75)的空 HashMap。
HashMap(int initialCapacity)tableSizeFor
这个算法就是经过先- 右移得到结果
- 再按位或 原来的值
0000 1001
0000 1101
0000 1111
0001 0000
/**
* Returns a power of two size for the given target capacity.
*/
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;
}- 1.int n = cap - 1;
- 2.如果 n 这时为 0 了（经过了cap - 1后），则经过后面的几次无符号右移依然是 0，最后返回的 capacity 是1（最后有个 n + 1 的操作）。
- 3.注意：容量最大也就是 32bit 的正数，因此最后 n |= n >>> 16; 最多也就 32 个 1（但是这已经是负数了，在执行 tableSizeFor 之前，对 initialCapacity 做了判断，如果大于MAXIMUM_CAPACITY(2 ^ 30)，则取 MAXIMUM_CAPACITY。如果等于MAXIMUM_CAPACITY，会执行位移操作。所以这里面的位移操作之后，最大 30 个 1，不会大于等于 MAXIMUM_CAPACITY。30 个 1，加 1 后得 2 ^ 30）。
this.threshold = tableSizeFor(initialCapacity);static final float DEFAULT_LOAD_FACTOR = 0.75f;static final int MAXIMUM_CAPACITY = 1 << 30; // 2的30次幂// 当桶（bucket）上的结点数大于这个值时会转为红黑树
static final int TREEIFY_THRESHOLD = 8;为什么桶中结点个数超过 8 才转为红黑树？
原因:- TreeNodes 占用空间是普通 Nodes 的两倍
- 当 hashCode 离散性很好的时候，树型 桶 用到的概率非常小
- 当用户使用不理想情况下随机 hashCode 算法下所有 bin 中结点的分布频率会遵循泊松分布，一个 bin 中链表长度达
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:
翻译：因为树结点的大小大约是普通结点的两倍，所以我们只在箱子包含足够的结点时才使用树结点(参见TREEIFY_THRESHOLD)。
当它们变得太小（由于删除或调整大小）时，就会被转换回普通的桶。在使用分布良好的用户 hashCode 时，很少使用树箱。
理想情况下，在随机哈希码下，箱子中结点的频率服从泊松分布
(http://en.wikipedia.org/wiki/Poisson_distribution) ，默认调整阈值为0.75，平均参数约为0.5，尽管由
于调整粒度的差异很大。忽略方差，列表大小k的预朗出现次数是(exp(-0.5) * pow(0.5, k) / factorial(k))。
第一个值是：
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// 当桶（bucket）上的结点数小于这个值，树转为链表
static final int UNTREEIFY_THRESHOLD = 6;// 桶中结构转化为红黑树对应的数组长度最小的值
static final int MIN_TREEIFY_CAPACITY = 64;- table 用来初始化（必须是二的n次幂）(重点)
// 存储元素的数组
transient Node[] table; - jdk8 之前数组类型是 Entry
- jdk1.8 之后是 Node
- HashMap 中存放元素的个数(重点)
// 存放元素的个数，注意这个不等于数组的长度
transient int size;// map修改元素的次数，如删除和增加，但是对同一个位置进行修改value，不增加
transient int modCount; // 临界值 当实际大小（容量*负载因子）超过临界值时，会进行扩容
int threshold;// 负载因子
final float loadFactor;- loadFactor 是用来衡量 HashMap 满的程度，表示HashMap的疏密程度，影响 hash 操作到同一个数组位置的概率，计算
- loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。
- 当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时，表示 HashMap 太挤了，需要扩容，而扩容这个过程涉到
// 构造方法，构造一个带指定初始容量和负载因子的空HashMap
HashMap(int initialCapacity, float loadFactor);为什么加载因子是 0.75？
- loadFactor 越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加
- loadFactor 越小，也就是趋近于0，数组中存放的数据(entry)也就越少，也就越稀疏。
- 所以既兼顾数组利用率又考虑链表不要太多，经过大量测试 0.75 是最佳方案。这个是官方进行大量测试的最佳方案
例如：负载因子是0.4。 那么16*0.4--->6 如果数组中满6个空间就扩容会造成数组利用率太低了。
负载因子是0.9。 那么16*0.9--->14 那么这样就会导致链表有点多了，导致查找元素效率低。Node
这个是数组里面的每个节点，是里面的一个静态内部类
static class Node implements Map.Entry {
final int hash; // 经过扰乱算法获取到的 hash值
final K key; // key
V value; // key
Node next; // 下一个节点，用于链表，下一个节点不为空，说明当前节点是 链表桶或者树桶 构造方法
HashMap 中重要的4个构造方法，它们分别如下： 1.HashMap()- 构造一个空的HashMap，默认初始容量（16）和默认负载因子（0.75）。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 将默认的负载因子0.75赋值给loadFactor，并没有创建数组
}- 构造一个具有指定的初始容量和默认负载因子（0.75）HashMap 。
// 指定“容量大小”的构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}- 构造一个具有指定的初始容量和负载因子的 HashMap。
/*
指定“容量大小”和“负载因子”的构造函数
initialCapacity：指定的容量
loadFactor:指定的负载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
// 判断初始化容量initialCapacity是否小于0
if (initialCapacity < 0)
// 如果小于0，则抛出非法的参数异常IllegalArgumentException
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
// 判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
// 如果超过MAXIMUM_CAPACITY，会将MAXIMUM_CAPACITY赋值给initialCapacity
initialCapacity = MAXIMUM_CAPACITY;
// 判断负载因子loadFactor是否小于等于0或者是否是一个非数值
if (loadFactor <= 0 || Float.isNaN(loadFactor))
// 如果满足上述其中之一，则抛出非法的参数异常IllegalArgumentException
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
// 将指定的负载因子赋值给HashMap成员变量的负载因子loadFactor
this.loadFactor = loadFactor;
// 根据 算法 返回一个 比指定初始化容量大的最小的2的n次幂 赋值给 扩容阈值
this.threshold = tableSizeFor(initialCapacity);
}
// 最后调用了tableSizeFor，来看一下方法实现：
/*
返回比指定初始化容量大的最小的2的n次幂
*/
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;
}
this.threshold = tableSizeFor(initialCapacity)tableSizeFor(initialCapacity)判断指定的初始化容量是否是2的n次幂，如果不是那么会变为比指定初始化容量大的最小的2的n次幂。
但是注意，在tableSizeFor方法体内部将计算后的数据返回给调用这里了，并且直接赋值给threshold边界值了。
有些人会觉得这里是一个bug，应该这样书写：
this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;
这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）。
但是请注意，在jdk8以后的构造方法中，并没有对table这个成员变量进行初始化，
table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。- 包含另一个 “Map” 的构造函数
// 构造一个映射关系与指定 Map 相同的新 HashMap。
public HashMap(Map<? extends K, ? extends V> m) {
// 负载因子loadFactor变为默认的负载因子0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//获取参数集合的长度
int s = m.size();
if (s > 0) {
//判断参数集合的长度是否大于0，说明大于0
if (table == null) { // 判断table是否已经初始化
// 未初始化，s为m的实际元素个数
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
// 计算得到的t大于阈值，则初始化阈值
if (t > threshold)
threshold = tableSizeFor(t);
}
// 已初始化，并且m元素个数大于阈值，进行扩容处理
else if (s > threshold)
resize();
// 将m中的所有元素添加至HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}成员方法
hash方法
很多方法都用到了，比如put方法- 就是获取到key的hashcode，然后进行一个扰乱算法获取一个新的hash值
- 后面会用这个新的hash值，来算出该数据应该存在哪个桶
// 扰动函数
// 作用：如何table比较短的时候，让key的hash值得高16位也参加路由运算
// 异或：相同为0，不同返回1
// h = 0b 0010 0101 1010 1100 0011 1111 0010 1110
// 0b 0010 0101 1010 1100 0011 1111 0010 1110 [h]
// ^
// 0b 0000 0000 0000 0000 0010 0101 1010 1100 [h >>> 16]
// => 0010 0101 1010 1100 0001 1010 1000 0010
// 在 table 还不是很长的情况下，让高16位也参与进来，为了减少冲突和碰撞
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}- key.hashCode()；返回散列值也就是 hashcode，假设随便生成的一个值。
- n 表示数组初始化的长度是 16。
- &（按位与运算）：运算规则：相同的二进制数位上，都是 1 的时候，结果为 1，否则为0。
- ^（按位异或运算）：运算规则：相同的二进制数位上，数字相同，结果为 0，不同为 1。
- 高 16bit 不变，低 16bit 和高 16bit 做了一个异或（得到的 hashCode 转化为 32 位二进制，前 16 位和后 16 位低 16bit 和高 16bit 做了一个异或）。
为什么要用高十六位和低十六位进行异或？(扰乱算法)
如果当 n 即数组长度很小，假设是 16 的话，那么 n - 1 即为 1111 ，这样的值和 新的hash值 直接做按位与操作，实际上只使用了哈希
值的后 4 位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解 决了这个问题。 就是减少hash冲突，更加散列-- 高位一直变化，但是数据长度很短， n - 1 即为 1111 ，得出来的结果就是一样的
1010 0001
0000 1111
------
1110 0001
0000 1111 增加方法put分析 - putVal(重点)
1.就是获取到key的hashcode，然后进行一个扰乱算法获取一个新的hash值
2.然后判断当前数组table是否为空，为空就调用resize，进行初始化，就是一个哈希表的懒加载
3.根据新的hash值，根据 (n - 1) & hash 计算出 数据存在哪个桶
3.1如果桶上没有碰撞冲突，则直接插入
3.2如果有碰撞，分别在数组，链表桶，树桶，三种情况来判断
3.2.1 如果在数组上的值，后面就进行新值替换旧值
3.2.2 如果是属于 树桶的节点，就调用树桶的方法解决冲突
3.3.3 如果的链表桶的冲突，就遍历链表
3.3.3.1 如果遍历到最后都没有找到 key值一样的，就再链表新插入一个节点
接着判断链表长度是否大于 8, 就调用方法判断是否扩容还是转为红黑树
3.3.3.2 如果在链表上找到相同key值的，后面就进行新值替换旧值
3.3 进行前面可能存在的两种情况之一的，新值替换旧值
4.修改次数增加，替换Node元素替换不算
5.如果当前map里面元素个数+1 的结果 > 扩容阈值，就进行扩容public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 扰动函数
// 作用：如何table比较短的时候，让key的hash值得高16位也参加路由运算
// 异或：相同为0，不同返回1
// h = 0b 0010 0101 1010 1100 0011 1111 0010 1110
// 0b 0010 0101 1010 1100 0011 1111 0010 1110 [h]
// ^
// 0b 0000 0000 0000 0000 0010 0101 1010 1100 [h >>> 16]
// => 0010 0101 1010 1100 0001 1010 1000 0010
// 在 table 还不是很长的情况下，让高16位也参与进来，为了减少冲突和碰撞
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// put的 核心方法
// hash：key的hash值
// key：key
// value: value
// onlyIfAbsent：如果为true，则不要更改现有值
// evict：如果为false，则表处于创建模式。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab：引用当前hashMap的散列表
// p：当前散列表的元素
// n：表示当前散列表的长度
// i：表示路由寻址的结果
Node[] tab; Node p; int n, i;
// 延迟初始化逻辑，第一次调用 putVal 的时候会初始化hashMap对象中最耗费内存的散列表
// 如果 table 为null，或者长度为0，就开始创建
if ((tab = table) == null || (n = tab.length) == 0)
// 第一次插入数据的时候才会初始化,
n = (tab = resize()).length;
// 最简单的一种情况，寻址找到的桶位，刚好是 null 此时就直接赋值到计算的位置
// tab 和 n 在上一个 if 赋值
// 执行一次路由运算 (n - 1) & hash] 得到hash的地址
// 如果 tab 中没有这个元素或者等于null
if ((p = tab[i = (n - 1) & hash]) == null)
// 创建一个新的Node 就把 k-v 封装一个Node放在 tab的i位置
tab[i] = newNode(hash, key, value, null);
// 此时可能是数组、可能是链表、可能是红黑树
else {
// e：不为null的话，找到了一个与当前要插入的k-v一致的元素
// k：表示临时的k
Node e; K k;
// p：在另一个分支if中获得
// 表示桶为中的该元素，与你当前插入的元素的key完全一致，后续进行替换操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// p：已经树化了
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
//是链表
else {
// 链表的头元素与要插入的key不一致，
for (int binCount = 0; ; ++binCount) {
// 如果到末尾了，就把p加到最后一个位置
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果当前链表的大小 binCount 大于基准树化的值，就执行树化操作
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 树化操作
treeifyBin(tab, hash);
break;
}
// 如何 hash 相等 且key也相等，需要进行替换操作
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 循环
p = e;
}
}
// 如果e不为null，找到老的值，返回
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
// 把新的值覆写
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//修改次数增加，替换Node元素替换不算
++modCount;
// 如果table大小大于阈值，就执行 resize()，进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} treeifyBin树化方法
将链表转换为红黑树 treeifyBin() 结点添加完成之后判断此时结点个数是否大于 TREEIFY_THRESHOLD 临界值 8，如果大于则进判断是扩容还是转为红黑树 则将链表转换为红黑树，转换红黑树的方法 treeifyBin，整体代码如下：if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//转换为红黑树 tab表示数组名 hash表示哈希值
treeifyBin(tab, hash);1.传整个hashmap的数组，还有相应的链表大于8的hash值过来
2.判断如果hashmap的元素没有大于64就进行扩容
3.根据hash值，根据寻址公式，hashmap找到相应的桶
然后遍历全部链表
3.1 将链表节点转为 树节点
3.2 然后将树节点连接起来，我的next(下一个)是你，你的prev(前一个)是我
3.3 然后将树桶替换原来索引位置的链表桶，然后再进行树化 (左旋转，右旋转)/*
替换指定哈希表的索引处桶中的所有链接结点，除非表太小，否则将修改大小。
Node[] tab = tab 数组名
int hash = hash表示哈希值
*/
final void treeifyBin(Node[] tab, int hash) {
int n, index; Node e;
/*
如果当前数组为空或者数组的长度小于进行树形化的阈值(MIN_TREEIFY_CAPACITY = 64)，就去扩容。而不是将结点变为红黑树。
目的：如果数组很小，那么转换红黑树，然后遍历效率要低一些。这时进行扩容，那么重新计算哈希值，链表长度有可能就变短了，
数据会放到数组中，这样相对来说效率高一些。
*/
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//扩容方法
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
/*
1）执行到这里说明哈希表中的数组长度大于阈值64，开始进行树形化
2）e = tab[index = (n - 1) & hash]表示将数组中的元素取出赋值给e，e是哈希表中指定位置桶里的链表结点，从第一个开始
*/
// hd：红黑树的头结点 tl：红黑树的尾结点
TreeNode hd = null, tl = null;
do {
// 新创建一个树的结点，内容和当前链表结点e一致
TreeNode p = replacementTreeNode(e, null);
if (tl == null)
hd = p; // 将新创键的p结点赋值给红黑树的头结点
else {
p.prev = tl; // 将上一个结点p赋值给现在的p的前一个结点
tl.next = p; // 将现在结点p作为树的尾结点的下一个结点
}
tl = p;
/*
e = e.next 将当前结点的下一个结点赋值给e，如果下一个结点不等于null
则回到上面继续取出链表中结点转换为红黑树
*/
} while ((e = e.next) != null);
/*
让桶中的第一个元素即数组中的元素指向新建的红黑树的结点，以后这个桶里的元素就是红黑树
而不是链表数据结构了
*/
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
- 根据哈希表中元素个数确定是扩容还是树形化。
- 如果是树形化遍历桶中的元素，将每个链表节点转化为树节点，复制内容，建立起联系。
- 然后让桶中的第一个元素指向新创建的树根结点，替换桶的链表内容为树形化内容。
扩容方法resize (重点)
第一部分.计算 获取到 扩容之后table数组的大小 扩容之后下次触发扩容阈值
1.1 如果原来的容量大于0,说明已经初始化过了,这是一次正常的扩容
1.1.1 如果原来的容量，大于规定的最大的容量了，设置阈值是interger最大值，直接返回原来的容量，不给扩容了
1.1.2 进行双倍扩容，阈值也变为之前的2倍
1.2 如果原来的容量不大于0(说明没初始化)，老的阈值大于0，说明是那三种指定参数的构造，这里进行初始化的，直接把之前 tableSizeFor
设置给阈值的，也赋值给 数组的大小
-- new HashMap(initCap,loadFactor)
-- new HashMap(intiCap)
-- new HashMap(map) 并且Map有数据
1.3 最后的情况，也是没初始化的，就是没有传参数的构造，直接设置 数组大小 为 16，阈值为12
1.4 如果新的阈值是空，就重新乘以 0.75设置阈值,例如就是三种传参的构造，是没有设置阈值
-- new HashMap(initCap,loadFactor)
-- new HashMap(intiCap)
-- new HashMap(map) 并且Map有数据
1.5. 将临时变量新阈值，更新到 阈值 threshold = newThr
第二部分 扩容
2.1创建一个 新数组大小的新数组
2.2 然后更新 table 的引用 table = newTab;
2.3 判断原来数组是否为空，初始化那些肯定是空，正常扩容的就不是空
然后循环遍历数组的每个桶，去处理扩容，桶不为空的才进行处理
2.3.1 如果节点的下一节点是空，说明是一个普通节点，则重新寻址放进新的数据 e.hash & (newCap - 1)
2.3.2 如果节点是树桶，调用树的扩容方法进行扩容
2.3.3 如果是链表 循环所有的链节点，根据算法 (e.hash & oldCap) 判断
如果原来节点的高一位是0，就放进低位链表，然后连接起来，用尾插法 .next
否则就是原来节点的高一位是1，就放进高位链表，然后连接起来，用尾插法 .next
2.3.3.1 遍历完所以链节点 判断遍历的最后的 低位链节点和高位链节点，是否为空
1）.低位链节点不为空，就设置 这个最后的链节点的下一个节点 next是 null
然后设置这个低位链，放到原来的位置 -- 原来是5 低位链表的位置还是 5
2）.高位链节点不为空，就设置 这个最后的链节点的下一个节点 next是 null
然后设置这个高位链，放到【原来的位置+原来数组大小】的位置 -- 原来是5 高位链表的位置 5+16 = 21// resize() 方法
// 为什么需要扩容？
// 当元素越来越多的时候，hashMap的查找速度就从O(1)升到O(n)，导致链化严重，
// 为了解决冲突带来的查询效率的下降，因此需要扩容[扩容是一个很不好的动作]
final Node[] resize() {
// oldTab：引用扩容之前的哈希表
Node[] oldTab = table;
// oldCap：表示扩容之前table数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// oldThr：表示扩容之前的阈值，触发本次扩容的预祝
int oldThr = threshold;
// newCap：扩容之后table数组的大小
// newThr：扩容之后下次触发扩容的条件
int newCap, newThr = 0;
// 条件如果成立，说明hashMap中的散列表已经初始化过了，是一次正常的扩容
if (oldCap > 0) {
// 当前数组的长度已经大于 hashMap所能容纳的最大大小 就不在扩容，直接返回原数组
// 设置扩容最大阈值为 int 的最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新的table大小为源table的2倍
// 通知扩容之后的newCap小于数组的最大值限制，其扩容之前的阈值为16
// 这种情况下，则下一次的扩容的阈值，翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 扩容的阈值也变为原来的2倍
newThr = oldThr << 1; // double threshold
}
// oldCap == 0 [说明hashMap中的散列表式null]
// 1.new HashMap(initCap,loadFactor)
// 2.new HashMap(intiCap)
// 3.new HashMap(map) 并且Map有数据
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// oldCap == 0 && oldThr == 0
// new HashMap();的时候
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; // 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //12
}
// newThr为0的时候，通过newCap和loadFactor计算出一个newThr
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 更新阈值为计算出来的 newThr
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 创建一个很大的数组
Node[] newTab = (Node[])new Node[newCap];
// 然后更新 table 的引用
table = newTab;
// oldTab不为null，说明hashMap本次扩容之前，table不为null
if (oldTab != null) {
// 迭代 一个一个位置去处理
for (int j = 0; j < oldCap; ++j) {
// e：当前的node节点
Node e;
// 迭代桶节点，如果节点不为空，才需要计算
// 但是桶里面的数据具体式哪种（单个数据、链表、树）不确定，需要继续判断
if ((e = oldTab[j]) != null) {
// 把原来的数组数据置空，等待GC回收，原来的数据已经存在e里面
oldTab[j] = null;
// 说明式单个元素数据，
if (e.next == null)
// 直接计算hash值放入即可
newTab[e.hash & (newCap - 1)] = e;
// 如果已经树化
else if (e instanceof TreeNode)
// 在红黑树部分讲解
((TreeNode)e).split(this, newTab, j, oldCap);
// 如果是链表
else { // preserve order
// 桶位已经形成链表
// 低位链表：存放在扩容之后的数组的下标的位置，与当前数组下标位置一致
Node loHead = null, loTail = null;
// 高位链表：存放在扩容之后数组的下标位置，
// 当前数组下标位置 + 扩容之前数组的长度
Node hiHead = null, hiTail = null;
// 当前链表的一个元素
Node next;
do {
next = e.next;
// e.hash & oldCap 之所以用这个方式，是因为，假设落在15的位置，则15位置的元素的key，后四位肯定都是 1111
// 扩容，只要判断第 5个 是0，还是1即可
// 如果跟 原来的数组的容量与， 操作，结果是0话，那第五位，肯定是 0，所以肯定是放在原来的位置
// 不是0的话，就在 双倍的位置
// hash -> .... 1 1111
// hash -> .... 0 1111
// 0b 1 0000 16
// 第一轮 e=1 lohread 1
// lotail 1 最后 e=2
// 第二轮 e=2 lotail.next = 1.next = e = 2
// lotail = e = 2 最后 e=3
// 第三轮 e=3 lotail.next = 2.next = e = 3
// lotail = e = 3 最后 e=null
// 循环出去后 此时 e.next可能是其他的 节点，直接置为空，切断跟高位连的联系
// 然后低位链就直接 设置到 原来的索引位置上
// head 是第一个头结点，因为e 复制
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
// 第一次 头节点赋值了，因为共享同一个地址，下次进来，其实就是头结点的next，就这样将链窜起来了
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 低位链表有数据 低位链节点不为空
if (loTail != null) {
loTail.next = null; //切断与旧tab中高位链的处理，最后一个节点了，那下一个节点就要设置为空了
newTab[j] = loHead; // 然后设置这个低位链，放到原来的位置 -- 原来是5 低位链表的位置还是 5
}
然后设置这个低位链，放到原来的位置 -- 原来是5 低位链表的位置还是 5
2）.高位链节点不为空，就设置 这个最后的链节点的下一个节点 next是 null
然后设置这个高位链，放到【原来的位置+原来数组大小】的位置 -- 原来是5 高位链表的位置 5+16 = 21
// 高位链表有数据 高位链节点不为空
if (hiTail != null) {
hiTail.next = null; //最后一个节点了，那下一个节点就要设置为空了
// 然后设置这个高位链，放到【原来的位置+原来数组大小】的位置 -- 原来是5 高位链表的位置 5+16 = 21
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 结束之后返回新的
return newTab;
} get方法分析
1.先调用hash方法，经过扰乱算法获取到新的hash值
2.然后判断map里面有数据，而且能经过 寻址算法，找到相应的桶
2.1 判断这个节点，直接key值相等了，直接返回去
2.2 如果当前节点的next不为空
2.2.1 如果是树节点，就调用树节点的获取方法
2.2.2 如果是链表，就直接循环链表比较key返回去即可
3.找不到直接返回null// 获得一个方法
public V get(Object key) {
Node e;
// 先调用 hash(key)计算hash值，然后调用 getNode方法
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// getNode方法
final Node getNode(int hash, Object key) {
// tab：引用当前hashMap的散列表
// first：桶位中的头元素
// e：临时node元素
// n：table数组元素
Node[] tab; Node first, e; int n; K k;
// 首先判断 table 不是空且长度不为0，并且first部位null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 对第一个first进行判断，如果hash值相等并且 key 相等，返回当前节点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果first的下一个不为null
if ((e = first.next) != null) {
// 如果是树，就调用树的查找方法
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
// 如果是链表，就循环进行判断
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 都没有，就返回null
return null;
} remove方法分析
1.先调用hash方法，经过扰乱算法获取到新的hash值
2.然后判断map里面有数据，而且能经过 寻址算法，找到相应的桶
2.1 判断这个节点，直接key值相等了，就直接赋值到，找到的节点node -- 直接在数组的位置，就是桶的第一个头元素就是找到了
2.2 如果当前节点的next不为空 -- 那就要去链表或者树去找了
2.2.1 如果是树节点，就调用树节点的获取方法,赋值到，找到的节点node
2.2.2 如果是链表，就直接循环链表比较key,找到节点，就直接赋值到，找到的节点node
2.3 判断是否找到节点
2.3.1 如果是树节点，就调用树节点的remove方法
2.3.2 如果是找到的节点就是当前节点，就直接把当前节点的next 重新设置到 桶的位置，则当前节点就游离了，jvm会删除
2.3.3 如果是链表，就把当前节点p的next = 找到节点node的.next，则node就游离了，jvm会删除
2.4 修改次数增加1 和 map的元素size减少1，然后返回删除的节点
3.找不到，直接返回null// 移除元素的方法
public V remove(Object key) {
Node e;
// 调用hash方法，获得哈希值，然后调用removeNode
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
// 核心方法 removeNode
// hash：hash值
// key：key
// value：value 如果matchValue则匹配的值，否则忽略
// matchValue：如果为true，则仅在值相等时删除
// movable：如果删除虚假不动其他节点
final Node removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// tab：引用当前hashMap的散列表
// p：当前node元素
// n：表示散列表数组长度
// index：表示寻址结果
Node[] tab; Node p; int n, index;
// 判断 table 是否为空，是否长度为0，且对应的hash值在数组里面存在，才继续向下走
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
// 说明桶位是由数据的，需要进行查找操作，并且删除
// node：查找到的结果
// e：当前Node的下一个元素
Node node = null, e; K k; V v;
// 判断头元素是不是要删除的元素，如果是就放进去node
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 桶的第一个不是
else if ((e = p.next) != null) {
// 树化结构
if (p instanceof TreeNode)
// 调用树化的结果
node = ((TreeNode)p).getTreeNode(hash, key);
else {
// 链表结构 循环遍历得到结构
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 判断是否得到了目标要删除的节点
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 如果是树节点，调用树的删除操作
if (node instanceof TreeNode)
((TreeNode)node).removeTreeNode(this, tab, movable);
// 如果node = p 表示是第一个数据
else if (node == p)
// 更新地址为下一个数据，放到桶
tab[index] = node.next;
else
// 如果node 不等于 p 那就直接指向链表的下一个元素地址
p.next = node.next;
// 修改次数增加
++modCount;
// 大小减1
--size;
afterNodeRemoval(node);
// 返回删除的node
return node;
}
}
// 如果都没有执行，那么就返回null
return null;
} 1.先调用hash方法，经过扰乱算法获取到新的hash值
2.然后调用getNode方法，get方法就调用了这个方法，找节点
3.找到了，就新值替换旧值// 根据 k 和 v 替换
@Override
public V replace(K key, V value) {
Node e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
// 根据 k oldValue newValue 替换
@Override
public boolean replace(K key, V oldValue, V newValue) {
Node e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
} 5.遍历HashMap的几种方式
1.分别遍历 Key 和 Valuesfor (String key : map.keySet()) {
System.out.println(key);
}
for (Object vlaue : map.values() {
System.out.println(value);
}Iterator> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry mapEntry = iterator.next();
System.out.println(mapEntry.getKey() + "---" + mapEntry.getValue());
} Set keySet = map.keySet();
for (String str : keySet) {
System.out.println(str + "---" + map.get(str));
} default void forEach(BiConsumer<? super K,? super V> action)
// BiConsumer接口中的方法：
void accept(T t, U u) 对给定的参数执行此操作。
参数
t - 第一个输入参数
u - 第二个输入参数 HashMap map = new HashMap();
map.put("001", "zhangsan");
map.put("002", "lisi");
map.forEach((key, value) -> {
System.out.println(key + "---" + value);
});