开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 大数据进阶21-TreeSet、Map以及一些面试题 -> 正文阅读

[数据结构与算法]大数据进阶21-TreeSet、Map以及一些面试题

这一块的内容主要是有关TreeSet、Map以及Java中的一些面试题的内容。

TreeSet

有关TreeSet

TreeSet：能够使元素按照某种规则进行排序
排序有两种：1、自然排序；2、选择器排序
TreeSet集合的特点：元素唯一、可以排序
通过观察TreeSet的add()方法，我们发现最终要看TreeMap的put()方法

发现经过TreeSet，元素按照升序输出了

public static void main(String[] args) {
        //创建集合对象
        //现在这样的排序叫做 自然排序
        TreeSet<Integer> set = new TreeSet<Integer>();
        set.add(10);
        set.add(20);
        set.add(23);
        set.add(90);
        set.add(13);
        set.add(1);
        //遍历
        for(Integer i:set){
            System.out.println(i);
        }
    }
}
//1
//10
//13
//20
//23
//90

TreeSet中的add()方法图解

TreeSet的底层是二叉树（红黑树）
主要是记住它是中序遍历（左根右）遍历

TreeSet中的add方法源码解析

add方法保证了元素的有序性
我的理解：
TreeSet里面的add实际上调用的是TreeMap里面的put方法

1、首先我们点进去add方法，发现add方法是m来实现的
2、m又是NavigableMap接口
3、接下来要找实现NavigableMap接口的一个子类对象
4、子类对象也就是TreeMap
5、最后发现调用的是TreeMap中的put方法

public interface Collection{
    ...
}

public interface Set<E> extends Collection{
    ...
}

Interface NavigableMap{

}

class TreeMap implements NavigableMap{
    public V put(K key, V value) {
        Entry<K,V> t = root;
        //一开始添加元素的时候，一定是没有根的，所以第一个元素t一定是等于null的
        //造一个根节点
        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;
        //由于是无参构造，是自然比较，没有比较器，所以是==null的
        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);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
            //通过观察API发现，Integer类实现了Comparable接口，所以可以向上转型
            //又发现了一点：无参构造虽然是自然排序，但是也需要有一个Comparable自然比较器
                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);
            } 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;
    }
}


class TreeSet implements Set{
    private transient NavigableMap<E,Object> m;

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
}

TreeSet存储自定义对象并保证元素的排序和唯一

首先我们开始第一种做法
我们用TreeSet存储自定义对象，并保证元素的排序和唯一性，但是并没有说明怎么排序，元素怎么保证唯一也没说（实际上，成员变量相同，就是同一个变量）

public static void main(String[] args) {

        TreeSet<Student> treeSet = new TreeSet<Student>();

        Student s1 = new Student("zhangsan", 21);
        Student s2 = new Student("lisi", 22);
        
        treeSet.add(s1);
        treeSet.add(s2);

        for(Student s : treeSet){
            System.out.println(s.getName()+"---"+s.getAge());
        }
    }
}
//Exception in thread "main" java.lang.ClassCastException: com.bigdata.shujia20.Student cannot be cast to java.lang.Comparable

按照我们固有的思维去做，在思维逻辑上并没有什么问题，但是我们发现这种做法出错了，报错的原因是我们没有重写 Comparable

第二种正确的做法：

需求：按照姓名的长度进行排序
TreeSet可以保证元素的排序和唯一性
排序：（自然排序和比较器排序）
自然排序：
创建集合的时候调用的无参构造
让元素所属的类实现自然排序接口Comparable
比较器排序：
创建集合的时候传入比较器对象，调用有参构造
让集合的构造方法接收一个比较器接口的子类对象Comparator

我们首先实现Comparator接口
并且做比较（首先比较姓名的长度，在一致的情况下，我们比较内容，之后我们比较年龄）

public class MyComparator implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        //比较姓名的长度
        int i = o1.getName().length() - o2.getName().length();

        //比较姓名的长度一样，但是内容不一定一样
        int i1 = i == 0 ? o1.getName().compareTo(o2.getName()) : i;

        //在内容相同的情况下，比较年龄
        int i2 = i1 == 0 ? o1.getAge() - o2.getAge() : i1;
        return i2;
    }
}

之后，继续按照上面的想法，我们存储自定义对象，并保证元素的唯一和有序

