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

专栏：Java数据结构秘籍

个人主页：手握风云

目录

一、Map和Set

1.1. 概念

二、搜索树

2.1. 概念

2.2. 查找操作

2.2. 插入操作

2.3. 删除操作

2.4. 性能分析

三、搜索

3.1. 概念及场景

3.2. 模型

四、Map

4.1. Map的说明

3.2. Map的使用

五、Set

5.1. Set的使用

---

一、Map和Set

1.1. 概念

        如果一些场景中需要设计到数据搜素相关的操作时，就需要用到上图中的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;}

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

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，打印1tree1.put('a',10);//设置key对应的value是唯一的System.out.println(tree1.get('a'));//打印10System.out.println(tree1.get('e'));//返回nullSystem.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;