week07_day05_Set&&Map

程序员文章站 2022-05-09 13:53:55

...

什么是hash表
hash表是一种二维结构，管理着一对对<Key,Value>这样的键值对,Hash表的结构如下图所示：
week07_day05_Set&&Map
如上图所示，左侧部分是一个一维顺序存储的数组，数组单元格里的内容是指向另一个链式数组的指针。图中绿色部分是<Key,Value>，绿色部分右侧的白色部分是指向下一对键值对的指针。

hash表的工作原理：
（1）.第一步先根据给定的key和散列算法得到具体的散列值，也就是对应的数组下标。
（2）.第二步，根据数组下标得到此下标里存储的指针，若指针为空，则不存在这样的键值对，否则根据此指针得到此链式数组。（此链式数组里存放的均为一对对<Key,Value>）。
（3）.遍历此链式数组，分别取出Key与给定的Key比较，若找到与给定key相等的Key，即在此hash表中存在此要查找的<Key,Value>键值对，此后便可以对此键值对进行相关操作；若找不到，即为不存在此键值对。

所以hash表其实就是管理一对对<Key，Value>这样的结构
week07_day05_Set&&Map
哈希表的插入、删除、查找：

·················································································································································································································

HashSet
概述：
底层数据结构是哈希表（哈希表是一种数据结构，HashMap是对哈希表的一个实现）
Set的底层实现都是Map
它不保证迭代顺序，特别是它不保证该顺序恒久不变 (无序的)。
允许存储 null 元素。
不同步

public class HashSetDemo01 {

    public static void main(String[] args) {
        // HashSet是无序，并且可以存储null元素
        Set<String> set = new HashSet<>();
        set.add("allen");
        set.add("beyonce");
        set.add("catalina");
        set.add("diana");
        set.add("allen");
        set.add("allen");
        set.add(null);
        set.add(null);
        set.add(null);
        System.out.println(set);
    }
}

构造方法

HashSet()
构造一个新的空 set，其底层 HashMap 实例的默认初始容量是 16，加载因子是 0.75。
HashSet(Collection<? extends E> c)
构造一个包含指定 collection 中的元素的新 set。
HashSet(int initialCapacity)
构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和默认的加载因子（0.75）。
JDK中HashMap数组的大小是2的n次方，所以数组的大小为大于等于initialCapacity的最小的2^n
HashSet(int initialCapacity, float loadFactor)
构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和指定的加载因子。

    public static void main(String[] args) {
        //HashSet(Collection<? extends E> c)
        //可以对一个含有重复元素的list进行去重
        List<Character> list = Arrays.asList('A', 'A', 'B', 'C', 'B');
        HashSet<Character> set = new HashSet<>(list);
        System.out.println(set);
    }

··············································································································································································································

HashSet 是如何保证元素的唯一性的呢？（Set 存储的元素是作为 Map 的 key）

查看源码 (JDK1.7)
它依赖于存储元素的两个方法: int hashCode() & boolean equals(Object obj)

HashSet源码剖析：

/*HashSet是如何保证元素的唯一性的呢？
  HashMap的 key 值是唯一的。
*/

class HashSet<E> implements Set {
    private transient HashMap<E,Object> map; // 里面的value都是PRESENT

    /*占位符 dumb value*/
    private static final Object PRESENT = new Object();

    public boolean add(E e) {
        //所有key对应的value都是PRESENT对象（static final），PRESENT就是一个占位符
        return map.put(e, PRESENT)==null;
    }
}

// JDK1.7
class HashMap<K, V> implements Map<K, V> {

    public V put(K key, V value) {
        //看哈希表是否为空，如果空，就开辟空间
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }

        //判断对象是否为null
        if (key == null)
            return putForNullKey(value);

        int hash = hash(key); // 和key对象的hashCode()方法相关

        //在哈希表中查找hash值
        int i = indexFor(hash, table.length);