public static void main(String[] args) {

        TreeSet<Student> students = new TreeSet<Student>(new MyComparator());

        Student s1 = new Student("zhangsna", 21);
        Student s2 = new Student("lisi", 22);
        Student s3 = new Student("wangwu", 23);

        students.add(s1);
        students.add(s2);
        students.add(s3);

        for(Student s:students){
            System.out.println(s.getName()+"---"+s.getAge());
        }

    }
}
//lisi---22
//wangwu---23
//zhangsna---21

Set集合的一些小练习

HashSet类的简单概述

在这里插入图片描述

使用HashSet编写一个小程序，获取10个随机数，且随机数不重复

public static void main(String[] args) {
        //创建随机数对象
        Random rd = new Random();

        //创建HashSet集合
        HashSet<Integer> integers = new HashSet<>();

        //判断集合的长度是否小于10
        while (integers.size()<10){
            int i = rd.nextInt(20)+1;
            integers.add(i);
        }

        //遍历集合
        for(Integer i:integers){
            System.out.println(i);
        }
    }
}
//16
//17
//18
//5
//7
//9
//10
//13
//14
//15

使用TreeSet键盘录入五个学生信息（姓名、语数英，按总分从高到低输出）

public static void main(String[] args) {
        //创建Scanner对象
        Scanner sc = new Scanner(System.in);

        //创建TreeSet集合
        TreeSet<Student1> treeSet = new TreeSet<Student1>(new Comparator<Student1>() {
            @Override
            public int compare(Student1 o1, Student1 o2) {
                //总分从高到低
                int i = o2.sum() - o1.sum();
                //总分相同，不一定语文成绩相同
                int i1 = i == 0 ? o1.getChinese() - o2.getChinese():i;
                //总分相同不一定数学成绩相同
                int i2 = i1 == 0?o1.getMath() - o2.getMath():i1;
                //总分相同不一定英语成绩相同
                int i3 = i2 == 0?o1.getEnglish() - o2.getEnglish():i2;
                //姓名还不一定相同
                int i4 = i3 == 0?o1.getName().compareTo(o2.getName()):i3;
                return i4;
            }
        });

        System.out.println("请输入学生信息");

        for(int i=0;i<5;i++){
            System.out.println("你正在输入第"+(i+1)+"位学生的姓名");
            String name = sc.next();
            System.out.println("你正在输入第"+(i+1)+"位学生的语文成绩");
            int chinese = sc.nextInt();
            System.out.println("你正在输入第"+(i+1)+"位学生的数学成绩");
            int math = sc.nextInt();
            System.out.println("你正在输入第"+(i+1)+"位学生的英语成绩");
            int english = sc.nextInt();

            //创建学生对象，并赋值
            Student1 s = new Student1(name, chinese, math, english);

            treeSet.add(s);

        }

        System.out.println("学生信息录入完毕.......");

        System.out.println("学生按照总分从高到低如下：");
        System.out.println("姓名\t语文成绩\t数学成绩\t英语成绩\t总分");
        for(Student1 s: treeSet){
            System.out.println(s.getName()+"\t"+s.getChinese()+"\t"+s.getMath()+
                    "\t"+s.getEnglish()+"\t"+s.sum());
        }
        
    }
}

Map集合

Map集合的引入

作为一个学生，是根据学号的不同来区分学生，假设我们以及用学生的学号来获取到了学生的姓名了，那年龄该怎么获取呢
如果采取前面的集合的方式的话，我们把学生的学号和姓名作为一个对象存入到集合，然后存储整个对象，将来在遍历的时候，通过判断获取到学生的姓名
但我们这时候都已经把姓名拿出来了，为什么还要拿出学号呢
我们的需求是：仅仅知道学号，就想知道学生的姓名或者其他信息，该怎么办？
Java中提供了一个新的方式：Map集合

通过查看API我们发现，Map集合的特点是将键映射到值的对象
Map中不能包含重复的键，每个键可以映射到最多一个值
<K,V>映射
Key Value
1001 zhangsan
1002 lisi
1003 wangwu
1004 zhaoliu
1001（重复了） tianqi

Map集合的特点

将键映射到值的对象
一个映射不能包含重复的键
每个键最多只能映射到一个值

Map接口和Collection接口的不同：

Map集合的元素是成对出现的，Map集合的键是唯一的，值是可以重复的
Collection集合存储的元素是单独出现的，Collection的子接口Set中的元素是唯一的，List中的元素是可以重复的

Map集合的功能

