【数据结构】Map和Set

水深无声 2024-04-23 20:31 60阅读 0赞

> ⭐ 作者：小胡\_不糊涂  
> ? 作者主页：[小胡\_不糊涂的个人主页][Link 1]  
> ? 收录专栏：[浅谈数据结构][Link 2]  
> ? 持续更文，关注博主少走弯路，谢谢大家支持 ?

#### Map、Set ####

*  1. 搜索树
 *   *  1.1 概念
     *  1.2 性能分析
 *  2. 搜索
 *   *  2.1 概念及场景
     *  2.2 模型
 *  3. Map的使用
 *   *  3.1 关于Map.Entry<K, V>的说明
     *  3.2 Map的常用方法说明
     *  3.4 TreeMap的使用案例
 *  4. Set的说明
 *   *  4.1 常见方法说明
     *  4.2 TreeSet的使用案例

![在这里插入图片描述][72e9a3f3e1be4160a598a8ee801a344c.gif_pic_center]

## 1. 搜索树 ##

### 1.1 概念 ###

**二叉搜索树又称二叉排序树**，它或者是一棵空树，或者是具有以下性质的二叉树:

*  若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
 *  若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
 *  它的左右子树也分别为二叉搜索树

下图就是一个二叉搜索树：

![在这里插入图片描述][fd840132e3a74fad826b5197b7247251.png]

进行查找操作：  
![在这里插入图片描述][8f11b28bdd08426e922e40d85117531e.png]

进行插入操作：  
**1. 树为空树**  
![在这里插入图片描述][30785ad5ea63467e811501416ddb0bc2.png]  
**2. 如果树不是空树，按照查找逻辑确定插入位置，插入新结点**  
![在这里插入图片描述][2caf6b5fbdc349dba81ece42533c3ef7.png]  
进行删除操作：  
**设待删除结点为 cur, 待删除结点的双亲结点为 parent**

1.  cur.left == null  
    cur 是 root，则 root = cur.right  
    cur 不是 root，cur 是 parent.left，则 parent.left = cur.right  
    cur 不是 root，cur 是 parent.right，则 parent.right = cur.right
2.  cur.right == null  
    cur 是 root，则 root = cur.left  
    cur 不是 root，cur 是 parent.left，则 parent.left = cur.left  
    cur 不是 root，cur 是 parent.right，则 parent.right = cur.left
3.  cur.left != null && cur.right != null  
    需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题

![在这里插入图片描述][f9fd1bd8bd82497283818c5e547f67ed.png]  
代码实现：

public class BinarySearchTree {
        
        public static class TreeNode{
        
            int val;
            TreeNode left;
            TreeNode right;
            public TreeNode(int val){
        
                this.val=val;
            }
        }
        public TreeNode root;
    
        /**
         * 查找元素
         * 最好情况：完全二叉树 O(logN)
         * 最坏情况: 单分支的树 O(N)
         * @param key
         * @return
         */
        public boolean search(int key){
        
            TreeNode cur=root;
            while(cur!=null){
        
                if(cur.val==key){
        
                    return true;
                }else if(cur.val>key){
        
                    cur=cur.left;
                }else{
        
                    cur=cur.right;
                }
            }
            return false;
        }
    
        //插入元素
        public boolean insert(int key){
        
            if(root==null){
        
                root=new TreeNode(key);
                return true;
            }
            TreeNode cur=root;
            TreeNode parent=null;
            while(cur!=null){
        
                if(cur.val>key){
        
                    parent=cur;
                    cur=cur.left;
                }else if(cur.val<key){
        
                    parent=cur;
                    cur=cur.right;
                }else{
        
                    return false;//树中不能有相等元素
                }
            }
            //若cur=null，判断key与父亲节点的大小
            if(parent.val>key){
        
                parent.left=new TreeNode(key);
            }
            if(parent.val<key){
        
                parent.right=new TreeNode(key);
            }
            return true;
        }
    
    	//删除元素
        public void remove(int key){
        
            TreeNode cur = root;
            TreeNode parent = null;
            while (cur != null) {
        
                if(cur.val < key) {
        
                    parent = cur;
                    cur = cur.right;
                }else if(cur.val > key) {
        
                    parent = cur;
                    cur = cur.left;
                }else {
        
                    //开始删除
                    removeNode(cur,parent);
                }
            }
        }
        public void removeNode(TreeNode cur,TreeNode parent){
        
            //第一种情况
            if(cur.left==null){
        
                if(cur==root){
        
                    root=cur.right;
                }
                if(cur==parent.left){
        
                    parent.left=cur.right;
                }
                if(cur==parent.right){
        
                    parent.right=cur.right;
                }
            }
            //第二种情况
            if(cur.right == null) {
        
                if(cur == root) {
        
                    root = cur.left;
                }else if(cur == parent.left) {
        
                    parent.left = cur.left;
                }else {
        
                    parent.right = cur.left;
                }
            }
            //第三种情况
            if(cur.left!=null && cur.right!=null){
        
                TreeNode targetParent = cur;
                TreeNode target = cur.right;
                while (target.left != null) {
        
                    targetParent = target;
                    target = target.left;
                }
                cur.val = target.val;
                //删除target
                if(targetParent.left == target) {
        
                    targetParent.left = target.right;
                }else {
        
                    targetParent.right = target.right;
                }
            }
        }
    }

