- (一)Map子父层级：
- (二)Map实现类
- 1、TreeMap实现类
- 2、常见必会源码
- （1）构造方法
- （2）put方法
- （3）get方法
- （4）remove方法
- 3、总结
map接口常用实现类分为：HashMap、linkedHashMap、HashTable、TreeMap、Properties;
（1）TreeMap的主要核心成员变量有Entry类型的root、Comparator类型的comparator、size和modCount等; （2）TreeMap底层为Entry类型的红黑树,其Entry成员为key、value、left、right、parent、color(默认BLACK是true); （3）TreeMap是支持两种排序，一种是默认的自然排序，另外一种自定义排序为键key实现comparable或者通过构造器传入对比器Comparator; （4）TreeMap是线程不安全的，在多线程环境下，会报并发修改异常java.util.ConcurrentModificationException。2、常见必会源码 （1）构造方法
//无参构造，默认排序器为null即使用默认自然排序
//定制排序，键key实现comparable接口或者传入比较器Comparator
public TreeMap() {
comparator = null;
}
//含参构造器，定制排序，使用comparator比较器
public TreeMap(Comparator comparator) {
this.comparator = comparator;
}
//含参构造器,基于普通Map对象进行构建TreeMap,默认自然排序
public TreeMap(Map m) {
comparator = null;
putAll(m);//将普通Map进行构建TreeMap
}
//将普通Map映射到TreeMap中
public void putAll(Map map) {
int mapSize = map.size();
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator c = ((SortedMap)map).comparator();
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {
buildFromSorted(mapSize, map.entrySet().iterator(),null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
super.putAll(map);//调用父类AbstractMap中的方法，TreeMap重写其putAll中的put方法进行构建
}
//含参构造器,基于SortMap接口进行构建TreeMap
public TreeMap(SortedMap m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
（2）put方法
public V put(K key, V value) {
Entry t = root;//获取成员变量root，用于根节点设置
if (t == null) {
compare(key, key);
root = new Entry<>(key, value, null);//设置根节点
size = 1;//容量设置为1
modCount++;//操作次数自增
return null;//终止操作，并返回null
}
int cmp;//用于比较后的结果，1前者大 0一样大 -1后者大
Entry parent;
// split comparator and comparable paths
Comparator cpr = comparator;//内部比较器成员
if (cpr != null) {//定制排序
do {
parent = t;
cmp = cpr.compare(key, t.key);//利用定制排序的compare方法从根节点出发进行对比key
if (cmp < 0)//是否比根节点小
t = t.left;//递推左子树
else if (cmp > 0)//是否比根节点大
t = t.right;//递推右子树
else
return t.setValue(value);//一样大，则直接替换旧值
} while (t != null);//直到遍历到底进行退出循环
}else {//此逻辑为默认排序
if (key == null)//键不能为空，否则报错
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable k = (Comparable) key;//强制转为key为Comparable
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 e = new Entry<>(key, value, parent);//创建新Entry
if (cmp < 0)
parent.left = e;//将新Entry设置为左边
else
parent.right = e;//将新的Entry设置为右边
fixAfterInsertion(e);//新节点e添加到红黑树中，先将其变为red，然后是否需要通过左旋和右旋进行调整树结构
size++;//容量自增
modCount++;//操作次数
return null;
}
（3）get方法
public V get(Object key) {
Entry p = getEntry(key);//根据key获取Entry节点
return (p==null ? null : p.value);//返回结果
}
//根据key查找红黑树并返回结果
final Entry getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);//基于比较器Comparator对比查找
if (key == null)//空key校验
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable k = (Comparable) key;//默认排序查找
Entry 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;//找不到即返回null
}
（4）remove方法
public V remove(Object key) {
Entry p = getEntry(key);//根据key查找Entry节点
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);//删除该Entry节点并调整树结构
return oldValue;//返回删除值
}
//删除指定节点并调整
private void deleteEntry(Entry p) {
modCount++;
size--;
//删除原理：将后继节点的值赋值给当前节点，然后删除节点指向后继节点,此处的后继节点为最左子树
if (p.left != null && p.right != null) {//p节点存在左右子树
Entry s = successor(p);//返回p节点的后继节点即左节点
p.key = s.key;//改变删除节点的key
p.value = s.value;//改变删除节点的value
p = s;//将删除节点重新定向为后继节点
}
// 修复被移除节点的树结构(可能为上述被重定向的，也可能未满足两个孩子节点逻辑)
Entry replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {//对其子树进行操作
replacement.parent = p.parent;//将原子节点的父节点指向删除节点的父节点
if (p.parent == null)//删除节点是否为根节点
root = replacement;//将子节点设置为根节点
else if (p == p.parent.left)//是否为左节点
p.parent.left = replacement;//将原父节点下属左节点连接
else
p.parent.right = replacement;//将原父节点下属右节点连接
p.left = p.right = p.parent = null;//便于GC
//删除节点是否是黑色节点
if (p.color == BLACK)
fixAfterDeletion(replacement);//调整树结构
} else if (p.parent == null) { // return if we are the only node.
root = null;//删除的节点为根节点
} else { //无孩子节点
if (p.color == BLACK)//删除节点为黑色
fixAfterDeletion(p);//调整树结构
if (p.parent != null) {//在树中将删除节点移除
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
3、总结
（1）TreeMap底层为Entry类型的红黑树,存储原理为根据key来进行compare或compareTo进行对比，存入红黑树中; （2）TreeMap是支持两种排序，一种是默认的自然排序，另外一种为键key实现comparable或者通过构造器传入对比器Comparator; （3）TreeMap是线程不安全的，在多线程环境下，会报并发修改异常java.util.ConcurrentModificationException。
