HashTable，LinkedHashMap，TreeMap理解

HashTable

hashtable就是hash槽套了一个数组，利用数组+链表解决hash冲突，针对put,remove，get等方法加上了synchronized简单粗暴的解决线程安全
?

LinkedHashMap

继承自hashMap

public class LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>

AccessOrder为false

直接使用父类hashMap的put方法
重写了afterNodeInsertion和afterNodeAccess ，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;}

 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;}}

尾插法将节点插入linkedhashMap维护的链表中
?

如果map remove操作，在afterNodeRemoval中维护链表

void afterNodeRemoval(Node<K,V> e) {
     // unlinkLinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.before = p.after = null;if (b == null)head = a;elseb.after = a;if (a == null)tail = b;elsea.before = b;}

?

?

例如keySet按照链表顺序

  public Set<K> keySet() {
    Set<K> ks = keySet;if (ks == null) {
    ks = new LinkedKeySet();keySet = ks;}return ks;}

LinkedKeySet是linkedHashMap的内部类，其foreach，按照链表顺序遍历。
?

?

AccessOrder为true

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);}}

removeEldestEntry模仿默认返回false，如果需要实现lru，清楚老元素，需要继承linkedHashMap,实现removeEldestEntry方法把头节点删除

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;}}

这个方法的功能就是 move node to last

get

   public V get(Object key) {
    Node<K,V> e;if ((e = getNode(hash(key), key)) == null)return null;if (accessOrder)afterNodeAccess(e);return e.value;}

同样访问的节点move node to last
?

?

TreeMap

需要传入比较器，treemap不再有hash槽，put，get,remove等操作直接针对红黑树，因此其时间复杂度为O(logN)而不再是O(1)，也不再有负载因子等概念