### 1.2 性能分析 ###

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

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：  
![在这里插入图片描述][4eac14a3d4234b24975250fba5c1ab00.png]

> 最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log2(N)  
> 最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2

## 2. 搜索 ##

### 2.1 概念及场景 ###

**Map 和 Set 是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。** 以前常见的搜索方式有：

1.  直接遍历，时间复杂度为O(N)，元素如果比较多效率会非常慢
2.  二分查找，时间复杂度为，但搜索前必须要求序列是有序的

上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，而现实中的查找比如：

1.  根据姓名查询考试成绩
2.  通讯录，即根据姓名查询联系方式
3.  不重复集合，即需要先搜索关键字是否已经在集合中  
    可能在查找时进行一些插入和删除，即动态查找，那上述两种方式就不太适合了，而 Map 和 Set 则是一种适合动态查找的集合容器。

### 2.2 模型 ###

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

1.  **纯 key 模型**，比如：

*  有一个英文词典，快速查找一个单词是否在词典中
 *  快速查找某个名字在不在通讯录中

1.  **Key-Value 模型**，比如：

*  统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>  
    **而Map中存储的就是key-value的键值对，Set中只存储了Key**

## 3. Map的使用 ##

![在这里插入图片描述][7eac284fa72846e9841c736e540717ba.png]  
![在这里插入图片描述][84e9b78150dc4a0887ebf2f977061a2b.png]  
**Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。**

### 3.1 关于Map.Entry<K, V>的说明 ###

Map.Entry<K, V> 是Map内部实现的**用来存放<key, value>键值对映射关系的内部类**，该内部类中主要提供了<key, value>的获取，value的设置以及Key的比较方式。

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>解释</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>K getKey()</td> 
   <td>返回 entry 中的 key</td> 
  </tr> 
  <tr> 
   <td>V getValue()</td> 
   <td>返回 entry 中的 value</td> 
  </tr> 
  <tr> 
   <td>V setValue(V value)</td> 
   <td>将键值对中的value替换为指定value</td> 
  </tr> 
 </tbody> 
</table>

`Map.Entry<K,V>并没有提供设置Key的方法`

### 3.2 Map的常用方法说明 ###

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>解释</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>V get(Object key)</td> 
   <td>返回 key 对应的 value</td> 
  </tr> 
  <tr> 
   <td>V getOrDefault(Object key, V defaultValue)</td> 
   <td>返回 key 对应的 value，key 不存在，返回默认值</td> 
  </tr> 
  <tr> 
   <td>V put(K key, V value)</td> 
   <td>设置 key 对应的 value</td> 
  </tr> 
  <tr> 
   <td>V remove(Object key)</td> 
   <td>删除 key 对应的映射关系</td> 
  </tr> 
  <tr> 
   <td>Set keySet()</td> 
   <td>返回所有 key 的不重复集合</td> 
  </tr> 
  <tr> 
   <td>Collection values()</td> 
   <td>返回所有 value 的可重复集合</td> 
  </tr> 
  <tr> 
   <td>Set&lt;Map.Entry&lt;K, V&gt;&gt; entrySet()</td> 
   <td>返回所有的 key-value 映射关系</td> 
  </tr> 
  <tr> 
   <td>boolean containsKey(Object key)</td> 
   <td>判断是否包含 key</td> 
  </tr> 
  <tr> 
   <td>boolean containsValue(Object value)</td> 
   <td>判断是否包含 value</td> 
  </tr> 
 </tbody> 
</table>

注：

1.  **Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap**
2.  **Map中存放键值对的Key是唯一的，value是可以重复的**
3.  在**TreeMap中插入键值对时，key不能为空**，否则就会抛NullPointerException异常，**value可以为空**。但是**HashMap的key和value都可以为空**。
4.  Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
5.  Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
6.  **Map中键值对的Key不能直接修改**，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。
7.  TreeMap和HashMap的区别：

