当前位置:   article > 正文

集合进阶-HashSet、LinkedHashSet、TreeSet

hashset、linkedhashset、treeset

Set系列集合

  • 无序:存取顺序不一致
  • 不重复:可以去除重复
  • 无索引:没有带索引的方法,所以不能使用普通for循环遍历,也不能通过索引获取元素

Set集合的实现类

HashSet:无序、无索引、不重复

LinkedHashSet:有序、不重复、无索引

TreeSet:可排序、不重复、无索引

Set系列集合没有特有的方法,直接继承顶层接口Collection中的所有方法并使用。

1.HashSet

HashSet底层:

  • HashSet集合底层采用哈希表存储数据
  • 哈希表是一种对于增删改查数据性能都比较好的结构

哈希表的组成:

  • JDK8之前:数组+链表
  • JDK8开始:数组+链表+红黑树

HashSet底层存储数据:

通过调用hashCode方法计算对象的哈希值,然后根据哈希值和数组长度计算出对象应存入哈希表的位置,然后该对象再调用equals方法和当前位置的所有对象依次比较,若存在相同属性值对象,则舍弃该对象不存,若不存在属性值相同对象,则将该对象存入当前位置。

注意:一定要重写hashCode和equals方法,这样才能保证实现不重复

哈希值细节:

  • 根据hashCode方法算出来的int类型的整数
  • 该方法定义在Object类中,所有对象都可以调用,默认使用地址值进行计算
  • 一般情况下,都会重写hashCode方法,利用对象内部的属性值计算哈希值
  • 如果没有重写hashCode方法,不同对象计算出来的哈希值是不同的
  • 如果重写了hashCode方法,不同对象只有属性值相同,计算出来的哈希值就是一样的
  • 小部分情况下,不同属性值或者不同地址值计算出来的哈希值也有可能一样。(哈希碰撞)

HashSet底层原理:

  1. 创建一个默认长度16,默认加载因子0.75的数组,数组名table
  2. 根据元素的哈希值跟数组的长度计算出应存入的位置
  3. 判断当前位置是否为null,如果是null直接存入
  4. 如果位置不为null,表示当前位置已经有元素,则调用equals方法比较属性值
  5. 一样:表明重复了,不存 ;不一样:存入数组,形成链表(JDK8以前:新元素存入数组,老元素挂在新元素下面;JKD8开始:新元素直接挂在老元素下面)
  6. 当元素个数达到16*0.75=12个时,数组会扩容为原来的2倍长度变成32

JDK8以后,当链表长度超过8且数组长度大于等于64时,自动转换为红黑树

如果集合中存储的是自定义对象,必须重写hashCodeequals方法

三个问题:

HashSet为什么存和取的顺序不一样?

HashSet为什么没有索引?

HashSet是利用什么机制保证数据去重的?

2.LinkedHashSet

  • 有序、不重复、无索引
  • 有序指的是存储和取出元素的顺序一致
  • 原理:底层数据结构依然是哈希表,只是每个元素又额外多了一个双链表的机制记录存储的顺序

总结:

1.LinkedHashSet集合的特点和原理是怎样的?

  • 有序、不重复、无索引
  • 底层基于哈希表,使用双链表记录添加顺序

2.以后如果要数据去重,我们应该使用哪个?

  • 默认使用HashSet,因为HashSet的效率更高
  • 如果要求去重且存取有序,才使用LinkedHashSet

3.TreeSet

TreeSet的特点:

  • 不重复、无索引、可排序
  • 可排序:按照元素的默认规则(由小到大)排序
  • TreeSet集合底层是基于红黑树的数据结构实现排序的,增删改查性能都比较好

