Set集合——hashSet、treeSet_treeset和hashset

J2EE

目录

J2EE

一、HashSet

1、概念：

2、Hashset

三、Hashset底层去重原理

四、treeset的两种排序

1、特点：

2、自然排序

二、比较器排序

总结：

---

前言：这篇分享treeset两种排序的使用，HashSet（就是HashMap）仅初步了解去重原理。

一、HashSet

1、概念：

无序（存储顺序和取出顺序无序），唯一。

对于无序易产生误区：我们有顺序的对元素进行存储，set是按照它自己的存储方式对我们的元素进行储存，然后输出来的顺序可能会和我们的存储顺序不一致，并不是每一次输出都是随机无序的。那么它的存储方式是怎样的呢？往下看

2、Hashset

HashSet就是HashMap

我们来看Hashset的无参构造源码。

 /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     * 翻译：构建一个新的空的Set集合，映射的HashMap的初始容量是16、加载因子0.75
     */
    public HashSet() {
        map = new HashMap<>();
    }

从源码我们可以看出来，Hashset底层就是一个hashMap。

        ①介绍：HashMap—散列图（一种以键值对形式进行存储的数据结构）

        ②如何实现：基于哈希表实现，也能说HashMap是数组+链表+红黑树（JDK1.8版本后增加），1.8之前是数组+链表

        ③图解：

 

④该结构优点：

首先了解是哈希相关知识：哈希法也被称为散列法、杂凑法、以及关键字地址计算法，对应的表就是哈希表。基本思想：在关键字K和存储地址P之间建立一个关系P=f(K),f是哈希函数，从而实现通过关键字取值。这里会有一个冲突，在关键字很庞大的情况下，会导致关键字值不同的情况映射到同一个地址上，即K1！=K2，但是f(K1)=f(K2)

解决冲突方法：

1、开放地址法

2、链地址法（数组+链表） 

java解决该冲突就是使用了第二个方法

回顾List集合中，ArrayList（底层数据结构：数组）的查询和修改快，LinkedList（底层数据结构：链表）的增加

和修改快。那么HashMap（数组+链表）在链表长度小的情况下查询修改速度快，增加和删除也快。

查询：通过K快速定位到数组的index然后在链表上查找元素（前提链表长度小）。增加，删除，修改同理，在链

表上增加（如果链表长度>8就转变成红黑树）、删除快。总而言之，这个结构就是综合了数组和链表的优点。

三、Hashset底层去重原理

首先我举一个简单例子理解了再看下面的流程图：

假设我们的table容量为4，然后有元素计算出来的哈希值分别为1，2，4，7。那么他们的存储位置是在那里呢？

用1%4计算出余数（即下标index）为1，所以先