服务器之家

服务器之家 > 正文

java教程散列表和树所对应容器类及HashMap解决冲突学习

时间:2022-02-10 15:13     来源/作者:chuangjizai7518

java中散列表、树所对应的的容器类

散列表:hashmap,hashtable,concurrentHashmap

树:hashset,treemap,treeset

jdk7与jdk8中HashMap的区别

jdk7中hashMap采用数组+链表,如果过多的节点在hash时发生碰撞,如果要查找其中一个节点,需要O(n)的查找时间。

jdk7中hashMap采用数组+链表/红黑树,当某个桶位达到某个阈值时,链表将转化为红黑树,红黑树时间复杂度O(nlogn)

HashMap如何解决冲突

1.开放定址法: 通过探测算法,当一个槽位已经被占用情况下继续查找下一个
2.链地址法(数组+链表)
3.再哈希 准备多个散列函数,当发生冲突时,再选择一个散列函数进行散列。

HashMap的工作原理

HashMap 底层是数组和单向链表实现,数组中的每个元素都是链表,由 Node 内部类(实现 Map.Entry<K,V>接口)实现,HashMap 通过 put & get 方法存储和获取。

HashCode是定位(存储位置),equals是定性(两者是否相等)

1.存储对象时,将K/V传给put()方法:

2.hash(K)计算K的hash,结合数组长度,计算数组下标

调整数据大小(当容器中的元素个数大于 capacity * loadfactor 时,容器会进行扩容resize 为 2n)

3.三种情况:

  • 当K的hash值不在HashMap中,则执行插入
  • 当K的hash值存在HashMap中,发生碰撞
       它们两者equals为true,更新键值对
       它们两者equals为false,插入链表尾部或红黑树(当链表长度超过8)中

获取对象时(get方法):

  • 调用hash(K),计算K的hash值从而获取数组的下标
  • 顺序遍历链表,equal方法查找相同 Node 链表中 K 值对应的 V 值

转载于:https://my.oschina.net/u/3973793/blog/3100006

以上就是java教程散列表和树所对应容器类及HashMap解决冲突学习的详细内容,更多关于java散列表树所对应容器类及HashMap解决冲突的资料请关注服务器之家其它相关文章!

原文链接:https://blog.csdn.net/chuangjizai7518/article/details/101010546

标签:

相关文章

热门资讯

蜘蛛侠3英雄无归3正片免费播放 蜘蛛侠3在线观看免费高清完整
蜘蛛侠3英雄无归3正片免费播放 蜘蛛侠3在线观看免费高清完整 2021-08-24
2022年最旺的微信头像大全 微信头像2022年最新版图片
2022年最旺的微信头像大全 微信头像2022年最新版图片 2022-01-10
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
返回顶部