【JavaDS】集合Map和Set及其相关实现类

以你之姓@ 2023-09-25 12:33 158阅读 0赞

![在这里插入图片描述][3f9026f5c260455c8ecd6dfef03f83ed.gif_pic_center]

✨**博客主页:**[ **心荣~**][Link 1]  
✨**系列专栏:**[**【Java实现数据结构】**][Java]  
✨**一句短话:** **难在坚持,贵在坚持,成在坚持!**

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

*  一. Map和Set的概述
 *  二. Map
 *   *  1. 注意事项
     *  2. 关于Map.Entry<K,V>的说明
     *  3. Map接口中常用方法
     *  4. HashMap和TreeMap
     *  5. 遍历Map
 *  三. Set
 *   *  1. 注意事项
     *  2. Set接口中常用方法
     *  3. TreeSet和HashSet
     *  4. 遍历Set
 *  四. 小试牛刀

## 一. Map和Set的概述 ##

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

以前常见的搜索方式有：

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

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

1.  根据姓名查询考试成绩
2.  通讯录，即根据姓名查询联系方式
3.  不重复集合，即需要先搜索关键字是否已经在集合中

可能在查找时进行一些插入和删除的操作，即动态查找，那上述两种方式就不太适合了，这里介绍的Map和Set是一种适合动态查找的集合容器。

**两种模型 :**

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

1.  **纯 key 模型(Set就是一个纯key模型)**，比如 :

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

1.  **Key-Value 模型(Map就是一个key-val模型)**，比如 :

*  统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>。
 *  梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号。

![img][]

![img][img 1]

## 二. Map ##

**Map没有继承自Collection/Iterable接口，所以Map不能使用迭代器去遍历, 实现该接口的实现类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复**。

### 1. 注意事项 ###

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

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

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

<table> 
 <thead> 
  <tr> 
   <th><strong>方法</strong></th> 
   <th><strong>解释</strong></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并没有提供设置Key的方法**

### 3. Map接口中常用方法 ###

<table> 
 <thead> 
  <tr> 
   <th><strong>方法</strong></th> 
   <th><strong>解释</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>int size();</td> 
   <td>获取map中键值对个数</td> 
  </tr> 
  <tr> 
   <td>boolean isEmpty();</td> 
   <td>判断map是否为空表</td> 
  </tr> 
  <tr> 
   <td>boolean containsKey(Object key);</td> 
   <td>判断map中是否包含关键字key</td> 
  </tr> 
  <tr> 
   <td>boolean containsValue(Object value);</td> 
   <td>判断map中是否包含值value</td> 
  </tr> 
  <tr> 
   <td>V get(Object key);</td> 
   <td>根据关键字key获取value</td> 
  </tr> 
  <tr> 
   <td>V put(K key, V value);</td> 
   <td>增加键值对&lt;key, value&gt;，如果已经存在则更新value值</td> 
  </tr> 
  <tr> 
   <td>V remove(Object key);</td> 
   <td>根据关键字key删除键值对</td> 
  </tr> 
  <tr> 
   <td>void putAll(Map&lt;? extends K, ? extends V&gt; m);</td> 
   <td>根据传入的map插入键值对</td> 
  </tr> 
  <tr> 
   <td>void clear();</td> 
   <td>清空map</td> 
  </tr> 
  <tr> 
   <td>Set keySet();</td> 
   <td>获取map中所有的key并放入set集合中</td> 
  </tr> 
  <tr> 
   <td>Collection values();</td> 
   <td>获取map中所有的value，并放入collection集合中，可重复</td> 
  </tr> 
  <tr> 
   <td>Set&lt;Map.Entry&lt;K, V&gt;&gt; entrySet();</td> 
   <td>将map中所有的键值对以Map.Entry&lt;K,V&gt;类型打包到set中</td> 
  </tr> 
  <tr> 
   <td>default V getOrDefault(Object key, V defaultValue)</td> 
   <td>返回 key 对应的 value，key 不存在，返回默认值</td> 
  </tr> 
  <tr> 
   <td>default V replace(K key, V value)</td> 
   <td>修改key关键字对应的value</td> 
  </tr> 
  <tr> 
   <td>default boolean replace(K key, V oldValue, V newValue)</td> 
   <td>将关键字对应的oldValue修改为newValue</td> 
  </tr> 
 </tbody> 
