2020.5.17

Set接口

特点：相对于list接口，set接口不能包含重复元素，并且可以有null元素
常用的set子集合

HashSet集合

特点：底层用的是哈希表存放元素，在1.7之前哈希表是用链表和数组存放，1.8之后优化成链表，数组和二叉树。
哈希表原理：

Set接口以及子集合（HashSet/LinkedHashSet/TreeSet）的用法和数据结构2020.5.17

一个数据储存过程，先根据元素通过hash函数，计算出元素的哈希值，由于哈希值比较大，然后用该数字对数组长度取余，得到的数据就是数组对应的下标，由于数组长度是有限的，所以在存储过程中可能会出现碰撞，多个元素计算的结果对应一个数组下标，链表就解决了这个情况，如果计算出的数组下标相同，就判断是否是同一个元素，如果是同一个元素，就不存储。不是就使用链表存放。
因此我们在存放对象时，对象就要重写Hash()方法那和equals()方法，重写Hash()方法是为了减少碰撞，重写equals()是避免元素重复。
- 元素特征转变为数组下标的方法就是散列法。散列法当然不止一种，下面列出三种比较常用的：
1，除法散列法

最直观的一种，上图使用的就是这种散列法，公式：

index = value % 16

学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“除法散列法”。

2，平方散列法

求index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU来说，估计我们感觉不出来），所以我们考虑把除法换成乘法和一个位移操作。公式：

index = (value * value) >> 28 （右移，除以2^28。记法：左移变大，是乘。右移变小，是除。）

如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。

3，斐波那契（Fibonacci）散列法

平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。

1，对于16位整数而言，这个乘数是40503

2，对于32位整数而言，这个乘数是2654435769

3，对于64位整数而言，这个乘数是11400714819323198485
```
这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，即如此形式的序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377, 610， 987, 1597, 2584, 4181, 6765, 10946，…。另外，斐波那契数列的值和太阳系八大行星的轨道半径的比例出奇吻合。
  
  对我们常见的32位整数而言，公式： 
          index = (value * 2654435769) >> 28
           
```
原文链接：https://blog.csdn.net/duan19920101/article/details/51579136
影响Hash碰撞（冲突）发生的除了Hash函数本身意外，底层数组容量也是一个重要原因。很明显，极端情况下如果数组容量为1，哪必然发生碰撞，如果数组容量无限大，哪碰撞的概率非常之低。所以，哈希碰撞还取决于负载因子。负载因子是存储的键值对数目与数组容量的比值，比如数组容量100，当前存贮了90个键值对，负载因子为0.9。负载因子决定了哈希表什么时候扩容，如果负载因子的值太大，说明存储的键值对接近容量，增加碰撞的风险，如果值太小，则浪费空间。
优点：因为它集合了数组和链表的特点，所以它查询块，增删也快。
缺点：它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以必须要清楚表中将要存储多少数据。

构造方法及方法

Set接口以及子集合（HashSet/LinkedHashSet/TreeSet）的用法和数据结构2020.5.17
代码示例：

1.package org.westos.demo0518; 
 
/*Author:LH
CreatTime:2020.05.18.15:04*/

import java.util.HashSet;
import java.util.Iterator;
import java.util.function.Consumer;

public class MyTest {
    public static void main(String[] args) {
        HashSet<Integer> hashset = new HashSet<>();
        hashset.add(100);
        hashset.add(200);
        hashset.add(200);
        hashset.add(300);
        System.out.println(hashset);
        System.out.println("========");
//        迭代器遍历方法
        Iterator<Integer> iterator = hashset.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        System.out.println("++++++++");
//        增强for循环遍历方法
        for (Integer integer : hashset) {
            System.out.println(integer);
        }
        System.out.println("++++++++");
//        foreach遍历方法
        hashset.forEach(new Consumer<Integer>() {
            @Override
            public void accept(Integer integer) {
                System.out.println(integer);
            }
        });
        /*集合中存放的是Integer和String类型时，不用手动重写hash方法和equals方法
        * 因为这两个类型已经默认重写了此方法，所以数据才会存进去并去重。
        * */
    }
}
2.package org.westos.demo0518; 
 
