网站再就业培训班,免费个人简历模板在线编辑,网站开发常用工具,百度公司电话是多少水平有限#xff0c;难免会有疏漏之处#xff0c;如有错误#xff0c;还请指出#xff0c;感谢#xff01;前言HashMa是Java中最常用的集合类框架#xff0c;也是Java语言中非常典型的数据结构#xff0c;同时也是我们需要掌握的数据结构#xff0c;更重要的是进大厂面…水平有限难免会有疏漏之处如有错误还请指出感谢前言HashMa是Java中最常用的集合类框架也是Java语言中非常典型的数据结构同时也是我们需要掌握的数据结构更重要的是进大厂面试必问之一。数组特点存储区间是连续且占用内存严重空间复杂也很大时间复杂为O1。优点是随机读取效率很高原因数组是连续随机访问性强查找速度快。缺点插入和删除数据效率低因插入数据这个位置后面的数据在内存中要往后移的且大小固定不易动态扩展。链表特点区间离散占用内存宽松空间复杂度小时间复杂度O(N)。优点插入删除速度快内存利用率高没有大小固定扩展灵活。缺点不能随机查找每次都是从第一个开始遍历查询效率低。哈希表特点以上数组和链表大家都知道各自优缺点。那么我们能不能把以上两种结合一起使用从而实现查询效率高和插入删除效率也高的数据结构呢答案是可以滴那就是哈希表可以满足接下来我们一起复习HashMap中的put()和get()方法实现原理。HashMap的put()和get()的实现1、map.put(k,v)实现原理第一步首先将k,v封装到Node对象当中节点第二步通过哈希算法计算出当前key的hash值第三步再通过哈希表函数/哈希算法将hash值转换成数组的下标下标位置上如果没有任何元素就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true那么这个节点的value将会被覆盖。// 存储时:
// 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值即可
int hash key.hashCode();
int index hash % Entry[].length;
Entry[index] value;2、map.get(k)实现原理//数组长度减1与运算hash值
first tab[(n - 1) hash]第一步先调用k的hashCode()方法得出哈希值并通过哈希算法转换成数组的下标。第二步通过上一步哈希算法转换成数组的下标之后在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有则返回null。如果这个位置上有单向链表那么它就会拿着参数K和单向链表上的每一个节点的K进行equals如果所有equals方法都返回false则get方法返回null。如果其中一个节点的K和参数K进行equals返回true那么此时该节点的value就是我们要找的value了get方法最终返回这个要找的value。3、为何随机增删、查询效率都很高的原因是原因增删是在链表上完成的而查询只需扫描部分则效率高。HashMap集合的key会先后调用两个方法hashCode and equals方法这两个方法都需要重写。4、为什么放在hashMap集合key部分的元素需要重写equals方法因为equals默认比较是两个对象内存地址5、HashMap总结无序不可重复为什么是无序的因为不一定挂到哪一个单向链表上的因此加入顺序和取出也不一样。怎么保持不可重复使用equals方法来保证HashMap集合key不可重复如key重复来value就会覆盖。存放在HashMap集合key部分的元素其实就是存放在HashSet集合中则HashSet集合也需要重写equals和hashCode方法。hashmap集合的默认初始化容量为16默认加载因子为0.75也就是说这个默认加载因子是当hashMap集合底层数组的容量达到75%时数组就开始扩容。hashmap集合初始化容量是2的陪数为了达到散列均匀提高hashmap集合的存取效率6、注意JDK8之后JDK8之后如果哈希表单向链表中元素超过8个那么单向链表这种数据结构会变成红黑树数据结构。当红黑树上的节点数量小于6个会重新把红黑树变成单向链表数据结构,官方源码如下图。问题如果O1和O2的hash值相同就会存放到同一个单向链表上如果不同但由于哈希算法执行结束之后转换的数组下标可能相同此时会发上“哈希碰撞”。HashMap的存取是采用什么算法实现// 存储时:
// 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值即可
int hash key.hashCode();
int index hash % Entry[].length;
Entry[index] value;// 取值时:
int hash key.hashCode();
int index hash % Entry[].length;
return Entry[index];7、高频面试题HashMap的工作原理是什么HashMap中的“死锁”是怎么回事HashMap中能put两个相同key吗为什么HashMap中的键值可以为空吗原理HashMap扩容机制另如果觉得这本篇文章写得不错有点东西的话记得来个三连【点赞关注分享】。需要大数据、Java、redis、Dubbo框架等教程关注微信公众号自学大数据踩的抗 【回复相关术语】