</table>

通过下面的代码区分get()和 getOrDefault()两个方法的细节

![img][img 2]

![img][img 3]

当我们通过get 获取的是Integer类型的值，让他赋值给整形会发生拆包，这里map中没有key，那么会返回null，此时拆包，就会发生空指针异常;

而使用 getOrDefault() , 如果map中没有key , 就会返回我们设置的默认值, 就不会进行拆包操作了 .

### 4. HashMap和TreeMap ###

HashMap与TreeMap都实现了Map接口, 两者的区别如下:

<table> 
 <thead> 
  <tr> 
   <th><strong>Map底层结构</strong></th> 
   <th><strong>TreeMap</strong></th> 
   <th><strong>HashMap</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>底层结构</td> 
   <td>红黑树</td> 
   <td>哈希桶（表）</td> 
  </tr> 
  <tr> 
   <td>插入/删除/查找时间复杂度</td> 
   <td>O(log2N)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>是否有序</td> 
   <td>关于Key有序 (因为实现了SortedMap接口)</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>

TreeMap继承关系图如下:

![img][img 4]

<table> 
 <thead> 
  <tr> 
   <th><strong>TreeMap构造方法</strong></th> 
   <th><strong>解释</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>public TreeMap()</td> 
   <td>无参构造</td> 
  </tr> 
  <tr> 
   <td>public TreeMap(Comparator&lt;? super K&gt; comparator)</td> 
   <td>传入比较器，能够控制Mapk的key的排序</td> 
  </tr> 
  <tr> 
   <td>public TreeMap(Map&lt;? extends K, ? extends V&gt; m)</td> 
   <td>根据传入的map对象来构造新的Treemap对象</td> 
  </tr> 
  <tr> 
   <td>public TreeMap(SortedMap&lt;K, ? extends V&gt; m)</td> 
   <td>根据传入的SortedMap对象构造新的Treemap对象</td> 
  </tr> 
 </tbody> 
</table>

HashMap继承关系图如下:

![img][img 5]

<table> 
 <thead> 
  <tr> 
   <th><strong>HashMap构造方法</strong></th> 
   <th><strong>解释</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>public HashMap()</td> 
   <td>无参构造</td> 
  </tr> 
  <tr> 
   <td>public HashMap(int initialCapacity, float loadFactor)</td> 
   <td>指定容量（必须是二的幂）和负载因子构造对象</td> 
  </tr> 
  <tr> 
   <td>public HashMap(int initialCapacity)</td> 
   <td>指定容量（必须是二的幂）构造对象</td> 
  </tr> 
  <tr> 
   <td>public HashMap(Map&lt;? extends K, ? extends V&gt; m)</td> 
   <td>根据map对象构造新HashMap对象</td> 
  </tr> 
 </tbody> 
</table>

### 5. 遍历Map ###

Map当中没有实现Iterable接口, 所以遍历map的思路是将Map放到实现Iterable接口中的Set中即可;

*  通过keySet()方法

public static void main(String[] args) {
        
        Map<String,Integer> map = new HashMap<>();
        map.put("张三",1);
        map.put("李四",2);
        map.put("王五",3);
        Set<String> set = map.keySet();
        for (String s : set) {
        
            System.out.println(s+" = "+map.get(s));
        }
    }

*  通过entrySet()方法

public static void main(String[] args) {
        
        Map<String,Integer> map = new HashMap<>();
        map.put("张三",1);
        map.put("李四",2);
        map.put("王五",3);
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        for (Map.Entry<String, Integer> entry : entries) {
        
            System.out.println(entry.getKey()+" = "+entry.getValue());
        }
    }

*  通过Map提供的forEach(BiConsumer)方法

BiConsumer是一个函数式接口，接受两个输入参数

public static void main(String[] args) {
        
        Map<String,Integer> map = new HashMap<>();
        map.put("张三",1);
        map.put("李四",2);
        map.put("王五",3);
        map.forEach(new BiConsumer<String, Integer>() {
        
            @Override
            public void accept(String key, Integer value) {
        
                System.out.println(key+" = "+value);
            }
        });
    }

## 三. Set ##