/*Author:LH
CreatTime:2020.05.18.15:15*/
import java.util.HashSet;
//要将Student对象存入set集合，对象就要重写Hash方法和equals方法,来保证元素唯一性
public class MyTest2 {
    public static void main(String[] args) {
        HashSet<Student> hashset = new HashSet<>();
        hashset.add(new Student("小王",23));
        hashset.add(new Student("李辉",23));
        hashset.add(new Student("王培红",24));
        hashset.add(new Student("扎西格勒",25));
        hashset.add(new Student("东方日出2",26));
//        System.out.println(hashset);
        for (Student student : hashset) {
            System.out.println(student.toString());
        }
    }
}
package org.westos.demo0518; 
 
/*Author:LH
CreatTime:2020.05.18.15:16*/

import java.util.Objects;

public class Student {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public Student() {
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age &&
                Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}
3.package org.westos.demo0518; 
 
/*Author:LH
CreatTime:2020.05.18.15:51*/

import java.util.ArrayList;
import java.util.LinkedHashSet;

//将list集合中重复元素去除。
//可以自己写方法去掉，也可以根据set集合的特点，转换
public class MyTest3 {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(100);
        list.add(100);
        list.add(300);
        list.add(200);
        list.add(300);
        list.add(500);
        list.add(600);
        list.add(700);
        for (Integer integer : list) {
            System.out.println(integer);
        }
        System.out.println("==========");
//        使用有参构造,将list集合传入，创建新的set集合，将自动去除重复元素
        LinkedHashSet<Object> linkedHashSet = new LinkedHashSet<>(list);
        for (Object o : linkedHashSet) {
            System.out.println(o);
        }
    }
}

LinkedHashSet集合

它的底层数据结构是链表和哈希表，链表保证有序（存取顺序一致），哈希表保证元素唯一。因此此集合的特点是元素有序，且唯一。但是线程不安全。
构造方法及方法

Set接口以及子集合（HashSet/LinkedHashSet/TreeSet）的用法和数据结构2020.5.17

案例演示：

1.package org.westos.demo0518.LinkedHashSet; 
 
/*Author:LH
CreatTime:2020.05.18.16:08*/

import java.util.LinkedHashSet;
//LinkedHashSet集合存取元素顺序一致，保证元素唯一性。
public class Test {
    public static void main(String[] args) {
        LinkedHashSet<Integer> integers = new LinkedHashSet<>();
        integers.add(100);
        integers.add(200);
        integers.add(200);
        integers.add(300);
        integers.add(300);
        integers.add(400);
        for (Integer integer : integers) {
            System.out.println(integer);
        }
    }
}

2.package org.westos.demo0518.LinkedHashSet; 
 
/*Author:LH
CreatTime:2020.05.18.16:35*/

import java.util.LinkedHashSet;
//LinkedHashSet存自定义对象，也要重写Hash方法和equals方法，来保证元素的唯一性
public class Test2 {
    public static void main(String[] args) {
        LinkedHashSet<Student> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add(new Student("李瑶",23));
        linkedHashSet.add(new Student("李其",23));
        linkedHashSet.add(new Student("李其",23));
        linkedHashSet.add(new Student("章子路",23));
        linkedHashSet.add(new Student("章子路",23));
        linkedHashSet.add(new Student("上官风雨",23));
        for (Student student : linkedHashSet) {
            System.out.println(student.toString());
        }
    }
}
package org.westos.demo0518.LinkedHashSet;
 
/*Author:LH
CreatTime:2020.05.18.15:16*/

import java.util.Objects;

