1 树节点Entry
TreeMap树的节点是Entry 对象,Entry是TreeMap的一个内部类。
在TreeMap(红黑树)中false代表红色,true代表红色。
// Red-black mechanics private static final boolean RED = false; private static final boolean BLACK = true;
Entry的代码如下:
/** * Node in the Tree. Doubles as a means to pass key-value pairs back to * user (see Map.Entry). */ static final class Entry<K,V> implements Map.Entry<K,V> { K key; //键 V value; //值 Entry<K,V> left = null; //指向其左节点 Entry<K,V> right = null; //指向其右节点 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; } }