三道题教你快速掌握Map和Set

简介: Map 和 Set 都是接口类,都不能不能直接实例化对象,如果要实例化只能实例化其对于实现类!

0、简单介绍 Map 和 Set

Map 和 Set 都是接口类,都不能不能直接实例化对象,如果要实例化只能实例化其对于实现类!

一般情况下,都会使用 HashMap 和 HashSet 进行实例化

Map内部存储的是 键值对 <key,value>,其中 key 不能重复,value可以重复

Set内部存到的是 key,其中 key 不能重复

Map 常用方法如下

方法 解释
V get(Object key) 返回 key 对应的 value
V getOrDefault(Object key, V defaultValue) 返回 key 对应的 value,key 不存在,返回默认值
V put(K key, V value) 设置 key 对应的 value
V remove(Object key) 删除 key 对应的映射关系
Set<K> keySet() 返回所有 key 的不重复集合
Collection<V> values() 返回所有 value 的可重复集合
Set<Map.Entry<K, V>> entrySet() 返回所有的 key-value 映射关系
boolean containsKey(Object key) 判断是否包含 key
boolean containsValue(Object value) 判断是否包含 value

Set 常用方法如下

方法 解释
boolean add(E e) 添加元素,但重复元素不会被添加成功
void clear() 清空集合
boolean contains(Object o) 判断 o 是否在集合中
Iterator<E> iterator() 返回迭代器
boolean remove(Object o) 删除集合中的 o
int size() 返回set中元素的个数
boolean isEmpty() 检测set是否为空,空返回true,否则返回false
Object[] toArray() 将set中的元素转换为数组返回
boolean containsAll(Collection<?> c) 集合c中的元素是否在set中全部存在,是返回true,否则返回
false
boolean addAll(Collection<? extends
E> c)
将集合c中的元素添加到set中,可以达到去重的效果

1、三道关于 Map 和 Set 面试题

现在进行角色扮演,大家现在要去找面试官面试,而我就是大家召唤出来的外挂😁,帮大家指指引迷津

     

现在面试官给你 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);
}

Random 类可以产生随机的数据

import java.util.Random;

第一道题:把这 10W 个数据中的 重复 的元素 删除掉

问题记好了吗,记好了我就要睡觉了😂(开玩笑开玩笑)

这道题我们根据最重要的修饰词是什么?当然是 重复 !! 而当题目中出现 重复 这个关键词时,就相当于告诉我们这道题用 Map 或 Set来解

Map 和 Set最大的特点在于其内部存储的数据不能重复

为了方便,这道题就用 Set 来解。这道题非常简单,我们只需操心把 10W 个数据全部交给 HashSet,剩下的就 HashSet 帮你解决!!!

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);
    }
    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_000);
        }
        func1(array);
    }

结果如下

第二道题:找到这 10W 个数据当中,第一个重复的数据

面试官:不错不错,第一道题竟然这么快就解决了,让我来提升一下难度

看到这道题,我们如果能想到用 Map 和 Set 来解决,就说明我们已经成功 一半了。


为了方便,咱们还用 Set 来解。但是跟第一道不同,我们这次不能一股脑的全部交给 Set 来操作,我们要在存数据的同时判断该数据是由在 Set 中已经出现。


而判断 Set 内部是否包含某个元素我们可以用 contains() 方法,有则返回 true,无则返回 false

public static int func2(int[] array){
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if(set.contains(array[i])){
                return array[i];
            }else{
                set.add(array[i]);
            }
        }
        return -1;
    }
    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_000);
        }
        System.out.println(func2(array));
    }

第三道题:统计这 10W 个数据当中,每个数据出现的次数

面试官:小伙子不错啊,能走到这一步,看了我要加大难度啦

这道题,我们就不能用 Set 来解决了,因为 Set 只能存储 key值,也就是说 Set 只能简单的去重或者查找第一个重复的元素,而不能记录每个数出现次数。


而 Map 确可以,因为 Map 内部存储的 key-value 键值对,key 和 value 相当于绑定,拿到 key 就能拿到 value


例如 1 1 1 1 2 2  这六个数,放到 Set 内部就变成了 { 1 , 2 }

而放到 Map 中就能变成 { <1,4> , <2,2> },也就是说我们拿到 ‘1’ 就能知道 ‘1’ 出现的次数为四!!!


思路跟第二题差不多,要边存数据边操作。我们把元素 存到 key 中,而元素出现的次数放到 value 中。


