Java 中的 Map 与 Set 集合

桃扇骨 2023-09-27 21:04 135阅读 0赞

# 1. Map 和 Set 是什么？ #

## 1.1 概念 ##

在Java中，`Map`和`Set`都是接口，是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。`Map`的实例化子类有`TreeMap`、`HashMap`等，`Set`的实例化子类有`TreeSet`，`HashSet`等

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

**Map中存储的是key-value的键值对，Set中只存储了Key，并且每个key都是唯一的，不能重复。**

# 2.Map 接口的使用 #

在Java中，`Map`接口的实现类有：`TreeMap、HashMap`。

`Map`中提供了一些方法的规范，下面是一些常用的：

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>void clear()</code></td> 
   <td>从Map中删除所有的键值对。</td> 
  </tr> 
  <tr> 
   <td><code>boolean containsKey(Object key)</code></td> 
   <td>判断Map中是否包含指定的键。</td> 
  </tr> 
  <tr> 
   <td><code>boolean containsValue(Object value)</code></td> 
   <td>判断Map中是否包含指定的值。</td> 
  </tr> 
  <tr> 
   <td><code>Set&lt;Map.Entry&lt;K, V&gt;&gt; entrySet()</code></td> 
   <td>返回Map中包含的所有键值对的Set集合。</td> 
  </tr> 
  <tr> 
   <td><code>V get(Object key)</code></td> 
   <td>返回与指定键相关联的值。如果Map中不包含该键，则返回null。</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td><code>boolean isEmpty()</code></td> 
   <td>判断Map是否为空。</td> 
  </tr> 
  <tr> 
   <td><code>Set&lt;K&gt; keySet()</code></td> 
   <td>返回Map中包含的所有键的Set集合。</td> 
  </tr> 
  <tr> 
   <td><code>V put(K key, V value)</code></td> 
   <td>将指定的键值对添加到Map中。如果Map中已经包含了该键，则使用新值替换旧值，并返回旧值。</td> 
  </tr> 
  <tr> 
   <td><code>void putAll(Map&lt;? extends K, ? extends V&gt; m)</code></td> 
   <td>将指定Map中的所有键值都添加到当前Map中。</td> 
  </tr> 
  <tr> 
   <td><code>V remove(Object key)</code></td> 
   <td>从Map中删除与指定键相关联的键值对。如果Map中不包含该键，则返回null。</td> 
  </tr> 
  <tr> 
   <td><code>int size()</code></td> 
   <td>返回Map中键值对的数量。</td> 
  </tr> 
  <tr> 
   <td><code>Collection&lt;V&gt; values()</code></td> 
   <td>返回Map中包含的所有值的Collection集合。</td> 
  </tr> 
  <tr> 
   <td><code>V getOrDefault(Object key, V defaultValue)</code></td> 
   <td>返回 key 对应的 value，key 不存在，返回默认值</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中的key不能为null，HashMap中的key可以为null。

## 2.1 TreeMap ##

在Java中，`TreeMap`是基于红黑树实现的一种有序`Map`数据结构。**红黑树是一种自平衡的二叉搜索树**，它可以保证插入、删除、查找等操作的最坏情况时间复杂度为`O(log n)`，在`TreeMap`中`key`不能为`null`。

### （1）TreeMap 的常见构造方法 ###

<table> 
 <thead> 
  <tr> 
   <th>构造方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>TreeMap()</code></td> 
   <td>创建一个空的TreeMap。</td> 
  </tr> 
  <tr> 
   <td><code>TreeMap(Comparator&lt;? super K&gt; comparator)</code></td> 
   <td>创建一个空的TreeMap，使用指定的比较器对键进行排序。</td> 
  </tr> 
  <tr> 
   <td><code>TreeMap(Map&lt;? extends K, ? extends V&gt; m)</code></td> 
   <td>创建一个包含指定Map中的所有键值对的TreeMap。</td> 
  </tr> 
 </tbody> 
</table>

由于`TreeMap`底层是用搜索树实现的，所以`TreeMap`里元素的 `key` 必须是可比较的（根据`key`来比较，生成搜索树），不然要报错，这时候就需要传一个比较器。