1、添加功能：
V put(K key, V value) 将指定的值与该映射中的指定键相关联（可选操作）。
2、删除功能：
void clear() 从Map中删除所有的映射（可选操作）。
V remove(Object key) 如果存在（从可选的操作），从该地图中删除一个键的映射。
3、判断功能：
boolean containsKey(Object key) 如果此映射包含指定键的映射，则返回 true 。
boolean containsValue(Object value) 如果此地图将一个或多个键映射到指定的值，则返回 true 。
boolean isEmpty() 如果此地图不包含键值映射，则返回 true 。
4、获取功能：
Set<Map.Entry<K,V>> entrySet() 返回Map中包含的映射的Set视图。
V get(Object key) 返回到指定键所映射的值，或 null如果此映射包含该键的映射。
Set keySet() 返回此地图中包含的键的Set视图。
Collection values() 返回Map中包含的值的Collection视图。
5、长度功能：
int size() 返回Map中键值映射的数量。

Map集合中的方法测试

public static void main(String[] args) {

        HashMap<String, String> hashMap = new HashMap<String, String>();

        hashMap.put("zhangsan","21");
        hashMap.put("lisi","22");
        hashMap.put("wangwu","23");
        hashMap.put("zhaoliu","24");

        System.out.println(hashMap);

//        //void clear()
        hashMap.clear();
        System.out.println(hashMap);
//
//        //V remove(Object key)删除一个键的映射
        hashMap.remove("zhangsan");
        System.out.println(hashMap);

//        //containsKey(Object key)如果此映射包含指定键的映射，返回true
        System.out.println(hashMap.containsKey("lisi"));
//
//        //boolean isEmpty() 如果不包含键值的映射，返回true
        System.out.println(hashMap.isEmpty());
//
//        //int size() 返回Map集合中键值映射的数量
        System.out.println(hashMap.size());

    }
}

Map集合的获取功能

Set<Map.Entry<K,V>> entrySet() 返回Map中包含的映射的Set视图。
V get(Object key) 返回到指定键所映射的值，或 null如果此映射包含该键的映射。
Set keySet() 返回此地图中包含的键的Set视图。
Collection values() 返回Map中包含的值的Collection视图。

public static void main(String[] args) {
        //创建集合对象
        HashMap<String, String> hashMap = new HashMap<String,String>();

        //创建元素并添加
        hashMap.put("zhangsan","21");
        hashMap.put("lisi","22");
        hashMap.put("wangwu","23");
        hashMap.put("zhaoliu","24");

        //V get(Object key)返回到指定键所映射的值，或null，如果此映射包含该键的映射
        System.out.println(hashMap.get("zhangsan"));//21
        System.out.println(hashMap.get("lisi"));//22

        //Set<K> KeySet() 返回Map中包含所有键的Set集合
        Set<String> strings = hashMap.keySet();
        for(String s : strings){
            System.out.println(s);//返回了所有的Key
        }

        //Collection<V> values() 返回Map中包含的值的Collection集合
        Collection<String> values = hashMap.values();
        for(String s:values){
            System.out.println(s);//返回了所有的Value
        }
    }

Map集合的两种遍历

第一种

先把所有的Key集中起来
遍历每个Key，通过Key来获取Value

   public static void main(String[] args) {

        HashMap<String, String> hashMap = new HashMap<String, String>();

        hashMap.put("zhangsan","21");
        hashMap.put("lisi","22");
        hashMap.put("wangwu","23");

        //遍历
        //首先遍历Map集合中的Key
        Set<String> keys = hashMap.keySet();
        for(String key:keys){
            String value = hashMap.get(key);
            System.out.println(key+"---"+value);
        }

    }
}
//lisi---22
//zhangsan---21
//wangwu---23

第二种

先把K和V组成一个集合
遍历集合，得到每一个键值对对象
根据键值对获取元素的键和值

如何获取键值对对象的集合：
Set<Map.Entry<K,V>> entrySet() 返回Map中包含的映射的Set集合

public static void main(String[] args) {

        HashMap<String, String> hashMap = new HashMap<String,String>();

        hashMap.put("zhangsan","21");
        hashMap.put("lisi","22");
        hashMap.put("wangwu","23");
        hashMap.put("zhaoliu","24");

        Set<Map.Entry<String, String>> entries = hashMap.entrySet();

        //遍历集合，得到每一个键值对对象
        for (Map.Entry<String, String> s : entries) {
            String key = s.getKey();
            String value = s.getValue();
            System.out.println(key + "---" + value);
        }
        
    }
}
//lisi---22
//zhaoliu---24
//zhangsan---21
//wangwu---23

