学习内容：

1. Map集合概述
2. 红黑树
3. Map集合的实现TreeMap
4. Map集合实现HashMap

学习产出：

1，Map集合概述

Map属于JCF的范围，但是Map的顶级接口java.util.Map并没有继承Collection。Map集合属于映射式结构，key-value，一个集合中不能出现两个系统的key。

（1.1）K-V键值对定义-Entry

Map中存储的是K-V键值对节点，也就是说一个Map集合可以有成千上万个Map.Entry<K,V>接口的实例化对象。Map.Entry接口的部分源码如下

interface Entry<K, V> {//获取key值信息K getKey();//获取value值信息V getValue();V setValue(V value);//比较两个K-v键值对是否相同boolean equals(Object o);//计算当前的节点的 hash值int hashCode();

Map中存储的键值对。都按照一定的规律存储，这个存储规则由实现Map接口的具体集合进行管理。
其实实现了Map接口的类，会根据自己的结构特点实现Map.Entry接口的方法，例如TreeMap如下

//TreeMap内部所有键值对构成一颗红黑树，也就是说entry对象需要记录当前节点的父节点，儿子节点以及当前树节点的颜色
//用于描述红黑数中的一个k-v键值对节点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 color = BLACK;//在实例化时为这个键值对指定父级的EntryEntry(K key, V value, Entry<K,V> parent) {this.key = key;this.value = value;this.parent = parent;}

（1.2）与Map集合的重要接口和抽象类

几个重要的接口和抽象类java.util.Map接口,java.utilSortedMap接口，Java.utilNavigableMap接口和AbstractMap抽象类
1，java.util.Map接口：是Map集合中的顶层接口，给出了Map体系的基本操作功能，有如下
put，clear，get，size，isEmpty等（太多啦，idea快捷键alt+7查看）

2，java.util.SortedMap接口
Map集合中对键值对的读写方法，在存储和读取时，不一定能够保证key的顺序。但是在实际业务场景中，需要存储在Map集合的的节点按照一定的规则存储，这时我们可能需要使用实现了SortedMap的Map集合，这里的规则不一定是顺序的，例如利用红黑树结构存储
SortedMap提供了很多与有序存储相关的方法

//获取当前集合的比较器
Comparator<? super K> comparator();
//由于是有序的，可以获取从一个key到另一个key直接的SortedMap集合
SortedMap<K,V> subMap(K fromKey, K toKey);
//返回一个小于指定key值的集合SortedMap<K,V> headMap(K toKey);
//返回一个大于指定key值的集合
SortedMap<K,V> tailMap(K fromKey);
//返回权值最小的key信息
K firstKey();
//权值最大的key信息
K lastKey();

3，java.util.NavigableMap
SortedMap接口为有序的键值接触存储定义了基本的操作，那么该接口精确定义了返回上一个键值对，下一个键值对等一系列操作

//以下两个方法会返回一个键值对节点或者key信息，这个被返回信息满足以下条件：属于一个集合A，A集合是原集合的子集，他代表的键值对或者是key信息在A中的权值是最大的，如果原集合中没有入参key代表的键值对节点则返回nullMap.Entry<K,V> lowerEntry(K key);K lowerKey(K key);//最小的Map.Entry<K,V> higherEntry(K key);K higherKey(K key);//以下两个方法会返回一个键值对节点或者key信息，这个被返回信息满足以下条件：属于一个集合A，A集合是原集合的子集，他代表的键值对或者是key信息在A中的权值是最大的。如果不存在这样的集合A，则返回入参key代表的键值对或者key键信息。如果原集合中没有入参key代表的键值对节点则返回nullMap.Entry<K,V> floorEntry(K key);K floorKey(K key);//最小的Map.Entry<K,V> ceilingEntry(K key);K ceilingKey(K key);

3，java.util.AbstractMap
是实现了Map接口的一个抽象类，用于向下次具体的Map集合添加一下默认功能逻辑，减少具体Map集合的构建源码量，从而降低实现Map集合的的难度。
AbstractMap抽象类中已实现的默认逻辑实际上不能独立运行，因为逻辑中的重要过程都是缺失的，例如对size()方法的实现，源码如下

public int size() {return entrySet().size();}//使用了entrySet()方法，当AbstractMap中并没有对entrySet()方法实现//HashMap中的entrySet()方法实现如下public Set<Map.Entry<K,V>> entrySet() {Set<Map.Entry<K,V>> es;return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;}

//就像前面介绍的，抽象类的作用是减少实现具体Map集合时的编码工作量。除此之外，还给不同性质的Map提供了编码建议，如果需要一个不能新增键值对的集合，那么秩序实现entrySet()方法，无需实现put()和remove()方法，并且默认方法会抛出异常public V put(K key, V value) {throw new UnsupportedOperationException();}

AbstractMap抽象类中的SimpleEntry类
提供了一个Map.Entry接口的默认实现，源码如下

public static class SimpleEntry<K,V>implements Entry<K,V>, java.io.Serializable{@java.io.Serialprivate static final long serialVersionUID = -8499721149061103585L;@SuppressWarnings("serial") // Conditionally serializableprivate final K key;@SuppressWarnings("serial") // Conditionally serializableprivate V value;public SimpleEntry(K key, V value) {this.key   = key;this.value = value;}public SimpleEntry(Entry<? extends K, ? extends V> entry) {this.key   = entry.getKey();this.value = entry.getValue();}public K getKey() {return key;}public V getValue() {return value;}public V setValue(V value) {V oldValue = this.value;this.value = value;return oldValue;}public boolean equals(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry<?,?> e = (Map.Entry<?,?>)o;return eq(key, e.getKey()) && eq(value, e.getValue());}public int hashCode() {return (key   == null ? 0 :   key.hashCode()) ^(value == null ? 0 : value.hashCode());}public String toString() {return key + "=" + value;}}

红黑树

从1.8开始，几个重要的Map集合（TreeMap,HashMap,LinkedMap）在构造思路上没有进行大调整，即TreeMap是基于红黑树构造的，另外两个是数组+链表+红黑树的复合机构。因此需要先学习红黑树
红黑树是一种自平衡二叉查找树，由于其稳定性，因此多个具体的集合都是基于红黑树。

1，二叉查找数

特点如下

• 他是一颗二叉树
• 如果存在左子树，那么左子树的任意节点权值小于当前节点
• 如果存在右子树，那么右子树的任意节点权值大于当前节点
• 没有权值相等的节点

2，为什么需要红黑树

二叉树具有良好的查找性能，不是极端的情况下，查找操作的时间复杂度可以控制为O(logn)，但是极端情况下（右倾），其时间复杂度为O(n)。为了避免这种极端情况，需要找到一种方式，使二叉查找树，能够引入类似平衡二叉树的约束，并且无论怎样对二叉查找树进行写操作，都可以自行调整这个平衡结构—这就是红黑树。
注意：红黑树并不是平衡二叉树，二者的最大区别是红黑树放弃了绝对的子树平衡，转而追求一种大致平衡，这保证了与平衡二叉树的时间复杂度差不多的情况下，在红黑树中新增的节点最多进行三次选择操作，就能重写满足红黑树的结构要求。

3，红黑树的基本结构

为了简化红黑树的处理逻辑，引入外部节点的概念。注意外部节点只是一种记号，并不真正存储数据，也不是红黑树中的实际节点。方便程序员在设计和编程的时候理解节点的操作理则，在实际应用中没有实际意义，红黑树除了外部节点，还具有以下特性。

• 包括外部节点在内的所有节点都带有颜色（黑色红色）
• 根节点一定是黑色的
• 如果某个节点没有左子树或者右子树，会使用外部节点进行补齐，外部节点一定是黑色的
• 每个红节点的儿子节点必须是黑色的，但黑节点的儿子既可以是红色也可以是黑色‘红不相邻’
• 在任意节点到其所属子树的任意外部节点的路径上，标记为黑色节点的数目相同-这个规则理解为‘黑平衡’
• 在添加节点时，默认添加的节点是红色的，如果是根节点，则涉及改色操作

红黑树的操作规则

当某些操作让红黑树不再满足红黑树的结构要求市，可以自行修正当前树结构，使自己重写满足红黑树的结构要求
修正操作有三种，改色操作，节点左旋操作，节点有旋操作
1，改色操作，可以在‘红不相邻’特性收到影响时进行，当左右子树平衡发生改变时，也需要进行改色操作
2，红黑树的节点左旋操作：当前节点P，左儿子LP，右儿子RP。P左旋到LP位置，则RP到原P的位置，成为P的父节点（建议百度图解）
3，右旋，类似

红黑树的添加操作

添加操作包括两个步骤
1，根据权值将新的节点添加到红黑树的正确位置，类似于二叉查找树的添加
2，从新添加的节点开始，重新递归调整红黑树的平衡性，这是因为添加破坏了平衡结构
具体过程百度学习

Map集合的实现TreeMap

TreeMap是一种基于红黑树构建的键值对集合与HashMap中基于红黑树的部分逻辑相似（HashMap集合内部是复合结构，数组+链表+红黑树），但也有区别，没有HashMap集合中的桶概念，也没有数组概念。

基本使用方法

其集合内的所有节点都是这个这颗红黑树上的节点，这些键值对的排列顺序基于两种逻辑考虑：第一种是基于key信息的Hash值，第二种是基于使用者设置的Compatator接口实现的比较结果。选择哪种基于实例化时使用的哪个构造方法。
拥有较低的时间复杂度，在进行节点查询，添加，删除操作的时候，平均时间复杂度控制在O（logn）。
TreeMap不是线程安全的集合，并且在JCF原生的线程安全集合中没有与他机构类型的集合可以选择。使用者需要在线程安全的情况下使用TreeMap集合，可以采用下面的方式将一个线程不安全的集合封装为一个线程安全的集合（同样适用于其他集合）