class Student{
        String name;
        int age;
    
        public Student(String name, int age) {
            this.name = name;
            this.age = age;
        }
        @Override
        public String toString() {
            return "Student{" + "name=" + name + ", age=" + age + '}';
        }
    }
    
    public class Main {
        public static void main(String[] args) {
    
            //因为 Student 不可比较，所以传入一个比较器
            Map<Student,Integer> map = new TreeMap<>(new Comparator<Student>() {
                @Override
                public int compare(Student o1, Student o2) {
                    //比较名字
                    return o1.name.compareTo(o2.name);
                }
            });
    
            map.put(new Student("小明",20),1);
            map.put(new Student("张三",20),2);
            map.put(new Student("王五",20),3);
            map.put(new Student("李四",20),4);
    
            System.out.println(map);//TreeMap重写了toString()方法，可以直接打印。
        }
    }
    
    结果：{Student{name=小明, age=20}=1, Student{name=张三, age=20}=2, Student{name=李四, age=20}=4, Student{name=王五, age=20}=3}
    复制代码

还有另一种方式，就是 `Student` 实现`Comparable`接口重写`compareTo()`方法。

class Student implements Comparable<Student>{
        String name;
        int age;
    
        public Student(String name, int age) {
            this.name = name;
            this.age = age;
        }
    
        @Override
        public String toString() {
            return "Student{" + "name=" + name + ", age=" + age + '}';
        }
    
        @Override
        public int compareTo(Student o) {
            return this.name.compareTo(o.name);
        }
    }
    复制代码

### （2）TreeMap 方法的演示 ###

`TreeMap`的常见方法都是重写了`Map`接口的方法，这里演示几个比较有趣的方法。

1.  getOrDefault() 方法。

public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("小明",20);
        map.put("张三",19);
        map.put("王五",18);
    
        //返回 key 对应的 value，key 不存在，返回默认值
        int n = map.getOrDefault("李四",1000);
        System.out.println(n);
    }
    
    结果：1000
    复制代码

1.  keySet() 方法 与 values() 方法

public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("小明",20);
        map.put("张三",19);
        map.put("王五",20);
    
        //返回所有 key 的不重复集合
        Set<String> set = map.keySet();
        System.out.println(set);
    
        //返回所有 value 的可重复集合
        Collection<Integer> collection = map.values();
        System.out.println(collection);
    }
    
    结果：
    [小明, 张三, 王五]
    [20, 19, 20]
    复制代码

### （4）Map 的遍历问题：Map.Entry<K, V> ###

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

![format_png][]

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

当我们遍历`Map`时，需要注意的是`Map`中存储的是键值对`（Entry）`，因此我们需要先获取`Map`中的所有`Entry`，再逐个遍历每个`Entry`的键和值。

public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("小明",20);
        map.put("张三",19);
        map.put("王五",20);
    
        //遍历 Map，   Map.Entry<String,Integer> 表示 Map 中的键值对，就像链表中的 Node 一样
        Set<Map.Entry<String,Integer>> set = map.entrySet();//将 Map 里的所有键值对存入一个 Set 里面
        //遍历 Set
        for(Map.Entry<String,Integer> entry: set){  
            String key = entry.getKey();
            //将“小明”的 value 改为 30
            if(entry.getKey().equals("小明")){
                entry.setValue(30);
            }
            int value = entry.getValue();
            System.out.println("Key: " + key +" "+ "Value: " + value);
        }
    }
    结果：
    Key: 小明 Value: 30
    Key: 张三 Value: 19
    Key: 王五 Value: 20
    复制代码

为什么需要将所有键值对存入`set`里面，再对`set`遍历？为什么不能直接对`Map`进行`for-each`遍历？

因为`Map`接口没有直接实现`Iterable`接口，因此无法直接使用`for-each`语句遍历`Map`中的元素。

![format_png 1][]

## 2.2 HashMap ##

Java中`HashMap`的底层是一个哈希桶（开散列表），什么是哈希桶？

哈希桶：一个数组，每个数组元素都是一个单向链表或红黑树，这些链表或树的头结点组成了一个桶数组，用来存储键值对，也可以叫做哈希表。

