Set集合不允许存储重复元素原理

package com.Set;

import java.util.HashSet;
/*
    Set集合不允许存储重复元素原理
 */
public class Demo02HashSetSaveString {
    public static void main(String[] args) {
        //创建HashSet集合对象
        HashSet<String> set = new HashSet<>();
        String s1 = new String("abc");
        String s2 = new String("abc");
        set.add(s1);
        set.add(s2);
        set.add("重地");
        set.add("通话");
        set.add("abc");
        System.out.println(set);  //[重地, 通话, abc]
    }
}

01：Set集合在调用add方法的时候，add方法会调用元素的hashCode方法和equals方法，判断元素是否重复。

1. set.add(s1);
   add方法会调用s1的hashCode方法，计算字符串“abc”的哈希值，哈希值是96354
   在集合中找有没有96354这个哈希值的元素，发现没有
   就会把s1存储在集合中
2. set.add(s2);
   add方法会调用s2的hashCode方法，计算字符串“abc”的哈希值，哈希值是96354
   在集合中找有没有96354这个哈希值的元素，发现有(哈希冲突） s2会调用equals方法和哈希值相同的元素进行比较
   s2.equals(s1),返回true 两个元素的哈希值相同，equals方法返回true,认定两个元素相同
   就不会把s2存储到集合中
3. set.add(“重地”);
   add方法会调用"重地"的hashCode方法，计算字符串"重地"的哈希值，哈希值是1179395
   在集合中找有没有1179395这个哈希值的元素，发现没有
   就会把"重地"存储在集合中
4. set.add(“通话”);
   add方法会调用"通话"的hashCode方法，计算字符串"通话"的哈希值，哈希值是1179395
   在集合中找有没有"通话"这个哈希值的元素，发现有(哈希冲突）
   “通话"会调用equals方法和哈希值相同的元素进行比较"通话”.equals"重地"),返回false
   两个元素的哈希值相同，equals方法返回false,认定两个元素不同
   就把"通话"存储到集合中

02：Set集合存储不重复的元素
前提：存储的元素必须重写hashCode方法和equals方法

目录

庖丁解牛术法总纲

第一重境界：所见莫非全牛者

1、概述：

2、Set集合特点：

3、分类（实现子类）：

 4、所有已知实现类：

 5、注意事项

 6、所有方法

第二重境界：未尝见全牛也

HashSet

1、HashSet特点：

2、HashSet集合添加一个元素的过程：

3、代码演示

 4、注意事项（特殊之处，遍历无序的原因不是排序的无序，而是底层哈希值的存放地址的原因）

5、LinkedHashSet集合概述和特点

TreeSet

1、TreeSet集合特点

2、注意事项

3、代码展示（比较器排序）

第三重境界：官知止而神欲行

1、哈希值（hashCode）

概念：

特点：

代码展示：

2、哈希表

概念：

哈希表的实现：

哈希表的优缺点：

哈希表的学习：

---

庖丁解牛术法总纲

       吾生也有涯，而知也无涯 。以有涯随无涯，殆已！已而为知者，殆而已矣！为善无近名，为恶无近刑。缘督以为经，可以保身，可以全生，可以养亲，可以尽年。

       “庖丁为文惠君解牛，手之所触，肩之所倚，足之所履，膝之所踦，砉然向然，奏刀騞然，莫不中音。合于《桑林》之舞，乃中《经首》之会。

       文惠君曰：“嘻，善哉！技盖至此乎？”

       庖丁释刀对曰：“臣之所好者，道也，进乎技矣。始臣之解牛之时，所见无非牛者。三年之后，未尝见全牛也。方今之时，臣以神遇而不以目视，官知止而神欲行。依乎天理，批大郤，导大窾，因其固然，技经肯綮之未尝，而况大軱乎！良庖岁更刀，割也；族庖月更刀，折也。今臣之刀十九年矣，所解数千牛矣，而刀刃若新发于硎。彼节者有间，而刀刃者无厚；以无厚入有间，恢恢乎其于游刃必有余地矣，是以十九年而刀刃若新发于硎。虽然，每至于族，吾见其难为，怵然为戒，视为止，行为迟。动刀甚微，謋然已解，如土委地。提刀而立，为之四顾，为之踌躇满志，善刀而藏之。”

                                                                                                                ——《庄子·养生主》

呔，妖怪。看法宝！

第一重境界：所见莫非全牛者

1、概述：

       Set集合类似于一个罐子，程序可以依次把多个对象“丢进”Set集合，而Set集合通常不能记住元素的添加顺序。实际上Set就是Collection，只是行为略有不同(Set不允许包含重复元素)。
       Set集合不允许包含相同的元素，如果试图把两个相同元素加入同一个Set集合中，则添加操作失败，add()方法返回false，且新元素不会被加入。

2、Set集合特点：

（1）、不包含重复元素的集合

（2）、没有带索引的方法，所以不能使用普通for循环遍历

3、分类（实现子类）：

（1）、HashSet

（2）、TreeSet

 4、所有已知实现类：

• AbstractSet ， ConcurrentHashMap.KeySetView ， ConcurrentSkipListSet ， CopyOnWriteArraySet ， EnumSet ， HashSet ， JobStateReasons ， LinkedHashSet ， ReadOnlySetProperty ， ReadOnlySetPropertyBase ， ReadOnlySetWrapper ， SetBinding ， SetExpression ， SetProperty ， SetPropertyBase ， SimpleSetProperty ， TreeSet

 5、注意事项

不包含重复元素的集合。 更正式地，集合不包含一对元素e1和e2 ，使得e1.equals(e2) ，并且最多只有一个空元素。 正如其名称所暗示的那样，这个接口模拟了数学集抽象。

该Set接口放置额外的约定，超过从继承Collection接口，所有构造函数的合同，而位于该合同add ， equals和hashCode方法。 其他继承方法的声明也包括在这里以方便。 （这些声明中附带的规格已针对Set接口进行了定制，但不包含任何其他规定。）

构造函数的额外规定并不奇怪，所有构造函数都必须创建一个不包含重复元素的集合（如上所定义）。

注意：如果可变对象用作设置元素，则必须非常小心。 如果对象的值以影响equals比较的方式更改，而对象是集合中的元素，则不指定集合的行为。 这种禁止的一个特殊情况是，一个集合不允许将其本身作为一个元素。

一些集合实现对它们可能包含的元素有限制。 例如，一些实现禁止空元素，有些实现对元素的类型有限制。 尝试添加不合格元素会引发未经检查的异常，通常为NullPointerException或ClassCastException 。 尝试查询不合格元素的存在可能会引发异常，或者可能只是返回false; 一些实现将展现出前者的行为，一些实现将展现出后者。 更一般来说，尝试对不符合条件的元素的操作，其完成不会导致不合格元素插入到集合中，可能会导致异常，或者可能会成功执行该选项。 此异常在此接口的规范中标记为“可选”。

 6、所有方法

• • Modifier and Type	方法	描述
    boolean	add​(E e)	如果指定的元素不存在，则将其指定的元素添加（可选操作）。
    boolean	addAll​(Collection<? extends E> c)	将指定集合中的所有元素添加到此集合（如果尚未存在）（可选操作）。
    void	clear​()	从此集合中删除所有元素（可选操作）。
    boolean	contains​(Object o)	如果此集合包含指定的元素，则返回 true 。
    boolean	containsAll​(Collection<?> c)	如果此集合包含指定集合的所有元素，则返回 true 。
    boolean	equals​(Object o)	将指定的对象与此集合进行比较以实现相等。
    int	hashCode​()	返回此集合的哈希码值。
    boolean	isEmpty​()	如果此集合不包含元素，则返回 true 。
    Iterator<E>	iterator​()	返回此集合中元素的迭代器。
    static <E> Set<E>	of​()	返回一个包含零个元素的不可变集合。
    static <E> Set<E>	of​(E e1)	返回一个包含一个元素的不可变集合。
    static <E> Set<E>	of​(E... elements)	返回一个包含任意数量元素的不可变集合。
    static <E> Set<E>	of​(E e1, E e2)	返回一个包含两个元素的不可变集合。
    static <E> Set<E>	of​(E e1, E e2, E e3)	返回一个包含三个元素的不可变集合。
    static <E> Set<E>	of​(E e1, E e2, E e3, E e4)	返回一个包含四个元素的不可变集合。
    static <E> Set<E>	of​(E e1, E e2, E e3, E e4, E e5)	返回一个包含五个元素的不可变集合。
    static <E> Set<E>	of​(E e1, E e2, E e3, E e4, E e5, E e6)	返回一个包含六个元素的不可变集合。
    static <E> Set<E>	of​(E e1, E e2, E e3, E e4, E e5, E e6, E e7)	返回一个包含七个元素的不可变集合。
    static <E> Set<E>	of​(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8)	返回一个包含八个元素的不可变集合。
    static <E> Set<E>	of​(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9)	返回一个包含九个元素的不可变集合。
    static <E> Set<E>	of​(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10)	返回一个包含十个元素的不可变集合。
    boolean	remove​(Object o)	如果存在，则从该集合中删除指定的元素（可选操作）。
    boolean	removeAll​(Collection<?> c)	从此集合中删除指定集合中包含的所有元素（可选操作）。
    boolean	retainAll​(Collection<?> c)	仅保留该集合中包含在指定集合中的元素（可选操作）。
    int	size​()	返回此集合中的元素数（其基数）。
    default Spliterator<E>	spliterator​()	在此集合中的元素上创建一个 Spliterator 。
    Object[]	toArray​()	返回一个包含此集合中所有元素的数组。
    <T> T[]	toArray​(T[] a)	返回一个包含此集合中所有元素的数组; 返回的数组的运行时类型是指定数组的运行时类型。

第二重境界：未尝见全牛也

HashSet

1、HashSet特点：

（1）底层数据结构是哈希表(查询速度快)，使用HashCode哈希值

（2）对集合的迭代顺序不作任何保证，也就是说不保证存储和取出的元素顺序一致

（3）没有带索引的方法，所以不能使用普通for循环遍历

（4）由于是Set集合，所以是不包含重复元素的集合

2、HashSet集合添加一个元素的过程：

      

3、代码演示

package SetDemo;

import java.util.HashSet;

public class Set01 {
    public static void main(String[] args) {
        //导包创建对象HashSet
        HashSet<String> set=new HashSet<String>();

        //添加数据
        set.add("aaa");
        set.add("bbb");
        set.add("ccc");
        set.add("ddd");

        //增强for循环遍历
        for (String i:set){
            System.out.println(i);
        }

    }
}

//代码输出结果
E:\develop\JDK\bin\java.exe "-javaagent:E:\IDEA\IntelliJ IDEA Community Edition 
aaa
ccc
bbb
ddd

Process finished with exit code 0

 4、注意事项（特殊之处，遍历无序的原因不是排序的无序，而是底层哈希值的存放地址的原因）

 public static void main(String[] args) {
        HashSet<String> set=new HashSet<String>();

        set.add("hello");
        set.add("world");
        set.add("java");

        //集合自带排序方式
        System.out.println(set);
        System.out.println("--------");
        //迭代器方式
        Iterator<String> it = set.iterator();
        while (it.hasNext()){
            String s = it.next();
            System.out.println(s);
        }
        System.out.println("--------");
        //增强for循环
        for (String s:set){
            System.out.println(s);
        }

 }

//输出结果
[world, java, hello]
--------
world
java
hello
--------
world
java
hello

Process finished with exit code 0

 上述代码是正常输出的结果，但是以下的代码的输出，请看：

public static void main(String[] args) {
        HashSet<String> set=new HashSet<String>();

        set.add("6");
        set.add("7");
        set.add("8");
        set.add("9");
        set.add("10");

        //集合自带排序方式
        System.out.println(set);
        System.out.println("--------");
        //迭代器方式
        Iterator<String> it = set.iterator();
        while (it.hasNext()){
            String s = it.next();
            System.out.println(s);
        }
        System.out.println("--------");
        //增强for循环
        for (String s:set){
            System.out.println(s);
        }

    }

//代码输出结果
[6, 7, 8, 9, 10]
--------
6
7
8
9
10
--------
6
7
8
9
10

Process finished with exit code 0

public static void main(String[] args) {
        HashSet<String> set=new HashSet<String>();
        set.add("a");
        set.add("b");
        set.add("c");
        set.add("d");
        set.add("e");

        //集合自带排序方式
        System.out.println(set);
        System.out.println("--------");
        //迭代器方式
        Iterator<String> it = set.iterator();
        while (it.hasNext()){
            String s = it.next();
            System.out.println(s);
        }
        System.out.println("--------");
        //增强for循环
        for (String s:set){
            System.out.println(s);
        }

    }

//代码输出结果
[a, b, c, d, e]
--------
a
b
c
d
e
--------
a
b
c
d
e

Process finished with exit code 0

上述两则代码结果，可以看到输出结果都是有序的，而HashSet特点有一，就是不保证迭代顺序。这不就是矛盾的一处地方吗？

原因：但并不是HashSet的自相矛盾，其原因就是底层实现的特点。哈希表实现，计算哈希值，通过哈希值代替索引的作用，查询存储的值。

而哈希值的计算，有一套自己的计算规则，当一串字符串计算哈希值时，哈希值的区别也许会很大，但如果是有规律的数字、字符进行计算哈希值时，其哈希值有会时有序的。

表现出来的结果就是在控制台输出有顺序有规律的单节字符时，输出也是有规律的。

5、LinkedHashSet集合概述和特点

（1）集合特点：

哈希表和链表实现的Set接口，具有可预测的迭代顺序。

由链表保证元素有序，也就是说元素的存储和取出顺序是一致的。

由哈希表保证元素唯一，也就是说没有重复的元素。

（2）代码案例

TreeSet

1、TreeSet集合特点

（1）元素有序，这里的顺序不是指存储和取出的顺序，而是按照一定的规则进行排序，具体排序方式取决于构造方法
    TreeSet​()：根据其元素的自然排序进行排序
    TreeSet​(Comparator<? super E> comparator) ：根据指定的比较器进行排序

（2）没有带索引的方法，所以不能使用普通for循环遍历

（3）由于是Set集合，所以不包含重复元素的集合

2、注意事项

用TreeSet集合存储自定义对象，无参构造方法使用的是自然排序对元素进行排序的

 自然排序，就是让元素所属的类实现Comparable接口，重写compareTo​(T o)方法
    重点：如何重写方法

重写方法时，一定要注意排序规则必须按照要求的主要条件和次要条件来写
    重点：主要条件与次要条件

用TreeSet集合存储自定义对象，带参构造方法使用的是比较器排序对元素进行排序的

 比较器排序，就是让集合构造方法接收Comparator的实现类对象，重写compare​(T o1,T o2)方法

重写方法时，一定要注意排序规则必须按照要求的主要条件和次要条件来写

3、代码展示（比较器排序）

package SetDemo;

import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class Set003 {
    public static void main(String[] args) {

        Set<News> set=new TreeSet<News>(new Comparator<News>() {
            @Override
            public int compare(News n1, News n2) {
                int num=n1.getTitle().compareTo(n2.getTitle());
                return num;
            }
        });

        News news1=new News("中国多地遭雾霾笼罩空气质量再成热议话题");
        News news2=new News("民进党台北举行“火大游行”");
        News news3=new News("春节临近北京“卖房热”");
        News news4=new News("春节临近北京“卖房热”");

        System.out.println("新闻一与新闻二的比较："+news1.equals(news2));
        System.out.println("新闻三与新闻四的比较："+news3.equals(news4));
        System.out.println("--------");
        set.add(news1);
        set.add(news2);
        set.add(news3);
        set.add(news4);

        for (int i = 0; i < set.size(); i++) {

        }

        Set<News> set1=new HashSet<News>();
        set1.addAll(set);

        for (News n:set1){
            System.out.println(n);
        }
        System.out.println("--------");


        System.out.println("集合中新闻的长度为："+set1.size());



    }
}

第三重境界：官知止而神欲行

1、哈希值（hashCode）

概念：

       是Jdk根据对象的地址/String/数字算出来一串数字(int)，hashCode()是Object类的方法,所以说Java的对象都可以调用这个hashCode方法返回哈希值。

特点：

       （1）如果自定义类没有重写hashCode方法,那么自定义类的对象生成的哈希值是根据对象的内存地址值生成的,所以说即便两个对象的属性一样,哈希值也不一样。
       （2）诉求:如果两个对象属性一样,那么两个对象哈希值也要一样,所以在自定义的类中重写了      hashCode方法(不调用Object类hashCode),是根据对象的属性生成哈希值。
       （3）两个对象哈希值一样,不代表两个对象的属性一样.两个对象的属性一样,则两个对象的哈希值肯定一样。
       （4）数字的哈希值是它本身。

代码展示：

public static void main(String[] args) {
        
        //创建学生类对象，实例化
        Student s1 = new Student02("盘古大神", 100, 100, 100,300);
        Student s2 = new Student02("女娲娘娘", 100, 95, 90,285);
        Student s3 = new Student02("天皇伏羲", 98, 100, 90,288);
        Student s4 = new Student02("地皇神农", 99, 95, 90,284);
        Student s5 = new Student02("人皇轩辕", 95, 98, 80,273);
           
        //输出哈希值
        System.out.println(s1.hashCode());
        System.out.println(s2.hashCode());
        System.out.println(s3.hashCode());
        System.out.println(s4.hashCode());
        System.out.println(s5.hashCode());


    }

//输出结果

356573597
1735600054
21685669
2133927002
1836019240

Process finished with exit code 0

2、哈希表

概念：

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

哈希表的实现：

实现哈希表我们可以采用两种方法：

1、数组+链表

2、数组+二叉树

哈希表的优缺点：

优点：

1. 无论数据有多少，处理起来都特别的快
2. 能够快速地进行 插入修改元素 、删除元素 、查找元素 等操作
3. 代码简单（其实只需要把哈希函数写好，之后的代码就很简单了）

缺点：

1. 哈希表中的数据是没有顺序的
2. 数据不允许重复

哈希表的学习：

如果大家想再深入学习哈希表的知识，下附链接：

数据结构 Hash表（哈希表）_积跬步 至千里-CSDN博客_哈希表

 ending!!!!!

Redis 有序集合（Sorted Set）和集合（Set）的相同点是，都是 String 类型元素的集合，且都不允许出现重复元素。不同的是有序集合的每个元素都会关联一个 double 类型的分数，而 Redis 正是通过分数来为集合中的成员进行从小到大的排序。虽然有序集合的元素是唯一的，但是元素对应的分数（score）却是可以重复。

有序集合是通过哈希表实现的，所以添加、删除、查找的复杂度都是 O(1)。集合中最大成员数为 2^32 - 1 （4294967295）个。

Redis 中有序集合（Sorted Set）的相关命令如下：

Redis 有序集合(Sorted Set) 命令

命令	说明	返回值	示例
ZADD key score1 member1 [score2 member2]	用于将一个或多个成员及其分数值加入到有序集合 key 中，如果某个成员已经是该有序集合的成员，则更新其分数值，并重新插入，以确保该成员在正确的位置上，分数值可以是整数值或双精度浮点数。如果指定的 key 不存在，则创建一个空的有序集合并执行 ZADD 操作，当 key 存在但不是有序集合类型时，返回一个错误	被成功添加的新成员的数量，不包括被更改的和已经存在的成员
ZRANGE key start stop [WITHSCORES]	用于返回有序集合中执行区间内的成员，其中成员的位置按照分数值从小到大排列，具有相同分数值的成员按照字典序来排列，下标 start 和 stop 都以 0 为底，即有序集合中的第一个成员的下标是 0，同时也可以使用负数下标，-1 表示最后一个成员，-2 表示倒数第二个成员	返回指定区间内，带有分数值(可选)的有序集合内的成员列表
ZRANGEBYSCORE key min max [WITHSCORES]	用于返回有序集合中指定分数区间的成员列表，有序集合中成员按照分数值递增的顺序排列，具有相同分数值的成员按照字典序升序来排列。默认为闭区间[min, max]	返回指定区间内，带有分数值(可选)的有序集合内的成员列表
ZCARD key	用于计算有序集合中的元素的数量	当 key 存在且是有序集合类型时，返回有序集合中元素的数量，当 key 不存在时，返回 0
ZCOUNT key min max	用于计算有序集合中执行分数区间的成员数量	返回分数值在 min 和 max 之间的成员数量，闭区间[min, max]
ZLEXCOUNT key min max	用于计算有序集合中指定字典区间内的成员数量	返回指定字典区间内的成员数量
ZRANGE BYLEX key min max [LIMIT offset count]	用于通过字典区间返回有序集合的成员	返回指定区间内的元素列表
ZRANK key member	用于返回有序集合中指定成员的排名，也可以理解为索引，其中有序集合中成员按照分数递增顺序排列	返回指定成员 member 的索引（从 0 开始）
ZREVRANGE key start stop [WITHSCORES]	与 ZRANGE 命令相似，用于返回有序集合中指定区间内的成员，其中成员的位置按照分数值递减来排列，具有相同分数值的成员，按照字典的升序排列	返回指定区间内带有分数值(可选)的有序集合成员列表
ZREVRANGEBYSCORE key max min [WITHSCORES]	与 ZRANGEBYSCORE 命令相似，用于返回有序集合中指定分数区间的成员列表，有序集合中成员按照分数值递减的顺序排列，具有相同分数值的成员按照字典序逆序来排列。默认为闭区间[max, min]	返回指定区间内带有分数值(可选)的有序集合成员列表
ZREVRANK key member	与 ZRANK 命令相似，用于返回有序集合中指定成员的排名，也可以理解为索引，其中有序集合中成员按照分数递减顺序排列	返回指定成员 member 的索引（从 0 开始）
ZSCORE key member	返回有序集合中成员 member 的分数值	成员的分数值，以字符串形式表示，当 key 或者 member 不存在时，返回 nil
ZINTERSTORE distination numkeys key1 [key2 ...]	用于计算给定的一个或多个有序集合的交集，其中给定 key1 的数量必须以 keynums 参数指定，并将该交集结果集存储到 destination 中。目标有序集合 destination 中某个成员的分数值是所有给定集合下的该成员分数值之和	保存到目标结果集中的成员的数量
ZUNIONSTORE destination numkeys key1 [key2 ...]	用于计算给定的一个或多个有序集合的交集，其中给定 key1 的数量必须以 keynums 参数指定，并将该交集结果集存储到 destination 中。目标有序集合 destination 中某个成员的分数值是所有给定集合下的该成员分数值之和	保存到目标结果集中的成员的数量
ZINCRBY key increment member	对有序集合中指定成员的分数加上指定的增量，增量可为负值	member 成员的新的分数值，以字符串形式表示
ZSCAN key cursor [MATCH pattern] [COUNT count]	用于迭代有序集合中的元素，包括元素成员和元素的分值	返回的每一个元素都是一个有序集合元素，由成员 member 和分值 score 组成
ZREM key member [member ...]	用于移除有序集合中的一个或多个成员，不存在的成员将被忽略。当 key 不存在或者不是有序集合类型时，返回一个错误	返回被成功移除的元素的数量，不包括被忽略的成员
ZREMRANGEBYLEX key min max	用于移除有序集合中给定的字典区间的所有成员	返回被成功移除的元素的数量，不包括被忽略的成员
ZREMRANGEBYRANK key start stop	用于移除有序集合中指定排名区间内的所有成员	返回被移除成员的数量
ZREMRANGEBYSCORE key min max	用于移除有序集合中指定分数区间内的所有成员	返回被移除成员的数量

目前对于有关 LEX 的命令理解与官方文档有些出入，后期会专门写一篇关于这些命令的文章，同时由于 ZSCAN 命令是继承于 SCAN 命令的，此处也不再描述，后期会专门有一篇来说明 SCAN 命令的用法的。