集合精通

Set集合：

HashSet集合和TreeSet集合的区别：

HashSet：底层是hash表，线程不安全

TreeSet：底层是二叉树，线程不安全

哈希表：

简介：Set集合的两个实现类HashSet和LinkedHashSet，底层实现都是哈希表

1.Hash，一般译为散列，也有直接译为哈希的，它是一个基于快速存取的角度设计的，也是一种典型的空间换时间的做法，顾名思义，该数据结构可以理解为一个线性表，但是其中的元素不是紧密排列的，而是可能存在空隙

2.散列表（Hash Table）：是根据键值码值（key value）而直接进行访问的数据结构，也就是说，它通过把键值码值映射到表中的一个位置来访问记录，以加快查找的速度，这个映射函数称为散列函数（Hash Table）

3.Hash表的组成是：数组+链表这些元素是按照什么样的规则存储到数组中的呢，一般情况下是通过hash（key）%length获取，也就是元素的key的哈希值对数组长度取模得到

hash表扩容的理解：

可是当哈希表接近装满的时候，因为数组的扩容问题，性能较低（转移到更大的哈希表中）

Java默认的散列单元大小全部都是2的幂，初始值为16（2^4），假如16条链表中的75%有数据的时候，则认为加载因子达到默认的0.75。hashSet开始宠幸散列，也就是将原来的散列结构全部抛弃，并重新计算各个数据的存储位置，以此类推下去

负载（加载）因子：0.75——>>hash表提供的空间是16，也就是当到达12的时候就扩容

排重机制的实现：

假如我们有一个数据（散列码76268），而此时的HashSet有128个散列单元，那么这个数据将有可能插入到数组的第108和链表中（76268 % 128 = 108）。但这只是有可能，如果在第108号链表中发现了有一个老数据与新数据equals（）= true的话，这个新数据将被视为已经加入，而不再重复丢入链表

优点:

hash表的插入和查找都是很优秀的

对于查找：直接根据数据的散列码和散列表的数组大小计算除余后，就得到了所在数组的位置，然后在查找链表中是否有这条数据即可，因为数组本身的查找速度快，所以查找的效率高低体现在链表中，但是真实情况下，一条链表中的数据又很少，有的甚至没有，所以就几乎没有什么迭代的代价，所以散列表的查找效率建立在散列单元所指向的链表中的数据的多少上

对于插入：数组的插入速度慢，而链表的插入速度快，当我们不再使用hash表的时候不需要更改数组的结构，只需要在找到对应的数组下标后，进入对应的链表，操作链表即可，所以hash表的整体插入顺序也很快

二叉树：

概念：树是由根节点和若干棵子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位、这个结点称为该树的根节点，或称为树根。

注意：普通树的每个结点的子节点个数不一定是2个

注意：单个节点也是一棵树，树根就是该结点本身

注意：空集合也是树，称为空树，空树中没有节点

森林：

相关概念：

由m（m大于等于0）棵互不相交的树的集合称为森林

孩子节点或者子节点：一个节点中含有的子树的称为该结点的子节点

结点的度：一个节点含有子结点的个数称为该结点的度

叶节点或者终端节点：度为0的结点称为叶结点

非终端节点或者分支节点：度不为0的结点

双亲结点或者父节点：若一个结点含有子节点，则这个节点称为其子节点的父节点

兄弟节点：具有相同父节点的结点称为兄弟节点

树的度：一棵树中，最大的节点的度称为树的度

结点的层次：从根开始定义，根为第一层，跟的子节点为第二层，以此类推

树的高度和深度：树中节点的最大层次

堂兄弟节点：双亲在同一层的结点互为堂兄弟

结点的祖先：从跟到该结点所经分支上的所有结点

子孙：以某节点为根的子树中任一节点都称为该结点的子孙

树的分类：

无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称*树

有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树

二叉树：每个结点最多含有两个子树的树称为二叉树

满二叉树：叶节点除外的所有节点均含有两个子树的树称为满二叉树

完全二叉树：有2^k-1个节点的满二叉树称为完全二叉树

哈夫曼树（最优二叉树）：带权路劲最短的二叉树称为哈夫曼树或最优二叉树

二叉树的遍历