        // 遍历链表
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            // e.hash = hash, 判断e.hash = hash(key) 两者哈希值不一样，key一定不相等。
            //如果这步就不相等了，根据短路原则，&&后面的条件也不会判断了
            //如果相等，哈希值相等，key不一定相等，还等接着往后判断
            //(k = e.key) == key 相等的话，两个key相等，也就是说两个对象地址相等，代表找到了
            //如果这步就相等了，根据短路原则，||后面的条件也不会判断了
            //如果不相等，才会调用key.equals(k)方法
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                // key 与 e.key 是相等的，只更新value
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
                //走这里其实是没有添加元素
            }
        }
        // 遍历完之后发现没有相等的key，就添加键值对
        modCount++;
        addEntry(hash, key, value, i); //把元素添加
        return null;
    }

    transient int hashSeed = 0;

    final int hash(Object k) { //k="hello", hash(Object k) 只和k的hashCode()方法有关。
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode(); //这里调用的是对象的hashCode()方法

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
}

看一下Object类中的hashCode方法和equals方法：
根据截图中的这条约定，重写equals方法一定要重写hashCode方法。我们重写equals方法时，是根据age和name重写的，那重写hashCode方法也得根据这两个属性来重写。
week07_day05_Set&&Map

注意事项：千万不要修改 HashSet 元素的属性值!

做个练习：
HashSet存储自定义对象Student(name, age)。如果name和age都相等，那么我们就认为两个对象相等。

Student类：

package com.cskaoyan.set;

import java.util.Objects;

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

    public Student() {
    }

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

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

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

    @Override
    //equals方法的参数类型是Object类型，写成Student类型就不是方法重写了
    //而是方法重载，从Object类中继承了equals方法，把参数类型改变了
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        Student s = (Student) obj;
        //如果用name.equals(s.name)，万一name为null，就会报空指针异常
        //所以用Objects.equals(name, s.name)，可以看其源码
        //public static boolean equals(Object a, Object b) {
        //    return (a == b) || (a != null && a.equals(b));
        //}
        //如果a和b存储的地址相等或a为null且b为null，返回true
        //否则，判断(a != null && a.equals(b)
        return age == s.age && Objects.equals(name, s.name);
    }

    @Override
    //每个Student对象的hashCode返回的是此对象在内存地址中的哈希值
    //对象不同，hashCode就不一样，而HashSet源码中hash(key)方法
    // 只和hashCode有关，所以所得的哈希值一定不同，
    // if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
    //执行源码中的这条语句时，e.hash == hash条件就没通过，
    //也就是说两个姓名年龄相同的学生也给认为是不一样了，所以得重写hashCode方法
    public int hashCode() {
        int h = 0;
        h = h * 31 + age;
        //调用Objects.hashCode(name)还是为了避免name为null而报空指针异常
        //Objects.hashCode(name);点开源码看，即在String对象上调用hashCode方法
        //String类已经重写了hashCode方法了
        h = h * 31 + Objects.hashCode(name);
        return h;
    }

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

测试代码：

package com.cskaoyan.set;

import java.util.HashSet;

/*
HashSet 是如何保证元素的唯一性的呢？
Set存储的元素是作为Map的key，而Map的key是唯一的

它依赖于存储元素的两个方法: int hashCode() & boolean equals(Object obj)
练习：
    HashSet存储自定义对象Student(name, age)
    如果name和age都相等，那么我们就认为两个对象相等。

注意事项：千万不要修改 HashSet 元素的属性值!
 */
public class HashSetDemo03 {

    public static void main(String[] args) {
        HashSet<Student> set = new HashSet<>();
        Student s1 = new Student("刘亦菲", 16);
        Student s2 = new Student("刘亦菲", 16);
        Student s3 = new Student("刘亦菲", 16);
        Student s4 = new Student("小龙女", 22);
        Student s5 = new Student("花木兰", 18);
        Student s6 = new Student("赵灵儿", 17);
        set.add(s1);
        set.add(s2);
        set.add(s3);
        set.add(s4);
        set.add(s5);
        set.add(s6);
        /*System.out.println(s1.equals(s2));
        System.out.println(s1.equals(s3));*/

        System.out.println(set.size()); // 4
        System.out.println(set);

        // 修改s4的属性值
        //改完后这个对象依然存在set中，就造成了set中存了重复元素的效果
        //HashSet只有在执行add(a)方法时才会判断是否set中是否有a对象
        //所以存进去了就不要再修改属性值了
        /*s4.setName("刘亦菲");
        s4.setAge(16);
        System.out.println(set.size()); // 4
        System.out.println(set);*/
    }
}