<table> 
 <thead> 
  <tr> 
   <th>Map底层结构</th> 
   <th>TreeMap</th> 
   <th>HashMap</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>底层结构</td> 
   <td>红黑树</td> 
   <td>哈希桶</td> 
  </tr> 
  <tr> 
   <td>插入/删除/查找时间复杂度</td> 
   <td>O(log2(N))</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>是否有序</td> 
   <td>关于Key有序</td> 
   <td>无序</td> 
  </tr> 
  <tr> 
   <td>线程安全</td> 
   <td>不安全</td> 
   <td>不安全</td> 
  </tr> 
  <tr> 
   <td>插入/删除/查找区别</td> 
   <td>需要进行元素比较</td> 
   <td>通过哈希函数计算哈希地址</td> 
  </tr> 
  <tr> 
   <td>比较与覆写</td> 
   <td>key必须能够比较，否则会抛出ClassCastException异常</td> 
   <td>自定义类型需要覆写equals和hashCode方法</td> 
  </tr> 
  <tr> 
   <td>应用场景</td> 
   <td>需要Key有序场景下</td> 
   <td>Key是否有序不关心，需要更高的时间性能</td> 
  </tr> 
 </tbody> 
</table>

### 3.4 TreeMap的使用案例 ###

public static void TestMap(){
        
            Map<String, String> m = new TreeMap<>();
            // put(key, value):插入key-value的键值对
            // 如果key不存在，会将key-value的键值对插入到map中,返回null
            m.put("林冲", "豹子头");
            m.put("鲁智深", "花和尚");
            m.put("武松", "行者");
            m.put("宋江", "及时雨");
            String str = m.put("李逵", "黑旋风");
            System.out.println(m.size());//5
            System.out.println(m);
            //{宋江=及时雨, 李逵=黑旋风, 林冲=豹子头, 武松=行者, 鲁智深=花和尚}
    
            // put(key,value): 注意key不能为空，但是value可以为空
            // key如果为空，会抛出空指针异常
            //m.put(null, "花名");
            str = m.put("无名", null);
            System.out.println(m.size());//6
    
            // put(key, value):
            // 如果key存在，会使用value替换原来key所对应的value，返回旧value
            str = m.put("李逵", "铁牛");
    
            // get(key): 返回key所对应的value
            // 如果key存在，返回key所对应的value
            // 如果key不存在，返回null
            System.out.println(m.get("鲁智深"));//花和尚
            System.out.println(m.get("史进"));//null
    
            //GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值
            System.out.println(m.getOrDefault("李逵", "铁牛"));//铁牛
            System.out.println(m.getOrDefault("史进", "九纹龙"));//九纹龙
            System.out.println(m.size());//6
    
            //containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN)
            // 按照红黑树的性质来进行查找
            // 找到返回true，否则返回false
            System.out.println(m.containsKey("林冲"));//true
            System.out.println(m.containsKey("史进"));//false
            
            // containValue(value): 检测value是否包含在Map中，时间复杂度: O(N)
            // 找到返回true，否则返回false
            System.out.println(m.containsValue("豹子头"));//true
            System.out.println(m.containsValue("九纹龙"));//false
            
            // 打印所有的key
            // keySet是将map中的key防止在Set中返回的
            for(String s : m.keySet()){
        
                System.out.print(s + " ");//宋江 无名 李逵 林冲 武松 鲁智深 
            }
            System.out.println();
            
            // 打印所有的value
            // values()是将map中的value放在collect的一个集合中返回的
            for(String s : m.values()){
        
                System.out.print(s + " ");//及时雨 null 铁牛 豹子头 行者 花和尚
            }
            System.out.println();
            
            // 打印所有的键值对
            // entrySet(): 将Map中的键值对放在Set中返回了
            for(Map.Entry<String, String> entry : m.entrySet()){
        
                System.out.println(entry.getKey() + "--->" + entry.getValue());
            }
            System.out.println();
            //宋江--->及时雨
            //无名--->null
            //李逵--->铁牛
            //林冲--->豹子头
            //武松--->行者
            //鲁智深--->花和尚
        }

## 4. Set的说明 ##

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

### 4.1 常见方法说明 ###

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>解释</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean add(E e)</td> 
   <td>添加元素，但重复元素不会被添加成功</td> 
  </tr> 
  <tr> 
   <td>void clear()</td> 
   <td>清空集合</td> 
  </tr> 
  <tr> 
   <td>boolean contains(Object o)</td> 
   <td>判断 o 是否在集合中</td> 
  </tr> 
  <tr> 
   <td>Iterator iterator()</td> 
   <td>返回迭代器</td> 
  </tr> 
  <tr> 
   <td>boolean remove(Object o)</td> 
   <td>删除集合中的 o</td> 
  </tr> 
  <tr> 
   <td>int size()</td> 
   <td>返回set中元素的个数</td> 
  </tr> 
  <tr> 
   <td>boolean isEmpty()</td> 
   <td>检测set是否为空，空返回true，否则返回false</td> 
  </tr> 
  <tr> 
   <td>Object[] toArray()</td> 
   <td>将set中的元素转换为数组返回</td> 
  </tr> 
  <tr> 
   <td>boolean containsAll(Collection&lt;?&gt; c)</td> 
   <td>集合c中的元素是否在set中全部存在，是返回true，否则返回false</td> 
  </tr> 
  <tr> 
   <td>boolean addAll(Collection&lt;? extendsE&gt; c)</td> 
   <td>将集合c中的元素添加到set中，可以达到去重的效果</td> 
  </tr> 
 </tbody> 