1.二叉树是一种非常重要的数据结构，他同时具有数组和链表各自的特点：它可以像数组一样快速的查找，也可以像链表一样快速添加。但他也有自己缺点：删除操作复杂

2.二叉树：是每个结点最多有两个子树的有序树，在使用二叉树的时候，数据并不是随便插入到节点中的，一个节点的左子节点的关键值，必须小于此节点，右子节点的关键值必须大于或是等于此节点，所以又称二叉查找树，二叉排序树，二叉搜索树

二叉树的遍历方式：

先序遍历：

首先访问根，再先序遍历左子树，最后先序遍历右子树（根左右）

中序遍历：

首先中序遍历左子树，再访问根，最后中序遍历右子树（左跟右）

后序遍历：

首先后序遍历左子树，再后序遍历右子树，最后访问根

去重原理：

HashSet和LinkedHashSet

是通过调用元素的hashCode和equals方法实现去重，首先调用hashCode方法，拿到当前对象的哈希码值，去让两个对象的哈希码值进行比较，如果不同，直接认为是两个对象，不再去调用equals，如果相同，再继续调用equals方法，返回true认为是一个对象，返回false认为是两个对象

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bz4y5oJZ-1622422018276)(C:\Users\16326\Desktop\dayHomework\数据结构\QQ截图20210530151636.png)]

package bk.javase;

import java.util.HashSet;
import java.util.StringJoiner;

public class p530 {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        set.add("java");
        set.add("php");
        set.add("bigData");
        set.add("java");
        System.out.println(set); //[bigData, java, php]
        //说明Set本身的add方法内部实现了去重功能，默认调用的是元素的hashCode方法和equals方法
        //String方法已经默认重写了hashCode和equals方法

        //在创建一个HashSet
        HashSet<Person> set2 = new HashSet<>();
        set2.add(new Person("zhangsan", 20));
        set2.add(new Person("lisi", 30));
        set2.add(new Person("wangwu", 40));
        set2.add(new Person("zhangsan", 20));
        System.out.println(set2);
        //[Person[name='wangwu', age=40], Person[name='lisi', age=30], Person[name='zhangsan', age=20], Person[name='zhangsan', age=20]]
        //new出来的四个对象的地址肯定不同，那么放到HashSet中的第一步就直接判断而这不相同了。
        //解决方式：
        //自己制定比较的规则：并按照年龄和性别比较，相同则认为是同一个人
        //第一步：重写hashcode方法
        //第二步：重写equals方法
//[Person[name='lisi', age=30], Person[name='zhangsan', age=20], Person[name='wangwu', age=40]]
    }
}

class Person{
    String name;
    int age;

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

    @Override
    public String toString() {
        return new StringJoiner(", ", Person.class.getSimpleName() + "[", "]")
                .add("name='" + name + "'")
                .add("age=" + age)
                .toString();
    }

    //自己指定比较的规则：并按照年龄与姓名进行比较，相同则认为是同一个人
    @Override
    public boolean equals(Object obj) {
       //若二者地址相同，那内容一定相同
        if (this == obj) return true;
        //若obj为空，那内容一定不同
        if (obj == null) return false;
        //若二者真实类型不同，那内容一定不同
        if(this.getClass() != obj.getClass()) return false;
        //强转为子类真实类型
        Person p = (Person) obj;
        //开始比较
        if (age == p.age && name.equals(p.name)){
            return true;
        }else{
            return false;
        }
    }

    @Override
    public int hashCode() {
        return name.hashCode() + age * 1000;
    }
}

TreeSet

简介：TreeSet是Set接口的实现类，底层是二叉树，这样的集合，会对添加进集合的元素进行去重的处理，同时，这个集合中会对添加进入的元素进行自动的升序排序

Comparable接口（默认排序）

如果某一个类实现这个接口，表示自己实现了一个可以和自己的对象进行大小的规则。此时，这个类的对象就可以直接存储到TreeSet集合中了，因此此时的TreeSet集合已经知道了怎么对这两个类的对象进行大小的比较

package bk.javase.p530;

import java.util.StringJoiner;
import java.util.TreeSet;