HashMap

基于哈希表的Map接口的实现
哈希表：用来保证键的唯一性
HashMap<String,String>
键：String
值：String

HashMap<String,String>:

   public static void main(String[] args) {

        HashMap<String, String> hashMap = new HashMap<String,String>();

//存储数据的时候，尽量不使用001、002这样的数据，因为以0开头的是八进制
//在008之后，就会开始报错
        hashMap.put("zhangsan","21");
        hashMap.put("lisi","22");
        hashMap.put("wangwu","23");
        hashMap.put("zhaoliu","24");

        Set<Map.Entry<String, String>> entries = hashMap.entrySet();
        for(Map.Entry<String, String> s:entries){
            String key = s.getKey();
            String value = s.getValue();
            System.out.println(key+"---"+value);
        }
    }
}
//lisi---22
//zhaoliu---24
//zhangsan---21
//wangwu---23

HashMap<String,Student>:

public static void main(String[] args) {
        HashMap<String, Student> hashMap = new HashMap<String,Student>();

        Student s1 = new Student("zhangsan", 21);
        Student s2 = new Student("lisi", 22);
        Student s3 = new Student("wangwu", 23);
        Student s4 = new Student("zhaoliu", 24);

        hashMap.put("s1",s1);
        hashMap.put("s2",s2);
        hashMap.put("s3",s3);
        hashMap.put("s4",s4);

        Set<Map.Entry<String, Student>> entries = hashMap.entrySet();

        for (Map.Entry<String, Student> s : entries){
            String key = s.getKey();
            Student value = s.getValue();
            System.out.println(key+"---"+value.getName()+"---"+value.getAge());
        }
    }
}
//s3---wangwu---23
//s4---zhaoliu---24
//s1---zhangsan---21
//s2---lisi---22

HashMap<Student,String>:
要求：如果两个对象的成员变量的值都相同，就判定同一个对象
关键点就是重写hashCode和equals方法

class Student3{
    private String name;
    private int age;

    public String getName() {
        return name;
    }

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

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

    @Override
    public int hashCode() {

        return Objects.hash(name, age);
    }

    public int getAge() {
        return age;
    }

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

    Student3(){}

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

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

        HashMap<Student3, String> hashMap = new HashMap<Student3, String>();

        Student3 s1 = new Student3("zhangsan", 21);
        Student3 s2 = new Student3("lisi", 22);
        Student3 s3 = new Student3("wangwu", 23);
        Student3 s4 = new Student3("zhangsan", 21);

        hashMap.put(s1,"s1");
        hashMap.put(s2,"s2");
        hashMap.put(s3,"s3");
        hashMap.put(s4,"s1");

        Set<Map.Entry<Student3, String>> entries = hashMap.entrySet();

        for(Map.Entry<Student3, String> s:entries){
            Student3 key = s.getKey();
            String value = s.getValue();
            System.out.println(key.getName()+"---"+key.getAge()+"---"+value);
        }
    }
}
//lisi---22---s2
//zhangsan---21---s1
//wangwu---23---s3

LinkedHashMap

是哈希表和链表实现的Map接口，具有可预知的迭代顺序
由哈希表保证唯一性
由链表保证顺序，有序（存储和取出的顺序一致）

   public static void main(String[] args) {
        LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>();

        linkedHashMap.put("zhangsan","21");
        linkedHashMap.put("lisi","22");
        linkedHashMap.put("wangwu","23");
        linkedHashMap.put("zhaoliu","24");

        Set<Map.Entry<String, String>> entries = linkedHashMap.entrySet();
        for(Map.Entry<String, String> s:entries){
            String key = s.getKey();
            String value = s.getValue();
            System.out.println(key+"---"+value);
        }
    }
}
//zhangsan---21
//lisi---22
//wangwu---23
//zhaoliu---24

TreeMap

是基于红黑树的Map接口的实现
TreeMap<String,String>

public static void main(String[] args) {
        TreeMap<String, String> treeMap = new TreeMap<String,String>();

        treeMap.put("zhangsan","21");
        treeMap.put("lisi","22");
        treeMap.put("wangwu","23");
        treeMap.put("zhaoliu","24");

        Set<Map.Entry<String, String>> entries = treeMap.entrySet();

        for (Map.Entry<String, String> s : entries){
            String key = s.getKey();
            String value = s.getValue();
            System.out.println(key+"---"+value);
        }
    }
}
//lisi---22
//wangwu---23
//zhangsan---21
//zhaoliu---24

