安徽制作网站的公司哪家好,商家联盟会员管理系统,北京平台网站建设找哪家,网站ftp账号密码目录一、知识点回顾二、HashMap 的 put() 和 get() 的实现2.1 map.put(k, v) 实现原理2.2 map.get(k) 实现原理三、HashMap 的常见面试题3.1 为何随机增删、查询效率都很高#xff1f;3.2 为什么放在 HashMap 集合 key 部分的元素需要重写 equals 方法?3.3 HashMap 的 key 为…
目录一、知识点回顾二、HashMap 的 put() 和 get() 的实现2.1 map.put(k, v) 实现原理2.2 map.get(k) 实现原理三、HashMap 的常见面试题3.1 为何随机增删、查询效率都很高3.2 为什么放在 HashMap 集合 key 部分的元素需要重写 equals 方法?3.3 HashMap 的 key 为什么是无序的3.4 HashMap 怎么保持不可重复3.5 HashMap 是如何扩容的3.4 HashMap 在 JDK7 和 JDK8 有什么不同3.5 HashMap 的哈希碰撞3.6 HashMap 的 key 允许为 null 吗HashMap的底层是通过数组 单向链表/红黑树实现的。 一、知识点回顾
数组特点
存储区间是连续的且占用内存严重空间复杂度也很大时间复杂度为 O(1)。优点 随机读取效率很高原因是数组是连续的随机访问性强查找速度快。缺点 插入和删除数据效率低因插入数据这个位置后面的数据在内存中要后移且大小固定不易动态扩展。
链表特点
区间离散占用内存宽松空间复杂度小时间复杂度 O(n)。优点 插入删除速度快内存利用率高没有大小固定扩展灵活。缺点 不能随机查找每次都是从第一个开始遍历查询效率低。
哈希表特点
以上数组和链表大家都知道各自优缺点。那么我们能不能把以上两种结合在一起使用从而实现查询效率高和删除插入效率也高的数据结构呢答案是可以滴那就是哈希表可以满足接下来我们一起复习下 HashMap 中的 put() 和 get() 方法实现原理。 二、HashMap 的 put() 和 get() 的实现
2.1 map.put(k, v) 实现原理 第1步首先将 k, v 封装到 Node 对象当中节点。 第2步它的底层会调用 K 的 hashCode() 方法得出 hash 值。 第3步通过哈希表函数/哈希算法将 hash 值转换成数组的下标 下标位置上如果没有任何元素就把 Node 添加到这个位置上如果说下标对应的位置上有链表就会拿着 k 和链表上每个节点的 k 进行 equals 如果所有的 equals 方法返回都是 false那么这个新的节点将被添加到链表的末尾如其中有一个 equals 返回了 true那么这个节点的 value 将会被覆盖。 2.2 map.get(k) 实现原理
第1步先调用 k 的 hashCode() 方法得出哈希值并通过哈希算法转换成数组的下标。第2步通过上一步哈希算法转换成数组的下标之后再通过数组下标快速定位到链表所在位置上。 如果这个位置上什么都没有则返回 null如果这个位置上有单向链表那么它就会拿着参数 k 和单向链表上的每一个节点的 k 进行 equals 如果所有 equals 方法都返回 false则 get 方法返回 null如果其中一个节点的 k 和参数 k 进行 equals 返回 true那么此时该节点的 value 就是我们要找的 value 了get 方法最终返回这个要找的 value。 三、HashMap 的常见面试题
3.1 为何随机增删、查询效率都很高
增删是在链表上完成的而查询主要是通过数组定位然后扫描部分链表所以效率高。
HashMap 集合的 key会先后调用两个方法hashCode() 和 equals() 方法所以当对象充当 key 时这两个方法都需要重写。
3.2 为什么放在 HashMap 集合 key 部分的元素需要重写 equals 方法?
因为 equals 默认比较的是两个对象的内存地址如果想根据对象的属性来判断则需要重写。
3.3 HashMap 的 key 为什么是无序的
因为不一定挂到哪一个单向链表上因此加入顺序和取出也不一样。
3.4 HashMap 怎么保持不可重复
使用 equals 方法来保证 HashMap 的 key 不可重复。如果 key 重复的话value 就会覆盖。存放在 HashMap 集合中的 key其实就是存放在 HashSet 集合中所以 HashSet 集合也需要重写 equals() 和 hashCode() 方法。
3.5 HashMap 是如何扩容的
HashMap 集合的默认初始化容量为16默认加载因子为 0.75也就是说当 HashMap 集合底层数组的容量达到 75% 时数组就开始扩容。HashMap 集合初始化容量是 2 的倍数是为了达到散列均匀提高 HashMap 集合的存取效率。
3.4 HashMap 在 JDK7 和 JDK8 有什么不同 new HashMap()底层不会再创建一个长度为 16 的数组改为首次调用 put() 方法时创建 jdk8 底层的数组是 Node[]而非 Entry[] jdk7 底层结构只有数组链表jdk8 中底层结构数组链表红黑树。 3.1 形成链表时七上八下 jdk7头插法新元素指向旧元素多线程修改会有死锁问题 jdk8尾插法旧元素指向新元素 3.2 为什么要用红黑树 首先正常场景下不会一下子产生特别多的 Hash 冲突只有非常规的场景下才会出现 Hash 冲突需要转化为红黑树结构。红黑树解决了超长链表查询效率低下的问题但是小数据量的链表并不比红黑树的查询效率要低。Hash 值如果足够随机则在 Hash 表内按泊松分布在负载因子 0.75 的情况下长度超过 8 的链表出现概率时 0.00000006选择 8 就是为了尽量降低树化的几率。 3.3 树化的两个条件必须都满足 哈希单向链表中的元素数 8当前数组的长度 64 3.4 退化链表的条件任何一个满足 红黑树上的节点数 6remove 节点时若 root、root.left、root.right、root.left.left 有任意一个为 null也会退化为链表。
3.5 HashMap 的哈希碰撞
如果 key1 和 key2 的哈希值相同就会存放到同一个单向链表上。
如果 key1 和 key2 的哈希值不同但由于哈希算法执行结束之后转换的数组下标可能相同此时会发生哈希碰撞。
3.6 HashMap 的 key 允许为 null 吗
允许
JDK8 中 HashMap 的 put() 方法
public V put(K key, V value) {// 采用 hash(key) 来计算 key 的 hashCode 值return putVal(hash(key), key, value, false, true);
}static final int hash(Object key) {int h;// 当 key 为 null 的时候不走 hashCode() 方法return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}HashMap 中使用 hash() 方法来计算 key 的哈希值当 key 为 null 时直接令 key 的哈希值为0不走 key.hashCode() 方法所以即使为 null 也不会抛出空指针异常。
整理完毕完结撒花~ 参考地址
1.来复习一波HashMap底层实现原理解析https://baijiahao.baidu.com/s?id1665667572592680093wfrspiderforpc
2.java中的hashMap允许key为null的原因https://blog.csdn.net/weixin_46984636/article/details/120606095
3.HashMaphttps://blog.csdn.net/qq_39181839/article/details/109478003
4.HashMaphttps://blog.csdn.net/weixin_42470732/article/details/124027786
