文章目录
??一、概念、场景及模型
Map
和
set是一种专门用来进行搜索的容器或者数据结构，
Map
和
Set是一种适合动态查找的集合容器。TreeMap和TreeSet集合背后的数据结构就是搜索树，红黑树。其中TreeSet底层就是一个TreeMap。
一般把搜索的数据称为关键字（
Key
），和关键字对应的称为值（Value），将其称之为
Key-value
的键值对，所以模型会有两种：
1.
纯
key
模型
2.
Key-Value
模型
而
Map
中存储的就是
key-value
的键值对，
Set
中只存储了
Key
。
二、Map的使用
Map的官方文档：Map (Java Platform SE 8 )
https://docs.oracle.com/javase/8/docs/api/java/util/Map.html1.关于Map的说明
Map
是一个接口类，该类没有继承自
Collection
，该类中存储的是
<K,V>
结构的键值对，并且
K
一定是唯一的，不
能重复，因为底层是二叉搜索树
。
2.关于Map.Entry的说明
Map.Entry<K, V>
是
Map
内部实现的用来存放
<key, value>
键值对映射关系的内部类
，该内部类中主要提供了<key, value>的获取，
value
的设置以及
Key
的比较方式。
| 方法 | 说明 |
|
K
getKey
()
|
返回
entry
中的
key
|
|
V
getValue
()
|
返回
entry
中的
value
|
|
V setValue(V value)
|
将键值对中的
value
替换为指定
value
|
注意：
Map.Entry<K,V>
并没有提供设置
Key
的方法
3.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
|
注意：
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
和
HashMap
的区别
| Map | TreeMap | HashMap |
| 底层结构 | 红黑树 | 哈希桶 |
|
插入
/
删除
/
查找时间
复杂度
| O(logN) |
O(1)
|
|
是否有序
|
关于
Key
有序
|
无序
|
|
线程安全
|
不安全
|
不安全
|
|
插入
/
删除
/
查找区别
|
需要进行元素比较
|
通过哈希函数计算哈希地址
|
|
比较与覆写
|
key
必须能够比较，否则会抛出 ClassCastException异常
|
自定义类型需要覆写
equals
和 hashCode方法
|
|
应用场景
|
需要
Key
有序场景下
|
Key
是否有序不关心，需要更高的时间性能
|
4.Map的遍历方式
使用最多也最简单的是for循序遍历:
HashMap<Integer,Integer> map = new HashMap<>();
map.put(1,1);
map.put(2,2);
int[] arr = new int[2];
int k = 0;
for (Map.Entry<Integer,Integer> entry:map.entrySet()) {
arr[k++] = entry.getKey();
}
其实还有使用迭代遍历map、使用keySet迭代遍历map、使用entrySet遍历map这几种方式，但是觉得使用比较麻烦，直接使用for循环比较方便。?
5.试题案例
统计10W个数据当中，每个数据出现的次数以及对应的关系。
public static void func3(int[] array) {
HashMap<Integer,Integer> map = new HashMap<>();
//1、遍历原来的数据，统计每个数据出现的次数
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);//key出现的 次数
map.put(key,val+1);
}
}
for (Map.Entry<Integer,Integer> entry: map.entrySet()) {
System.out.println("key: "+entry.getKey()+" 出现了："+entry.getValue()+"次！");
}
}三、Set的使用
Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key。
Set的官方文档：Set (Java Platform SE 8 )https://docs.oracle.com/javase/8/docs/api/java/util/Set.html1.关于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. 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则可以插入空的key
。
2.试题案例
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
public int singleNumber(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (!set.contains(nums[i])){
set.add(nums[i]);
}else {
set.remove(nums[i]);
}
}
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i])){
return nums[i];
}
}
return -1;
}