# TreeMap

## 1. 数据结构分析

### 1. 继承体系

```public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
// ....
}```

```// 既然叫做SortMap, 要排序的话，当然需要一个比较器了
Comparator<? super K> comparator();

SortedMap<K,V> subMap(K fromKey, K toKey);

// 源码注释: 返回比Map中key比参数toKey小的所有kv对

// 源码注释：返回比Map中key比参数fromKey大或相等的所有kv对
SortedMap<K,V> tailMap(K fromKey);

K firstKey();

K lastKey();```

```// 返回Map中比传入参数key小的kv对中，key最大的一个kv对
Map.Entry<K,V> lowerEntry(K key);
K lowerKey(K key);

// 返回Map中比传入参数key小或相等的kv对中，key最大的一个kv对
Map.Entry<K,V> floorEntry(K key);
K floorKey(K key);

// 返回Map中比传入参数key大或相等的kv对中，key最小的一个kv对
Map.Entry<K,V> ceilingEntry(K key);
K ceilingKey(K key);

// 返回Map中比传入参数key大的kv对中，key最小的一个kv对
Map.Entry<K,V> higherEntry(K key);
K higherKey(K key);

Map.Entry<K,V> firstEntry();
Map.Entry<K,V> lastEntry();
Map.Entry<K,V> pollFirstEntry();
NavigableMap<K,V> descendingMap();
NavigableSet<K> navigableKeySet();
NavigableSet<K> descendingKeySet();```

### 2. 数据结构

`private transient Entry<K,V> root;`

```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;

/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}

/**
* Returns the key.
*
* @return the key
*/
public K getKey() {
return key;
}

/**
* Returns the value associated with the key.
*
* @return the value associated with the key
*/
public V getValue() {
return value;
}

/**
* Replaces the value currently associated with the key with the given
* value.
*
* @return the value associated with the key before this method was
*         called
*/
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 valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}

public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}

public String toString() {
return key + "=" + value;
}
}```

## 2. 添加一个kv对

```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) {
// 下面这个循环可以得出树的左节点小于根小于右节点
// 然后找到新增的节点，作为叶子节点在树中的位置
// 注意这个相等时，直接更新了value值（这里表示插入一条已存在的记录）
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 {
// 比较器不存在的逻辑，这时要求key继承 Comparable 接口
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节点
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;
}```

1. 树结构为二叉排序树（且不能出现相等的情况）
2. 重排的方法可以保证该树为红黑树

## 小结

1. TreeMap 底层结构为红黑树
2. 红黑树的Node排序是根据Key进行比较
3. 每次新增删除节点，都可能导致红黑树的重排
4. 红黑树中不支持两个or已上的Node节点对应`红黑值`相等

## 相关博文

• JDK容器学习之HashMap (一) ： 底层存储结构分析
• JDK容器学习之HashMap (二) ： 读写逻辑详解
• JDK容器学习之HashMap (三) : 迭代器实现

241 篇文章61 人订阅

0 条评论

## 相关文章

### 2010 求后序遍历

2010 求后序遍历 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver 题目描述 Description 输入一...

33060

### [LeetCode] 78. Subsets

【原题】 Given a set of distinct integers, nums, return all possible subsets. Not...

28390

8930

23750

33710

88120

36680

32730

### Leetcode 209 Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minima...

210100

40270