在这种情况下, 我们用扩展的比较器来进行比较, 同时会注意到另一个问题, 比如我们创建了一个简单的对象, User:
public class User implements Comparable<User> { private int age; private String name; private int class; @Override public int compareTo(User u); }我们实现了内部比较器, 这时候为了保持一致性, 需要重写equals()方法,并与compare保持一致.
但如果我们传入的比较器为通过 age进行比较, 那么age相同的元素呢? 虽然equals方法并不相等, 但在排序中属于等值的元素. 说到这里我们就会发现, 其实在TreeMap中的 不一致性是允许存在的.
public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; putAll(m); } public TreeMap(SortedMap<K, ? extends V> m) { comparator = m.comparator(); try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } }
核心类型
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; Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent; } public K getKey(); public V getValue(); public V setValue(V value); 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; } }为了不采用递归的方式解决问题, 不出意外的加了一个属性, parent; 同时当创建一个节点的时候, 默认颜色为黑色(true), 但事实上并没有太大影响.
put()
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; }首先不支持key == null, 其次comparator的优先级要高于 comparable, 优先级的控制是 通过下面的 compare()方法实现的.
//补充 final int compare(Object k1, Object k2) { return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2) : comparator.compare((K)k1, (K)k2); }继续来看这个方法, 首先判断比较器是否为null, 之后进行插入操作.从根节点开始向下查找, 直到命中节点(更新value值), 或者找到未命中节点, 同时未命中节点的 父节点. 从这里就可以看出来, 在之前提到过的, 如果仅仅是通过 age 这个属性实现比较器, 那么在 TreeMap中会把他们当成同一个节点, 而直接更新value值, 所带来的直接后果是, 你会发现明明不是同一个对象, 但偏偏可以相互覆盖. 所以需要注意的就是一定要尽可能的利用到每一个你认为必要的属性.
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; }其余操作都是常规操作, 没有太多需要注意的地方, 红黑树的关键点在于fixAfterInsertion(e);