LinkedHashSet概述：
HashSet 的子类
底层是HashMap & 双向链表
HashMap 保证了元素的唯一性。
链表定义了迭代的顺序，按照元素的插入顺序进行迭代。
不同步。
week07_day05_Set&&Map
LinkedHashSet相比HashSet多了一个按照元素的插入顺序进行迭代的功能，除此之外，构造方法、成员方法都和HashSet一样。
其他的注意事项啥的都和HashSet一样。

    public static void main(String[] args) {
        LinkedHashSet<String> set = new LinkedHashSet<>();
        set.add("catalina");
        set.add("diana");
        set.add("allen");
        set.add("beyonce");
        set.add("allen");
        set.add("allen");
        set.add(null);
        set.add(null);
        set.add(null);
        System.out.println(set);
    }

TreeSet概述：
底层的数据结构是 TreeMap, TreeMap的底层是红黑树。
如果创建对象时，没有传入 Comparator 对象，则根据自然顺序（字典顺序）进行排序。
如果创建对象时，传入了 Comparator 对象，则根据 Comparator 进行排序。
不能存储 null 元素，除非在Comparator中定义的null的比较规则
不同步

构造方法

TreeSet() 根据其元素的自然顺序进行排序
TreeSet(Comparator<? super E> comparator) 它根据指定比较器进行排序

注意事项：
TreeSet 是通过compareTo()或者比较器去重的。
并不是依赖于equals方法和hashCode方法

代码一：演示构造方法TreeSet()
Teacher类：

package com.cskaoyan.set;

//Teacher类必须是可比较的，TreeSet底层是红黑树，红黑树属于BST，
//在之前实现BST中：public class BinarySearchTree<E extends Comparable<? super E>>
//让其中的元素E是Comparable接口的子类
//所以teacher也得实现Comparable接口
public class Teacher implements Comparable<Teacher> {
    private String name;
    private int age;

    public Teacher() {
    }

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

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

    @Override
    public int compareTo(Teacher t) {
        // 先按年龄比较，再按姓名比较
        int cmp = age - t.age;
        cmp = cmp != 0 ? cmp : name.compareTo(t.name);
        return cmp;
    }
}

测试类：

package com.cskaoyan.set;

import java.util.TreeSet;

/*
练习：
    存储自定义对象Teacher(name,age)
    认为name和age相等，那么这两个对象就相等
 */
public class TreeSetDemo1 {

    public static void main(String[] args) {
        //  TreeSet()
        TreeSet<Teacher> set = new TreeSet<>();
        Teacher t1 = new Teacher("风华大叔", 38);
        Teacher t2 = new Teacher("蓝胖", 88);
        Teacher t3 = new Teacher("严汉", 20);
        Teacher t4 = new Teacher("张帅", 19);
        Teacher t5 = new Teacher("黑大帅", 18);
        Teacher t6 = new Teacher("黑大帅", 18);

        set.add(t1);
        set.add(t2);
        set.add(t3);
        set.add(t4);
        set.add(t5);
        set.add(t6);

        System.out.println(set.size()); //
        System.out.println(set);
    }
}

用默认构造方法不太方便，假如Teacher类是别人写的，这个类没有实现Comparable接口。你不能修改人家的代码，就不能用默认构造方法了

演示TreeSet(Comparator<? super E> comparator)构造方法：

Teacher02类：

package com.cskaoyan.set;

/**
 * @author shihao
 * @create 2020-05-22 18:00
 */
public class Teacher02 {
    private String name;
    private int age;

    public Teacher02() {
    }

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

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

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

}

测试代码：

package com.cskaoyan.set;

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

/**
 * @author shihao
 * @create 2020-05-22 18:01
 */
public class TreeSetDemo02 {