### （1）构造方法 ###

<table> 
 <thead> 
  <tr> 
   <th>构造方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>HashMap()</code></td> 
   <td>构造一个空的 <code>HashMap</code>。</td> 
  </tr> 
  <tr> 
   <td><code>HashMap(int initialCapacity)</code></td> 
   <td>构造具有指定初始容量的 <code>HashMap</code>。</td> 
  </tr> 
  <tr> 
   <td><code>HashMap(int initialCapacity, float loadFactor)</code></td> 
   <td>构造具有指定初始容量和负载因子的 <code>HashMap</code>。负载因子是哈希表在自动增长之前可以达到多满的一种尺度，通常情况下，负载因子越大，哈希表的装填因子越高，空间利用率就越高，但冲突的可能性也会越高。</td> 
  </tr> 
  <tr> 
   <td><code>HashMap(Map&lt;? extends K, ? extends V&gt; m)</code></td> 
   <td>构造一个新的 <code>HashMap</code>，其映射关系与给定的 <code>Map</code> 相同。</td> 
  </tr> 
 </tbody> 
</table>

`HashMap`的使用与`TreeMap`都是相同的，比如遍历等，下面是使用`HashMap`的注意点：

1.  HashMap中的元素**必须是能比较出是否相同的**，自定义类型需要重写equals和 hashCode方法，对是否能比较大小没有要求。

class Student{
        String name;
        int age;
    
        public Student(String name, int age) {
            this.name = name;
            this.age = age;
        }
    
        @Override
        public String toString() {
            return "Student{" + "name=" + name + ", age=" + age + '}';
        }
    }
    
    public class Main {
        public static void main1(String[] args) {
    
            
            Map<Student,Integer> map = new HashMap<>();
    
            map.put(new Student("小明",19),1);
            map.put(new Student("张三",18),2);
            map.put(new Student("王五",20),3);
            map.put(new Student("王五",20),4);
    
            System.out.println(map);
        }
    }
    复制代码

结果：

![format_png 2][]

我们期望的是王五只出现一次，但是这里出现了两次，为什么？因为`Student`没有比较是否相等的能力，它需要重写`equals`和 `hashCode`方法。

class Student{
        String name;
        int age;
    
        public Student(String name, int age) {
            this.name = name;
            this.age = age;
        }
    
        @Override
        public String toString() {
            return "Student{" + "name=" + name + ", age=" + age + '}';
        }
    
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Student student = (Student) o;
            return age == student.age && name.equals(student.name);
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(name, age);
        }
    }
    
    public class Main {
        public static void main(String[] args) {
           
            HashMap<Student,Integer> map = new HashMap<>();
            map.put(new Student("小明",19),1);
            map.put(new Student("张三",18),2);
            map.put(new Student("王五",20),3);
            map.put(new Student("王五",20),4);
            System.out.println(map);
        }
    }
    
    结果：
    
    {Student{name=小明, age=19}=1, Student{name=张三, age=18}=2, Student{name=王五, age=20}=4}
    复制代码

在`HashMap`源码中，重写的`hashCode()`方法是用来计算哈希值进而确定key的位置，`equals()`方法是用来比较两个对象是否相等的。

1.  顺序问题：`HashMap`中键值对的顺序是不确定的，而`TreeMap`中默认按键的自然顺序或指定的比较器进行排序。
2.  扩容机制：如果`new`的时候没有传参数，**那么当第一次 `put()` 的时候，才会为`HashMap`分配内存**，大小为 16；如果`new`的时候传了参数`n`，**那么会分配最接近（大于等于）你给的参数的2次幂的值**，比如：n = 19，那么会分配252^525 = 32 的大小。
3.  在 JDK 8 中，当一个桶中的元素数量超过了 8 个，并且哈希表的容量大于等于 64，这个桶就会被转换成红黑树。

## 2.4 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(log2N)O(log_2N) O(log2N)</td> 
   <td>O(1)O(1) 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. Set 接口的使用 #

