每个平凡人心中都有一个不平凡的世界,让Map和Set带你跨过山和大海,也穿过人山人海
HashMap和HashSet数据类型 增删改查 的时间复杂度都是 O(1)
Map
概述
- Map是一个接口,如果要实例化一个对象,只能实例化其实现类HashMap或TreeMap
- 由图可知,Map接口没有继承Iterable接口,所以Map实例的对象不能使用迭代器来打印(Map中也没有iterator()方法)
- Map属于Key-Value类型 key值是唯一的,不能重复,但是value 是可重复的
常用方法
HashMap常用方法 | 解释 |
---|---|
V get(Object key) | 返回value对应的key;key不存在,返回null |
V getOrDefault(Object key , V defaultValue) | 返回value对应的key;key不存在,返回defaultValue |
V put(K key, V value) | 设置key-value;如果原来有相同的key,value更新;key和value都可以是null |
V remove(Object key) | 删除key-value;key存在,返回value;key不存在,返回null |
Collection< V > values() | 返回value的不重复集合 |
Set< K > keySet() | 返回所有key值的Set集合 |
Set< Map.Entry< K , V> > entrySet() | 返回所有key-value(集合中key-value是一个整体,类型是Map.Entry )的Set集合 |
Boolean containsKey(Object key) | 判断是否包含key |
Boolean containsValue(Object value) | 判断是否包含value |
Map.Entry< K,V >的方法 | |
---|---|
K getKey() | 返回 entry中的key |
V getValue() | 返回entry中的value |
V setValue(V value) | 替换value |
底层结构
Map的底层结构 | HashMap | TreeMap |
---|---|---|
增删改查时间复杂度 | 通过哈希函数计算得到哈希地址 O(1) | 需要进行元素(key)的比较 O(log2N) |
底层结构 | 哈希表(数组+链表+红黑树) | 红黑树 |
元素是否有序 | 无序 | 关于key有序(通过key的大小比较) |
比较和重写 | 自定义类型要重写equals和hashcode方法 | key要能够进行比较,否则会抛出异常(如:put(null , value) 或 remove(null)…) |
应用场景 | 对时间复杂度要求高 | key需要有序 |
因为TreeMap是按照key进行组织的,所以查找key的时间复杂度为O(log2N),但是如果单纯的查找value的话,需要遍历所有元素,时间复杂度O(N)
观察有序性
Map<Integer,String> treeMap = new TreeMap<>();
treeMap.put(1,"孙少安");
treeMap.put(12,"孙少平");
treeMap.put(6,"孙兰花");
treeMap.put(52,"贺秀莲");
System.out.println(treeMap);
Map<Integer,String> hashMap = new HashMap<>();
hashMap.put(1,"孙少安");
hashMap.put(12,"孙少平");
hashMap.put(6,"孙兰花");
hashMap.put(52,"贺秀莲");
System.out.println(hashMap);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
应用
Map主要用于求数据的频率(出现次数)
某数组中有100,000个数据,求每个数据出现的次数
public static Map<Integer,Integer> findTimes(int[] array){
Map<Integer,Integer> map = new HashMap();
for (int count : array) {
if(map.get(count) == null){
map.put(count,1);
}else{
int value = map.get(count);
map.put(count,value+1);
}
//map.put(count,map.getOrDefault(count,0)+1);
}
return map;
// 重复的数据出现的此数
// for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
// if(entry.getValue() > 1){
// System.out.println("数据" + entry.getKey() + "出现的次数" + entry.getValue());
// }
// }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
public static void main(String[] args) {
int[] array = new int[100000];
Random random = new Random();
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(1000);
}
System.out.println(findTimes(array));
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
Set
概述
- Set是key类型,Set中的key值要求唯一
- Set是个接口,实例化一个对象要用HashSet或TreeSet类进行实例化
- Set继承了Collection类,能通过Iterator打印Set中的元素
Set<Integer> set = new HashSet<>();
Iterator iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
- 1
- 2
- 3
- 4
- 5
常用方法
HashSet常用方法 | 解释 |
---|---|
boolean add(E e) | 插入,但是重复元素不会插入成功 |
boolean contains(Object e) | 判断是否在集合中 |
boolean remove(Object e) | 删除元素 |
Object[ ] toArray() | set中的元素转为数组返回 |
boolean addAll(Collection<? extend E> c ) | 集合c中的元素添加到set中 |
boolean containsAll(Collection<? extend E> c) | 判断集合c中的元素是否在set中 |
void clear() | 清空set中的元素 |
底层结构
Set的底层结构 | HashSet | TreeSet |
---|---|---|
增删改查时间复杂度 | 通过哈希函数计算得到哈希地址 O(1) | 需要进行元素(key)的比较 O(log2N) |
底层结构 | 哈希表(数组+链表+红黑树) | 红黑树 |
元素是否有序 | 无序 | 有序 |
比较和重写 | 自定义类型要重写equals和hashCode方法 | key要能够进行比较,否则会抛出异常(如:add(null)或 remove(null)…) |
应用场景 | 对时间复杂度要求高 | key需要有序 |
作用
Set常用于去重
哈希表
顺序结构及平衡树中,关键码和存储位置之间没有对应的关系,查找一个元素时,要经过一系列的比较;顺序查找时间复杂度为O(N),平衡二叉树中为O(log2N)
能否不经过比较,一次性的从表中得到想要的元素?
建立一种结构,通过哈希函数将元素的存储位置与元素(关键码)之间建立一一对应的映射关系[ 存储位置=F(元素) ],查找的时间复杂度为O(1),这种结构就叫做哈希表
哈希冲突
不同的关键码通过相同的哈希函数计算出相同的哈希地址,叫做哈希冲突或哈希碰撞
哈希冲突是必然存在的,不能从根本上解决
如上图:14%%10 =4 24%%10=4 34%%10=4
避免哈希冲突
- 设计合适的哈希函数
哈希函数的定义域包括需要存储的所有关键码,值域是0~m-1(哈希表有m个地址)
直接定制法:线性函数 Hash(key) = A*key+B
除数残留法:Hash(key) = key%%p(p<=m)
2.调节负载因子
哈希表的负载因子 = 填入的元素个数 / 哈希表的长度
0~1范围内,负载因子越大,冲突率越高
由于填入的关键码个数无法更改,通过调整哈希表中数组的大小来实现对负载因子的调节
解决哈希冲突
- 闭散列
(1)线性探索
从冲突位置开始,依次向后探测,直到找到下一个空位置为止,遍历完哈希表后,再从头开始
缺点:冲突的元素会挤在一起的,而且不能随便物理删除哈希表中已有的元素
(2)二次探索
二次探索在线性探索的基础上修改了 找下一个空位置的方法
Hi = (H0 + i^2 )%%m
Hi = (H0 - i^2 )%%m
H0是计算的得到的哈希地址
Hi 是插入的哈希地址 - 开散列(哈希桶)
具有相同哈希地址的关键码通过一个单链表连接起来,各链表的头节点存储在哈希表中(哈希数组中是一个单链表头节点的引用)
当数组长度超过64并且链表长度超过8,链表变成红黑树
jdk1.8采用尾插法,jdk1.7以前采用头插法
负载因子在,链表不会很长,找数据遍历单链表
有没有打NBA2k的老铁?加个好友切磋切磋哦
推荐阅读