Java数据结构第二十二期：Map与Set的高效应用之道(一)-EW帮帮网

如果一些场景中需要设计到数据搜素相关的操作时，就需要用到上图中的Map和Set接口。Map用于存储键值对，每个键都映射到一个值，键必须是唯一的，但值可以重复，常见的实现类为HashMap、TreeMap。用于存储不重复的元素。它不允许存储重复的值，但不存储键值对，常见的实现类为HashSet、TreeSet。

二、搜索树

2.1. 概念

TreeSet和TreeMap是与二叉搜索树相关的，二叉搜索树底层是用红黑树实现的。二叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树：

若它的左⼦树不为空，则左⼦树上所有节点的值都⼩于根节点的值；
若它的右⼦树不为空，则右⼦树上所有节点的值都⼤于根节点的值；
它的左右⼦树也分别为⼆叉搜索树。

2.2. 查找操作

查找的思路是，让需要查找的值key与结点的值域val进行比较。如果key大于val，就去遍历右子树；如果key小于val，就去遍历左子树；如果相等，直接返回这个结点。

    public TreeNode root = null;

    public TreeNode Search(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val > val) {
                cur = cur.left;
            } else if (cur.val < val) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }

上面算法的时间复杂度最好情况下（一棵满二叉树）为 $logn$ ，最坏情况下（只有单个分支）时间复杂度为 $n$ 。

2.2. 插入操作

我们在完成插入操作之后，依然要保证这棵树是一棵二叉搜索树。我们把需要插入的数值val先与根结点的值root.val进行比较，大于在右树插入，小于在左树插入。如下图所示，我们需要将70插入进73的左边，70成为61的右子树，而此时的cur已经为空了。但问题来了，程序没有记录下30的位置，所以我们还需要一个p引用来记录cur走过的前一个位置。当cur为空时，如果val大于p.val，则插入p的右边；如果val小于p.val，则插入p的左边。如果这棵树为空，我们插入第一个结点时，直接让root等于插入的结点就可以。

    public void Insert(int val) {
        TreeNode newNode = new TreeNode(val);

        if (root == null) {
            root = newNode;
            return;
        }

        TreeNode cur = root;
        TreeNode parent = null;

        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else {
                return;
            }
        }
        if (parent.val < val) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
    }

2.3. 删除操作

删除操作相较于前两个来说比较复杂。如果这个节点没有左右结点，就直接置为空；如果这个结点有左孩子结点或者右孩子结点，就直接将孩子结点变为删除结点的父亲结点的子结点。但如果待删除的结点左右都不为空，该怎么办。

我们要想删除val，就要先查询到该元素。如果要删除的结点为cur，它的父亲结点为parent。我们先假设cur.left为空，且cur是parent.left，那么parent.left=cur.right；再假设cur是parent.right，那么parent.right=cur.right。如下图所示，我们要删除的结点为61。

同理，如果cur.right为空，且cur是parent.left，那么parent.left=cur.left；再假设cur是parent.right，那么parent.right=cur.left。

完整代码实现：

    public void Remove(int val){
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null){
            if(cur.val < val){
                parent = cur;
                cur = cur.right;
            }else if(cur.val > val){
                parent = cur;
                cur = cur.left;
            }else{
                RemoveNode(cur,parent);
                return;
            }
        }
    }

    private void RemoveNode(TreeNode cur, TreeNode parent) {
        if(cur.left == null){
            if(cur == root){
                root = root.right;
            }else if(cur == parent.left){
                parent.left = cur.right;
            }else{
                parent.right = cur.right;
            }
        }else if(cur.right == null){
            if(cur == root){
                root = root.left;
            }else if(cur == parent.left){
                parent.left = cur.left;
            }else{
                parent.right = cur.left;
            }
        }
    }

下面是最难的一种情况，就是cur的左右结点都不为空，如果删除，该如何安排它的左右结点。利用替换法，找出一个“替罪羊”，让替换的值去替换我们要删除的结点。比如我们要删除73，在73的左子树找出最大值来替换73，这样就能保证要删除的结点左侧都是比它小的，然后我们去删70。如下图所示，这样就会出现要删除的结点一边为空，一边不为空。

TreeNode target = cur.right;
TreeNode targetParent = cur;
while(target.left != null){
    targetParent = target;
    target = target.left;
}
targetParent.left = target.right;

