TreeSet与TreeMap的那些关系

向右看齐 2024-03-27 14:08 79阅读 0赞

#### 文章目录 ####

*  1.写在前面
 *  2.TreeMap、TreeSet相同点
 *  3.具体使用
 *   *  3.1 TreeMap的使用
     *  3.2TreeSet的使用

## 1.写在前面 ##

接下来要介绍的TreeSet、TreeMap，分别实现了Set、Map接口，在数据结构中 **Map和Set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。**

其在java中的关系如下：  
![在这里插入图片描述][69fda9f7732546769c137f85ad4d7445.png]

简单说明：

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

1.  纯 key 模型，比如：  
    有一个英文词典，快速查找一个单词是否在词典中。
2.  Key-Value 模型，比如：  
    统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>  
    **Map中存储的就是key-value的键值对，Set中只存储了Key。**

注意：Map和Set中存储的key都不能重复，并且存储的key必须是可以比较的。其中**Set最大的功能就是用来去重**。

## 2.TreeMap、TreeSet相同点 ##

虽然分别实现的接口不同但是二者相同处很多,如下：

<table> 
 <thead> 
  <tr> 
   <th>底层结构</th> 
   <th>TreeMap、TreeSet</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>插入/删除/查找时间复杂度</td> 
   <td>O(logN)</td> 
  </tr> 
  <tr> 
   <td>是否有序</td> 
   <td>关于Key有序</td> 
  </tr> 
  <tr> 
   <td>线程安全</td> 
   <td>不安全</td> 
  </tr> 
  <tr> 
   <td>插入/删除/查找时</td> 
   <td>需要进行元素比较</td> 
  </tr> 
  <tr> 
   <td>比较与覆写</td> 
   <td>Key必须能够比较，否则会抛出ClassCastException异常</td> 
  </tr> 
  <tr> 
   <td>应用场景</td> 
   <td>需要Key有序的场景下</td> 
  </tr> 
 </tbody> 
</table>

**解释说明**：

1.红黑树 实际上是一颗近似平衡的二叉搜索树（**又称二叉排序树，左右子树不为空时，左子树节点所有值小于根节点，右子树所有节点大于根节点**），在二叉搜索树的基础之上 + 颜色以及红黑树性质验证。

2.由于底层是红黑树，所以Key一定是可以比较的，并且关于Key有序，其插入、删除、查找的时间复杂度即树的高度。  
二叉搜索树如下图所示：  
![在这里插入图片描述][fb2ad87899b3468f8f833c9860653e22.png]

3.TreeSet底层实际上是Map实现的，所以其也需要Key不重复且可比较。  
其底层构造方法：

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

其使用key与Object的一个默认对象作为键值对插入到Map中。  
4. Map中键值对的Key，和Set的Key都不能直接修改，Map的value可以修改。如果要修改key，只能先将该key删除掉，然后再来进行重新插入。

## 3.具体使用 ##

### 3.1 TreeMap的使用 ###

代码展示：  
\*\*注意：\*\*可以使用entrySet()方法打印所有键值对。

package demo10;
    
    import java.util.Map;
    import java.util.TreeMap;
    
    /**
     * @author zq
     */
    public class TreeMap1 {
        
        public static void main(String[] args) {
        
            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());
            System.out.println(str);
            System.out.println(m);
            // put(key,value): 注意key不能为空，但是value可以为空
            // key如果为空，会抛出空指针异常
            str = m.put("无名", null);
            System.out.println(str);
            // 如果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("史进"));
            //GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值
            System.out.println(m.getOrDefault("李逵", "铁牛"));
            System.out.println(m.getOrDefault("史进", "九纹龙"));
            System.out.println(m.size());
            //containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN)
            // 按照红黑树的性质来进行查找
            // 找到返回true，否则返回false
            System.out.println(m.containsKey("林冲"));
            System.out.println(m.containsKey("史进"));
            // containValue(value): 检测value是否包含在Map中，时间复杂度: O(N)
            // 找到返回true，否则返回false
            System.out.println(m.containsValue("豹子头"));
            System.out.println(m.containsValue("九纹龙"));
            // 打印所有的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 + " ");
            } System.out.println();
            // 打印所有的键值对
            // entrySet(): 将Map中的键值对放在Set中返回了
            for(Map.Entry<String, String> entry : m.entrySet()){
        
                System.out.println(entry.getKey() + "--->" + entry.getValue());
            }
        }
    
    }

### 3.2TreeSet的使用 ###

代码展示：  
**注意：** Set继承了Iterable接口，可以使用迭代器遍历输出。

package demo10;
    
    import java.util.Iterator;
    import java.util.Set;
    import java.util.TreeSet;
    
    /**
     * @author zq
     */
    public class TreeSet1 {
        
        public static void main(String[] args) {
        
            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());
            System.out.println(s);
             isIn = s.add("apple");
            // add(key): key如果是空，抛出空指针异常
            //s.add(null);
            // contains(key): 如果key存在，返回true，否则返回false
            System.out.println(s.contains("apple"));
            System.out.println(s.contains("watermelen"));
            // remove(key): key存在，删除成功返回true
            // key不存在，删除失败返回false
            // key为空，抛出空指针异常
            s.remove("apple");
            System.out.println(s);
            s.remove("watermelen");
            System.out.println(s);
            //迭代器遍历
            Iterator<String> it = s.iterator();
            while(it.hasNext()){
        
                System.out.print(it.next() + " ");
            } System.out.println();
        }
    }

[69fda9f7732546769c137f85ad4d7445.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/20675e66e8be4e428182bda6ce8a0f43.png
[fb2ad87899b3468f8f833c9860653e22.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/cf1fe7ce5b6b4a748c733aaffa8a4bf0.png