TreeMap分析
一、直接使用红黑树进行数据存储
HashMap 是使用数组+红黑树的方式进行存储
红黑树算法这里不做介绍（建议看视频进行学习）
二、为什么TreeMap是有序的
实现步骤：
- 内置比较器
private final Comparator<? super K> comparator; //比较器定义，一经赋值，不能修改
public TreeMap() { // 无参创建对象时，比较器为空
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {//传入比较器，然后创建map
this.comparator = comparator;
}
- 放值时进行排序
此处调用compare()方法,或者强制转换,将键进行比较,然后按照红黑树的数据结构进行存储
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // 调用compare()方法
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);// 调用compare()方法
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; //强制转换成Comparable
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0) //<0 时 放到左子节点
t = t.left;
else if (cmp > 0) //>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;
}
- compare()方法
final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
//当比较器为空时,强制转换类型,进行比较
: comparator.compare((K)k1, (K)k2);//使用自定义比较器,进行比较
}
这样就实现了TreeMap的有序存储
4. 取值forEach()
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
int expectedModCount = modCount; // 这个跟size大小一致,记录了map修改量,put(),clear()都会进行+1操作
for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
// getFirstEntry() 获取第一个节点
// successor()获取下一个节点
action.accept(e.key, e.value); // 调用BiConsumer函数式接口的方法
if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
}
}
//通过一直获取左子节点,找到最小的那个节点,也就是第一个节点
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;
}
}
这样就实现了一整套的基于红黑树的有序map