【源码】TreeMap
java.util.TreeMap
package java.util;
import java.io.Serializable;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
private final Comparator<? super K> comparator;//比较器
private transient Entry<K,V> root;//红黑树
private transient int size = 0;//Entry的数量
/**
* The number of structural modifications to the tree.
*/
private transient int modCount = 0;
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(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) {
}
}
// Query Operations
public int size() {//获取Entry数量
return size;
}
public boolean containsKey(Object key) {//包含key
return getEntry(key) != null;
}
public boolean containsValue(Object value) {//包含value
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
if (valEquals(value, e.value))
return true;
return false;
}
public V get(Object key) {//获取value
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
public Comparator<? super K> comparator() {//返回比较器
return comparator;
}
public K firstKey() {
return key(getFirstEntry());
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public K lastKey() {
return key(getLastEntry());
}
public void putAll(Map<? extends K, ? extends V> 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);
}
final Entry<K,V> getEntry(Object key) {//通过key获取Entry
// 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)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
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;
}
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;
}
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;
}
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;
}
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;
}
public V put(K key, V value) {//新增一个K/V
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();//key不能为null
@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;
}
public V remove(Object key) {//移除K/V
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;
}
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.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;
}
// NavigableMap API methods
/**
* @since 1.6
*/
public Map.Entry<K,V> firstEntry() {//最左的节点
return exportEntry(getFirstEntry());
}
/**
* @since 1.6
*/
public Map.Entry<K,V> lastEntry() {//最右的节点
return exportEntry(getLastEntry());
}
/**
* @since 1.6
*/
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;
}
/**
* @since 1.6
*/
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) {//小于的第一个key值
return keyOrNull(getLowerEntry(key));
}
public Map.Entry<K,V> floorEntry(K key) {//小于等于的第一个节点
return exportEntry(getFloorEntry(key));
}
public K floorKey(K key) {//小于等于的第一个key值
return keyOrNull(getFloorEntry(key));
}
public Map.Entry<K,V> ceilingEntry(K key) {//大于等于的第一个节点
return exportEntry(getCeilingEntry(key));
}
public K ceilingKey(K key) {//大于等于的第一个key值
return keyOrNull(getCeilingEntry(key));
}
public Map.Entry<K,V> higherEntry(K key) {//大于的第一个节点
return exportEntry(getHigherEntry(key));
}
public K higherKey(K key) {//大于的第一个key值
return keyOrNull(getHigherEntry(key));
}
// Views
/**
* Fields initialized to contain an instance of the entry set view
* the first time this view is requested. Views are stateless, so
* there's no reason to create more than one.
*/
private transient EntrySet entrySet;
private transient KeySet<K> navigableKeySet;
private transient NavigableMap<K,V> descendingMap;
//此处省略1000字。。。
}
总结
- TreeMap是有序的
- TreeMap是非线程安全的
- TreeMap不支持K/V为null
以上源码均来自JDK1.8.0_171