本文主要介绍:
- map(字典)与set(集合)的概念
- 它们是如何被实现的,也就是实现原理
- 在java中他们在具体的实现过程
- 如何进行遍历,删除,以及具体的实现过程
- 介绍下java中常用的几个map与set的类,以及它们的异同
读完这篇文章,你肯定会对map与set了如指掌。下面我们先从介绍概念开始吧。
1. 简单介绍
1.1 什么是map
俗称的字典。就是将一个唯一标识的对象与另外一个对象关联起来的一个结构。
- 这个唯一标识对象称为key,被关联的对象称为value。
- key到value的映射关系为n对1.比方说身份证关联到一个具体的人,身份证就是key,而人就是value。一个身份证可以唯一确定到一个人,而一个人可不可以有多个身份证号?完全可以。
map有什么作用
当你查字典的时候,你不是一页一页去翻找到那个字位置,而是根据拼音或者部首跳到指定页面。而map就类似这个,在一个列表中,当你给出要查询的对象时,他就能根据你这个对象计算出这个对象可能放在的位置。也就是说,用key值 a 映射拼音a开头第一个字的页码即value,用key值b映射拼音b开头的第一个字的页码,以此类推。
1.2 什么是set
即为集合。存储对象的集合,重复的数据只存一份,区别于上一期讲的列表(list)。例如如果有 a,b,c,e,a,b,c,d。这样的列表,转换为set就变成了a,b,c,d,e。
2. 实现原理
前面在list的篇章中提到,计算机底层只有数组与链表。因此map也是基于这两个之上来实现的。
这里我们先以HashMap为例,介绍其是如何使用数组来完成实现映射的过程的。
2.1 添加元素过程
添加元素的过程有以下步骤:
- 首先先初始化一个数组我们记为table,这个数组的长度记为size
- 先将key通过哈希函数做hash处理,将其变成一个数值记为keyHash
- 将数值keyHash对size取模,得到对应的下标值index
- 为了优化取模这个计算,将table的长度设计成了2的n次幂
- 因为计算机是二进制,因此在取模时,可以直接做keyHash与2^n-1的位与运算,即可得到index
- 因为与2^n-1做位与 其实就是取2进制的后(n-1)值,即为其取模后的值,这个运算远比除法高效快速。
- 然后用一个entry对象来保存key,value值
- 将这个entry放入table对应index下标中
那么问题来了,如果有两个key对应的index值一样,要怎么处理?那么只要在entry中加入一个指针,指向下一个entry的地址即可。
举个例子:
我们有这样的键值对:1-》4,2-》7,3-》2,5-》11,6-》10。我们用一个简单的哈希函数index=key%4。此时我们新建一个长度为4的table,那么就会有:
此时可以看到table中的每个对象都是一个链表的结构。当冲突的时候就通过拉链表的方式来解决。因此上面步骤的第五步将变为:
- 遍历index下标中的链表,如果链表中不包含此元素,就将它添加到链表尾部
2.2 根据key获取元素的过程
map的内部根据key获取到存入的数据过程如下:
- 先将key做hash处理,将其变成一个数值记为keyHash
- 将数值keyHash对size取模,得到对应的下标值index
- 然后去table指定index中,遍历链表元素,判断是否当前的key,如果是则获取返回,如果到链尾依然没有,则返回null即可
2.3 hashMap元素不断增加时的优化
当hashMap存储的元素不断增加时,其中元素冲突情况就越多。如果对应index的链表太长,那么也就大大降低了获取的性能。
为了优化这种情况则有两种做法:
- 为table进行扩容,新建一个更大的list称为newEntryList,然后将所有元素添加进这个newEntryList中,然后放入map替代原来的table。
- 每次扩容都会保持为2的n次幂的策略
- 当元素大于table的size的一定比例时(默认是0.75*size的个数),就会触发扩容的操作。
- 将链表结构更改为红黑树,将原本O(n)复杂度的查找变为了O(log(n))。
- 默认当链长大于等于8时会触发转换成红黑树的操作
扩容策略使得map的key冲突的概率降低。红黑树使得冲突的key的查找速率更快。
2.4. 遍历
2.4.1 entrySet()方法与keySet()方法
这两个方法返回的对象本身不包含数据。但返回对象都是Map的内部类对象,它覆盖了遍历,contain等一些跟访问、删除相关的方法,使得每次对返回对象的访问其实就是对Map的访问。返回对象覆盖的方法有:
- size() 返回Map的size
- clear() 清空Map的数据
- iterator 返回Map的iterator
- contains 调用Map的contains
- remove 调用map的remove
- foreach() 遍历父类中的table。逐个遍历table对应index的链表
2.4.2 遍历的方式
因此遍历的方式主要有:
1. 迭代器遍历entry
- 迭代器遍历keyset
- for-each 对entry循环遍历,本质上是使用iterator实现的
- for-each 对key循环遍历
- labmda foreach遍历,会先获取spliterator()方法返回Spliterator对象,然后调用forEachRemaining方法
- stream foreach 遍历
//1. 迭代器遍历entry
it=map.entrySet().iterator();
while(it.hasNext()){
entry=it.next();
}
//2. 迭代器遍历keyset
it=map.keySet().iterator();
while(it.hasNext()){
key=it.next();
}
//3. foreach entry遍历
for(entry:map.entrySet()){
}
//4. foreach key遍历
for(key:map.keySet()){
}
//5.lambda foreach遍历
map.foreach((key,value)->{});
//6. stream api单线程
map.entrySet().stream().foreach((entry)->{});
//7. stream api多线程
map.entrySet().parallelStream().foreach((entry)->{});
2.5 删除
map的remove删除步骤:
- 与获取元素类似,先找到对应的元素
- 如果找到了,则执行链表的删除过程
//可正确删除,依赖于iterator的remove方法
map.keySet().removeIf(key->{})
//使用filter删除,只有filter函数中的运行结果返回true,才会被accept进stream中
map.entrySet().stream().filter(entry->{entry.key()>0}).foreach();
//remove删除
for(Object key:arrayList){
map.remove(key);
}
2.6 Map的总结
常见的有HashMap,LinkHashMap。与并发相关的有HashTable,ConcurrentHashMap。
- linkHashMap是在HashMap的基础上维护了一个元素添加顺序的链表,为了能够在遍历的时候能够按添加顺序遍历出来而已。
- hashTable与HashMap类似,只是在新增、删除、更改等修改操作的方法上增加了对象锁,保证线程安全性
- ConcurrentHashMap改进了hashTable将整个对象锁定的问题,他每次只锁定table的某个index。
- 好处:允许不同index的元素同时进行修改,而不会出现问题。
3. set
Set是基于Map来实现的,常见的set与Map相对应的有HashSet,LinkHashSet。
- 每次新增的元素都作为Map的key,value中放入一个统一的空的Object对象。也就是说每次对set.add(item)其实就是做map.put(item,object)处理。
- 每次删除也是基于map的删除,也就是说set.remove调用的就是map.remove。
4. 总结
通过上面的内容,我们对重点部分进行总结:
- map通过使用hash将key映射到list的对应下标来存储数据,通过链表的方式来解决冲突的问题
- map的元素个数总为2的n次幂,这是为了简化计算映射到数组下标的过程
- 当元素超过一定数量时,就会进行扩容,如果table的某个index冲突数大于等于8,会被转换为红黑树,来提高搜索速度
- set通过Map来实现,将set的数据作为Map的key,将一个统一的Object空对象作为Map的value值
- LinkedHashMap只比HashMap多维护了一个元素添加进来的顺序链表,使得遍历的时候可以按照元素添加顺序输出
- HashMap的遍历是对内部的table进行从前到后的遍历,对每个table的元素进行链表的遍历方式
- hashTable的更改会锁定整个对象,而concurrentHashMap的更改只锁定对应index的对象
如果各位觉得不错的话,欢迎点赞,评论,关注,转发,一波四连呀。还可以关注我的公众号“空亦语”。你的鼓励就是作者持续创作的动力。