Java中HashMap及其相关类的底层原理与实现详解

// jdk 1.8 源码核心字段
public class hashmap<k,v> extends abstractmap<k,v>
    implements map<k,v>, cloneable, serializable {
    
    // 1. 核心数组（node 数组，即哈希桶）
    transient node<k,v>[] table;
    
    // 2. 实际元素个数
    transient int size;
    
    // 3. 扩容阈值（capacity * loadfactor）
    int threshold;
    
    // 4. 负载因子（默认 0.75）
    final float loadfactor;
    
    // 5. 静态内部类 node（链表节点）
    static class node<k,v> implements map.entry<k,v> {
        final int hash;
        final k key;
        v value;
        node<k,v> next;  // 指向下一个节点（链表指针）
    }
    
    // 6. 树化阈值（链表长度 >= 8 且数组长度 >= 64 时转红黑树）
    static final int treeify_threshold = 8;
    
    // 7. 退树化阈值（红黑树节点数 <= 6 时退化为链表）
    static final int untreeify_threshold = 6;
    
    // 8. 最小树化容量
    static final int min_treeify_capacity = 64;
}

final v putval(int hash, k key, v value, boolean onlyifabsent, boolean evict) {
    node<k,v>[] tab; node<k,v> p; int n, i;
    // 1. table 为空则初始化（resize）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. 计算数组下标 (n - 1) & hash，若该位置为空则直接放入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newnode(hash, key, value, null);
    else {
        node<k,v> e; k k;
        // 3. 如果 key 相同（hash 相同 && (引用相同 || equals 为 true)）→ 覆盖
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4. 如果已经是红黑树节点 → 走红黑树的 puttreeval
        else if (p instanceof treenode)
            e = ((treenode<k,v>)p).puttreeval(this, tab, hash, key, value);
        else {
            // 5. 链表情况：遍历链表
            for (int bincount = 0; ; ++bincount) {
                if ((e = p.next) == null) {
                    p.next = newnode(hash, key, value, null);
                    // 5a. 如果链表长度 >= 8 → 尝试转红黑树
                    if (bincount >= treeify_threshold - 1) // -1 for 1st
                        treeifybin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 6. 覆盖旧值
        if (e != null) {
            v oldvalue = e.value;
            if (!onlyifabsent || oldvalue == null)
                e.value = value;
            return oldvalue;
        }
    }
    ++modcount;  // 记录修改次数（用于 fast-fail）
    if (++size > threshold)  // 7. 超过阈值则扩容
        resize();
    return null;
}

static final int hash(object key) {
    int h;
    // 让 hashcode 的高 16 位参与低 16 位的运算（混合扰动），减少哈希碰撞
    return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);
}

// jdk 源码
public class hashset<e> extends abstractset<e>
    implements set<e>, cloneable, java.io.serializable {
    
    private transient hashmap<e,object> map;  // 底层就是 hashmap！
    
    // 虚拟占位值（所有 value 都指向它）
    private static final object present = new object();
    
    // 构造方法（直接 new hashmap）
    public hashset() {
        map = new hashmap<>();
    }
    
    // 添加元素：存到 map 的 key 位置
    public boolean add(e e) {
        return map.put(e, present) == null;
    }
    
    // 删除元素
    public boolean remove(object o) {
        return map.remove(o) == present;
    }
}

// 1. 插入顺序（默认）
linkedhashmap<string, string> map1 = new linkedhashmap<>();
map1.put("a", "1");
map1.put("b", "2");
map1.put("c", "3");
// 遍历输出：a, b, c（按插入顺序）

// 2. 访问顺序（accessorder = true）
linkedhashmap<string, string> map2 = new linkedhashmap<>(16, 0.75f, true);
map2.put("a", "1");
map2.put("b", "2");
map2.put("c", "3");
map2.get("a");  // 访问 a，a 会被移动到链表尾部
// 遍历输出：b, c, a（最近访问的放在最后）

// 实现一个固定大小的 lru 缓存
class lrucache<k, v> extends linkedhashmap<k, v> {
    private final int maxsize;
    
    public lrucache(int maxsize) {
        super(maxsize, 0.75f, true);  // accessorder = true
        this.maxsize = maxsize;
    }
    
    @override
    protected boolean removeeldestentry(map.entry<k, v> eldest) {
        // 当元素数量超过最大容量时，自动移除最老的元素（链表头部）
        return size() > maxsize;
    }
}

// 使用示例
lrucache<string, integer> cache = new lrucache<>(3);
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
cache.get("a");  // 访问 a
cache.put("d", 4);  // 触发淘汰，淘汰最久未使用的 b
// 缓存中：c, a, d

// jdk 8+ 源码核心（putval 方法片段）
final v putval(k key, v value, boolean onlyifabsent) {
    if (key == null || value == null) throw new nullpointerexception();  // 禁止 null
    int hash = spread(key.hashcode());
    for (node<k,v>[] tab = table;;) {
        node<k,v> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = inittable();
        else if ((f = tabat(tab, i = (n - 1) & hash)) == null) {
            // 1. 位置为空 → cas 尝试插入（无锁）
            if (castabat(tab, i, null, new node<k,v>(hash, key, value, null)))
                break;
        } else if ((fh = f.hash) == moved)
            // 2. 正在扩容 → 帮助迁移
            tab = helptransfer(tab, f);
        else {
            v oldval = null;
            // 3. 位置不为空 → synchronized 锁住头节点
            synchronized (f) {
                // ... 插入或覆盖逻辑
            }
            break;
        }
    }
    addcount(1l, bincount);
    return null;
}

// 问题 1：下面代码输出什么？为什么？
public static void main(string[] args) {
    hashset<string> set = new hashset<>();
    string s1 = new string("hello");
    string s2 = new string("hello");
    set.add(s1);
    set.add(s2);
    system.out.println(set.size());  // a
}

// 问题 2：下面代码在多线程环境下会有什么问题？
public class test {
    private static final map<string, string> map = new hashmap<>();
    public static void main(string[] args) {
        for (int i = 0; i < 100; i++) {
            new thread(() -> {
                map.put(thread.currentthread().getname(), "value");
            }).start();
        }
    }
}

// 问题 3：下面哪个 map 最合适用来实现一个带有过期淘汰策略的缓存？
// a. hashmap   b. linkedhashmap   c. concurrenthashmap   d. hashtable