HashTable，LinkedHashMap，TreeMap理解

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

继承自hashMap

public class linkedHashMap
    extends HashMap
    implements Map

直接使用父类hashMap的put方法
重写了afterNodeInsertion和afterNodeAccess ，newNode

   Node newNode(int hash, K key, V value, Node e) {
        linkedHashMap.Entry p =
            new linkedHashMap.Entry(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

 private void linkNodeLast(linkedHashMap.Entry p) {
        linkedHashMap.Entry last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

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

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

void afterNodeRemoval(Node e) { // unlink
        linkedHashMap.Entry p =
            (linkedHashMap.Entry)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

​

​

例如keySet按照链表顺序

  public Set keySet() {
        Set ks = keySet;
        if (ks == null) {
            ks = new linkedKeySet();
            keySet = ks;
        }
        return ks;
    }

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

​

void afterNodeInsertion(boolean evict) { // possibly remove eldest
        linkedHashMap.Entry 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 e) { // move node to last
        linkedHashMap.Entry last;
        if (accessOrder && (last = tail) != e) {
            linkedHashMap.Entry p =
                (linkedHashMap.Entry)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

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

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

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

​

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