Set集合不重复原理(加急)

积硅步 至千里

学完集合这块部分，我们知道Set是一个不包含重复元素的集合

Set接口:
特点:
1.没有索引值
2.不能重复
3.HashSet 无序 底层: 哈希表(数组+链表+红黑树)
4.LinkedHashSet 有序 哈希表+链表
5.TreeSet 可排序 红黑树

说Set不重复原理，我觉得还是得先从Set集合的新增过程开始说起
我们先搞清楚他是如何新增的
我们从源码入手

先把判断两个元素是否重复规则说一下:

*

重点

*

哈希值相同 && (地址值相同 || equals相同)

新增过程:

可以看到,Set集合它的底层用的是map集合,用的是map的新增方法put()方法添加元素;
a.计算新增元素的哈希值

然后会初始化集合然后进入resize()里面。(这里我就不放图了)
确定数组类型:java.util.HashMap$Node
在resize()中确定了数组的长度为:16
b.通过哈希值%数组长度,获取索引值

他底层源码是(n-1)&hash 这步和哈希值%数组长度的结果是一样的。但是这样它的效能比较高一点
c.如果该位置为null，则直接新增。上图可以看到
如果不为null: 就会用到去重规则
c1:如果重复,不新增
c2:如果不重复,则新增到当前链表的最后
在上面说明底层是Node数组，Node是一个链表结构，这样的话，每一个索引值下面可能会有多个元素
无序:因为哈希值的计算是不一定的,那么它的索引值位置前后顺序也就不一定了，所以元素存储的无序性就这样了。。
还有一个特殊的:String类覆盖重写了HashCode方法,它只要内容相同，那么它的哈希值一定相同。

另外我们需要注意，在集合里面添加自定义类型时，如果我们需要去重，那我们需要覆盖重写HashCode()和equals();

假如只重写了equals()而不重写HashCode(),那么自定义类中的HashCode()就是Object默认的HashCode()方法，由于默认的HashCode()时根据对象的内存地址经过哈希算法得来的。所以肯定就是去重失败

还有一些关于HashCode的规定:(部分寻查)

• 两个对象相等，HashCode一定相等
• 两个对象不等，HashCode不一定相等
• HashCode相等，两个对象不一定相等
• HashCode不等，两个对象一定不等

到这差不多就结束了,还有很多我讲不清楚。待我在学习学习