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

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

散列表：hashmap,hashtable,concurrentHashmap

树：hashset,treemap,treeset

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

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

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

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方法）：

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

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

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

展开阅读全文