HashMap vs Hashtable vs LinkedHashMap 横向对比

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {

    // 存储桶的数组（注意：不是 2 的幂！）
    private transient Entry<?,?>[] table;

    // 默认初始容量 11（不是 16！）
    public Hashtable() {
        this(11, 0.75f);
    }

    // put：整个方法加 synchronized —— 锁住整张表
    public synchronized V put(K key, V value) {
        if (value == null)        // ① 不允许 null value
            throw new NullPointerException();
        // ... 计算 hash、定位桶、插入
        if (key == null)          // ② 不允许 null key
            throw new NullPointerException();
    }

    // get：同样加 synchronized
    public synchronized V get(Object key) { ... }

    // 扩容：newCapacity = oldCapacity * 2 + 1
    protected void rehash() {
        int oldCapacity = table.length;
        int newCapacity = (oldCapacity << 1) + 1;  // ×2+1，不保证 2 的幂
        // ... 逐个 rehash 转移
    }
}

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);  // 复用 HashMap.Node 的全部字段
    }
}

// LinkedHashMap 持有头尾引用
transient LinkedHashMap.Entry<K,V> head;  // 链表头（最早插入 / 最久未访问）
transient LinkedHashMap.Entry<K,V> tail;  // 链表尾（最近插入 / 最近访问）

// 每次 get/put 命中已有 key 后调用
void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    // accessOrder = true 时，把被访问的节点移到链表尾部
    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;     // p 是头节点 → head 后移
        else b.after = a;           // p 从中间摘出
        if (a != null) a.before = b;
        else last = b;              // p 是尾节点
        if (last == null) head = p;  // 链表只有一个节点
        else { p.before = last; last.after = p; }
        tail = p;                   // p 成为新的尾节点
    }
}

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        // initialCapacity, loadFactor, accessOrder = true
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    /**
     * 每次 put/putAll 之后被调用。
     * 返回 true → 自动删除链表头部（最久未访问）的元素。
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;  // 超出容量就淘汰最老的
    }
}

// 使用示例
LRUCache<String, Integer> cache = new LRUCache<>(3);
cache.put("A", 1);   // {A=1}
cache.put("B", 2);   // {A=1, B=2}
cache.put("C", 3);   // {A=1, B=2, C=3}
cache.get("A");       // {B=2, C=3, A=1}  ← A 被访问，移到尾部
cache.put("D", 4);   // {C=3, A=1, D=4}  ← B 被淘汰（最久未访问）

public class LRUCache2<K, V> {
    private final int capacity;
    private final HashMap<K, DLinkedNode<K,V>> map;
    private final DLinkedNode<K,V> head, tail; // 哨兵节点

    public V get(K key) {
        DLinkedNode<K,V> node = map.get(key);
        if (node == null) return null;
        moveToHead(node);     // 标记为"最近使用"
        return node.value;
    }

    public void put(K key, V value) {
        DLinkedNode<K,V> node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
        } else {
            node = new DLinkedNode<>(key, value);
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                DLinkedNode<K,V> removed = removeTail();
                map.remove(removed.key);  // 淘汰最久未使用的
            }
        }
    }
}