Java基础之TreeMap详解

Java基础之TreeMap详解

一、写在前面

TreeMap的底层数据结构是红黑树，且TreeMap可以实现集合元素的排序。

所以TreeMap的源码需要实现：

1.红黑树的数据结构，以及红黑树的节点插入，删除，以及红黑树的自平衡操作，如左旋，右旋，以及节点变色

2.红黑树需要支持按照指定的比较器进行排序，或者进行自然排序。

二、定义

public class TreeMap

extends AbstractMap

implements NavigableMap, Cloneable, java.io.Serializable

public interface NavigableMap extends SortedMap {

TreeMap

继承了AbstractMap

实现了NavigableMap，而NavigableMap接口继承了SortedMap接口,SortedMap接口表示其实现类是一个有序集合

实现了Cloneable，所以支持对象克隆

实现了Serializable，所以支持对象序列化

三、成员变量

comparator

/**

* The comparator used to maintain order in this tree map, or

* null if it uses the natural ordering of its keys.

*

* @serial

*/

private final Comparator super K> comparator;

外部指定的比较器。在创建TreeMap对象时可以指定。如果指定了比较器，则TreeMap插入键值对时，按照comparator比较排序。

root

private transient Entry root;

root指代TreeMap底层红黑树的根节点。 root的类型Entry就是红黑树节点的类型。

红黑树数据结构的实现就依赖于Entry

size

/**

* The number of entries in the tree

*/

private transient int size = 0;

表示TreeMap集合中键值对个数。

modCount

/**

* The number of structural modifications to the tree.

*/

private transient int modCount = 0;

表示TreeMap集合被结构化修改的次数。用于迭代器迭代过程中检测集合是否被结构化修改，若是，则fail-fast。

四、内部类

Entry

Entry是红黑树节点的代码实现，是实现红黑树数据结构的基础。

static final class Entry implements Map.Entry {

K key;

V value;

Entry left;

Entry right;

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

}

}

成员变量

K key,V value分别是TreeMap集合中存储的键值对的键和值

Entry left 代表当前节点的左子节点

Entry right 代表当前节点的右子节点

Entry parent 代表当前节点的父节点

boolean color 代表当前节点的颜色，默认是黑色，为true

构造器

Entry只提供了一个构造器 Entry(K key, V value, Entry parent)

即：创建一个红黑树节点，只需要指定其存储的键值信息，以及其父节点引用。不需要指定左孩子和右孩子，以及颜色。

成员方法

提供了getKey()方法返回当前节点的key值。

提供了getValue()，setValue(V v)分别用于获取Value，以及覆盖Value后返回oldValue

重写了equals()方法用于判断两个红黑树节点是否相同。逻辑是：两个红黑树节点的key要么都为null，要么equals结果true，且，value要么都为null,要么equals结果为true。

重写了hashCode()方法。

重写了toString()方法。

五、构造器

public TreeMap()

public TreeMap() {

comparator = null;

}

无参构造器，即不指定比较器的构造器。

注意，此时插入集合的键值对的key的类型必须实现Comparable接口，即提供自然排序能力，否则会报错类型转换异常。

public TreeMap(Comparator super K> comparator)

public TreeMap(Comparator super K> comparator) {

this.comparator = comparator;

}

指定比较器的构造器。

指定的比较器用于比较key，且comparator指定了泛型，即比较器比较的元素的类型必须是K或者K的父类类型。

public TreeMap(Map extends K, ? extends V> m)

public TreeMap(Map extends K, ? extends V> m) {

comparator = null;

putAll(m);

}

将非TreeMap集合转为TreeMap集合构造器

public TreeMap(SortedMap m)

public TreeMap(SortedMap m) {

comparator = m.comparator();

try {

buildFromSorted(m.size(), m.entrySet().iterator(), null, null);

} catch (java.io.IOException cannotHappen) {

} catch (ClassNotFoundException cannotHappen) {

}

}

将有序Map集合转为TreeMap集合

六、成员方法

public V get(Object key)

public V get(Object key) {

Entry p = getEntry(key);

return (p==null ? null : p.value);

}

TreeMap的get方法用于获取指定key的value。如果指定key没有对应的红黑树节点，则返回null，否则返回对应红黑树节点的value。

可以看到get方法实现依赖于getEntry(Object key)方法。

getEntry(Object key)方法是根据指定key找对应的红黑树节点并返回该节点。

final Entry getEntry(Object key)

final Entry getEntry(Object key) {

// Offload comparator-based version for sake of performance

if (comparator != null)//如果外部指定了比较器

return getEntryUsingComparator(key);//则使用指定比较器来查找

if (key == null)//如果外部没有指定比较器，且要查找的key为null，则抛出空指针异常

throw new NullPointerException();

@SuppressWarnings("unchecked")//此时外部没有指定构造器，且要查的Key不为null

Comparable super K> k = (Comparable super K>) key;//检查Key的类型是否实现了Comparable接口，即是否实现了自然排序，如果实现了，则此处可以强转成功，否则会报错类型转换异常

Entry p = root;

while (p != null) {//从红黑树根节点开始使用key本身的自然排序进行比较

int cmp = k.compareTo(p.key);

if (cmp < 0)//如果要查找的key小于树节点的key，则说明要找的key在当前节点的左子树上，则下次遍历从左子树的根节点开始

p = p.left;

else if (cmp > 0)//如果要查找的key大于树节点的key，则说明要找的key在当前节点的右子树上，则下次遍历从右子树的根节点开始

p = p.right;

else//如果要查找的key等于树节点的key，则该节点就是要找的，直接返回该节点

return p;

}

return null;//如果上面遍历没有找到对应Key的节点，则返回null

}

final Entry getEntryUsingComparator(Object key) {//使用指定比较器来查找，逻辑基本和自然排序查找一样，只是这里使用了比较器排序查找

@SuppressWarnings("unchecked")

K k = (K) key;

Comparator super K> cpr = comparator;

if (cpr != null) {

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

}

public V put(K key, V value)

public V put(K key, V value) {

Entry 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 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);

http://if (cmp < 0)

t = t.left;

else if (cmp > 0)

t = t.right;

else

return t.setValue(value);

} while (t != null);

}

Entry 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);

}

public V setValue(V value) {

V oldValue = this.value;

this.value = value;

return oldValue;

}

TreeMap的put方法用于插入一个键值对，

当插入的key在集合中不存在时，则put表示新增键值对，并返回null；

当插入的key在集合中存在时，则put表示覆盖已存在key对应的value，并返回老value。

private void fixAfterInsertion(Entry x)

private void fixAfterInsertion(Entry x) {//x是被插入的红黑树节点

x.color = RED;//默认被插入的节点都是红色

while (x != null && x != root && x.parent.color == RED) {//如果被插入节点不是根节点

if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {

Entry y = rightOf(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 == rightOf(parentOf(x))) {

x = parentOf(x);

rotateLeft(x);

}

setColor(parentOf(x), BLACK);

setColor(parentOf(parentOf(x)), RED);

rotateRight(parentOf(parenthttp://Of(x)));

}

} else {

Entry 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;//如果被插入的节点是根节点，则节点颜色改为黑色

}

fixAfterInsertion方法用于：当TreeMap插入红黑树节点后，导致红黑树不平衡时，TreeMap保持自平衡的自旋和变色操作。

该方法的入参就是插入的红黑树节点。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。