一文学懂Map和Set——详解

太过爱你忘了你带给我的痛 2024-04-01 15:27 20阅读 0赞

**目录**

1. Map

1.1 Map常用方法

1.2注意

1.3Map的底层结构

2. Set

2.1 Set常用方法

2.2 注意

2.3 Set的底层结构

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

Map与Set是一种专门用来搜索的容器或者数据结构，其搜索的效率与具体的实例化子类有关。一般的查找如二分查找，它适合静态类型的查找，即就是不进行插入、删除操作。但现实中，如根据学号查找学生姓名，这种查可能会在查找时进行插入或删除操作，二分查找就不适用了。

Map就是一个数据对应于另一个数据，如学号与姓名是一一对应的、身份证与某个人是一一对应的

Set就像是一个集合，它里面存放一组不重复的数据。

## 1. Map ##

Map底层有HashMap或者TreeMap，主要运用的是HashMap。

Map<key，value>有两个变量，就是键值对，下面是Map的初始化

例如

![86696449179a40cbbc5940d9447a5115.png][]

输出发现，定义时“hello”在前，“love”在后，但是输出时却先输出“love”，后输出“hello”。

**这是因为存储的时候，是根据一个函数来进行存储的。具体存储在哪里，是由这个函数确定的，这个函数是哈希函数**

**注意：Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。**

### 1.1 Map常用方法 ###

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

1.如keySet()这个函数，作用是返回所有的key，返回值的类型是Set<K>.

public class Main {
        public static void main(String[] args) {
            Map<String,Integer> map = new HashMap<>();
            map.put("hello",10);
            map.put("love",20);
            map.put("map",9);
    
            Set<String> set = map.keySet();
            System.out.println(set);
        }
    }

输出结果，即就是返回所有的key。

![d627ce908f6446dbb367bee9149721d2.png][]

2.再如entrySet()这个函数，它的返回值是Set<Map.Entry<K, V>>。如：

> Set<Map.Entry<String，Integer>> set = map.entrySet();

set的类型是Set<Map.Entry<String，Integer>>，而set中存放的数据类型是Map.Entry<String，Integer>，就是将map中的“键值对”作为一个整体存放的set中，set像是一个大数组，这个类似数组的set中每个值都是map的“键值对”。对于set的输出，可以利用foreach循环进行。

例如下面代码

public class Main{
        public static void main(String[] args) {
            Map<String,Integer> map = new HashMap<>();
            map.put("hello",10);
            map.put("love",20);
            map.put("map",9);
    
            System.out.println(map);
    
            Set<Map.Entry<String,Integer>> set = map.entrySet();
            for (Map.Entry<String,Integer> i:set) {
                System.out.println(i.getKey() +" "+ i.getValue() );
            }
        }
    }

输出结果：

![c889921b0e4d46d7be63182dae5902f6.png][]

### 1.2注意 ###

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

### 1.3Map的底层结构 ###

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

**HashMap的时间复杂度为O(1)，所以通常情况下，一般使用的是HashMap。**

## 2. Set ##

Set会自动**去重**

public class Main{
        public static void main(String[] args) {
            Set<Integer> set = new HashSet<>();
            set.add(1);
            set.add(2);
            set.add(3);
            set.add(1);
            System.out.println(set);
        }
    }

输出：

![4a04f87470fc449d80ea0a7ede1096c1.png][]

### 2.1 Set常用方法 ###

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

对于Iterator<E> iterator()函数，返回值类型是Iterator<E>。对于Set的输出，可以利用这个迭代器函数。

public class Main {
        public static void main2(String[] args) {
            Set<Integer> set = new HashSet<>();
            set.add(1);
            set.add(2);
            set.add(3);
            System.out.println(set);
    
            Iterator<Integer> iterator = set.iterator();
            while(iterator.hasNext()){
                System.out.println(iterator.next());
            }
        }
    }

输出结果：

![ea6e1f218baa405abc23e2a4b6bc0cd2.png][]

### 2.2 注意 ###

> 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 。 
> 
> 8. TreeSet 和 HashSet 的区别

### 2.3 Set的底层结构 ###

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

**一般情况下用的是HashSet**

[86696449179a40cbbc5940d9447a5115.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/72a8e35f5d3c4e6795260bc996d9a024.png
[d627ce908f6446dbb367bee9149721d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/da1b464ff2784e838297a41ad55c18e8.png
[c889921b0e4d46d7be63182dae5902f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ddee664f425445ab9a0e3b7ad767956a.png
[4a04f87470fc449d80ea0a7ede1096c1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4d04df5cbfa04ab18bf1efa06428bf4b.png
[ea6e1f218baa405abc23e2a4b6bc0cd2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b53c4358224b4c898455a5b41ef9075a.png