【数据结构】Map的使用与注意事项

概念

Map 和 set 是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。 以前常见的搜索方式有：

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

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

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

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

模型

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

1. 纯key模型，比如：

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

2. Key-Value模型，比如：

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

而 Map 中存储的就是 key-value 的键值对，Set 中只存储了 Key 。

Map 的使用

Map 和 Set 主要用于搜索

• TreeSet 和 TreeMap 底层就是一颗二叉搜索树==>红黑树

put() 和 get()

Map<String,String> map = new TreeMap<>();  
map.put("及时雨","松江");  
map.put("齐天大圣","孙悟空");  
  
String val = map.get("齐天大圣");  
String val2 = map.get("孙悟空");  
System.out.println(val);  
System.out.println(val2);
/*
运行结果：
孙悟空
null
*/

• put 的时候是有顺序的，前面的是 Key ，后面的是 Value
• 进行 get 的时候是返回 Key 所对应的 Value，而不能返回 Value 所对应的 Key

getOrDefault()

当没有找到 Key 所对应的 Value 值时，会默认输出 null，但默认值可以改

Map<String,String> map = new TreeMap<>();  
map.put("及时雨","松江");  
map.put("齐天大圣","孙悟空");  
  
String val3 = map.getOrDefault("弼马温","没找到啊");  
System.out.println(val3);
/*
运行结果：
没找到啊
*/

• 如果没有“弼马温”这个 Key，就取不到 Value，就给一个默认值“没找到啊”

remove()

就是删除的意思，删除 Key 对应的映射关系

Map<String,String> map = new TreeMap<>();  
map.put("及时雨","松江");  
map.put("齐天大圣","孙悟空");  
String val3 = map.remove("齐天大圣");  
System.out.println(val3);
String val4 = map.get("齐天大圣");
System.out.println(val4);
/*
运行结果：
孙悟空
null
*/

• 因为这个方法的返回值是 Value，所以还是会打印出“孙悟空”，但之后 Key（齐天大圣）和 Value（孙悟空）之间的映射关系就被删除了，不存在了
• 所以第二次再 get 这个 Key 的 Value 值就找不到了

keySet()

将所有的 Key 都拿出来，放在一个 Set 集合中

Map<String,String> map = new TreeMap<>();  
map.put("及时雨","松江");  
map.put("齐天大圣","孙悟空");    
map.put("齐天大圣","弼马温");
  
Set<String> set = map.keySet();  
System.out.println(set);
System.out.println(map.get("齐天大圣"));
/*
运行结果：
[及时雨, 齐天大圣]
弼马温
*/

• 因为 Key 都是 String，所以用一个 String 类型的 Set 进行接收
• Key 是不能重复的，如果重复了，就会更新 Key 的值

entrySet()

如果想将 Key 和 Value 的映射关系一起返回，就可以调用 entrySet

Map<String,String> map = new TreeMap<>();  
map.put("及时雨","松江");  
map.put("齐天大圣","孙悟空");  
  
Set<Map.Entry<String,String>> entries = map.entrySet();  
System.out.println(entries);
System.out.println(===============);
for (Map.Entry<String,String> entry : entries){  
    System.out.println(entry);  
}
System.out.println(===============);
for (Map.Entry<String,String> entry : entries){  
    System.out.println("Key:"+entry.getKey()+" Value:"+entry.getValue());  
}
/*
运行结果：
[及时雨=松江, 齐天大圣=孙悟空]
===============
及时雨=松江
齐天大圣=孙悟空
===============
Key:及时雨 Value:松江
Key:齐天大圣 Value:孙悟空
*/

• 在 Entry 里面也可以单独的取出 Key 或者 Value。
• Entry是Map接口的内置接口，其内部有

• getKey 方法，用来获取 Key
• getValue 方法，用来获取 Value
• setValue 方法，用来更新 Value

注意事项

1. Map 是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类 TreeMap 或者 HashMap （搜索树，红黑树）
   
2. Map 中存放键值对的 Key 是唯一的，value 是可以重复的
   
3. 在 TreeMap 中插入键值对时，key 不能为空，否则就会抛 NullPointerException 异常，value 可以为空。但是 HashMap 的 key 和 value 都可以为空。
   
4. Map 中的 Key 可以全部分离出来，存储到 Set 中来进行访问(因为 Key 不能重复)。
   
5. Map 中的 value 可以全部分离出来，存储在 Collection 的任何一个子集合中(value 可能有重复)。
   
6. Map 中键值对的 Key 不能直接修改，value 可以修改，如果要修改 key，只能先将该 key 删除掉，然后再来进行重新插入。
   
7. 往 TreeMap 中存储元素的时候，Key 一定是要可以比较的，因为 Key 的底层是红黑树，要将 Key 按大小顺序排列好。如果你传入一个类的时候，就要注意了