    public static void main(String[] args) {
        //传入一个实现Comparator接口的子类对象
        //这个对象我们只使用一次，所以传入匿名内部类即可
        //并且应当重写其中的compare方法
        TreeSet<Teacher02> set = new TreeSet<>(new Comparator<Teacher02>() {
            @Override
            public int compare(Teacher02 t1, Teacher02 t2) {
                int cmp = t1.getAge() - t2.getAge();
                //String类型是实现了comparable接口的
                cmp = cmp != 0 ? cmp : t1.getName().compareTo(t2.getName());
                return cmp;
            }
        });
        Teacher02 t1 = new Teacher02("风华大叔", 38);
        Teacher02 t2 = new Teacher02("蓝胖", 88);
        Teacher02 t3 = new Teacher02("严汉", 20);
        Teacher02 t4 = new Teacher02("张帅", 19);
        Teacher02 t5 = new Teacher02("黑大帅", 18);
        Teacher02 t6 = new Teacher02("黑大帅", 18);

        set.add(t1);
        set.add(t2);
        set.add(t3);
        set.add(t4);
        set.add(t5);
        set.add(t6);

        System.out.println(set.size()); //
        System.out.println(set);
    }

}

TreeSet 是如何保证元素的唯一性的呢？
查看源码
它依赖于存储元素的 compareTo(obj) 方法，或者是传入的 Comparator 对象的 compare(o1, o2) 方法
注意事项：千万不要修改 TreeSet 元素的属性值!

剖析TreeSet源码：

class TreeSet implements Set {

    //NavigableMap是一个接口
    private transient NavigableMap<E, Object> m;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    //这个构造方法调用的其实是下下个构造方法
    public TreeSet() {
        //传入的其实还是一个TreeMap
        this(new TreeMap<E, Object>());
    }

    public TreeSet(Comparator<? super E> comparator) {
        //传入的其实还是一个带comparator的TreeMap
        this(new TreeMap<>(comparator));
    }

    TreeSet(NavigableMap<E, Object> m) {
        this.m = m;
    }

    public boolean add(E e) {
        //调用的是TreeMap中的put方法，应当去TreeMap中分析put方法的源码
        return m.put(e, PRESENT) == null;
    }
}

class TreeMap implements Map {

    //比较器
    private final Comparator<? super K> comparator;
    //根节点
    private transient Entry<K, V> root;
    //树的大小
    //TreeMap底层是一个红黑树，所以属性会有root和size
    private transient int size = 0;

    public TreeMap() {
        comparator = null;
    }

    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }


    public V put(K key, V value) {
        Entry<K, V> t = root;
        //建树
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K, V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        // 传入比较器
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value); // 更新value,并把原来的value返回
            } while (t != null);
        }
        // 没有传入比较器
        else {
            // key不能为null，因为null不能进行比较
            if (key == null)
                throw new NullPointerException();
            // 要求元素必须实现Comparable接口，所以将形参key强转
            @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value); //更新value,并把原来的value返回
            } while (t != null);
        }
        // 插入结点
        Entry<K, V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        // 重新调整平衡
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }
}

因为TreeSet的底层实现是红黑树，所以他有一些其他Set所没有的方法：

E ceiling(E e)
返回此 set 中大于等于给定元素的最小元素；如果不存在这样的元素，则返回 null。
E floor(E e)
返回此 set 中小于等于给定元素的最大元素；如果不存在这样
E pollFirst()
获取并移除第一个（最低）元素；如果此 set 为空，则返回 null。
E pollLast()
获取并移除最后一个（最高）元素；如果此 set 为空，则返回 null。
E first()
返回此 set 中当前第一个（最低）元素。
E last()
返回此 set 中当前最后一个（最高）元素。
E higher(E e)
返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。
E lower(E e)
返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。

另外，TreeSet还有几个视图技术的方法：

SortedSet subSet(E fromElement, E toElement)
返回此 set 的部分视图，其元素从 fromElement（包括）到 toElement（不包括）。

public class TreeSetDemo03 {