public class Student {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public Student() {
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age &&
                Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

TreeSet集合

底层数据结构是二叉树，可以对元素排序，并且保证元素唯一性。
二叉树原理图

Set接口以及子集合（HashSet/LinkedHashSet/TreeSet）的用法和数据结构2020.5.17

二叉树存放数据，将进来的数据和根数据对比，根据排序方法，将数据放在其左右，相同元素不能被存放。

方法和构造方法

Set接口以及子集合（HashSet/LinkedHashSet/TreeSet）的用法和数据结构2020.5.17

代码演示：

1.package org.westos.demo0518.TreeSet; 
 
/*Author:LH
CreatTime:2020.05.19.16:26*/
//TreeSet集合使用自然排序存Integer类型数据
import java.util.Iterator;
import java.util.TreeSet;
import java.util.function.Consumer;

public class Test {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(23);
        treeSet.add(14);
        treeSet.add(15);
        treeSet.add(28);
        treeSet.add(8);
        Iterator<Integer> iterator = treeSet.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        for (Integer integer : treeSet) {
            System.out.println(integer);
        }
        treeSet.forEach(new Consumer<Integer>() {
            @Override
            public void accept(Integer integer) {
                System.out.println(integer);
            }
        });
    }
}
2.package org.westos.demo0518.TreeSet; 
 
/*Author:LH
CreatTime:2020.05.19.16:31*/

import java.util.Comparator;
import java.util.TreeSet;
//使用比较器排序
public class Test2 {
    public static void main(String[] args) {
//        重写Comparator接口的compare方法。
        TreeSet<Integer> treeSet = new TreeSet<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        treeSet.add(12);
        treeSet.add(34);
        treeSet.add(14);
        treeSet.add(67);
        treeSet.add(2);
        for (Integer integer : treeSet) {
            System.out.println(integer);
        }
    }
}
3.package org.westos.demo0518.TreeSet; 
 
/*Author:LH
CreatTime:2020.05.19.16:35*/

import java.util.TreeSet;
//TreeSet集合使用自然排序存自定义对象
public class TestStudent {
    public static void main(String[] args) {
        TreeSet<Student> treeSet = new TreeSet<>();
        treeSet.add(new Student("张三",23));
        treeSet.add(new Student("李四",23));
        treeSet.add(new Student("张三",25));
        treeSet.add(new Student("王五",28));
        treeSet.add(new Student("赵六",23));
        for (Student student : treeSet) {
            System.out.println(student.toString());
        }
    }
}
package org.westos.demo0518.TreeSet;
 
/*Author:LH
CreatTime:2020.05.18.15:16*/
// 自定义对象实现 Comparable<Student>，如果能明确泛型，一定要准确的把泛型写出来，此处不写也不会报错，
//只是重写compareTo(Student o)方法时，括号给的是Object数据类型，需要转型。
public class Student implements Comparable<Student> {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public Student() {
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
//    根据年龄大小排序，如果年龄相同，再判断姓名是否相同，相同就是同一个元素，不同则存进来
    public int compareTo(Student o) {
        int num=this.age-o.age;
        int num2=num==0?this.name.compareTo(o.name):num;
        return num2;
    }
}
4.package org.westos.demo0518.TreeSet; 
 
/*Author:LH
CreatTime:2020.05.19.17:09*/

import java.util.Comparator;
import java.util.TreeSet;
//使用比较器对自定义对象排序
public class TestStudent2 {
    public static void main(String[] args) {
        TreeSet<Student2> treeSet = new TreeSet<>(new Comparator<Student2>() {
            @Override
            //    根据年龄大小排序，如果年龄相同，再判断姓名是否相同，相同就是同一个元素，不同则存进来
            public int compare(Student2 o1, Student2 o2) {
                int num=o1.getAge()-o2.getAge();
                int num2=num==0?o1.getName().compareTo(o2.getName()):num;
                return num2;
            }
        });
        treeSet.add(new Student2("张三",18));
        treeSet.add(new Student2("李四",18));
        treeSet.add(new Student2("王五",27));
        treeSet.add(new Student2("李辉",18));
        treeSet.add(new Student2("张三",18));
        for (Student2 student2 : treeSet) {
            System.out.println(student2.toString());
        }
    }
}
package org.westos.demo0518.TreeSet;
 
/*Author:LH
CreatTime:2020.05.18.15:16*/

public class Student2 {
    private String name;
    private int age;

