# Map接口
Map结构用于存储键值对，是一个接口，其常见的实现类有HashMap、Hashtable、TreeMap等。在该接口中定义的统一操作有：
1. 添加元素：
~~~
// 用于键值对的绑定，当键不存在是返回null，当键存在是返回旧值。
V put(K key, V value);
~~~
2. 判断
~~~
// 是否包含键
boolean containsKey(Object key);
// 是否包含值
boolean containsValue(Object value);
// 是否为空
boolean isEmpty();
// 判断两个map是否相同
boolean equals(Object o);
~~~
3. 获取元素
~~~
// 根据键获取value值，不存在则返回null
V get(Object key);
// 获取所有键
Set<K> keySet();
// 获取所有的值
Collection<V> values();
// 获取所有键值对
Set<Map.Entry<K,V>> entrySet();
// 大小
int size();
~~~
4. 移除元素
~~~
// 移除某个键
V remove(object key);
// 清空map的内容
void clear();
~~~
******
Map接口的实现类：
## HashMap
HashMap是JDK1.2版本之后开始增加的，在1.8版本之前其底层使用数组+链表的方式来作为哈希表的存储结构，在1.8版本及之后改成了数组+链表/红黑树的方式来作为哈希表的存储结构，当链表的长度大于8的时候会将链表转换成一颗红黑树。
在分析HashMap的源码之前，先来看看一个键值对放入一个Map中应该经过什么步骤？
:-: 
**源码分析**
1. 几个重要成员属性
~~~
// 初始容量，必须为2的幂次方，默认为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大的容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表的长度的阈值，大于该长度会转化成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 红色树收缩成链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 哈希表的桶大于64时才会转换成树结构
static final int MIN_TREEIFY_CAPACITY = 64;
//----------------字段-----------------------
// 底层数组结构
transient Node<K,V>[] table;
// 键值对集合，可以用于键值对的遍历
transient Set<Map.Entry<K,V>> entrySet;
// 键值对的数量
transient int size;
// 修改容器的次数
transient int modCount;
// 容量阈值
int threshold;
// 负载因子
final float loadFactor;
~~~
2. 构造方法
~~~
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 设置为默认的负载因子
}
// 设置初始化容量，在阿里的开发手册中要求在创建HashMap时要指定初始化容量的大小
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 设置初始化容量，并指定负载因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 这里会将初始化容量转化成第一个比其大的一个2的幂次方的数
this.threshold = tableSizeFor(initialCapacity);
// n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
// numberOfLeadingZeros可以获取前导0的数量。
}
~~~
3. 关键操作
* put添加元素方法
~~~
// 不存在映射则会关联值，存在则直接替换值
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 计算hash值，从这里可以看出HashMap的key可以为null，其hash值为0 --> 面试可能会问。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
hash – 密钥的散列
key——钥匙
value – 要放置的值
onlyIfAbsent – 如果为真，则不更改现有值
evict – 如果为 false，则表处于创建模式。
返回：以前的值，如果没有，则为 null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 桶中还没有元素，直接创建节点放入
tab[i] = newNode(hash, key, value, null);
else {
// 桶中已经有元素，此时有两种情况，一种是键相同，一种是发生哈希冲突
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 进一步判断key是否相等，或者是key重写equals方法后相等
e = p;
else if (p instanceof TreeNode)
// 树节点的添加操作
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 采用尾插法的方式插入节点
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
// 链表长度大于8的时候转化成树结构，但是在里面还会判断桶的数量是否大于64，如果没有的话则进行扩容操作
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // key相等会直接替换值并返回旧值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 给LinkedHashMap扩展用的
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
// 初始化容量或加倍表的大小 HashMap的底层数组table并不会在构造方法中创建，而是延迟到添加元素时创建
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 第一次添加元素进来resize时table为空
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新的阈值×2
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) {
newCap = oldThr;
} else {
// 第一次添加元素，且使用空构造方法没有指定阈值大小时进入这个分支
newCap = DEFAULT_INITIAL_CAPACITY; // 初始化容量为16
// 设置阈值大小
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 新建底层数组结构
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 对老结构中所有的元素都进行重新hash
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 如果当前桶只有一个Node节点，则不用起改变其在桶的位置
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // e的后续仍有节点，且e不是树节点
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // 索引为0的位置
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else { // 索引为非0的位置
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 把一整条链都挂到新的位置去
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
~~~
总结put操作的过程：
1. 第一次添加元素时会调用resize方法扩容。该方法对所有的元素进行rehash，对于索引为0的桶的元素不改变其位置，对于其他元素则将整条链挂到当前索引+老容量的索引（j + oldCap）位置上去。
2. 如果桶中没有元素则直接放入。
3. 如果桶中有元素了，有相同的键值替换值，没有相同的键则发生冲突，采用尾插法的方式进行插入。
4. 在插入节点之后如果链表的长度大于8且桶的数量大于64则会转成一棵树结构。
## TreeMap
底层是一个红黑树结构，能够保证数据根据key排序，注意key不能为空。其结构如下
~~~
Entry = (key、value、左子树地址、右子树地址、父节点地址、颜色)
~~~
~~~
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
// 使用boolean类型来表示红黑，BLACK和RED是一个常量
boolean color = BLACK;
// 新增的节点默认为黑色
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
~~~
源码：
~~~
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
// 比较器，TreeMap需要内部比较器或者外部比较器
private final Comparator<? super K> comparator;
// 红黑树的树根
private transient Entry<K,V> root;
// 红黑树节点数量
private transient int size = 0;
// 修改次数
private transient int modCount = 0;
// 构造方法，key需要实现Comparable接口来实现内部的比较
public TreeMap() {
comparator = null;
}
// 传入自定义外部比较器
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
// -------------常见操作-------------------------
// 添加元素
public V put(K key, V value) { // key和Value的类型在创建的时候就确定了
Entry<K,V> t = root;
if (t == null) {
// 比较两个元素，有外部比较器优先调用外部比较器，没有时调用内部比较器
compare(key, key);
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// 将外部比较器赋值给cpr，看构造函数
Comparator<? super K> cpr = comparator;
// cpr不等于null，意味着创建对象时调用有参构造器
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key); // 比较元素的key值
// cmp返回的就是int类型的数据
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else// cmp=0,即键相等，直接替换value的值，但是key不变，唯一的
return t.setValue(value);
} while (t != null);
}
// 创建对象的时候没有指定外部比较器，使用的是内部比较器
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 维护红黑树的性质
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
// 获取key对应的值
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// 由外部比较器则使用外部比较器比较获取值
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
}
~~~
总结：
1. TreeMap底层就是一颗红黑树结构。
2. 节点的key需要实现内部比较器或者有自定义的外部比较器，有自定义的外部比较器的时候先使用外部比较器。
3. 节点的key不管在put还是在get都不能为空。
## LinkedHashMap
LinkedHashMap继承HashMap，可以在HashMap的基础上实现顺序的访问，其底层使用了双向链表+HashMap来实现。由于新版本的HashMap会将链表转化成树结构，因此这里称为“Linked”有点混淆，但是官方仍然采用了这个命名方式。
同时使用头尾节点和回调函数来维护双向链表的结构。回调函数在操作：access、insertion、removal后触发。
更重要的一点是LinkedHashMap底层使用了LRU算法来维护节点的顺序。
源码：
~~~
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
/**
* 头节点、也是最久没有使用的节点
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 尾结点、也是最近使用的节点
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* true：按照访问顺序遍历、LRU算法
* false：按照插入顺序遍历
*/
final boolean accessOrder;
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
// 要使用LRU算法则需将accessOrder设置为true
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
/**---------------------常用操作----------------------------*/
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
// 如果是按照访问顺序只要调用回调函数
afterNodeAccess(e);
return e.value;
}
// 将当前最近一次访问的节点移动到链表尾部
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
// 当前访问的节点不再最后一个位置
LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e,
// b：当前访问节点的上一个节点，a：当前访问节点的下一个节点
b = p.before, a = p.after;
p.after = null;
if (b == null)
// p就是头结点
head = a;
else
// p节点要移除到最后一个位置的
b.after = a;
if (a != null)
// p不是最后一个元素
a.before = b;
else
last = b;
if (last == null)
// 第一次访问，
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
}
~~~
### 使用LinkedHashMap实现LRU缓存
```java
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
// 传递true会使用LRU算法
super(capacity, 0.75f, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
// 重写这个方法，实现超过容量时移除
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
// 节点数大于容量时需要移除
return size() > capacity;
}
}
```
## 总结
1. HashMap、TreeMap、LinkedHashMap底层都是由红黑树结构的存在。
2. TreeMap可以实现key有序，LinkedHashMap可以实现访问有序和LRU缓存。
- 第一章 Java基础
- ThreadLocal
- Java异常体系
- Java集合框架
- List接口及其实现类
- Queue接口及其实现类
- Set接口及其实现类
- Map接口及其实现类
- JDK1.8新特性
- Lambda表达式
- 常用函数式接口
- stream流
- 面试
- 第二章 Java虚拟机
- 第一节、运行时数据区
- 第二节、垃圾回收
- 第三节、类加载机制
- 第四节、类文件与字节码指令
- 第五节、语法糖
- 第六节、运行期优化
- 面试常见问题
- 第三章 并发编程
- 第一节、Java中的线程
- 第二节、Java中的锁
- 第三节、线程池
- 第四节、并发工具类
- AQS
- 第四章 网络编程
- WebSocket协议
- Netty
- Netty入门
- Netty-自定义协议
- 面试题
- IO
- 网络IO模型
- 第五章 操作系统
- IO
- 文件系统的相关概念
- Java几种文件读写方式性能对比
- Socket
- 内存管理
- 进程、线程、协程
- IO模型的演化过程
- 第六章 计算机网络
- 第七章 消息队列
- RabbitMQ
- 第八章 开发框架
- Spring
- Spring事务
- Spring MVC
- Spring Boot
- Mybatis
- Mybatis-Plus
- Shiro
- 第九章 数据库
- Mysql
- Mysql中的索引
- Mysql中的锁
- 面试常见问题
- Mysql中的日志
- InnoDB存储引擎
- 事务
- Redis
- redis的数据类型
- redis数据结构
- Redis主从复制
- 哨兵模式
- 面试题
- Spring Boot整合Lettuce+Redisson实现布隆过滤器
- 集群
- Redis网络IO模型
- 第十章 设计模式
- 设计模式-七大原则
- 设计模式-单例模式
- 设计模式-备忘录模式
- 设计模式-原型模式
- 设计模式-责任链模式
- 设计模式-过滤模式
- 设计模式-观察者模式
- 设计模式-工厂方法模式
- 设计模式-抽象工厂模式
- 设计模式-代理模式
- 第十一章 后端开发常用工具、库
- Docker
- Docker安装Mysql
- 第十二章 中间件
- ZooKeeper