HashMap vs Hashtable vs LinkedHashMap 横向对比

// ---------- 常量 ----------
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   // 默认容量 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int MAXIMUM_CAPACITY = 1 << 30;      // 容量上限 2^30
static final int TREEIFY_THRESHOLD = 8;          // 链表长度 ≥ 8 → 考虑树化
static final int UNTREEIFY_THRESHOLD = 6;        // 树节点 ≤ 6 → 退化为链表
static final int MIN_TREEIFY_CAPACITY = 64;       // 树化要求数组容量 ≥ 64

// ---------- 字段 ----------
transient Node<K,V>[] table;    // 桶数组（首次 put 才分配）
transient int size;             // 键值对个数
int threshold;                   // 扩容阈值 = 容量 × 负载因子
final float loadFactor;          // 负载因子，默认 0.75
transient int modCount;         // 结构性修改次数，迭代器 fail-fast 的依据

// ① 扰动函数：key.hashCode() 的高 16 位与低 16 位异或，让高位参与定位
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// ② putVal 中定位桶下标：n 是 2 的幂，用位运算代替取模
i = (n - 1) & hash;   // 等价于 hash % n，但快得多；这也是容量必须为 2 的幂的原因

// null key 的 hash 恒为 0 → 永远落在桶 0
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

// putVal 中的写入流程：桶 0 空了直接挂节点，非空就遍历桶内链表找 key 是否已存在
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
else {
    // …… 遍历链表/红黑树：key == 已存在节点的 key 或 equals 相等 → 覆盖 value ……
}

public synchronized V put(K key, V value) {
    if (value == null)                    // ① value 为 null：显式抛 NPE
        throw new NullPointerException();
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();             // ② key 为 null 时，这一行直接 NPE
    int index = (hash & 0x7FFFFFFF) % tab.length;
    // ……
}

public class Hashtable<K,V>
    extends Dictionary<K,V>                  // 继承 1.0 遗留抽象类
    implements Map<K,V>, Cloneable, java.io.Serializable {

    private transient Entry<?,?>[] table;      // 桶数组，长度不必是 2 的幂

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

    // put：整个方法 synchronized —— 锁住整张表
    public synchronized V put(K key, V value) {
        if (value == null)                    // 不允许 null value
            throw new NullPointerException();
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();             // key 为 null 时在此抛 NPE
        int index = (hash & 0x7FFFFFFF) % tab.length;  // 取模定位，非位运算
        // …… 遍历桶内链表，已存在则覆盖，否则头插法插入 ……
    }

    public synchronized V get(Object key) { ... }   // 纯读也要抢同一把锁
    public synchronized V remove(Object key) { ... }
    public synchronized boolean containsKey(Object key) { ... }

    // 扩容：×2+1，刻意避开 2 的幂，让取模分布更均匀
    protected void rehash() {
        int newCapacity = (oldCapacity << 1) + 1;
        // …… 逐个元素重新计算 index 并转移（无高低位拆分优化）……
    }
}

// Enumerator 同时实现 Enumeration 和 Iterator，还带 fail-fast 的 modCount 校验
private class Enumerator<T>
    implements Enumeration<T>, Iterator<T> {
    int expectedModCount = modCount;
    ...
    public T nextElement() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();  // fail-fast
        ...
    }
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null)      // 与 Hashtable 一样拒绝 null
        throw new NullPointerException();
    int hash = spread(key.hashCode());
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();                        // 并发初始化由 sizeCtl 协调
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 桶为空 → CAS 原子写入，完全无锁
            if (casTabAt(tab, i, null, new Node<>(hash, key, value, null)))
                break;
        }
        else {
            synchronized (f) {                   // 桶非空 → 只锁桶头节点
                // …… 链表/红黑树插入或覆盖，复用 HashMap 的树化逻辑 ……
            }
        }
    }
    addCount(1L, binCount);                    // 走 CounterCell 分片计数
    return null;
}