public class TreeSetTest {
    public static void main(String[] args){
        //将字符串存储TreeSet
    /*
    TreeSet的add方法实现的排序，去重，通过调用元素的compareTo方法
    String类已经实现了Comparable接口，并且重写了compareTo方法
     */
        TreeSet<String> set = new TreeSet<>();
        set.add("java");
        set.add("php");
        set.add("bigData");
        set.add("java");
        System.out.println(set);
        //[bigData, java, php]

        //创建一个新的TreeSet集合
        TreeSet<Person2> set2 = new TreeSet<>();
        set2.add(new Person2("zhangsan",20));
        set2.add(new Person2("lisi",30));
        set2.add(new Person2("zhangsan",20));
        System.out.println(set2);
//Exception in thread "main" java.lang.ClassCastException: bk.javase.p530.Person2 cannot be cast to java.lang.Comparable
        //TreeSet集合也是元素不能重复，但是他的实现不同于HashSet，他去重是根据Comparable接口中的compareTo方法来实现的
        //[Person2[name='zhangsan', age=20], Person2[name='lisi', age=30]]
    }
}

class Person2 implements Comparable<Person2>{
    String name;
    int age;

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

    @Override
    public String toString() {
        return new StringJoiner(", ", Person2.class.getSimpleName() + "[", "]")
                .add("name='" + name + "'")
                .add("age=" + age)
                .toString();
    }

//自己制定比较的规则：先比姓名再比年龄
    /*
    == 0   this == o
    >0 | < 0 this != o
     */
    @Override
    public int compareTo(Person2 person2) {
        if (person2.name.equals(name) && person2.age == age){
            return 0;
        }
        return 1;
    }
}

Comparable接口：

定义：使用了实现了Comparable接口的compare（）方法的比例器对象进行比较

问题一：有了Comparable接口为什么还要有comparator?

答：

1.对于自定义的类，代码是我们自己编写的，所有在排序是不管是通过Comparator还是Comparable，排序规则我们都可以是自己制定，所以最终使用哪种方法没有太大的区别，

2.对于系统类影响非常大，系统中的代码我们只能用，不能修改，这也就意味着系统内部通过Comparable实现的比较规则已经确定了，这是我们想要使用的其他的规则对当前的系统类对象进行比较，只能使用Comparator自己重新制定比较规则

问题二：人工排序和默认排序的优先级？

答：人工排序的优先级高于默认排序，我们可以让TreeSet同时获取到Comparable和Comparator的比较方法。此时对于系统类来说默认排序是系统自带的，通过Comparator实现的人工排序规则是我们想要的，所以系统类必须让人工排序优先于默认排序，才能正常的使用后加色排序规则

package bk.javase.p530;
import java.util.Comparator;
import java.util.StringJoiner;
import java.util.TreeSet;

public class TestMyCom {
    public static void main(String[] args){
        //自己制定比较的规则，并按照年龄和性别进行比较，相同则认为是同一个人
        //2.将比较器作用于TreeSet
        ComWithPerson com = new ComWithPerson();
        TreeSet<Person4> set = new TreeSet<>(com);
        set.add(new Person4("zhangsan",20));
        set.add(new Person4("lisi",30));
        set.add(new Person4("zhangsan",20));
        System.out.println(set);
        /*
        我是Comparator
        [Person4[name='lisi', age=30], Person4[name='zhangsan', age=20]]
        如果同时实现了Comparator和Comparable，Comparator的优先级要高于Comparable
         */
    }
}
//1.生成一个比较器（实现了Comparator接口中的类的对象）
class ComWithPerson implements Comparator<Person4>{

    @Override
    public int compare(Person4 o1, Person4 o2) {
        int num = o1.name.compareTo(o2.name);
        System.out.println("我是Comparator");
        return num == 0 ? o1.age - o2.age : num;
    }

}

//直接实现Comparable接口
class Person4 implements Comparable<Person4>{
    String name;
    int age;

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

    @Override
    public String toString() {
        return new StringJoiner(", ", Person4.class.getSimpleName() + "[", "]")
                .add("name='" + name + "'")
                .add("age=" + age)
                .toString();
    }

    //自己制定比较的规则：如果姓名和年龄相同，相同则认为是同一个人
    @Override
    public int compareTo(Person4 o) {
        //先比较姓名再比较年龄
        int num = o.name.compareTo(name);
        System.out.println("我是Comparable");
        return num == 0 ? age - o.age : num;
    }
}

Comparable和Comparator的使用场景