TreeMap<Student,String>

public static void main(String[] args) {
        TreeMap<Student, String> treeMap = new TreeMap<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                int i = o1.getName().compareTo(o2.getName());
                int i1 = i == 0 ? o1.getAge() - o2.getAge() : i;
                return i1;
            }
        });

        Student s1 = new Student("zhangsan", 21);
        Student s2 = new Student("lisi", 22);
        Student s3 = new Student("wangwu", 23);
        Student s4 = new Student("zhaoliu", 24);

        treeMap.put(s1,"s1");
        treeMap.put(s2,"s2");
        treeMap.put(s3,"s3");
        treeMap.put(s4,"s4");

        Set<Map.Entry<Student, String>> entries = treeMap.entrySet();
        for(Map.Entry<Student, String> s : entries){
            Student key = s.getKey();
            String value = s.getValue();
            System.out.println(key.getName()+"---"+key.getAge()+"---"+value);
        }
    }
}
//lisi---22---s2
//wangwu---23---s3
//zhangsan---21---s1
//zhaoliu---24---s4

Map集合的一个小案例

“aababcabcdabcde”,获取字符串中每一个字母出现的次数要求结果:a(5)b(4)c(3)d(2)e(1)

public static void main(String[] args) {
        //定义一个字符串
//        String s = "aababcabcdabcde";

        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        //定义一个TreeMap
        TreeMap<Character, Integer> map = new TreeMap<>();

        //将字符串转换成字符数组
        char[] chars = s.toCharArray();

        //遍历字符数组，得到每一个字符
        for(char ch:chars){
            //拿到字符作为键去集合中找值，看返回值
            Integer i = map.get(ch);

            if(i == null){
                map.put(ch,1);
            }
            else{
                //不是null，就把value的值加1，把该字符作为键，value设置为1
                i++;
                map.put(ch,i);
            }
        }

        //定义一个StringBuidler进行拼接
        StringBuilder sb = new StringBuilder();

        //遍历集合
        Set<Map.Entry<Character, Integer>> entries = map.entrySet();
        for(Map.Entry<Character, Integer> e:entries){
            Character key = e.getKey();
            Integer value = e.getValue();
            sb.append(key).append("(").append(value).append(")");
        }

        //把StringBuilder转换成String输出
        String s1 = sb.toString();
        System.out.println(s1);
    }

面试题

HashMap和Hashtable的区别

HashMap中的键和值允许null，而Hashtable不允许键和值存在null
HashMap是线程不安全的，但是效率高；Hashtable是线程安全的，效率低

List、Set、Map等接口是否都继承Map接口

Collection（接口）

List（接口）
- ArrayList
  底层数据结构是数组，查询快，增删慢
  线程不安全，效率高
- Vector
  底层数据结构是数组，查询快，增删慢
  线程安全，效率低
- LinkedList
  底层数据结构是链表，查询慢，增删快
  线程不安全，效率高
  不知道选谁，就选ArrayList
Set（接口）
- HashSet
  底层数据结构是哈希表，保证数据的唯一性
  - LinkedHashSet
    底层数据结构是哈希表和链表（双链表）
    哈希表和链表共同保证数据的有序和唯一
- TreeSet
  底层数据结构是红黑树
  排序的两种方式：都是在创建TreeSet对象的时候，构造方法调用
  1、自然排序，通过类来实现接口
  2、比较器排序，可以重写个类实现，也可以用匿名内部类
Map（接口）
- HashMap
  底层数据结构是哈希表
  - LinkedHashMap
    底层数据结构是哈希表和链表
    哈希表和链表共同保证数据的唯一和有序
- TreeMap
  底层数据结构是红黑树（键是红黑树结构，可以保证键的排序和唯一性）
  排序的两种方式：都是在创建TreeMap对象的时候，构造方法调用
  1、自然排序，通过类来实现接口
  2、比较器排序，可以重写个类实现，也可以用匿名内部类

Hashtable中不能存null

public class InterviewDemo {
    public static void main(String[] args) {
        HashMap<String, String> map1 = new HashMap<String, String>();
        Hashtable<String, String> map2 = new Hashtable<String, String>();

        map1.put("shujia","hello");
        map1.put(null,"java");
        map1.put("world",null);
        map1.put(null,null);


        map2.put("shujia","hello");
        map2.put(null,"java");
        map2.put("world",null);
        map2.put(null,null);

        System.out.println(map1);
        System.out.println(map2);

    }
}