本文主要介绍：
- 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的对象
如果各位觉得不错的话，欢迎点赞，评论，关注，转发，一波四连呀。还可以关注我的公众号“空亦语”。你的鼓励就是作者持续创作的动力。