</table>

注意：

1.  Set是继承自Collection的一个接口类
2.  Set中只存储了key，并且要求**key一定要唯一**
3.  TreeSet的**底层是使用Map来实现的**，其使用key与Object的一个默认对象作为键值对插入到Map中的
4.  **Set最大的功能就是对集合中的元素进行去重**
5.  实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
6.  Set中的\*\*Key不能修改，\*\*如果要修改，先将原来的删除掉，然后再重新插入
7.  TreeSet中**不能插入null的key，HashSet可以**。
8.  TreeSet和HashSet的区别：

<table> 
 <thead> 
  <tr> 
   <th>Set底层结构</th> 
   <th>TreeSet</th> 
   <th>HashSet</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>底层结构</td> 
   <td>红黑树</td> 
   <td>哈希桶</td> 
  </tr> 
  <tr> 
   <td>插入/删除/查找时间复杂度</td> 
   <td>O(log2(N)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>是否有序</td> 
   <td>关于Key有序</td> 
   <td>不一定有序</td> 
  </tr> 
  <tr> 
   <td>线程安全</td> 
   <td>不安全</td> 
   <td>不安全</td> 
  </tr> 
  <tr> 
   <td>插入/删除/查找区别</td> 
   <td>按照红黑树的特性来进行插入和删除</td> 
   <td>1. 先计算key哈希地址 2. 然后进行</td> 
  </tr> 
  <tr> 
   <td>插入和删除</td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>比较与覆写</td> 
   <td>key必须能够比较，否则会抛出ClassCastException异常</td> 
   <td>自定义类型需要覆写equals和hashCode方法</td> 
  </tr> 
  <tr> 
   <td>应用场景需要</td> 
   <td>Key有序场景</td> 
   <td>Key是否有序不关心，需要更高的时间性能</td> 
  </tr> 
 </tbody> 
</table>

### 4.2 TreeSet的使用案例 ###

public static void TestSet(){
        
            Set<String> s = new TreeSet<>();
            // add(key): 如果key不存在，则插入，返回ture
            // 如果key存在，返回false
            boolean isIn = s.add("apple");
            s.add("orange");
            s.add("peach");
            s.add("banana");
            System.out.println(s.size());//4
            System.out.println(s);//[apple, banana, orange, peach]
            isIn = s.add("apple");
            
            // add(key): key如果是空，抛出空指针异常
            //s.add(null);
            // contains(key): 如果key存在，返回true，否则返回false
            System.out.println(s.contains("apple"));//true
            System.out.println(s.contains("watermelen"));//false
            
            // remove(key): key存在，删除成功返回true
            // key不存在，删除失败返回false
            // key为空，抛出空指针异常
            s.remove("apple");
            System.out.println(s);//[banana, orange, peach]
            s.remove("watermelen");
            System.out.println(s);//[banana, orange, peach]
            
            Iterator<String> it = s.iterator();
            while(it.hasNext()){
        
                System.out.print(it.next() + " ");
            }
            System.out.println();
            //banana orange peach
        }

[Link 1]: https://blog.csdn.net/iLoyo_
[Link 2]: http://t.csdnimg.cn/pu3jy
[72e9a3f3e1be4160a598a8ee801a344c.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e40ad2f5281b40b9bf98ce38f0091c86.gif
[fd840132e3a74fad826b5197b7247251.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/3372c4dc190b42a586b47cb247358502.png
[8f11b28bdd08426e922e40d85117531e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/7c31c6b26c2f4ad7ace370fa3935a938.png
[30785ad5ea63467e811501416ddb0bc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/02a03f945efb4ca686f5a4a0c3136009.png
[2caf6b5fbdc349dba81ece42533c3ef7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/62acb0b4ee754ac0a836dd05173cb1d0.png
[f9fd1bd8bd82497283818c5e547f67ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c58d45b2dcd2468bbbce520771fafe8d.png
[4eac14a3d4234b24975250fba5c1ab00.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e4d7a3a56ba84f3bb93fcaed9092cab3.png
[7eac284fa72846e9841c736e540717ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/2a76b2f2bfc34918b532b71d442de45a.png
[84e9b78150dc4a0887ebf2f977061a2b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/8875c472297346dc9c861c0ccbaf8992.png