代码写到这里，我们还有一种情况没有考虑到。我们看下图这种情况，81的左边为空，无法进入上面的while循环，那么我们就需要用81替换73。

    public void Remove(int val) {
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else {
                RemoveNode(cur, parent);
                return;
            }
        }
    }

    private void RemoveNode(TreeNode cur, TreeNode parent) {
        if (cur.left == null) {
            if (cur == root) {
                root = root.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if (cur == root) {
                root = root.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        } else {
            TreeNode target = cur.right;
            TreeNode targetParent = cur;
            while(target.left != null){
                targetParent = target;
                target = target.left;
            }
            if(target == targetParent.left) {
                targetParent.left = target.right;
            }else{
                targetParent.left = target.right;
            }
        }
    }

2.4. 性能分析

插⼊和删除操作都必须先查找，查找效率代表了⼆叉搜索树中各个操作的性能。对有n个结点的⼆叉搜索树，若每个元素查找的概率相等，则⼆叉搜索树平均查找⻓度是结点在⼆叉搜索树的深度的函数，即结点越深，则比较次数越多。

三、搜索

3.1. 概念及场景

Map和set是⼀种专⻔⽤来进⾏搜索的容器或者数据结构，其搜索的效率与其具体的实例化⼦类有关。以前常见的搜索方式有：直接遍历或者二分查找。但这些只能在特定场景下才能使用，一般的情况下效率相对较低。这两种查找比较适合静态类型的查找，即⼀般不会对区间进⾏插⼊和删除操作了。而现实中的查找比如：根据姓名查询考试成绩或者通讯录中根据姓名查询联系方式。

3.2. 模型

⼀般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以模型会有两种：

纯key模型

有⼀个英⽂词典，快速查找⼀个单词是否在词典中。

. Key-Value 模型

统计⽂件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数。

Map中存储的就是key-value的键值对，Set中只存储了Key。

四、Map

4.1. Map的说明

Map是⼀个接⼝类，该类没有继承⾃Collection，该类中存储的是结构的键值对，并且K⼀定是唯一的，不能重复。

public interface Map<K, V>

    interface Entry<K, V>

我们可以看下Structure里面，Map内部又实现了一个接口Entry，可以理解为二叉搜索树里的TreeNode。

3.2. Map的使用

方法	说明
V get(Object key)	返回key对应的value值
V getOrDefault(Object key,V defaultValue)	返回key对应的value值，若key不存在，返回默认值
V put<key,value>	设置key对应的value
V remove<Object key>	删除key的映射关系
Set<K> keySet()	返回所有key的不重复集合
Collection<V> values()	返回所有value的可重复集合
Set<Map.Entry<K,V>> entrySet()	返回key-value的所有映射关系
boolean containsKey(Object key)	判断是否包含key
boolean containsKey(Object value)	判断是否包含value

import java.util.Collection;
import java.util.Set;
import java.util.TreeMap;

public class Solution {
    public static void main(String[] args) {
        TreeMap<Character,Integer> tree1 = new TreeMap<>();
        //底层是二叉搜索树，要想实现插入与删除，进行的是k的比较
        //如果k是其他类，那么这个类必须是可比较的
        tree1.put('a',1);
        tree1.put('b',2);
        tree1.put('c',3);
        tree1.put('d',4);
        tree1.put('e',5);
        tree1.put('a',1);
        tree1.put('b',2);
        tree1.put('c',3);
        tree1.put('x',1);
        tree1.put('y',2);
        tree1.put('z',3);
        System.out.println(tree1.get('a'));//根据key获取value，打印1
        tree1.put('a',10);//设置key对应的value是唯一的

        System.out.println(tree1.get('a'));//打印10
        System.out.println(tree1.get('e'));//返回null

        System.out.println(tree1.getOrDefault('f',6));

        System.out.println(tree1.containsKey('c'));
        System.out.println(tree1.containsKey('f'));

        Set<Character> setTree = tree1.keySet();
        System.out.println(setTree);

        Collection<Integer> collection = tree1.values();
        System.out.println(collection);

        Integer in = tree1.remove('a');
        System.out.println(in);
    }
}

注意：

Map是⼀个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者 HashMap
在TreeMap中插⼊键值对时，key不能为空，否则就会抛NullPointerException异常，value可以为空。但是HashMap的key和value都可以为空。
Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。

五、Set

Set与Map主要的不同有两点：Set是继承⾃Collection的接⼝类，Set中只存储了Key。

5.1. Set的使用

方法	说明
boolean add(E,e)	添加元素，但重复元素不会被添加
void clear()	清空集合
boolean contains(Object o)	判断o是否在集合中
Iterator<E> Iterator()	返回迭代器
boolean remove(Object o)	删除集合中的o
int size()	返回集合中的元素个数
boolean isEmpty()	检查集合是否为空
Object[] toArray()	将集合中的元素转化成数组
boolean containsAll(Collection<?> c)	集合c中的元素是否全部存在于集合set中
boolean addAll(Collection<? extends E> c)	将集合c中的元素添加进set中

import java.util.Iterator;
import java.util.TreeSet;

public class Solution {
    public static void main(String[] args) {
        TreeSet<String> tree = new TreeSet<>();
        System.out.println(tree.isEmpty());//集合是否为空

        tree.add("abc");//添加
        tree.add("def");
        tree.add("hello");
        tree.add("world");
        tree.add("hello");//只能添加一个
        System.out.println(tree);
        System.out.println(tree.isEmpty());

        System.out.println(tree.contains("abc"));//判断是否存在集合中
        System.out.println(tree.contains("bac"));

        System.out.println(tree.size());//获取长度

        String[] array = tree.toArray(new String[3]);//转化成数组
        for (String i: array) {
            System.out.print(i+" ");
        }

        System.out.println();
        tree.remove("world");//删除元素
        System.out.println(tree);

        Iterator<String> it = tree.iterator();
        while (it.hasNext()){
            System.out.print(it.next()+" ");
        }
    }
}

Set中只存储了key，并且要求key⼀定要唯一，TreeSet的底层是使用Map来实现的，其使⽤key与Object的⼀个默认对象作为键值对插⼊到Map中的。我们来看一下TreeSet的构造方法的源码：

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

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

public interface NavigableMap<K,V> extends SortedMap<K,V>

public interface SortedMap<K,V> extends Map<K,V>

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

上面的TreeMap传给了m，m是NavigableMap类型的，而NavigableMap又继承了Map，我们再来看add方法，里面的e接收了key，PRESENT接收了value，而这个PRESENT又是一个Object类。

private transient NavigableMap<E,Object> m;

Java数据结构第二十二期：Map与Set的高效应用之道(一)

一、Map和Set

1.1. 概念