    public Student2(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public Student2() {
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}
5.package org.westos.demo0518.TreeSet;

import java.util.LinkedHashSet;
import java.util.Random;

/*Author:LH
CreatTime:2020.05.19.17:17*/
/*编写一个程序，获取10个1至20的随机数，要求随机数不能重复。
        并把最终的随机数输出到控制台。*/
public class Test3 {
    public static void main(String[] args) {
        Random random = new Random();
        LinkedHashSet<Integer> integers = new LinkedHashSet<>();
        while (integers.size()<=10) {
            int i = random.nextInt(20)+1;
            integers.add(i);
        }
        for (Integer integer : integers) {
            System.out.println(integer);
        }
    }
}
6.package org.westos.demo0518.TreeSet; 
 
/*Author:LH
CreatTime:2020.05.19.17:51*/

//案例演示:	需求：键盘录入3个学生信息(姓名,语文成绩,数学成绩,英语成绩),按照总分从高到低输出到控制台。

import java.util.Comparator;
import java.util.TreeSet;

/**
 * 步骤:
 * 		a: 自定义一个学生类
 * 		b: 创建一个TreeSet集合对象(使用比较器进行排序)
 * 		c: 键盘录入学生的数据,然后把学生的数据封装成一个学生对象,把学生对象添加到集合中
 * 		d: 遍历集合
 */
public class Test4 {
    public static void main(String[] args) {
        TreeSet<Student3> treeSet = new TreeSet<>(new Comparator<Student3>() {
            @Override
            public int compare(Student3 o1, Student3 o2) {
                int num=o1.getSum()-o2.getSum();
                int num2=num==0?o1.getName().compareTo(o2.getName()):num;
                return num2;
            }
        });
        treeSet.add(new Student3("张三",60,20,40));
        treeSet.add(new Student3("张三",67,20,47));
        treeSet.add(new Student3("李四",60,20,40));
        treeSet.add(new Student3("王五",69,90,41));
        treeSet.add(new Student3("张三",67,20,47));
        treeSet.add(new Student3("赵六",27,20,47));
        for (Student3 student3 : treeSet) {
            System.out.println(student3.toString());
        }
    }
}
package org.westos.demo0518.TreeSet; 
 
/*Author:LH
CreatTime:2020.05.19.17:53*/

public class Student3 {
    private String name;
    private  int chineseScore;
    private  int englishScore;
    private  int mathScore;

    public Student3(String name, int chineseScore, int englishScore, int mathScore) {
        this.name = name;
        this.chineseScore = chineseScore;
        this.englishScore = englishScore;
        this.mathScore = mathScore;
    }

    public Student3() {
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getChineseScore() {
        return chineseScore;
    }

    public void setChineseScore(int chineseScore) {
        this.chineseScore = chineseScore;
    }

    public int getEnglishScore() {
        return englishScore;
    }

    public void setEnglishScore(int englishScore) {
        this.englishScore = englishScore;
    }

    public int getMathScore() {
        return mathScore;
    }

    public void setMathScore(int mathScore) {
        this.mathScore = mathScore;
    }
    public int getSum(){
        return chineseScore+englishScore+mathScore;
    }

    @Override
    public String toString() {
        return
                "name='" + name + '\''+
                 '\t'+"chineseScore=" + chineseScore +
                '\t'+ "englishScore=" + englishScore +
                '\t'+"mathScore=" + mathScore +'\t'+
                "总分"+getSum();
    }
}

  public void setEnglishScore(int englishScore) {
        this.englishScore = englishScore;
    }

    public int getMathScore() {
        return mathScore;
    }

    public void setMathScore(int mathScore) {
        this.mathScore = mathScore;
    }
    public int getSum(){
        return chineseScore+englishScore+mathScore;
    }

    @Override
    public String toString() {
        return
                "name='" + name + '\''+
                 '\t'+"chineseScore=" + chineseScore +
                '\t'+ "englishScore=" + englishScore +
                '\t'+"mathScore=" + mathScore +'\t'+
                "总分"+getSum();
    }
}

Set接口以及子集合（HashSet/LinkedHashSet/TreeSet）的用法和数据结构2020.5.17

2020.5.17

Set接口

HashSet集合

LinkedHashSet集合

TreeSet集合

继续阅读

树的基本概念(定义、基本术语、性质)

GSL--GNU Scientific Library

D5|哈希表，善用数据结构

如何成为一名.net 工程师?

BMP文件结构及图像每行字节计算方法

D. Ehab the Xorcist(构造+思维)

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

[转]ISUP信令的IAM消息详细内容

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器