LinkedHashMap
HashMap由于使用了散列函数，无序的。但是有些场景下是需要有序的，比如缓存。HashMap就不能胜任。
LinkedHashMap就是一个升级版的HashMap。
思路与HashMap大体一样，使用的还是数组，链表，红黑树。特别的LinkedHashMap在每个节点上增加了一个前后指针，使得整个集合变得有序。
Entry节点如下
static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}}
由于LinkedHashMap继承了HashMap。put方法还是使用HashMap的。put实现细节在HashMap中有具体描述（HashMap见主页）这里主要叙述三个方法。 newNode，afterNodeAccess,afterNodeInsertion
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)//LinkedHashMap重写了newNode方法。tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;//LinkedHashMap重写了 afterNodeAccess(e)方法afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();//LinkedHashMap重写了 afterNodeInsertion(evict)方法 afterNodeInsertion(evict);return null;}
newNode
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {LinkedHashMap.Entry<K,V> p =new LinkedHashMap.Entry<K,V>(hash, key, value, e);linkNodeLast(p);return p;}
节点对象，由于默认是往链表末尾插入。锁以next=null
static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}}
//将新节点添加至链表末尾
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {LinkedHashMap.Entry<K,V> last = tail;tail = p;if (last == null)head = p;else {p.before = last;last.after = p;}}
afterNodeAccess
//该段代码就是在同一个下标位置key值一致发生替换的背景下调用的，思路就是将被替换的节点的前，后节点的连接断掉， 原链表末尾-原前节点-原后节点-替换的节点（末尾）
void afterNodeAccess(Node<K,V> e) { // move node to lastLinkedHashMap.Entry<K,V> last;if (accessOrder && (last = tail) != e) {LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.after = null;if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;}}
我们看到在LinkedHashMap中还重写了afterNodeInsertion(boolean evict)方法，它的目的是移除链表中最老的节点对象，也就是当前在头部的节点对象，但实际上在JDK8中不会执行，因为removeEldestEntry方法始终返回false。看源码：
void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}}
get,还是通过HashMap的put方法，没什么改变
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;if ((e = first.next) != null) {if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}
关键是在遍历的时候可以发现LinkedHashMap与Hashmap不一样。
由于LinkedHashMap的中定义了head，tail对象。可以直接找到head对象根据链表的特性一个接一个遍历，提高了效率。
abstract class LinkedHashIterator {LinkedHashMap.Entry<K,V> next;LinkedHashMap.Entry<K,V> current;int expectedModCount;LinkedHashIterator() {next = head;expectedModCount = modCount;current = null;}public final boolean hasNext() {return next != null;}final LinkedHashMap.Entry<K,V> nextNode() {LinkedHashMap.Entry<K,V> e = next;if (modCount != expectedModCount)throw new ConcurrentModificationException();if (e == null)throw new NoSuchElementException();current = e;next = e.after;return e;}
TreeMap 也是有序的，底层是用了红黑树，使用树形来存储数据，根据树的特性让节点有序。这中有序其实是一种排序。根绝key的大小来决定存放的位置。可以按自己的定义的排序方式对数据进行排序。
//下面代码思路：由于使用的是红黑树所以操作类似于红黑树的操作。
先拿到root节点，用root的key与新插入的key对比，大在右小在左，一只比下去，直到找到省略叶子结点或者找到与key相等的结点替换。
public V put(K key, V value) {Entry<K,V> t = root;if (t == null) {compare(key, key); // type (and possibly null) checkroot = new Entry<>(key, value, null);size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? 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;elsereturn 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;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0)parent.left = e;elseparent.right = e;//维护红黑树的平衡fixAfterInsertion(e);size++;modCount++;return null;}
get 思路更put一样，就是与root结点一个一个比较，大在右小在左，直到着到相等的key，或者找到了叶子结点说明没找到。直接放回null
{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 performanceif (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;while (p != null) {int cmp = k.compareTo(p.key);if (cmp < 0)p = p.left;else if (cmp > 0)p = p.right;elsereturn p;}return null;}
遍历,找到最左边即最小的节点，根据节点的parent，left，right以及树的特性找到下一个节点
class EntrySet extends AbstractSet<Map.Entry<K,V>> {public Iterator<Map.Entry<K,V>> iterator() {return new EntryIterator(getFirstEntry());}
//找到树中对应最小节点作为first final Entry<K,V> getFirstEntry() {Entry<K,V> p = root;if (p != null)while (p.left != null)p = p.left;return p;}
PrivateEntryIterator(Entry<K,V> first) {expectedModCount = modCount;lastReturned = null;next = first;}
//由于树形的特殊结构需要找到准确的下一个节点可以通过successor(e);
final Entry<K,V> nextEntry() {Entry<K,V> e = next;if (e == null)throw new NoSuchElementException();if (modCount != expectedModCount)throw new ConcurrentModificationException();next = successor(e);lastReturned = e;return e;}
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;}}
TreeMap的有序其实是一种排序。通过树形将节点按树的特性存储起来。然后get，或者遍历时同样通过树的特性遍历节点。从而达到一个有序的效果。最主要的手段时比较器。 Comparator。比较key的大小。找节点的位置。