 TreeMap<String,Object> treeMap=new TreeMap<>();//封装成线程安全的集合
Map<String, Object> cMap = Collections.synchronizedMap(treeMap);

重要属性和构造方法

几个重要的属性和如下

public class TreeMap<K,V>extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{//这个比较器对象记录了红黑树中各节点排列顺序的判断逻辑，如果为空会基于key的hash值进行判断private final Comparator<? super K> comparator;//根节点private transient Entry<K,V> root;//键值对节点数量private transient int size = 0;//执行写操作的次数private transient int modCount = 0;}

四个构造方法，进行的是同一个工作，根据入参情况决定comparator变量的赋值情况

//默认构造方法
public TreeMap() {comparator = null;}//设置一个比较器对象
public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;}
//将一个特定的map集合所有的键值对复制到新的TreeMap集合中
//源集合没有实现SortedMap接口，所以comparator为空
public TreeMap(Map<? extends K, ? extends V> m) {comparator = null;putAll(m);}
//实现了SortedMap接口所以将原集合的comparator赋值给当前集合
public TreeMap(SortedMap<K, ? extends V> m) {comparator = m.comparator();try {buildFromSorted(m.size(), m.entrySet().iterator(), null, null);} catch (java.io.IOException | ClassNotFoundException cannotHappen) {}}

TreeMap中buildFromSorted可以基于一个有序集合的迭代器构建一颗红黑树。

TreeMap集合的批量节点添加操作

public void putAll(Map<? extends K, ? extends V> map) {int mapSize = map.size();//当前的集合键值对的数量为0，传进来的不为0，并且实现了SortedMap接口if (size==0 && mapSize!=0 && map instanceof SortedMap) {//取得 传入对象的比较器，//如果和当前是同一个则，使用buildFromSorted创建if (Objects.equals(comparator, ((SortedMap<?,?>)map).comparator())) {++modCount;try {buildFromSorted(mapSize, map.entrySet().iterator(),null, null);} catch (java.io.IOException | ClassNotFoundException cannotHappen) {}return;}}//两个条件不成立，则对批量节点进行逐一操作super.putAll(map);}

TreeMap的添加删除节点操作

涉及到红黑树的场景，复杂，暂不学习

Map集合实现HashMap

HashMap集合指利用Hash算法来构造Map集合，具体来说，利用键值对key键对象的某个属性（默认是内存起始位置值）作为依据进行计算，然后根据计算结果将键值对添加到某个位置上。
hashCode方法是计算hash值的关键，有以下默认原则

• 对于同一个对象，无论他的hashCode方法被调用多少次，返回的结果相同
• 使用对象的equals(Object)方法比较，得到两个对象相等的结果，那么调用hashCode方法也会得到相同的返回值
• hashCode得到不同返回值，equals会得到不相等的结果，但是hashCode相等，equals不一定相等
• 程序员可以根据使用场景重写hashCode方法，但是基于以上原则还需重写equals方法

HashMap的结构

基础结构是一个数组，这个数组的最小长度是16，并且可以以3的幂次进行数组扩容操作
数组索引位置上可能存储键值对节点，也有可能没有存储任何对象，如果存储的节点是HashMap.Node类的对象，那么会以这个节点开始构建一个单向链表，如果是HashMap.TreeNode对象，那么会以这个节点为根节点构建一棵红黑树。

在某个索引位置上的链表长度达到指定的阈值（默认为超过8），链表会转换为红黑树，当红黑树的节点数量小于6时，会转换为单向链表。

HashMap的主要工作过程

HashMap中的一些关键常量和变量如下

    //默认数组的初始化容量为16，这个容量只能为2的指数倍扩张static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//数组最大容量static final int MAXIMUM_CAPACITY = 1 << 30;//默认负载因子为0.75static final float DEFAULT_LOAD_FACTOR = 0.75f;//如果一个单向链表的节点数量大于该值，则需要将他转换成红黑树static final int TREEIFY_THRESHOLD = 8;//如果小于该值，则从红黑树转成链表static final int UNTREEIFY_THRESHOLD = 6;//针对键值对过多时，是进行树化操作还是扩容操作呢？//只有集合中节点数大于该值，并且某个某个链表的节点数大于TREEIFY_THRESHOLD 该链表才会进行树化。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;//下一次扩容操作的门槛，等于当前集合容量值*loadFactorint threshold;//设置的负载因子，默认为DEFAULT_LOAD_FACTOR final float loadFactor;

LinkedHashMap

看名字猜出来是将hashMap的数组结构改成了链表