数据结构之Map&Set

系统管理员 2024-04-01 08:42 68阅读 0赞

## 文章目录 ##

*  **一、概念、场景及模型**
 *  **二、Map的使用**
    
     *  1.关于Map的说明
     *  2.关于Map.Entry的说明
     *  3.Map的常用方法
     *  4.Map的遍历方式
     *  5.试题案例
 *  **三、Set的使用**
    
     *  1.关于Set的说明
     *  2.试题案例

![c24c7205d0f94659b5d1095dbdca5d0e.png][]

--------------------

**一、概念、场景及模型**

**Map** **和** **set**是一种专门用来进行搜索的容器或者数据结构，Map和Set是一种适合动态查找的集合容器。TreeMap和TreeSet集合背后的数据结构就是搜索树，红黑树。其中TreeSet底层就是一个TreeMap。

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

1. **纯**  **key**  **模型**

2. **Key-Value**  **模型**

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

**二、Map的使用**

[Map的官方文档：Map (Java Platform SE 8 )![icon-default.png_t_M85B][]https://docs.oracle.com/javase/8/docs/api/java/util/Map.html][Map_Map _Java Platform SE 8 _icon-default.png_t_M85B_https_docs.oracle.com_javase_8_docs_api_java_util_Map.html]**1.关于Map的说明**

**Map**是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复 **，**因为底层是二叉搜索树。

**2.关于Map.Entry的说明**

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

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>说明</td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      K getKey() 
    </div> </td> 
   <td> 
    <div>
      返回 entry 中的 key 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      V getValue() 
    </div> </td> 
   <td> 
    <div>
      返回 entry 中的 value 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      V setValue(V value) 
    </div> </td> 
   <td> 
    <div>
      将键值对中的value替换为指定value 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

**注意：** **Map.Entry<K,V>** **并没有提供设置** **Key** **的方法**

**3.Map的常用方法**

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

注意：

1. **Map** **是一个接口，不能直接实例化对象**，如果 **要实例化对象只能实例化其实现类** **TreeMap** **或者** **HashMap**

2. **Map** **中存放键值对的** **Key** **是唯一的，** **value** **是可以重复的**

3. **Map** **中的** **Key** **可以全部分离出来，存储到** **Set** **中**来进行访问(因为Key不能重复)。

4. **Map** **中的** **value** **可以全部分离出来，存储在** **Collection** **的任何一个子集合中**(value可能有重复)。

5. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。

6. TreeMap和HashMap的区别

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

**4.Map的遍历方式**

使用最多也最简单的是for循序遍历:

HashMap<Integer,Integer> map = new HashMap<>();
               map.put(1,1);
               map.put(2,2);
                int[] arr = new int[2];
                int k = 0;
                for (Map.Entry<Integer,Integer> entry:map.entrySet()) {
                    arr[k++] = entry.getKey();
                }

其实还有使用迭代遍历map、使用keySet迭代遍历map、使用entrySet遍历map这几种方式，但是觉得使用比较麻烦，直接使用for循环比较方便。

**5.试题案例**

统计10W个数据当中，每个数据出现的次数以及对应的关系。

public static void func3(int[] array) {
            HashMap<Integer,Integer> map = new HashMap<>();
            //1、遍历原来的数据，统计每个数据出现的次数
            for (int i = 0; i < array.length; i++) {
                int key = array[i];
                if(map.get(key) == null) {
                    map.put(key,1);
                }else {
                    int val = map.get(key);//key出现的 次数
                    map.put(key,val+1);
                }
            }
            for (Map.Entry<Integer,Integer> entry: map.entrySet()) {
                System.out.println("key: "+entry.getKey()+" 出现了："+entry.getValue()+"次！");
            }
        }

**三、Set的使用**

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

**Set的官方文档：**[Set (Java Platform SE 8 )![icon-default.png_t_M85B][]https://docs.oracle.com/javase/8/docs/api/java/util/Set.html][Set _Java Platform SE 8 _icon-default.png_t_M85B_https_docs.oracle.com_javase_8_docs_api_java_util_Set.html]**1.关于Set的常见方法**

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

**注意：**

1. Set是继承自Collection的一个接口类

2. Set中只存储了key，并且要求key一定要唯一

3. Set的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的

4. Set最大的功能就是对集合中的元素进行去重

5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。

6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入

7. Set中不能插入null的key,而Map则可以插入空的key。

**2.试题案例**

给定一个**非空**整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

public int singleNumber(int[] nums) {
                HashSet<Integer> set = new HashSet<>();
                for (int i = 0; i < nums.length; i++) {
                    if (!set.contains(nums[i])){
                        set.add(nums[i]);
                    }else {
                        set.remove(nums[i]);
                    }
                }
                for (int i = 0; i < nums.length; i++) {
                    if (set.contains(nums[i])){
                        return nums[i];
                    }
                }
                return -1;
            }

##  ##

[c24c7205d0f94659b5d1095dbdca5d0e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/1bcc4047fd4748889497abe81026c7ff.png
[icon-default.png_t_M85B]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0b364af0388d46d0ad3c9de2e5472772.png
[Map_Map _Java Platform SE 8 _icon-default.png_t_M85B_https_docs.oracle.com_javase_8_docs_api_java_util_Map.html]: https://docs.oracle.com/javase/8/docs/api/java/util/Map.html
[Set _Java Platform SE 8 _icon-default.png_t_M85B_https_docs.oracle.com_javase_8_docs_api_java_util_Set.html]: https://docs.oracle.com/javase/8/docs/api/java/util/Set.html