当我们要存一个元素时,先检测它是否在 Map 中存储过,如果没有,就把它放到 Map 中,并把value赋值为1。如果已经存在,那就先获得该元素的 value 值,把 value+1 再放到 Map中。

public static void func3(int[] array){
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if(map.containsKey(array[i])){
                int val = map.get(array[i]);
                map.put(array[i],val+1);
            }else{
                map.put(array[i],1);
            }
        }
        System.out.println(map);
    }
    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_000);
        }
        func3(array);
    }

结果如下:

面试官:小伙子不错,三道题竟然都解决完了,不错不错,你被录用了😼🎉🎉🎉

突然你一阵眩晕,一睁眼发现原来自己都是自己做的一个梦😅


2、总结

我们通过上述三个题的练习,应该清楚 Map 和 Set 的用法了吧。

我们会发现,一道题能用 Set 解那么就能用 Map来解,而 Map 能解决的 Set 不一定能解决。

如果只是单词的消除重复的元素,那么可以使用 Set。

如果像第三道题那样,每个元素有附加的属性,就如 ‘1’ 出现次数是多少时,用 Map。

同时,Map 和 Set 内部还可以存储其他类型,或者自定义类,这里我给大家列举一些题目供大家练习掌握


1️⃣只出现一次的数字


2️⃣宝石与石头


3️⃣复制带随机指针的链表


4️⃣旧键盘 (20)


5️⃣前K个高频单词


相关文章
|
存储 JavaScript Java
(Python基础)新时代语言!一起学习Python吧!(四):dict字典和set类型;切片类型、列表生成式;map和reduce迭代器;filter过滤函数、sorted排序函数;lambda函数
dict字典 Python内置了字典:dict的支持,dict全称dictionary,在其他语言中也称为map,使用键-值(key-value)存储,具有极快的查找速度。 我们可以通过声明JS对象一样的方式声明dict
714 2
|
存储 缓存 JavaScript
Set和Map有什么区别?
Set和Map有什么区别?
947 1
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
516 2
|
存储 JavaScript 前端开发
for...of循环在遍历Set和Map时的注意事项有哪些?
for...of循环在遍历Set和Map时的注意事项有哪些?
965 156
|
存储 算法 容器
set_map的实现+set/map加持秒杀高频算法题锻炼算法思维
`set`基于红黑树实现,支持有序存储、自动去重,增删查效率为O(logN)。通过仿函数可自定义排序规则,配合空间配置器灵活管理内存。不支持修改元素值,迭代器失效需注意。`multiset`允许重复元素。常用于去重、排序及查找场景。
|
算法
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
379 18
你对Collection中Set、List、Map理解?
|
存储 C++ 容器
unordered_set、unordered_multiset、unordered_map、unordered_multimap的介绍及使用
unordered_set是不按特定顺序存储键值的关联式容器,其允许通过键值快速的索引到对应的元素。在unordered_set中,元素的值同时也是唯一地标识它的key。在内部,unordered_set中的元素没有按照任何特定的顺序排序,为了能在常数范围内找到指定的key,unordered_set将相同哈希值的键值放在相同的桶中。unordered_set容器通过key访问单个元素要比set快,但它通常在遍历元素子集的范围迭代方面效率较低。它的迭代器至少是前向迭代器。前向迭代器的特性。
900 0
|
编译器 C++ 容器
用一棵红黑树同时封装出map和set
再完成上面的代码后,我们的底层代码已经完成了,这时候已经是一个底层STL的红黑树了,已经已符合库里面的要求了,这时候我们是需要给他穿上对应的“衣服”,比如穿上set的“衣服”,那么这个穿上set的“衣服”,那么他就符合库里面set的要求了,同样map一样,这时候我们就需要实现set与map了。因此,上层容器map需要向底层红黑树提供一个仿函数,用于获取T当中的键值Key,这样一来,当底层红黑树当中需要比较两个结点的键值时,就可以通过这个仿函数来获取T当中的键值了。我们就可以使用仿函数了。
231 0
|
存储 编译器 容器
set、map、multiset、multimap的介绍及使用以及区别,注意事项
set是按照一定次序存储元素的容器,使用set的迭代器遍历set中的元素,可以得到有序序列。set当中存储元素的value都是唯一的,不可以重复,因此可以使用set进行去重。set默认是升序的,但是其内部默认不是按照大于比较,而是按照小于比较。set中的元素不能被修改,因为set在底层是用二叉搜索树来实现的,若是对二叉搜索树当中某个结点的值进行了修改,那么这棵树将不再是二叉搜索树。
541 0