Map&Set(3)

发布于:2023-01-20 ⋅ 阅读:(13) ⋅ 点赞:(0) ⋅ 评论:(0)

发生哈希冲突时,最常见的两种解决方案:

1.闭散列(开放定址法)

发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有位置,那么可以把key存放到冲突位置的下一个位置中去。好放难取

最大的问题就在于:如果整个哈希表冲突比较严重,此时查找元素过程就相当于遍历数组,查找效率退化为O(n)

2.开散列,当发生哈希冲突,就让冲突为止变为链表(简单实用)

实际上就是把单纯的数组转化为链表+数组

如果某个下标对应的冲突非常严重,单个链表长度过长,有以下解决方法:

a.针对整个哈希表进行扩容,假设以前7%(数组长度为7)扩容为原数组的一倍,现在是14%(数组长度为14),就可以大大降低冲突的概率,减少链表的长度。c++

b.单个链表过长,查询效率就会变为链表的遍历O(n),就针对这个单链表进行转换处理,可以把单个链表再转为哈希表或者变为搜索树(JDK8的HashMap,当某个链表长度>6且整个哈希表的元素个数>64,就把此链表转为RBTree)java


负载因子α:α = 填入表中的元素个数/散列表的长度

负载因子越大,发生哈希冲突的概率越小,数组长度就会偏小,节省空间。

负载因子越小,发生哈希冲突的概率越小,数组的长度就会偏大,浪费空间。

负载因子到底取多大?根据当前系统的需求得知。

JDKHashMap的负载因子是0.75


JDK中Set和Map的源码分析

1.Set和Map集合有啥关系吗?(应聘者是否有阅读源码的能力)

Set集合下的子类就是Map集合下的子类,

HashSet就是HashMap

TreeSet就是TreeMap

按两次shift然后勾选不包含当前项目

选择class和All Places 

 

之所以Set是不重复的,原因是Set中元素存储在了Map的key中

Alt+7显示类中的所有方法

如果想要看懂代码,首先要知道这个类里面有哪些方法,功能是什么。

调用Set集合的add方法实际上就是调用Map集合的put,将Set集合的元素放在key上,value大家都是同一个空的Object对象。

2.JDK的HashMap源码大概的结构以及重点方法是什么?(源码阅读)

JDK7之前的HashMap就是一个基于开散列的散列表实现  数组+链表结构

JDK8之后引入了红黑树:当某个链表的长度过长时,元素的查询退化为链表的遍历O(n),

当某个结点过长时,树化,元素个数再多查询效率起码也是O(logN)

数组+链表(或红黑树)

那什么时候会变成红黑树呢?

异或运^:相同返回0,不同返回1

哈希函数的设计:均衡性(高低16位都参与了运算) 

数组的长度为什么必须是2的N次方?

当数组的长度 =2 ^N,等价于hash%N

 为啥要多此一举呢?因为第一个的效率更高。