赞
踩
目录
HashMap 并没有继承 SortedMap 接口,所以 key 并不需要重新 CompareTO 方法,因此 HashMap 不关于 key 有序
HashMap 并没有继承 SortedMap 接口,所以 key 并不需要重新 CompareTO 方法,key 都不能进行比较了,那如何通过哈希函数计算哈希地址呢?
答:可以通过 hashCode 方法获取到哈希值,从而通过哈希函数计算出哈希地址
自定义类型为什么要重写 equals?
答:因为 key 无法进行比较,HashMap 中的 key 必须是唯一的,所以重写 equals 判断是否与 HashMap 中的其它 key 相同
自定义类型为什么要重写 hashCode?
假设我们现在有如下代码:
- public class Student {
- private String name;
-
- public Student(String name) {
- this.name = name;
- }
- }
- class Demo {
- public static void main(String[] args) {
- Student student1 = new Student("张三");
- Student student2 = new Student("张三");
- System.out.println(student1.hashCode());
- System.out.println(student2.hashCode());
- }
- }
打印结果:
答:明明姓名一样却通过 hashCode 方法得到的哈希值不一样,那么通过哈希函数获取到的位置也就不同了,既然位置都不同了那还如何在同一个链表中判断是否有相同的 key 了咧
如果像上图这样就无法确定 key 的唯一性
重写 hashCode 的代码:
- import java.util.Objects;
-
- public class Student {
- private String name;
-
- public Student(String name) {
- this.name = name;
- }
-
- @Override
- public boolean equals(Object o) {
- if (this == o) return true;
- if (o == null || getClass() != o.getClass()) return false;
- Student student = (Student) o;
- return Objects.equals(name, student.name);
- }
-
- @Override
- public int hashCode() {
- return Objects.hash(name);
- }
- }
-
- class Demo {
- public static void main(String[] args) {
- Student student1 = new Student("张三");
- Student student2 = new Student("张三");
- System.out.println(student1.hashCode());
- System.out.println(student2.hashCode());
- }
- }
运行结果:
只有获取的 hashCode 值相同才能确定位置相同,那么才能判断是否有相同的 key
那么现在有这样两个问题:
问题一:hashCode相同,equals 就一定相同嘛?
答:不一定,因为 hashCode 只是确定在同一个位置,但是同一个位置中存储的是一个链表,链表中有很多节点,节点中的 key 也是不同的,那么就无法保证 equals 就一定相同
问题二:equals 相同,hashCode 一定相同嘛?
答:一定,因为 equals 相同说明就是一样的 key ,那么 hashCode 获得的位置也就是同一个
默认初始容量:
最大容量:
默认的负载因子:
树化的前提条件:
当链表长度为8时并且数组长度为64时,则会转化成红黑树
解树化(红黑树转链表):
HashMap 的主要存储结构是一个 Node<K,V> 类型的数组:
数组的每个存储单元下存储的都是一个链表
Node是链表的节点结构
记录 HashMap 中的元素个数:
记录当前哈希表的负载因子:
通过当前哈希表的负载因子值与默认负载因子值比较,判断是否需要扩容
1.无参构造
第一个构造方法无参构造方法,直接将默认负载因子赋值给了当前负载因子
2.构造方法
第二个构造方法是有参构造方法, 将默认负载因子赋值给了当前负载因子,在根据传入的 Map 构造出一个新的 Map
3.构造方法
第三个构造方法是有参构造方法,指定容量和自定义负载因子
4.构造方法
第四个构造方法是有参构造方法,它会通过 this 调用第三个构造方法,传入指定容量和默认的负载因子
当我们使用不指定容量的构造方法时,也能够成功构造一个 HashMap。当时我们并没有指定容量那么数组容量就为空
但是当我们插入元素的时候也是能够插入成功的,这是为什么呢?
答:既然构造的时候没有开辟容量,那么能够插入元素成功肯定跟 put 方法有关了,那么接下来我们就来从 put 方法中找寻答案
put 方法:
进入 put 方法中,可以发现 put 方法调用了 putValue 方法 ,调用 putValue 方法的时候第一个参数调用了 hash 方法并把我们要插入的 key 传入进去。那么接下来我们先来了解 hash 方法是干嘛的,再看 putValue 方法
hash 方法:
hash方法中判断了,key 是否会 null,如果为 null 则返回 0,否则调用 key 的哈希方法得到的哈希值赋值给 h(如果 key 是自定义类型一定要重写 hashCode 方法,否则就会调用 Object 的hashCode 方法),然后将 h 和 h >>> 16 得到得值进行异或运算得到得结果进行返回
为什么要将 h 和 h >>> 16 得到得值进行异或运算?
答:因为能够将 h 的低16 位和高16 位都参与运算,这样得到的结果更均匀
putValue方法:
putValue 方法比较复杂我们分段来分析
首先定义了 Node<K,V> 类型的数组 tab,Node<K,V> 类型的变量 p,int 类型的变量 n 和 i 。将 table 赋值给 tab ,判断 tab 是否为空或者 tab 数组的长度是否为 0,如果满足则会调用 resize 方法,初始化数组。初始哈希表的长度是 16,临界阈值为 16 * 0.75 = 12,也就是数组元素达到 12个即会扩容
当 HashMap 扩容时,需要注意什么?
答:将里面的元素重新哈希地址
那咱们接着往下看 putValue 方法中的内容
计算插入节点在数组中的插入位置的下标放入 i 中,如果为空则直接插入
否则说明这个位置不为空,判断当前下标元素的 hash 值是否与我们要插入元素的 hash 值相同,如果相同则判断节点 key 是否存在,如果存在则覆盖当前元素 。如果节点 key 不存在,就会判断下标 i 的位置是不是一棵红黑树节点,如果是则采用红黑树的方式插入元素。如果下标 i 的位置是一个链表,则采用尾插的方式插入节点,在插入的时候会判断是否要转化为红黑树
红黑树里面的元素是可比较的,那么自定义类型并没有重写 CompareTo 怎么办?
答:会按照 key 的哈希值来进行比较,所以就算转换成红黑树也不会关于 key 有序。或者可能只是哈希表中一个下标位置下的结构是红黑树,其他的仍然可能是链表
++modCount 是有效元素个数的自增,判断节点插入后是否需要对数组进行扩容
HashSet 的底层就是 HashMap,只不过 HashSet 是纯 key 模型的,而 HashMap 是键值对模型的
通过 HashSet 的构造方法就可以证明 HashSet 的底层就是 HashMap
add 方法:
当对 HashSet 插入元素的时候,value 会给一个默认值
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。