/**
 * sizeCtl 状态机：
 *   -1         → 正在初始化（其他线程在 initTable 里自旋等待）
 *   -(1 + n)   → 正在扩容，n 为参与扩容的线程数（多线程协同扩容）
 *    0         → 尚未初始化
 *    正数       → 下一次扩容阈值（容量 × 0.75）
 */
private transient volatile int sizeCtl;

// 分片计数器：每个线程只 CAS 更新自己的分片，避免全局计数器争用
@sun.misc.Contended
static final class CounterCell {
    volatile long value;
}
// size() 时累加 baseCount + 所有 CounterCell 分片——牺牲一点即时性，换取并发度

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);  // 桶内 next 由 HashMap.Node 负责
    }
}

// LinkedHashMap 额外持有的三个字段
transient LinkedHashMap.Entry<K,V> head;   // 链表头：最早插入 / 最久未访问
transient LinkedHashMap.Entry<K,V> tail;   // 链表尾：最近插入 / 最近访问
final boolean accessOrder;               // false = 插入序（默认） true = 访问序

// 3 参构造是打开"访问序"的钥匙，LRU 就靠它
public LinkedHashMap(int initialCapacity,
                      float loadFactor,
                      boolean accessOrder) {
    super(initialCapacity, loadFactor);  // 复用 HashMap 的容量/扩容逻辑
    this.accessOrder = accessOrder;
}

// 每次插入新节点后调用：把 p 挂到双向链表尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;                  // 空链表：p 既是头也是尾
    else {
        p.before = last;
        last.after = p;            // 非空：接到末尾
    }
}

// 把被访问的节点从链表中间"摘"出来，重新挂到尾部
void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.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;    // p 是头 → head 指向其后继
        else b.after = a;           // 前驱跳过 p
        if (a != null) a.before = b;
        else last = b;              // p 原本是尾，则 last 前移
        if (last == null) head = p;  // 链表只有一个节点
        else { p.before = last; last.after = p; }
        tail = p;                     // p 成为新的 tail
        ++modCount;               // 结构变化：访问序模式下遍历中 get 会抛 CME
    }
}

// 插入后回调：evict=true 时，检查是否需要淘汰链表头
void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null
            && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);  // 淘汰头节点
    }
}

// 默认不淘汰；子类重写即可定制策略 —— LRU 的容量上限就写在这
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

// remove() / clear() 删除节点后，同步从双向链表摘除
void afterNodeRemoval(Node<K,V> e) {
    LinkedHashMap.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;    // 删的是头 → head 后移
    else b.after = a;
    if (a == null) tail = b;    // 删的是尾 → tail 前移
    else a.before = b;
}

// get：accessOrder=true 时，读也会改变顺序 —— LRU 的核心
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;
}

// containsValue：沿双向链表遍历，天然有序
public boolean containsValue(Object value) {
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

// clear：双向链表一并清空，否则 head/tail 会悬空
public void clear() {
    super.clear();
    head = tail = null;
}

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

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);  // 第三个参数 accessOrder = true
        this.capacity = capacity;
    }

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

// 使用示例：注意每一步 head/tail 的变化
LRUCache<String, Integer> cache = new LRUCache<>(3);
cache.put("A", 1);   // {A=1}           head=A tail=A
cache.put("B", 2);   // {A=1, B=2}      head=A tail=B
cache.put("C", 3);   // {A=1, B=2, C=3} head=A tail=C
cache.get("A");       // {B=2, C=3, A=1} A 被访问 → 移到尾部，head=B
cache.put("D", 4);   // {C=3, A=1, D=4} size=4 > 3 → 淘汰 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);   // 淘汰最久未使用的
            }
        }
    }
    // addToHead / removeTail / moveToHead：双向链表的常规操作，O(1)
}

// 扩容阈值 = 容量 × 0.75。想让 10000 个元素一次都不扩容：
int expected = 10_000;
Map<String, Integer> map =
    new HashMap<>((int) (expected / 0.75f) + 1);
// ≈ 13334 → tableSizeFor 取整为 16384，threshold = 16384 × 0.75 = 12288 > 10000
// 等价写法：Guava 的 Maps.newHashMapWithExpectedSize(expected)