### 1. 注意事项 ###

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不能修改，如果要修改，先将原来的删除掉，然后再重新插入

### 2. Set接口中常用方法 ###

Set接口中大部分方法都是从Collection接口中扩展的，常用方法如下：

<table> 
 <thead> 
  <tr> 
   <th><strong>方法</strong></th> 
   <th><strong>解释</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>int size();</td> 
   <td>获取集合中元素的个数</td> 
  </tr> 
  <tr> 
   <td>boolean isEmpty();</td> 
   <td>判断集合是否为空表</td> 
  </tr> 
  <tr> 
   <td>boolean contains(Object o);</td> 
   <td>判断set是否包含对象o</td> 
  </tr> 
  <tr> 
   <td>Iterator iterator();</td> 
   <td>获取集合迭代器</td> 
  </tr> 
  <tr> 
   <td>Object[] toArray();</td> 
   <td>将set转换成Object数组</td> 
  </tr> 
  <tr> 
   <td>T[] toArray(T[] a);</td> 
   <td>将set转换为数组</td> 
  </tr> 
  <tr> 
   <td>boolean add(E e);</td> 
   <td>增加元素e</td> 
  </tr> 
  <tr> 
   <td>boolean remove(Object o);</td> 
   <td>删除元素o</td> 
  </tr> 
  <tr> 
   <td>boolean containsAll(Collection&lt;?&gt; c);</td> 
   <td>判断set中是否含有collection对象中所有的元素</td> 
  </tr> 
  <tr> 
   <td>boolean addAll(Collection&lt;? extends E&gt; c);</td> 
   <td>插入c对象中所有的元素，可以去重</td> 
  </tr> 
  <tr> 
   <td>boolean retainAll(Collection&lt;?&gt; c);</td> 
   <td>set中保留和两个集合的交集</td> 
  </tr> 
  <tr> 
   <td>boolean removeAll(Collection&lt;?&gt; c);</td> 
   <td>根据c对象元素对应删除set中的元素</td> 
  </tr> 
  <tr> 
   <td>void clear();</td> 
   <td>清空set对象里面所有元素</td> 
  </tr> 
 </tbody> 
</table>

### 3. TreeSet和HashSet ###

HashSet与TreeSet都实现了Set接口, 两者的区别如下:

<table> 
 <thead> 
  <tr> 
   <th><strong>Set底层结构</strong></th> 
   <th><strong>TreeSet</strong></th> 
   <th><strong>HashSet</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>底层结构</td> 
   <td>红黑树</td> 
   <td>哈希桶（表）</td> 
  </tr> 
  <tr> 
   <td>插入/删除/查找时间复杂度</td> 
   <td>O(log2N)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>是否有序</td> 
   <td>关于Key有序 (因为实现了SortedSet接口)</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>key必须能够比较，否则会抛出ClassCastException异常</td> 
   <td>自定义类型需要覆写equals和 hashCode方法</td> 
  </tr> 
  <tr> 
   <td>应用场景</td> 
   <td>需要Key有序场景下</td> 
   <td>Key是否有序不关心，需要更高的时间性能</td> 
  </tr> 
 </tbody> 
</table>

TreeSet继承关系图如下:

![img][img 6]

<table> 
 <thead> 
  <tr> 
   <th><strong>TreeSet构造方法</strong></th> 
   <th><strong>解释</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>public TreeSet()</td> 
   <td>无参构造</td> 
  </tr> 
  <tr> 
   <td>public TreeSet(Comparator&lt;? super E&gt; comparator)</td> 
   <td>传入比较器，控制set的排序</td> 
  </tr> 
  <tr> 
   <td>public TreeSet(Collection&lt;? extends E&gt; c)</td> 
   <td>根据集合c的元素创建TreeSet</td> 
  </tr> 
  <tr> 
   <td>public TreeSet(SortedSet s)</td> 
   <td>根据SortedSet对象的元素创建TreeSet</td> 
  </tr> 
 </tbody> 
</table>

HashSet继承关系图如下:

![img][img 7]

