TreeMap & TreeSet & LinkedHashMap
一、TreeMap
HashMap缺陷：键值对之间没有特定的顺序。在TreeMap中，
键值对之间按键有序，TreeMap的实现基础是排序二叉树。
一）基本用法
构造方法：
//无参构造方法要求Map中的键实现Compareble接口 public TreeMap() //如果comparator不为null，在TreeMap内部进行比较时会调用compare方法 public TreeMap(Comparator<? super K> comparator)
TreeMap按键的比较结果对键进行重排，即使键实际上不同，但只要比较
结果相同，它们就会被认为相同，键只会保留一份。
TreeMap<String, String> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER); map.put("t", "try"); map.put("T", "order"); for (Map.Entry<String, String> kv : map.entrySet()) { System.out.println(kv.getKey() + " = " + kv.getValue()); //t = order }
二）实现原理
TreeMap内部是用红黑树实现的，红黑树是一种大致平衡的排序二叉树。
1）内部组成
内部主要成员：
private final Comparator<? super K> comparator; private transient Entry<K,V> root = null; //指向二叉树根节点 private transient int size = 0;
内部类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; //表示节点颜色，非黑即红。 Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent; } }
2）保存键值对
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; } //…
如果不是第一次添加，寻找父节点，寻找父节点根据是否设置了comparator分为两种情况：
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(); 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); }
基本思路：循环比较找到父节点，并插入作为其左孩子或者右孩子，然后调整保持树的大致平衡。
3）根据键获取值
public V get(Object key) { Entry<K,V> p = getEntry(key); return(p==null ? null : p.value); }
final Entry<K,V> getEntry(Object key) { // Offload comparator-based version for sake of performance if(comparator != null) return getEntryUsingComparator(key); if(key == null) throw new NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key; Entry<K,V> p = root; 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; }
4）查看是否包含某个值
按值查找需要遍历
public boolean containsValue(Object value) { for(Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) if(valEquals(value, e.value)) return true; return false; }
final Entry<K,V> getFirstEntry() { Entry<K,V> p = root; if(p != null) while (p.left != null) p = p.left; return p; }
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { if(t == null) return null; else if(t.right != null) { Entry<K,V> p = t.right; while (p.left != null) p = p.left; return p; } else { Entry<K,V> p = t.parent; Entry<K,V> ch = t; while(p != null && ch == p.right) { ch = p; p = p.parent; } return p; } }
三）小结
ThreeMap根据键保存、查找、删除的效率比较高，为O(h)，h为树的高度。
不要求排序优先考虑HashMap。
二、TreeSet
一）基本用法
TreeSet实现了两点：排重和有序
构造函数：
public TreeSet() public TreeSet(Comparator<? super E> comparator)
二）实现原理
TreeSet是基于TreeMap实现的：
private transient NavigableMap<E,Object> m; //背后的TreeMap private static final Object PRESENT = new Object(); //固定值
TreeSet(NavigableMap<E,Object> m) { this.m = m; } public TreeSet() { this(new TreeMap<E,Object>()); }
三）小结
没有重复元素，通过TreeMap实现。
三、LinkedHashMap
LinkedHashMap是HashMap的子类，可以保持元素按插入或者访问有序。
一）基本用法
该类内部有一个双向链表维护键值对顺序，每个键值对既位于哈希表中，也位于双向链表中。
该类支持两种顺序：
1）插入顺序：先添加的在前面，后添加的在后面，修改不影响顺序。
2）访问顺序：所谓访问就是get/put操作，对一个键执行get/put操作后，
其对应的键值会移到链表末尾。
LinkedHashMap有5个构造方法，其中4个都是按插入顺序，只有一个构造
方法可以指定按访问顺序：
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) //accessOrder为ture就是按顺序访问
默认情况下LinkedHashMap是按插入有序的：
LinkedHashMap<String, Integer> map = new LinkedHashMap<>(); map.put("c", 56); map.put("d", 22); map.put("a", 33); for (Map.Entry<String, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + " = " + entry.getValue()); } /*c = 56 d = 22 a = 33*/
插入有序一种常见的使用场景：希望Map按键有序，键在添加前已经排好序，
此时就没必要使用开销大的TreeMap。
LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true); map.put("c", 56); map.put("d", 22); map.put("a", 33); map.get("c"); map.put("d", 66); for (Map.Entry<String, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + " = " + entry.getValue()); } /*a = 33 c = 56 d = 66*/
二、实现原理
该类内部实例变量：
private transient Entry<K,V> header; //双向链表的表头 private final boolean accessOrder; //是否按访问顺序
Entry内部类：
private static class Entry<K,V> extends HashMap.Entry<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { super(hash, key, value, next); } private void remove() { before.after = after; after.before = before; } private void addBefore(Entry<K,V> existingEntry) { after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; } void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; if(lm.accessOrder) { lm.modCount++; remove(); addBefore(lm.header); } } void recordRemoval(HashMap<K,V> m) { remove(); } }
init用于初始化链表的头节点：
void init() { header = new Entry<>(-1, null, null, null); header.before = header.after = header; }
在LinkedHashMap中，put方法还会将节点加入到链表中来，如果是
按访问有序的，还会调整节点到末尾，并根据情况删除掉最久没有被访问的节点。
HashMap的put实现中，如果是新的键，会调用addEntry方法添加节点，LinkedHashMap重写了该方法:
void addEntry(int hash, K key, V value, int bucketIndex) { super.addEntry(hash, key, value, bucketIndex); //Remove eldest entry if instructed Entry<K,V> eldest = header.after; if(removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); } }
他先调用父类的addEntry方法，父类的addEntry会调用createEntry创建节点，
LinkedHashMap重写了createEntry方法：
void createEntry(int hash, K key, V value, int bucketIndex) { HashMap.Entry<K,V> old = table[bucketIndex]; Entry<K,V> e = new Entry<>(hash, key, value, old); table[bucketIndex] = e; //新建的节点，加入到链表末尾 e.addBefore(header); size++; }
例如执行：
Map<String,Integer> countMap = new LinkedHashMap<>(); countMap.put("hello", 1);
执行后内存结构：
在HashMap的put实现中，如果键已经存在，则会调用节点的recordAccess方法。
LinkedHashMap.Entry重写了该方法，如果是有序访问，则调整该节点到链表末尾。