无序: 存取的顺序不一样
不重复:可以去重
无索引:不能使用普通for进行遍历,也不能通过索引获取元素
Set集合的实现类
HashSet:无序,不重复,无索引
LinkedHashSet:有序,不重复,无索引
TreeSet:可排序,不重复,无索引
Set是一个接口,在方法上基本和Collection一样
一.三种遍历
<1>迭代器遍历
<2>增强for
<3>Lambda表达式
二.HashSet
HashSet在底层是使用哈希表存储数据的
哈希表是一个对于增删查改数据比较好的数据结构
哈希表的组成:
JDK8以前:数组+链表
JDK8开始:数组+链表+红黑树
在哈希表中有一个重要的知识——哈希值
哈希值:对象的整数形式
根据HashCode方法算出来的int类型的整数
该方法定义在Object类中,所有对象都可以调用,默认使用地址值进行计算(所以意义不大)
一般情况下,会重写HashCode方法,利用对象内部的属性值计算哈希值
哈希值的特点
如果没用重写hashCode方法,不同对象计算出的哈希值是不同的
如果已经重写hashCode方法,不同对象只要属性值相同,计算出的哈希值就是一样的
在小部分情况下,不同的属性值或者不同的地址值计算出来的哈希值也有可能是一样的(哈希碰撞)
哈希碰撞
举一个极端例子:整形的范围是-21亿---+21亿加入有50亿个对象那么必然会有重复的
没重写
重写
字符串内部自动重写了hashCode
HashSet的底层原理
1.创建一个默认长度为16,默认加载因子为0.75的数组,数组名字为table
2.根据元素的哈希值跟数组的长度计算出应该存入的位置
3.判断当前位置是否为null,如果是null直接存入
4.如果位置不为null,表示有元素,则调用equals方法比较属性值
5.如果一样就不存入,如果不一样就存入
存入的方式有两种
JDK8以前:新元素存入数组,老元素挂在新元素下面
JDK8以后:新元素直接挂在老元素下面
加载因子
当数组的总量(默认是16)被填满了四分之三时(默认是16×0.75=12)就会扩容二倍
JDK8以后,当链表的长度大于8并且数组的长度大于等于64时 当前的链表自动转换成红黑树
如果集合中存储的是自定义的对象,必须重写hashCode和equals方法否则就会使用地址值比较
三个问腿
Q1:hashSet为什么存和取的顺序不一样
A:因为遍历是在数组的0索引开始遍历,可能是null,可能是链表,可能是红黑树,索引小的数据不一定是先添加的
Q2:hashSet为什么没索引
A:因为hashSet里面包含链表 null 红黑树
Q3:hashSet是如何保证数据的去重呢
A:使用HashCode得到哈希值得到数据应存储的位置再使用equals比较属性值
三.LinkedHashSet
有序,无索引,不重复
这里的有序指的是保证数据的存储和取出的元素一致
原理:底层仍然是哈希表,只是每个元素又额外多了一个双链表的机制记录存储的数据
这样每两个相邻添加成功的数据,都会互相记录地址值,形成双向链表
LinkedHashSet遍历就是再双向链表的头节点开始遍历保证了数据存取一致
这个集合不为了效率,只保证顺序
四.TreeSet
不重复,无索引,可排序
底层是红黑树