<table> 
 <thead> 
  <tr> 
   <th><strong>HashSet构造方法</strong></th> 
   <th><strong>解释</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>public HashSet()</td> 
   <td>无参构造</td> 
  </tr> 
  <tr> 
   <td>public HashSet(Collection&lt;? extends E&gt; c)</td> 
   <td>根据集合对象c构造HashSet对象</td> 
  </tr> 
  <tr> 
   <td>public HashSet(int initialCapacity, float loadFactor)</td> 
   <td>指定容量（必须是二的幂）和负载因子构造HashSet对象</td> 
  </tr> 
  <tr> 
   <td>public HashSet(int initialCapacity)</td> 
   <td>指定容量（必须是二的幂）构造HashSet对象</td> 
  </tr> 
 </tbody> 
</table>

### 4. 遍历Set ###

*  通过迭代器遍历

public static void main(String[] args) {
        
        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        Iterator<Integer> it = set.iterator();
        while(it.hasNext()) {
        
            System.out.print(it.next()+" ");
        }
    }

*  foreach遍历

public static void main(String[] args) {
        
        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        for (Integer integer : set) {
        
            System.out.print(integer+" ");
        }
    }

*  通过Iterable接口中的forEach(Consumer)方法

Consumer是一个函数式接口，接受一个输入参数

public static void main(String[] args) {
        
        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        set.forEach(new Consumer<Integer>() {
        
            @Override
            public void accept(Integer key) {
        
                System.out.print(key+" ");
            }
        });
    }

## 四. 小试牛刀 ##

解决下面的三个问题:

1.  统计10W个数据当中，不重复的数据？(去重)
2.  统计10W个数据当中，第一个重复的数据？
3.  统计10W个数据当中，每个数据出现的次数？ (对应的关系)

import java.util.*;
    
    public class Test {
        
        //1、统计10W个数据当中，不重复的数据？[去重]
        public static void func1(int[] array) {
        
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < array.length; i++) {
        
                set.add(array[i]);
            }
            System.out.println(set);
        }
        //2、统计10W个数据当中，第一个重复的数据？
        public static void func2(int[] array) {
        
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < array.length; i++) {
        
                if(!set.contains(array[i])) {
        
                    set.add(array[i]);
                }else {
        
                    System.out.println(array[i]);
                    break;
                }
            }
        }
        //3、统计10W个数据当中，每个数据出现的次数？ 对应的关系
        public static void func3(int[] array) {
        
            Map<Integer, Integer> map = new HashMap<>();
            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);
                    map.put(key, val+1);
                }
            }
            for (Map.Entry<Integer, Integer> entry:map.entrySet()) {
        
                System.out.println("key: "+ entry.getKey()+"出现了: "+entry.getValue()+" 次");
            }
        }
    
        public static void main(String[] args) {
        
            int[] array = new int[10_0000];
            Random random = new Random();
            for (int i = 0; i < array.length; i++) {
        
                array[i] = random.nextInt(5_0000);
            }
            func1(array);
            func2(array);
            func3(array);
        }
    }

[3f9026f5c260455c8ecd6dfef03f83ed.gif_pic_center]: https://img-blog.csdnimg.cn/3f9026f5c260455c8ecd6dfef03f83ed.gif#pic_center
[Link 1]: https://blog.csdn.net/Trong_?spm=1000.2115.3001.5343
[Java]: https://blog.csdn.net/trong_/category_11997769.html
[img]: https://img-blog.csdnimg.cn/img_convert/506309d50fe24623709a732baf268af1.png
[img 1]: https://img-blog.csdnimg.cn/img_convert/c9228924ae824ca32b8030e2b1d050ac.png
[img 2]: https://img-blog.csdnimg.cn/img_convert/db9757b472c091bbb8f8aaac3531c264.png
[img 3]: https://img-blog.csdnimg.cn/img_convert/ecea7683c78f9bedd117b3aefbd5fbef.png
[img 4]: https://img-blog.csdnimg.cn/img_convert/3ad9dc7bfb6d7d325b27d704e7c2afbd.png
[img 5]: https://img-blog.csdnimg.cn/img_convert/1f851ac497f30aa54954160ae994045c.png
[img 6]: https://img-blog.csdnimg.cn/img_convert/d971418c3b08ec4c11d0d7afb248156d.png
[img 7]: https://img-blog.csdnimg.cn/img_convert/32b44179a4fe9e52f34eb91aa8d7444f.png