    public static void main(String[] args) {
        TreeSet<Character> set = new TreeSet<>();
        set.add('A');
        set.add('B');
        set.add('C');
        set.add('D');
        set.add('F');
        set.add('K');
        set.add('X');

        // E ceiling(E e)
        /*System.out.println(set.ceiling('C')); // C
        System.out.println(set.ceiling('E')); // F
        System.out.println(set.ceiling('Z')); // null*/

        // E floor(E e)
        /*System.out.println(set.floor('C')); // C
        System.out.println(set.floor('E')); // D
        System.out.println(set.floor('0')); // null*/

        // E higher(E e)
        /*System.out.println(set.higher('C')); // D
        System.out.println(set.higher('E')); // F
        System.out.println(set.higher('Z')); // null*/
        // E lower(E e)
        /*System.out.println(set.lower('C')); // B
        System.out.println(set.lower('E')); // D
        System.out.println(set.lower('0')); // null*/

        // E first()
       /* System.out.println(set.first()); // 'A'
        System.out.println(set);*/
        // E last()
        /*System.out.println(set.last()); // 'X'
        System.out.println(set);*/
        // E pollFirst()
        /*System.out.println(set.pollFirst());
        System.out.println(set);*/
        // E pollLast()
       /* System.out.println(set.pollLast());
        System.out.println(set);*/

       // NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
        // 视图技术
        NavigableSet<Character> subSet = set.subSet('C', false, 'L', true);
        System.out.println(subSet);
        subSet.pollFirst();
        System.out.println(subSet);
        System.out.println(set);
    }
}

练习：录入5个学生信息 (姓名，语文成绩，数学成绩，英语成绩)，并按照指定的格式，总分从高到低，输出到文件。

思路：
1.创建学生类
2.创建学生对象
3.添加到TreeSet中，按照总分从高到低进行排序
4.把TreeSet中的学生信息输出到文件

Student类：

package com.cskaoyan.exercise;

public class Student {
    private String name;
    private int chinese;
    private int math;
    private int english;

    public Student() {
    }

    public Student(String name, int chinese, int math, int english) {
        this.name = name;
        this.chinese = chinese;
        this.math = math;
        this.english = english;
    }

    public String getName() {
        return name;
    }

    public int getChinese() {
        return chinese;
    }

    public int getMath() {
        return math;
    }

    public int getEnglish() {
        return english;
    }

    public int totalScore() {
        return chinese + math + english;
    }

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

测试类：

package com.cskaoyan.exercise;

import com.cskaoyan.set.Student;
import com.cskaoyan.set.TreeSetDemo01;

import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Comparator;
import java.util.TreeSet;

/**
 * @author shihao
 * @create 2020-05-22 21:08
 */
public class ex1 {

    public static void main(String[] args) {
        Student2 s1 = new Student2("刘亦菲", 100, 100, 100);
        Student2 s2 = new Student2("迪丽热巴", 90, 90, 90);
        Student2 s3 = new Student2("古力娜扎", 90, 90, 90);
        Student2 s4 = new Student2("佟丽娅", 95, 95, 95);

        TreeSet<Student2> set = new TreeSet<>(new Comparator<Student2>() {
            @Override
            public int compare(Student2 s1, Student2 s2) {
                int cmp = s2.totalScore() - s1.totalScore();
                //总分相同，根据语文成绩排
                cmp = cmp != 0 ? cmp : s2.getChinese() - s1.getChinese();
                //总分相同，语文成绩相同，根据数学成绩排
                cmp = cmp != 0 ? cmp : s2.getChinese() - s1.getChinese();
                //总分相同，语文成绩相同，数学成绩相同，根据英语成绩排
                cmp = cmp != 0 ? cmp : s2.getChinese() - s1.getChinese();
                //都相同，根据名字排
                cmp = cmp != 0 ? cmp : s2.getName().compareTo(s1.getName());
                return cmp;
            }
        });

        set.add(s1);
        set.add(s2);
        set.add(s3);
        set.add(s4);
        System.out.println(set.size());
        System.out.println(set);

        //把TreeSet中的学生信息输出到文件
        //try with source格式，将定义的流写在try()的括号里
        try (PrintWriter out = new PrintWriter(new FileWriter("Student.txt"))) {
            out.println("姓名\t语文\t数学\t英语\t总分");
            //foreach循环
            for (Student2 s : set) {
                out.println(s.getName() + "\t" + s.getChinese() + "\t" + s.getMath() +
                        "\t" + s.getEnglish() + "\t" + s.totalScore());
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

至此，Collection接口就讲完了
Collection小结：

Collection
    |-- List
          |-- ArrayList
          |-- Vecotor
	|-- Stack
          |-- LinkedList
    |-- Set
          |-- HashSet
                |-- LinkedHashSet
          |-- TreeSet
    |-- Queue
          |--Deque
                |--LinkedList

作业：

LeetCode之找不同
LeetCode之拼写单词