【数据结构】JDK HashMap源码解析

🌟HashMap源码解析

🌈类的属性

🌈构造方法

🌈put方法

🌟对比常用Map的子类实现:

🌟HashMap源码解析

JDK8之前，HashMap就是数组+链表；

JDK8之后，变成了数组+链表+红黑树。

问题1：什么时候会进行树化操作呢？

（1）当某个子链表的长度>=8并且整个哈希表的元素个数>=64时才会将当前的链表进行树化操作。

（2）若子链表的长度>=8但是哈希表的元素个数不满足大于等于64时，会进行整表扩容（也就是简单的将数组进行扩容）

接下来我们主要从以下三部分来了解源码。

🌈类的属性

🌈构造方法

1、无参构造：只是初始化负载因子

2、有参构造

（1）一个参数的有参构造

（2）两个参数的有参构造

可以看见，在定义构造函数的时候，无论hi无参还是有参，这两种方式都并没有将数组容量进行初始化，那什么时候进行数组的初始化呢？我们接下来继续看。

🌈put方法（重点）

HashMap最核心的代码就在于它的put方法。

问题2：请解释Object类的hashCode与equals的关系与区别？

equals类是判断两个对象的内容是否相同；
hashCode：默认的hashCode会将对象地址映射为整型，需要将任意数据类型转化Wie整型。

🆚区分：

（1）两个对象的hashCode返回相同的数值，equals是否返回true? ❎

两个对象的hashCode虽然返回的数值相同，但是不同的数字经过哈希函数运算完全是有可能得到相同的索引值的，因此很有可能不是同一个对象，所以equals不一定相同；

（2）两个对象的equals方法返回true，hashCode是否返回相同的数值？ ✅

这其实也就是前文说到的哈希函数设计中的稳定性，一个相同的值经过哈希函数得到的值一定是相同的，因此两个对象是一样的，经过hashCode计算得到的值一定是相同的。

注意：若需要用到哈希方法，需要对默认的Object进行重写，因为我们需要使用对象的属性值来计算HashCode，而不是地址值。

你分清了吗？😁 我们接下来继续看put方法~

图太丑了🤣大家多看几遍理一理~通过上述，我们可以解决前文提出的问题：那就是数组容量是在第一次调用put方法时初始化的。这种现象叫做懒加载。我们顺便对put方法做一个小结~

🚨 put方法的核心流程小结：
（1）如果hashMap还没有初始化，就先进行哈希表的初始化操作（默认初始化容量是16）

（2）对传入的key值做哈希运算，得到要存放在数组中的索引位置

如果此时还没有发生哈希碰撞，将该节点头插到数组中

如果已经发生碰撞，判断此时是树还是链表形式：

如果是链表形式，就将该节点作为链表的最后一个节点插入

如果链表已经树化，就将该节点构造为树节点后再计入红黑树

（3）如果哈希表中存在key值，就只需要更新value值即可

（4）同时在更新元素个数的时候判断是否需要扩容。

🌟对比常用Map的子类实现:

	TreeMap	HashMap
内部数据结构	RBTree	哈希表
key和value是否可以为空	key: ✅ value: ❎ key必须具备可比较的性质或者传入比较器对象	key: ✅ value: ✅
是否有序	对于key“有序”，这个大小关系由Comparable或者比较器对象决定	无序
是否线程安全	不安全	不安全