1.如果这个对象，在项目中大多数情况下，都是采用相同的大小比较的方式，比如：一个Person类在大多数情况下，都是按照年龄进行大小比较的，此时就可以让Person类实现Comparable接口

2.如果一个类的对象，在临时比较大小的时候，使用的与默认的比较不一样的规则，比如一个Person类，大多数情况下都是使用年龄进行大小比较的，但是临时需要使用身高进行一次比较，此时就可以使用Comparator临时完成了。而且Comparator的优先级要高于Comparable

3.系统类想要实现新的比较规则，使用Comparator

TreeSet的去重：

无论使用Comparator还是Comparable，如果两个对象进行大小比较的结果是0，此时这两个对象是相同的对象，在TreeSet中会完成排重的处理

注意：TreeSet中元素的去重只与对象的大小比较结果有关，与hashCode()，equals()没有任何关系

Map集合

Map API

返回值	方法	描述
V	put(K key,V value)	插入，重复就覆盖
V	putlfAbsent(K key,V value)	插入，重复不覆盖
void	putAll(Map<K,V> ,map)	将参数Map集合中的所有键值对添加到当前集合
V	remove(Object key)	通过key删除k-v，并返回v
boolean	remove(Object key,Object value)	通过k-v删除
void	clear()	清空
V	replace(K k,V v)	修改k-v，返回原v
boolean	replaceAll(K k,V old,V new)	匹配k-v成功，修改为v
V	get(K k)	获取指定的V
V	getOrDefault(K k)	获取指定的v，没找到就返回默认值
int	size()	获取集合中元素的数量
boolean	isEmpty()	判断集合是否为空
boolean	constainsKey(K k)	判断是否包含指定的键
boolean	constainsValue(V v)	判断是否包含指定的值
Set	keySet()	获取由所有键组成的集合
Collection	values()	获取所有由值组成的集合

package bk.javase.p530;

import java.util.*;

public class TestMap {
    public static void main(String[] args){
        //1.实例化一个Map集合的实现类对象，并向上转型为接口类型
        Map<String,String> map = new HashMap<>();

        //2.向集合中插入数据
        String value = map.put("name","xiaoming");
        System.out.println(value); //由于第一次添加这个键值对，集合中没有被覆盖的值，因此返回值为null

        String value2 = map.put("name","xiaohong");
        System.out.println(value2);//这里是第二次设置name的值,会用xiaohong覆盖到xiaoming，因此返回xiaoming

        //3.向集合中插入数据：
        String value3 = map.putIfAbsent("name","xiaohong");
        System.out.println(value3);//这里返回的是集合中已经存在的的值，因为已经存在，所以就不会添加

        //4.将一个Map集合中所有的键值对添加到当前的集合中
        Map<String,String> temp = new HashMap<>();
        temp.put("height","175");
        temp.put("weight", "65");
        temp.put("age","30");
        map.putAll(temp);

        //5.删除：通过键，删除一个键值对，并返回这个被删除的键值对中的值
        String value4 = map.remove("weight");
        System.out.println(value4);

        //6.删除
        boolean value5 = map.remove("age","30");
        System.out.println(value5);

        //7.清空集合
//        map.clear();

        //8.修改集合中某一个键值对（通过键，值修改）
        String value6 = map.replace("name","xiaohei");
        System.out.println(value6); //返回被覆盖的值
        String value7 = map.replace("age","30");
        System.out.println(value7);//由于map中没有age，因此这个返回null

        //9.修改：只有当key和oldValue是匹配的情况下，才会将修改成newValue
        boolean value8 = map.replace("name","xiaohei","xiaohong");
        System.out.println(value8);

        //10.通过键获取值
        String value9 = map.get("name1");
        System.out.println(value9);

        //11.通过键获取值，如果这个键不存在，则返回默认的值
        String value10 = map.getOrDefault("name1","aaa");//aaa
        System.out.println(value10);

        //12.判断是否包含某一个键
        boolean value11 = map.containsValue("175");
        System.out.println(value11);
        boolean value12 = map.containsKey("height");
        System.out.println(value12);

        //13.获取由所有键组成的Set集合
        Set<String> keys = map.keySet();
        //14.获取由所有的值组成的Collection集合
        Collection<String> values = map.values();
        System.out.println(map);

    }
}

Map集合的遍历：

