基于红黑树（Red-Black tree）的 NavigableMap 实现；键的排序由构造方法决定：自然排序，Comparator排序；非线程安全（仅改变与现有键关联的值不是结构上的修改）；线程安全的最好方法是在创建的时候包装成线程安全的
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
迭代器与LinkedList相似。
构造器，基本属性：
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{ //比较器，如果是null就是自然顺序
private final Comparator<? super K> comparator; //根Entry
private transient Entry<K,V> root; //Entry个数
private transient int size = 0; //结构性修改次数
private transient int modCount = 0; //构造一个空的tree map，使用键的自然顺序，键必须是实现了Comparable，
public TreeMap() {
comparator = null;
} //构造一个空的tree map，键按给定的比较器排序，
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
} //构造一个与给定映射具有相同映射关系的新的tree map，该映射根据其键的自然顺序进行排序
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
} //构造一个与给定映射具有相同映射关系的新的tree map，该映射根据其m的键的比较器进行排序
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
。。。。。。
}
void putAll(Map<? extends K, ? extends V> map)； V put(K key, V value)； void fixAfterInsertion(Entry<K,V> x)
关于红黑树的详解可以参考这篇博文： https://www.cnblogs.com/CarpenterLee/p/5503882.html
有些概念的东西可以参考这篇博文： https://blog.csdn.net/sun_tttt/article/details/65445754
例如红黑树的删除，先寻找该结点的后继结点，然后互换值，但不互换颜色，最后再调整！
//将指定映射中的所有映射关系复制到此映射中。这些映射关系将替换此映射所有当前为指定映射的所有键所包含的映射关系。
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
if (size==0 && mapSize!=0 && map instanceof SortedMap) {//map是键有排序的map
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抽象map的方法
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
} //将key和value存放在map里，如果map里有相同的key，旧的value被替换
public V put(K key, V value) {
Entry<K,V> t = root;//根节点
if (t == null) {//如果根节点没有值，就把当前值作为根节点
compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {//比较器不是空
do {
parent = t;
cmp = cpr.compare(key, t.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<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);//key与key的父的key比较
if (cmp < 0)//如果小于，节点在t的左侧
t = t.left;//将t置为t的左侧节点
else if (cmp > 0)
t = t.right;
else //如果相等，新value替换旧value
return t.setValue(value);
} while (t != null);//t节点不是空
}
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;
} final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
} //红黑树插入新结点后调整
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED; while (x != null && x != root && x.parent.color == RED) {//x的父的颜色是红色
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//x的父==x的父的父的左侧
Entry<K,V> y = rightOf(parentOf(parentOf(x)));//y=x的父的父的右侧
if (colorOf(y) == RED) {//y的颜色是红色
setColor(parentOf(x), BLACK);//x的父置为黑色
setColor(y, BLACK);//y置为黑色
setColor(parentOf(parentOf(x)), RED);//x的父的父置为红色
x = parentOf(parentOf(x));//x=x的父的父
} else {//y的颜色是黑色
if (x == rightOf(parentOf(x))) {//x==x的父的右侧
x = parentOf(x);//x=x的父
rotateLeft(x);//左旋
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));//右旋
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
} //左旋
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
Entry<K,V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
} //右旋
private void rotateRight(Entry<K,V> p) {
if (p != null) {
Entry<K,V> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
buildFromSorted：（待解决）
//采用递归的思路，先构建后节点的左子树，在构建好节点的右子树，最后和节点组合成一个完整的子树。
private void buildFromSorted(int size, Iterator<?> it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
this.size = size;
root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
it, str, defaultVal);
} /**
* Recursive "helper method" that does the real work of the
* previous method. Identically named parameters have
* identical definitions. Additional parameters are documented below.
* It is assumed that the comparator and size fields of the TreeMap are
* already set prior to calling this method. (It ignores both fields.)
*
* @param level the current level of tree. Initial call should be 0.//当前树的级别
* @param lo the first element index of this subtree. Initial should be 0.//子树的第一个元素
* @param hi the last element index of this subtree. Initial should be //子树的最后一个元素
* size-1.
* @param redLevel the level at which nodes should be red.
* Must be equal to computeRedLevel for tree of this size.
*/
@SuppressWarnings("unchecked")
private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
int redLevel,
Iterator<?> it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
/*
* Strategy: The root is the middlemost element. To get to it, we
* have to first recursively construct the entire left subtree,
* so as to grab all of its elements. We can then proceed with right
* subtree.
*
* The lo and hi arguments are the minimum and maximum
* indices to pull out of the iterator or stream for current subtree.
* They are not actually indexed, we just proceed sequentially,
* ensuring that items are extracted in corresponding order.
*/ if (hi < lo) return null; int mid = (lo + hi) >>> 1; Entry<K,V> left = null;
if (lo < mid)
left = buildFromSorted(level+1, lo, mid - 1, redLevel,
it, str, defaultVal); // extract key and/or value from iterator or stream
K key;
V value;
if (it != null) {
if (defaultVal==null) {
Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
key = (K)entry.getKey();
value = (V)entry.getValue();
} else {
key = (K)it.next();
value = defaultVal;
}
} else { // use stream
key = (K) str.readObject();
value = (defaultVal != null ? defaultVal : (V) str.readObject());
} Entry<K,V> middle = new Entry<>(key, value, null); // color nodes in non-full bottommost level red
if (level == redLevel)
middle.color = RED; if (left != null) {
middle.left = left;
left.parent = middle;
} if (mid < hi) {
Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
it, str, defaultVal);
middle.right = right;
right.parent = middle;
} return middle;
}
Entry<K,V> getEntry(Object key)；successor(Entry<K,V> t)
//键值对个数
public int size() {
return size;
} //是否包含指定的key
public boolean containsKey(Object key) {
return getEntry(key) != null;
} final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
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) //key<p.key,p=p.left
p = p.left;
else if (cmp > 0)//key>p.key,p=p.right
p = p.right;
else //key=p.key,key=p
return p;
}
return null;
}
总结：比结点值大，向结点右边找，比结点值小，向结点左边找 //使用指定的比较器查找key
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
} //map是否含有指定的value
public boolean containsValue(Object value) {
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
if (valEquals(value, e.value))
return true;
return false;
} //返回treemap的第一个结点，如果treemap是null，则返回null
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
} //寻找结点后继
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
} 总结：t的右子树不空，则t的后继是其右子树中最小的那个元素。
t的右孩子为空，则t的后继是其第一个向左走的祖先。
getCeilingEntry, getFloorEntry, getHigherEntry, getLowerEntry
//两个值是否相等
static final boolean valEquals(Object o1, Object o2) {
return (o1==null ? o2==null : o1.equals(o2));
} //指定的key返回value ，如果map不包含key，返回null
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
} //查询treemap比较器
public Comparator<? super K> comparator() {
return comparator;
} //返回treemap的第一个结点的key，如果是null，抛出错误
public K firstKey() {
return key(getFirstEntry());
} //返回treemap的最后一个结点的key，如果是null，抛出错误
public K lastKey() {
return key(getLastEntry());
} //返回treemap的最后一个结点，如果treemap是null，则返回null
final Entry<K,V> getLastEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.right != null)
p = p.right;
return p;
} public Map.Entry<K,V> ceilingEntry(K key) {
return exportEntry(getCeilingEntry(key));
} //返回一个简单的不可变的结点
static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
return (e == null) ? null :
new AbstractMap.SimpleImmutableEntry<>(e);
} AbstractMap类
//以指定的结点创建一个相同的结点
public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
} public K ceilingKey(K key) {
return keyOrNull(getCeilingEntry(key));
} static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
return (e == null) ? null : e.key;
} //指定的key返回结点；如果没有，则返回比key大的最小的结点；
//若不存在(即TreeMap中所有节点的键都比key大)，就返回null”
final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else if (cmp > 0) {
if (p.right != null) {
p = p.right;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
return p;
}
return null;
} //指定的key返回结点；如果没有，则返回比key小的最大的结点；
//若不存在(即TreeMap中所有节点的键都比key小)，就返回null”
final Entry<K,V> getFloorEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp > 0) {
if (p.right != null)
p = p.right;
else
return p;
} else if (cmp < 0) {
if (p.left != null) {
p = p.left;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
return p; }
return null;
} //返回比key大的最小的结点；
//若不存在(即TreeMap中所有节点的键都比key小)，就返回null”
final Entry<K,V> getHigherEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else {
if (p.right != null) {
p = p.right;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
} //返回比key小的最大的结点；
//若不存在(即TreeMap中所有节点的键都比key大)，就返回null”
final Entry<K,V> getLowerEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp > 0) {
if (p.right != null)
p = p.right;
else
return p;
} else {
if (p.left != null) {
p = p.left;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
} //删除映射根据指定的key，如果存在
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null; V oldValue = p.value;
deleteEntry(p);
return oldValue;
} //删除所有结点
public void clear() {
modCount++;
size = 0;
root = null;
} //返回此 TreeMap 实例的浅表副本。（键和值本身不被复制。）
public Object clone() {
TreeMap<?,?> clone;
try {
clone = (TreeMap<?,?>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
} // Put clone into "virgin" state (except for comparator)
//将clone至于原始状态（除了比较器）
clone.root = null;
clone.size = 0;
clone.modCount = 0;
clone.entrySet = null;
clone.navigableKeySet = null;
clone.descendingMap = null; // Initialize clone with our mappings
try {
clone.buildFromSorted(size, entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
} return clone;
} public Map.Entry<K,V> firstEntry() {
return exportEntry(getFirstEntry());
} public Map.Entry<K,V> lastEntry() {
return exportEntry(getLastEntry());
} //弹出第一个结点
public Map.Entry<K,V> pollFirstEntry() {
Entry<K,V> p = getFirstEntry();
Map.Entry<K,V> result = exportEntry(p);
if (p != null)
deleteEntry(p);
return result;
} //弹出最后一个结点
public Map.Entry<K,V> pollLastEntry() {
Entry<K,V> p = getLastEntry();
Map.Entry<K,V> result = exportEntry(p);
if (p != null)
deleteEntry(p);
return result;
} public Map.Entry<K,V> lowerEntry(K key) {
return exportEntry(getLowerEntry(key));
} public K lowerKey(K key) {
return keyOrNull(getLowerEntry(key));
} public Map.Entry<K,V> floorEntry(K key) {
return exportEntry(getFloorEntry(key));
} public K floorKey(K key) {
return keyOrNull(getFloorEntry(key));
} public K ceilingKey(K key) {
return keyOrNull(getCeilingEntry(key));
} public Map.Entry<K,V> higherEntry(K key) {
return exportEntry(getHigherEntry(key));
} public K higherKey(K key) {
return keyOrNull(getHigherEntry(key));
}
遍历treemap的key，value，entry：
private transient EntrySet entrySet;
private transient KeySet<K> navigableKeySet;
private transient NavigableMap<K,V> descendingMap; //key集合
public Set<K> keySet() {
return navigableKeySet();
} //key集合（正序：map添加key的正向顺序）
public NavigableSet<K> navigableKeySet() {
KeySet<K> nks = navigableKeySet;
return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
} //key集合（降序：map添加key的反向顺序）
public NavigableSet<K> descendingKeySet() {
return descendingMap().navigableKeySet();
} //映射的值的集合，顺序和key的顺应一致（正序：map添加key的正向顺序）
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null) ? vs : (values = new Values());
} //映射的结点的集合，顺序和key的顺应一致（正序：map添加key的正向顺序）
public Set<Map.Entry<K,V>> entrySet() {
EntrySet es = entrySet;
return (es != null) ? es : (entrySet = new EntrySet());
} public NavigableMap<K, V> descendingMap() {
NavigableMap<K, V> km = descendingMap;
return (km != null) ? km :
(descendingMap = new DescendingSubMap<>(this,
true, null, true,
true, null, true));
} //返回此映射的部分视图，其键的范围从 fromKey 到 toKey。
如果 fromKey 和 toKey 相等，则返回的映射为空，除非 fromExclusive 和 toExclusive 都为 true。
43 返回的映射受此映射支持，因此返回映射中的更改将反映在此映射中，反之亦然。
44 返回的映射支持此映射支持的所有可选映射操作。
45 如果试图在返回映射的范围之外插入一个键，或者构造一个任一端点位于其范围之外的子映射，
46 则返回的映射将抛出 IllegalArgumentException。
public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive) {
return new AscendingSubMap<>(this,
false, fromKey, fromInclusive,
false, toKey, toInclusive);
} //返回此映射的部分视图，其键小于（或等于，如果 inclusive 为 true）toKey。
返回的映射受此映射支持，因此返回映射中的更改将反映在此映射中，反之亦然。
56 返回的映射支持此映射支持的所有可选映射操作。
57 如果试图在返回映射的范围之外插入一个键，则返回的映射将抛出 IllegalArgumentException。
public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
return new AscendingSubMap<>(this,
true, null, true,
false, toKey, inclusive);
} //同上
public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
return new AscendingSubMap<>(this,
false, fromKey, inclusive,
true, null, true);
} public SortedMap<K,V> subMap(K fromKey, K toKey) {
return subMap(fromKey, true, toKey, false);
} public SortedMap<K,V> headMap(K toKey) {
return headMap(toKey, false);
} public SortedMap<K,V> tailMap(K fromKey) {
return tailMap(fromKey, true);
} //替换指定key，和值的值
@Override
public boolean replace(K key, V oldValue, V newValue) {
Entry<K,V> p = getEntry(key);
if (p!=null && Objects.equals(oldValue, p.value)) {
p.value = newValue;
return true;
}
return false;
} //替换指定key的值
@Override
public V replace(K key, V value) {
Entry<K,V> p = getEntry(key);
if (p!=null) {
V oldValue = p.value;
p.value = value;
return oldValue;
}
return null;
} //类似ArrayList
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
int expectedModCount = modCount;
for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
action.accept(e.key, e.value); if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
}
}
replaceAll：替换所有的值
@Override
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Objects.requireNonNull(function);
int expectedModCount = modCount; for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
e.value = function.apply(e.key, e.value); if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
}
}
demo：
public static void main(String[] args) {
TreeMap<String,Object> treeMap= new TreeMap();
treeMap.put("1",1);
treeMap.put("2",3);
treeMap.put("3",3);
treeMap.put("4",3);
treeMap.put("5",3);
BiFunction ff = new BiFunction<String, Integer, Object>() {
@Override
public Integer apply(String str,Integer v) {
return 2;
}
};
treeMap.replaceAll(ff);
System.out.println(treeMap);
}
结果：
{1=2, 2=2, 3=2, 4=2, 5=2}
TreeMap有Values、EntrySet、KeySet、PrivateEntryIterator、EntryIterator、ValueIterator、KeyIterator、DescendingKeyIterator、NavigableSubMap、AscendingSubMap、DescendingSubMap、SubMap、Entry共十三个内部类。可以参考这篇博客：https://blog.csdn.net/jzhf2012/article/details/8540713