插入(put)
源码
public V put(K key, V value) {
Entry<K,V> t = root;
//如果是第一次put, 根节点肯定为null
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);
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;
}
记录点
在第一次插入的时候为何进行compare操作? ```java public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
//第一次put,为啥还要进行compare呢?原因是需要校验K是否是可比较的Type(即是否实现了Comparable)
//如果不是,则会报错(转换异常ClassCastException)
compare(key, key); // type (and possibly null) check
//...
}
//...
}
@SuppressWarnings(“unchecked”) final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2) : comparator.compare((K)k1, (K)k2);
}
> 另外,idea里面会有相应提示,如图:
![image.png](https://cdn.nlark.com/yuque/0/2021/png/876305/1612517483848-6202933f-0a9b-4607-98e4-c6a068dc2d7f.png#align=left&display=inline&height=109&margin=%5Bobject%20Object%5D&name=image.png&originHeight=109&originWidth=781&size=16185&status=done&style=none&width=781)
> 说明:有序的集合构造使用了不可比较的元素,也就是说:作为TreeMap的key的泛型类,需要实现Comparable!
- 如果未指定比较器,当非第一次put的时候,put null,此时会抛 NPE
```java
public V put(K key, V value) {
//...
Comparator<? super K> cpr = comparator;
if (cpr != null) {
//...
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
//...
}
则说明:如果比较器未对 null值做特殊处理,就会报NPE;也就是说,如果不能保证key不为null,比较器必须对null做处理!
删除(remove)
源码
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
/**
* Delete node p, and then rebalance the tree.
*/
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
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;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // No children. Use self as phantom replacement and unlink.
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;
}
}
}
查询(get)
源码
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
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)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
总结:
- 数据结构:红黑树,使用红黑树保证树的平衡,同时能够把查找时间控制在 O(logn);
- put和remove操作会触发调整红黑树