目录一. Set 集合的特点二. Set 集合的实现类三. Set 接口中的方法四. Set 的三种遍历方法五. HashSet 底层原理六. 关于HashSet的几个问题七. LinkedHashSet底层原理八. TreeSet详解九. 单列集合的使用场景上帖 Java单列集合——List 我们讲述了 Java 中的其中一种单列集合 List这期我们来说说Java中的另一种单列集合Set。一. Set 集合的特点无序存取顺序不一致不重复不允许有相同元素的出现可以用来去重无索引没有关于索引的方法所以List中关于索引的方法Set都不能用也不能使用for循环遍历不能通过索引存取元素。二. Set 集合的实现类Set的实现类主要有以下三个1HashSet无序不重复无索引2LinkedHashSet因为加入了链表有序不重复无索引3TreeSet可排序不重复无索引。三. Set 接口中的方法因为Set也是单列集合Collection中的一种所以方法基本与Collection中的方法一致。这里还是简单罗列一下吧注意因为Set没有索引这里边的删除方法只能根据对象删除与List稍有区别。四. Set 的三种遍历方法迭代器遍历增强for遍历Lambda表达式遍历遍历方法在单列集合篇已详细展开这里就不重复展示了。五. HashSet 底层原理1HashSet底层采用哈希表存储数据2哈希表是一种增删改查数据性能都很好的数据结构哈希表的组成在不同的JDK版本中也略显不同JDK1.8之前数组链表JDK1.8之后数组链表红黑树哈希表中有一个哈希值非常重要如下图所示是一个哈希表暂时所有元素都为空以下性质需要掌握1创建一个长度为16默认加载因子为0.75的数组数组名为table2当我们向哈希表中去添加元素时它不是向数组那样从数组第一个位置挨个添加元素的而是通过哈希值与数组的长度计算出它应该存放的位置3存放时会判断当前位置是否为null如果是则直接存入4如果位置不为null表示有元素则会调用equal()方法比较属性值5判断得出结果如果一样则不存不一样则存入数组形成链表这里是对上述的补充1. 这里JDK8以前新元素存入时会采用头插法插在老元素的头部老元素下移形成链表2. 在JDK8以后新元素存入时采用尾插法插在老元素的尾部老元素位置不动形成链表3. 这里我们再来说加载因子当我们的数组中存入16 * 0.75 12 个元素的时候那么此时数组就会扩容成原来的2倍4. 当链表的长度大于8且数组的长度大于64时链表会转换成红黑树从而提高查找效率。关于什么是红黑树以及红黑树的性质可以浏览我之前的文章 “数据结构——红黑树”点击下方链接浏览。数据结构——红黑树_m0_70325779的博客-CSDN博客5. 如果集合中存贮的是自定义对象必须要重写equals()和hashcode()方法原因可以参照我之前的文章结合理解链接如下为什么重写equals方法之后必须要重写hashCode_m0_70325779的博客-CSDN博客六. 关于HashSet的几个问题6.1 HashSet是怎样添加元素的呢答 当想要存储一个元素时先计算它的哈希值再根据哈希值判断它应该存放的位置。6.2 HashSet为什么存和取的顺序不一样答 我们可以设想当我们存入了一个字符串 a “abcdefg”根据计算哈希值它放在哈希表的最后后来存入了一个字符串 b “hijklmn” 根据计算哈希值它放在哈希表的最前面当我们去取字符串a时他是要从头遍历哈希表的在第二次会取到字符串a而存入时是率先存入的。这样看就很明显的说明了为什么存入的顺序和取出的顺序不一样。6.3 HashSet为什么没有索引答 因为哈希表它不像数组那样里面还包含着链表以及红黑树加入哈希表中第二个位置是一个链表存储了三个元素那么这三个元素的索引都是2吗而且我们还没有考虑红黑树的情况这样很明显是不可以的所以在哈希表中就干脆取消了索引这个性质。6.4 HashSet是利用什么机制保证数据的不可重复性的答 equals()方法和hashCode()方法当想要存储一个元素时先计算它的哈希值再根据哈希值判断它应该存放的位置有元素则进行equals()比较如果是链表或红黑树,要对其中的每一个元素进行equals()比较不同则插入。从而达到了元素的不可重复性。七. LinkedHashSet底层原理LinkedHashSet的特点有序不重复无索引。相比于HashSet从无序变成了有序这里的有序指的是存入和取出的顺序是有序的。为什么呢想必大家通过名字就能猜出来个大概了。LinkedHashSet的前缀Linked说明在HashSet的基础上添加了一个链表而且这个链表是双向链表。这里我来距离简单说明是如何有序的如下图四个元素和一个哈希表添加第一个元素找到自己所在的位置因为为null直接加入如下添加第二个元素找到自己的位置直接加入然后通过双向链表的形式与第一次插入的元素形成关联如下所示同理插入第三个元素找到自己的位置再与第二个插入的元素形成链表指向如下插入第四个元素时也是如此如下所示插入完成后当我们遍历LinkedHashSet时它就不会像HashSet那样从第一个位置从头便利哈希表而是那个元素最先插入从哪个元素开始遍历以此遍历直到得到自己想要的元素从而达到了存取的有序性。八. TreeSet详解TreeSet 的特点不重复无索引可排序。可排序按照元素的默认规则(从小到大)排列。TreeSet 集合的底层结构TreeSet的底层是基于红黑树这种数据结构实现排序的增删改查性能都很好。TreeSet 集合的默认排序规则1对于数值类型IntegetDouble默认按照从小到大的顺序排列2对于字符字符串类型按照字符在ASCII码表中的数字升序排序。这里字符的比较是一位一位的比较先比较第一位谁大谁小小的排前面第一位一样再比较第二位谁小排前面后面同理。TreeSet 的两种比较方式8.4.1 方式一默认排序/自然排序(javaBean类实现Comparable接口指定比较规则)如下图现要对student类进行排序实现Comparable接口然后我们就可以在Comparable方法中指定我们自己想要的比较规则假设我这里只看年龄修改后代码如下所示这里有一点需要注意TreeSet底层是红黑树所以不需要强制重写HashCode()和equals()方法。这里需要了解红黑树的性质与插入规则不懂的可以看我之前的文章数据结构——红黑树_m0_70325779的博客-CSDN博客上面我们定义的是按照年龄排序方法返回值为int这里分为三种情况当int 0即返回值为正数时该元素存到当前元素的右边当int 0即返回值为负数时该元素存到当前元素的左边当int 0 表明当前元素已经存在会舍弃不存这里要知道当前节点首先指红黑树的根节点然后从根一步步进行判断找到自己应该插入的位置。8.4.2 方式二比较器排序(创建TreeSet的时候传递比较器指定Comparator规则)这两种比较器的使用原则默认使用第一种比较器如果第一种无法满足我们的需求就会使用第二种。来看线面两个练习题我们就能更好地理解它了。练习1分析题目后很明显可以发现原有的比较规则一已经无法达到我们想要的目的了我们接着看其实String类中已经帮我们重写定义好了排序规则如下String类实现了Comparable接口上面就是我们的排序规则一但我们现在要添加另一种排序规则改Java的源码似乎不太合适吧。这里我们可以采用TreeSet的另一个构造方法它需要传一个比较器但这个比较器Comparator是一个接口所以我们要对它进行实现。实现后如下所示o1是要插入的元素o2是红黑树中已经存在的元素这里我们先把o1与o2的长度作比较然后下面做判断如果等于零再调用String类中已经定义好的排序规则如果不等于0直接返回 i 值插入到红黑树中。练习2这里分析得知也是需要重新定义比较规则的我们再Student类中实现Comparable接口如下九. 单列集合的使用场景1如果想要集合中的元素可重复用ArrayList集合基于数组的(也是实际开发中用的最多的)。2如果想要集合中的元素可重复而且增删操作远多于查询用LinkedList集合基于链表的。3如果想对集合中的元素去重用HashSet集合基于哈希表的(实际开发中也用得最多)。4如果想对集合中的元素去重而且保证存取有序用LinkedHashSet集合基于哈希表和链表但效率要比HashSet低。5想要对集合中的元素进行排序用TreeSet集合基于红黑树。后续也可以用List集合实现排序。