TreeSet集合默认规则

  • 对于数值类型:Integer,Double,默认是按照从小到大的顺序进行排序
  • 对于字符、字符串类型:按照字符在ASCII码表中的数字升序进行排序
  1. public class TreeSetDemo1 {
  2. public static void main(String[] args) {
  3. //创建TreeSet集合对象
  4. TreeSet<Integer> ts = new TreeSet<>();
  5. //添加元素
  6. ts.add(5);
  7. ts.add(3);
  8. ts.add(1);
  9. ts.add(4);
  10. ts.add(2);
  11. //打印集合
  12. System.out.println(ts);//[1, 2, 3, 4, 5]
  13. //三种通用遍历方式遍历
  14. //迭代器遍历
  15. /*Iterator<Integer> it = ts.iterator();
  16. while (it.hasNext()){
  17. int i = it.next();
  18. System.out.println(i);
  19. }*/
  20. //增强for遍历
  21. /*for (Integer t : ts) {
  22. System.out.println(t);
  23. }*/
  24. //lambda表达式遍历
  25. ts.forEach(i-> System.out.println(i));
  26. }
  27. }

TreeSet两种比较方式

方式一:

默认排序/自然排序:Javabean类实现Comparable接口指定比较规则

举例:学生有姓名、年龄属性,现要求按照学生的年龄进行排序,同年龄按照姓名字母排序

  1. public class Student2 implements Comparable<Student2>{
  2. //通过compareTo方法指定比较规则
  3. //this:表示当前要添加的元素
  4. //o:表示已经在红黑树中存在的元素
  5. //返回值:
  6. //正数:表示当前要添加的元素是大的,存右边
  7. //负数:表示当前要添加的元素是小的,存左边
  8. //0:表示当前要添加的元素已经存在,舍弃
  9. @Override
  10. public int compareTo(Student2 o) {
  11. //指定排序规则
  12. //按照年龄升序进行排列
  13. return this.getAge() - o.getAge();
  14. }
  15. }
  1. public class TreeSetDemo2 {
  2. public static void main(String[] args) {
  3. Student2 s1 = new Student2("zhangsan",23);
  4. Student2 s2 = new Student2("lisi",24);
  5. Student2 s3 = new Student2("wangwu",25);
  6. TreeSet<Student2> ts = new TreeSet<>();
  7. ts.add(s1);
  8. ts.add(s2);
  9. ts.add(s3);
  10. System.out.println(ts);
  11. }
  12. }

方式二:

比较器排序:创建TreeSet对象时,传递比较器Comparator指定规则

举例:存入字符串"b","ac","bc","abc",按照长度排序,如果一样长则按照首字母排序

  1. public class TreeSetDemo3 {
  2. public static void main(String[] args) {
  3. /*TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {
  4. @Override
  5. public int compare(String o1, String o2) {
  6. int i = o1.length() - o2.length();
  7. i = i == 0 ? o1.compareTo(o2) : i;
  8. return i;
  9. }
  10. });*/
  11. //o1:表示当前要添加的元素
  12. //o2:表示在红黑树中已经存在的元素
  13. TreeSet<String> ts = new TreeSet<>((o1,o2)->{
  14. //按照长度排序
  15. int i = o1.length() - o2.length();
  16. //如果长度一样按照首字母排序
  17. i = i == 0 ? o1.compareTo(o2) : i;
  18. return i;
  19. });
  20. ts.add("c");
  21. ts.add("ac");
  22. ts.add("bc");
  23. ts.add("abc");
  24. System.out.println(ts);
  25. }
  26. }

使用原则:默认使用第一种,如果第一种不能满足当前需求,就使用第二种

总结:

1.如果想要集合中的元素可重复

  • 用ArrayList集合,基于数组的。(用的最多)

2.如果想要集合中的元素可重复,而且当前的增删操作明显多于查询

  • 用LinkedList集合,基于链表的

3.如果想对集合中的元素去重

  • 用HashSet集合,基于哈希表的。(用的最多)

4.如果想对集合中的元素去重,而且保证存取有序

  • 用LinkedHashSet集合,基于哈希表和双链表,效率低于HashSet

5.如果想对集合中的元素进行排序

  • 用TreeSet集合,基于红黑树。后续也可以用List集合实现排序
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小舞很执着/article/detail/766232
推荐阅读
相关标签
  

闽ICP备14008679号