TreeMap分析

1.8与1.7相比，TreeMap的实现并没有发生改变。或者说，从1.2版本开始，TreeMap就没有发生过变化。

由于TreeMap的实现没有变化，推荐阅读倪升武博客。

下面我只是来总结一下倪升武的博客中没有提及的或者是我认为比较重要的几点。

一.TreeMap的几个重要特点

TreeMap内部是使用红黑树结构存储的。一个对象想要成为TreeMap中的key，那么该对象所属的类必须实现Comparable接口，否则抛异常，因为key的寻找是依赖于比较器的实现。TreeMap中允许null值作为value，但是不允许null成为key。

下面是关于上面结论的源码：

public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { compare(key, key); // type (and possibly null) check：类型检查，如果key为null的话就会抛出异常 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) //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);//如果已经存在key的映射了，那么覆盖原值。 } 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; } Entry的hashcode计算：将key的hashcode和value的hashcode进行位与。 public int hashCode() { int keyHash = (key==null ? 0 : key.hashCode()); int valueHash = (value==null ? 0 : value.hashCode()); return keyHash ^ valueHash; } TreeMap非线程安全。TreeMap与HashMap相比较而言，前者更适合按照自然顺序或者自定义的顺序遍历键。