Set接口提供的方法

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>boolean add(E e)</code></td> 
   <td>将指定元素添加到集合中（如果尚未存在）。</td> 
  </tr> 
  <tr> 
   <td><code>boolean remove(Object o)</code></td> 
   <td>从集合中移除指定元素。</td> 
  </tr> 
  <tr> 
   <td><code>boolean contains(Object o)</code></td> 
   <td>如果集合中包含指定元素，则返回 true。</td> 
  </tr> 
  <tr> 
   <td><code>boolean isEmpty()</code></td> 
   <td>如果集合不包含任何元素，则返回 true。</td> 
  </tr> 
  <tr> 
   <td><code>int size()</code></td> 
   <td>返回集合中的元素数量。</td> 
  </tr> 
  <tr> 
   <td><code>void clear()</code></td> 
   <td>从集合中移除所有元素。</td> 
  </tr> 
  <tr> 
   <td><code>Object[] toArray()</code></td> 
   <td>返回一个包含集合中所有元素的数组。</td> 
  </tr> 
  <tr> 
   <td><code>&lt;T&gt; T[] toArray(T[] a)</code></td> 
   <td>将集合中的所有元素转换为指定类型的数组。</td> 
  </tr> 
  <tr> 
   <td><code>boolean containsAll(Collection&lt;?&gt; c)</code></td> 
   <td>如果集合中包含指定集合中的所有元素，则返回 true。</td> 
  </tr> 
  <tr> 
   <td><code>boolean addAll(Collection&lt;? extends E&gt; c)</code></td> 
   <td>将指定集合中的所有元素添加到集合中（如果尚未存在）。</td> 
  </tr> 
  <tr> 
   <td><code>boolean retainAll(Collection&lt;?&gt; c)</code></td> 
   <td>仅保留集合中包含在指定集合中的元素（删除所有其他元素）。</td> 
  </tr> 
  <tr> 
   <td><code>boolean removeAll(Collection&lt;?&gt; c)</code></td> 
   <td>从集合中移除指定集合中包含的所有元素。</td> 
  </tr> 
 </tbody> 
</table>

由于Set接口实现了`lterable` ，所以`TreeSet、HashSet`的遍历直接用`for-each`即可。

1.  Set是继承自Collection的一个接口类。
2.  Set中只存储了key，并且要求key一定要唯一。
3.  Set的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的。
4.  Set最大的功能就是对集合中的元素进行去重。
5.  TreeSet中不能插入null的key，HashSet能插入null的key。

## 3.1 TreeSet ##

`TreeSet`底层是什么呢？它的底层其实就是`TreeMap`！

现在有以下代码

public static void main(String[] args) {
        Set<String> set = new TreeSet<>();
        set.add("小明");
    }
    复制代码

我们点进源码中的 add()：

![format_png 3][]

![format_png 4][]

也就是说，当我`new TreeSet()`的时候，它会 `new TreeMap()`然后赋给 m；但是`Set`明明不是键值对的形式来存储数据的呀，底层怎么会是`Map`呢？从上面的图中看到`put()`方法中第二个参数是`PRESENT`，而`PRESENT`的值是`new Object()`，换言之，无论add多少，第二个参数永远都是一个`Object`类，这就相当于忽略了`value`值。

## 3.2 HashSet ##

`HashSet`的底层是`HashMap`，`HashSet`的一些注意事项与`HashMap`相同，比如它们的`key`可以为`null`，自定义类型要重写`equals`与`hashCode`方法等，这里就不赘述了。

![format_png 5][]

## 3.3 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(log2N)O(log_2N) O(log2N)</td> 
   <td>O(1)O(1) 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>

[format_png]: https://img-blog.csdnimg.cn/img_convert/89e8e163e5875609abc10fc40e499927.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/bd434eb6c6b2714ab18b52deb3a7310d.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/8bee8be500ad4a48c82a2cddad2e4dfe.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/9eabf45c0c0ac5801aab362f0355794f.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/838642999f5b849d88705aed911ca018.webp?x-oss-process=image/format,png
[format_png 5]: https://img-blog.csdnimg.cn/img_convert/0306e69997ef3ee3ad00bbb2efb70810.webp?x-oss-process=image/format,png