1.使用keySet（）进行遍历

//1.获取存储了所有的键的集合
Set<String> keys = map.keySet();
//2.使用键进行遍历
for(String key : keys){
    System.out.println("key = "+ key + "value = " + map.get(key));
}

2.使用forEach方法

这个forEach方法，并不是Iterable接口中的方法，而是Map中定义的一个方法，从功能上讲，和Iterable中的方法差不多，仅仅在参数部分有区别

private static void forEach(Map<String,String> map){
	map.forEach(k,v)->{
        //k:遍历到的每一个键
        //v：遍历到的每一个值
        System.out.println("key = "+ k + ",value = " + v);   
    }
}

3.使用EntrySet进行遍历

Entry<K,V>:

是Map中的内部静态接口，一个Entry对象，我们称之为一个实体，用来描述集合中的每一个键值对

package bk.javase.p530;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class TestKeySet {
    public static void main(String[] args){
        Map<String,String> map = new HashMap<String, String>();
        //1.获取一个存储有所有的Entry的一个Set集合
        Set<Map.Entry<String,String>> entries = map.entrySet();
        //2.遍历Set集合
        for (Map.Entry<String,String> entry : entries){
            //2.1获取键
            String key = entry.getKey();
            //2.2获取值
            String value = entry.getValue();
            //2.3显示结果
            System.out.println("key = " + key + ",value = " + value);
            
             /*
        通过setValue可以修改原始map的值
        映射项（键值对）。Map.entrySet方返回映射的Collection视图，其中的元素属于此类
        获取映射项引用的唯一方法是通过此collection视图的迭代器来实现。这些Map.Entry对象仅在
        迭代期间有效，更正式地说，如果在迭代器返回项之后修改了底层的映射，则某些映射项的行为是不确定的
        除了通过setValue在映射项执行操作之外
         */
            entry.setValue("hello");
        }
    }
}

HashMap

HashMap基本实现：

注意：HashMap可以实现排序，因为他的底层数据结构，是数组+链表+二叉树共同实现的，所以可以实现排序，同时这样做的目的是提高数据存储的效率

HashMap和HashTable的区别：

1.HashMap是线程不安全的集合，HashTable是线程安全的集合

2.HashMap允许出现的null键值，HashTable是不允许的

3.HashMap的父类是AbstractMap，HashTable的父类是Dictionary

4.HashMap的Map接口的新的实现类，底层算法效率优于HashTable

TreeMap

原理实现:

与TreeSet一样，进行排列，只是TreeMap是按照键的大小实现，对于值是不管的，我们可以将TreeSet中的值理解成TreeMap中的键

注意：

1.什么类型的数据类型可以作为key？

实现了Comparable接口中的compareTo()方法

实现了Comparator接口中的compare()方法

2.经常作为key的有？

String，包装类，自定义类（实现了接口）

3.不可以的代表？、

ArrayList，数组，LinkedList（如果给他们建立的比较器也可以比较但是不建议使用）

4.元素可不可以作为key，跟元素内部的成员没有关系

LinkedHashMap：

与HashMap类似，底层多维护了一个链表，记录了每一个键的存储顺序，也就是说，在LinkedHashMap中，键值对的添加顺序可以得到保障，类似于LinkedHashSet和HashSet

ashTable是不允许的

3.HashMap的父类是AbstractMap，HashTable的父类是Dictionary

4.HashMap的Map接口的新的实现类，底层算法效率优于HashTable

TreeMap

原理实现:

与TreeSet一样，进行排列，只是TreeMap是按照键的大小实现，对于值是不管的，我们可以将TreeSet中的值理解成TreeMap中的键

注意：

1.什么类型的数据类型可以作为key？

实现了Comparable接口中的compareTo()方法

实现了Comparator接口中的compare()方法

2.经常作为key的有？

String，包装类，自定义类（实现了接口）

3.不可以的代表？、

ArrayList，数组，LinkedList（如果给他们建立的比较器也可以比较但是不建议使用）

4.元素可不可以作为key，跟元素内部的成员没有关系

LinkedHashMap：

与HashMap类似，底层多维护了一个链表，记录了每一个键的存储顺序，也就是说，在LinkedHashMap中，键值对的添加顺序可以得到保障，类似于LinkedHashSet和HashSet