数据结构 Map和Set（看这篇就够了~）_map结构和set结构

系列文章目录

---

一、Set

1.1 Set和List以及Map的区别

Iterable:实际上就是for-each循环
Collection:线性表接口

1.2 Set集合基本用法

add()

contains()

remove()

set没有提供修改数据的方法，是因为大部分用途都是去重处理

1.3注意事项

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

2.1基本用法

重点：遍历map集合

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

// 打印所有的键值对
 // entrySet(): 将Map中的键值对放在Set中返回了
 for(Map.Entry<String, String> entry : m.entrySet()){
   
 System.out.println(entry.getKey() + "--->" + entry.getValue());
 }
1
2
3
4
5
6

2.2 get（）

get(key): 返回key所对应的value
如果key存在，返回key所对应的value
如果key不存在，返回null

2.3 put()

身兼两职：既可以修改数据也可以新增数据

2.4 remove()

返回的是key对应的value值

2.5 keySet()

// 打印所有的key
 // keySet是将map中的key防止在Set中返回的
 for(String s : map.keySet()){
   
 System.out.print(s + " ");
 }
1
2
3
4
5
6

2.6 values()

// 打印所有的value
 // values()是将map中的value放在collect的一个集合中返回的
 for(String s : m.values()){
   
 System.out.print(s + " ");
 }
1
2
3
4
5
6

三、Map接口常见子类问题

3.1添加问题

TreeMap和HashMap区别

类型转换异常：


但是如果换成HashMap：两者底层数据结构不同

3.2 null值

Hashmap的key和value值可以为null

换成子类：TreeMap，key值不能为null，value可以为null

总结

3.3注意事项

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

四、常见面试题

4.1只出现一次的数字（简单）

添加链接描述

public int singleNumber(int[] nums) {
   
        Map<Integer,Integer> map=new HashMap<>();
        //1.先扫描原数组
        for (int i:nums
             ) {
   
            map.put(i,map.getOrDefault(i,0)+1);
        }
        //2.遍历map集合找到value=1的数字
        int num=0;
        for (Map.Entry<Integer,Integer> entry:map.entrySet()
             ) {
   
            if(entry.getValue().equals(1)){
   
                num=entry.getKey();
            }
        }
        return num;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4.2只出现一次的数字II（中等）

添加链接描述

public int[] singleNumber(int[] nums) {
   
        Map<Integer,Integer> map=new HashMap<>();
        for (int i: nums
             ) {
   
            map.put(i,map.getOrDefault(i,0)+1);
        }
        int[] num=new int[2];
        int i=0;
        for (Map.Entry<Integer,Integer> entry:map.entrySet()
             ) {
   
            if(entry.
1
2
3
4
5
6
7
8
9
10
11
12
13