http://www.importnew.com/29713.html
HashMap通过hashcode对其内容进行快速查找，而 TreeMap基于红黑树的一种访问的Map,所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。存取的时间复杂度都是O(log(n))
HashMap 非线程安全 TreeMap 非线程安全
HashMap：适用于在Map中插入、删除和定位元素。Treemap：适用于按自然顺序或自定义顺序遍历键(key)。
TreeMap是基于红黑树（一种自平衡的二叉查找树）实现的一个保证有序性的Map，在继承关系结构图中可以得知TreeMap实现了NavigableMap接口，而该接口又继承了SortedMap接口，我们先来看看这两个接口定义了一些什么功能。
SortedMap 首先是SortedMap接口，实现该接口的实现类应当按照自然排序保证key的有序性，所谓自然排序即是根据key的compareTo()函数（需要实现Comparable接口）或者在构造函数中传入的Comparator实现类来进行排序，集合视图遍历元素的顺序也应当与key的顺序一致。SortedMap接口还定义了以下几个有效利用有序性的函数：
package java.util; public interface SortedMap<K,V> extends Map<K,V> { /** * 用于在此Map中对key进行排序的比较器，如果为null，则使用key的compareTo()函数进行比较。 */ Comparator<? super K> comparator(); /** * 返回一个key的范围为从fromKey到toKey的局部视图（包括fromKey，不包括toKey，包左不包右）， * 如果fromKey和toKey是相等的，则返回一个空视图。 * 返回的局部视图同样是此Map的集合视图，所以对它的操作是会与Map互相影响的。 */ SortedMap<K,V> subMap(K fromKey, K toKey); /** * 返回一个严格地小于toKey的局部视图。 */ SortedMap<K,V> headMap(K toKey); /** * 返回一个大于或等于fromKey的局部视图。 */ SortedMap<K,V> tailMap(K fromKey); /** * 返回当前Map中的第一个key（最小）。 */ K firstKey(); /** * 返回当前Map中的最后一个key（最大）。 */ K lastKey(); Set<K> keySet(); Collection<V> values(); Set<Map.Entry<K, V>> entrySet(); }NavigableMap 然后是SortedMap的子接口NavigableMap，该接口扩展了一些用于导航（Navigation）的方法，像函数lowerEntry(key)会根据传入的参数key返回一个小于key的最大的一对键值对，例如，我们如下调用lowerEntry(6)，那么将返回key为5的键值对，如果没有key为5，则会返回key为4的键值对，以此类推，直到返回null（实在找不到的情况下）。
public static void main(String[] args) { NavigableMap<Integer, Integer> map = new TreeMap<>(); for (int i = 0; i < 10; i++) map.put(i, i); assert map.lowerEntry(6).getKey() == 5; assert map.lowerEntry(5).getKey() == 4; assert map.lowerEntry(0).getKey() == null; }NavigableMap接口相对于SortedMap接口来说灵活了许多，正因为TreeMap也实现了该接口，所以在需要数据有序而且想灵活地访问它们的时候，使用TreeMap就非常合适了。
上文我们提到TreeMap的内部实现基于红黑树，而红黑树又是二叉查找树的一种。二叉查找树是一种有序的树形结构，优势在于查找、插入的时间复杂度只有O(log n)，特性如下：
任意节点最多含有两个子节点。 任意节点的左、右节点都可以看做为一棵二叉查找树。 如果任意节点的左子树不为空，那么左子树上的所有节点的值均小于它的根节点的值。 如果任意节点的右子树不为空，那么右子树上的所有节点的值均大于它的根节点的值。 任意节点的key都是不同的。 尽管二叉查找树看起来很美好，但事与愿违，二叉查找树在极端情况下会变得并不是那么有效率，假设我们有一个有序的整数序列：1,2,3,4,5,6,7,8,9,10,…，如果把这个序列按顺序全部插入到二叉查找树时会发生什么呢？二叉查找树会产生倾斜，序列中的每一个元素都大于它的根节点（前一个元素），左子树永远是空的，那么这棵二叉查找树就跟一个普通的链表没什么区别了，查找操作的时间复杂度只有O(n)。
为了解决这个问题需要引入自平衡的二叉查找树，所谓自平衡，即是在树结构将要倾斜的情况下进行修正，这个修正操作被称为旋转，通过旋转操作可以让树趋于平衡。
红黑树是平衡二叉查找树的一种实现，它的名字来自于它的子节点是着色的，每个子节点非黑即红，由于只有两种颜色（两种状态），一般使用boolean来表示，下面为TreeMap中实现的Entry，它代表红黑树中的一个节点：
// Red-black mechanics private static final boolean RED = false; private static final boolean BLACK = true; /** * 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; Entry<K,V> right; 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; } }任何平衡二叉查找树的查找操作都是与二叉查找树是一样的，因为查找操作并不会影响树的结构，也就不需要进行修正，代码如下：
public V get(Object key) { Entry<K,V> p = getEntry(key); return (p==null ? null : p.value); } final Entry<K,V> getEntry(Object key) { // 使用Comparator进行比较 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; // 从根节点开始，不断比较key的大小进行查找 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; // 没有相等的key，返回null }