排序规则：Integer,Double等数值类型默认按照从小到大的顺序排序，对于字符，字符串类型，按照ASCII码表中的数字进行升排序 

 接下来演示一下，创建自定义类型的TreeSet

例如：给出一个Student类，要求按照学生的年龄排序

首先创建好Student类之后，需要实现Comparable接口，然后重写compareTo和toString方法

public class Student implements Comparable<Student>{    public String name;    public int age;    public Student(String name, int age) {        this.name = name;        this.age = age;    }    @Override    public String toString() {        return "Student{" +                "name='" + name + ''' +                ", age=" + age +                '}';    }    @Override    public int compareTo(Student o) {        return this.age - o.age;//this.age表示要添加的元素    }}

 this.age表示要添加的元素，所以如果返回值是负数，表示要添加的元素是小的，存左边，如果是0，表示元素已经存在，直接舍弃

public class Text2 {    public static void main(String[] args) {        Student s1 = new Student("zhang",18);        Student s2 = new Student("wang",20);        Student s3 = new Student("li",19);        TreeSet<Student> treeSet = new TreeSet<>();        treeSet.add(s1);        treeSet.add(s2);        treeSet.add(s3);        System.out.println(treeSet);    }}

 最终，虽然插入时没有按顺序，由于TreeSet底层是红黑树，所以最终也实现了排序的效果

 比较器排序

问题：根据字符串长度比较，长度相同再按字典序比较

//o1:当前要添加的元素        //o2:红黑树中已经存在的元素        TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {            @Override            public int compare(String o1, String o2) {                return (o1.length() - o2.length()) == 0 ? o1.compareTo(o2) : o1.length() - o2.length();            }        });        ts.add("bbcd");        ts.add("abcde");        ts.add("abcd");        System.out.println(ts);

也就是在创建对象的时候传入比较器进行比较

🍁2. 单列集合的使用场景分析

介绍完Set系列集合之后，我们的单列集合就都学习完了，接下来分析一下这写集合的使用场景

如果集合中元素可重复：使用ArrayList（基于数组）

如果集合中元素可重复并且用到增删操作多余查询:使用LinkedList

如果需要对集合去重：使用HashSet

如果需要在去重的前提下还要保证存取顺序：使用LinkedHashSet

如果需要对集合中的元素进行排序：使用TreeSet

🍁3. Map系列集合

Map系列的集合称为双列集合

1. 双列集合一次存储一对数据，分别为键和值

2. 键不能重复，值可以重复

3. 键和值是一一对应的，每一个键都对应一个值

4. 键+值整体称为键值对，也叫Entry对象

 和Set集合类似，Map是顶层接口，底下有这些实现类

以下就是Map集合常用的API

🍁3.1 HashMap

HashMap的底层也是哈希表，和之前的HashSet不同，HashMap中，当插入的key相同时，第二次插入会覆盖原来的value值，同时，如果存储的是自定义类型的对象还需要重写HashCode和equals方法

其他方法就不演示了，下面来介绍一下map的遍历

Map的遍历

键找值：调用keySet方法，获取所有的key，把返回值放在Set集合中，再遍历Set集合，通过get方法获取每一个key的value

//获取所有的键，并放在Set集合中        Set<String> set = map.keySet();        //遍历set,根据所有的键获取值        for(String key:set){            int value = map.get(key);            System.out.println(key + " = " + value);        }

通过键值对对象进行遍历

调用entrySet方法，把所有键值对对象放在Set集合中，再遍历Set集合

 可以看出，Entry是Map接口的一个内部接口，所以需要通过Map.Entry的形式调用，也可以直接导入

import java.util.Map.Entry;

就可以省略Map.

遍历时，可以直接打印Entry对象，也可以通过get的方式获取key和value        

Set<Map.Entry<String, Integer>> entries = map.entrySet();        for(Map.Entry<String,Integer> entry : entries){            //System.out.println(entry);            String s = entry.getKey();            Integer i = entry.getValue();            System.out.println(s + " = " + i);        }

最后还可以通过lambda的形式遍历

map.forEach(new BiConsumer<String, Integer>() {            @Override            public void accept(String key, Integer value) {                System.out.println(key + " = " + value);            }        });        map.forEach((key, value) -> System.out.println(key + " = " + value));

🍁3.2 LinkedHashMap

和LinkedHashSet一样，LinkedHashMap存储的键是有序的（存储顺序和取出顺序一样）

🍁3.3 TreeMap

TreeMap和TreeSet底层一样，都是红黑树，根据键进行排序，排序规则也是类似的，对于非数值等类型，可以实现Comparable接口，指定比较规则，也可以传入比较器

🍁4. 面试OJ题练习

🍁4.1 随机链表的复制

138. 随机链表的复制

 也就是下面这种情况

如果说直接对链表节点进行复制是不可以的，因为题目中要求的是深拷贝，所以说拷贝后的 节点可能和原来的地址不一样

思路：遍历原来的链表，每遍历一次都创建一个新的节点，把原来的节点和拷贝的新节点的映射关系使用map存储起来，再通过get方法得到节点，再连接next和random

public Node copyRandomList(Node head) {        Map<Node, Node> map = new LinkedHashMap<>();        Node cur = head;        while (cur != null) {            Node copy = new Node(cur.val);            map.put(cur, copy);            cur = cur.next;        }        /*cur = head;        while (cur != null) {            map.get(cur).next = map.get(cur.next);            map.get(cur).random = map.get(cur.random);            cur = cur.next;        }*/        Set<Node> keySet = map.keySet();        for (Node curNode : keySet) {            map.get(curNode).next = map.get(curNode.next);            map.get(curNode).random = map.get(curNode.random);        }        return map.get(head);    }

🍁4.2 宝石与石头 

771. 宝石与石头

 这一题就可以很好的利用Set集合元素不能重复的特性了，如果不用Set集合，把全部元素异或一遍就可以找到了，而且速度更快，这里只是为了练习一下Set集合的使用，只需要把jewels存一个set，再遍历stones，判断是否有set集合里的元素即可

public class Text {    public static void main(String[] args) {        String jewels = "aA";        String stones = "aAABBBBB";        System.out.println(numJewelsInStones(jewels, stones));    }    public static int numJewelsInStones(String jewels, String stones) {        Set<Character> set = new HashSet<>();        for (int i = 0; i < jewels.length(); i++) {            set.add(jewels.charAt(i));        }        int cnt = 0;        for (int i = 0; i < stones.length(); i++) {            if (set.contains(stones.charAt(i))) {                cnt++;            }        }        return cnt;    }}

🍁4.3 前k个高频单词

692. 前K个高频单词

 思路：前k个高频词，就是经典的topk问题，根据之前我们学到的，就是用小根堆解决，首先统计一下每个单词出现的频率，并通过map存储它们的映射关系，接着创建小根堆，套用之前的模板解决

public List<String> topKFrequent(String[] words, int k) {        Map<String, Integer> map = new HashMap<>();        //统计单词个数并存入map        for (String s : words) {            if (map.get(s) == null) {                map.put(s, 1);            } else {                int val = map.get(s);                map.put(s, ++val);            }        }        //创建根据map的value创建小根堆        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {            @Override            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {                //相同时根据key创建大根堆，最后反转的时候就可以把字典序靠前的排到前面了                if (o1.getValue().compareTo(o2.getValue()) == 0) {                    return o2.getKey().compareTo(o1.getKey());                }                return o1.getValue().compareTo(o2.getValue());            }        });        //根据之前讲解的topk问题解决        for (Map.Entry<String, Integer> entry : map.entrySet()) {            //先把前K个元素加入大根堆            if (minHeap.size() < k) {                minHeap.offer(entry);            } else {                Map.Entry<String, Integer> top = minHeap.peek();                //堆顶元素频率小于后面的                if (top.getValue().compareTo(entry.getValue()) < 0) {                    minHeap.poll();                    minHeap.offer(entry);                } else if (top.getValue().compareTo(entry.getValue()) == 0) {                    //堆顶元素等于后面时，堆顶的key字典序大于后面的                    if (top.getKey().compareTo(entry.getKey()) > 0) {                        minHeap.poll();                        minHeap.offer(entry);                    }                }            }        }        ArrayList<String> ans = new ArrayList<>();        //把key存入ArrayList        for (int i = 0; i < k; i++) {            ans.add(minHeap.poll().getKey());        }        //题目要求出现频率由高到低，进行翻转        Collections.reverse(ans);        return ans;    }