JDK 核心哈希容器源码深度解析：HashMap、LinkedHashMap 等

JDK 核心哈希容器源码深度解析：HashMap、LinkedHashMap 等 | 极客日志

// 默认初始容量 16（必须是 2 的幂，位运算优化） static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量 2^30 static final int MAXIMUM_CAPACITY = 1 << 30; // 默认负载因子，平衡内存与冲突 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 底层哈希桶数组，存储 Entry 节点 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; // 空数组常量，懒加载使用 static final Entry<?,?>[] EMPTY_TABLE = {}; // 实际存储的键值对数量 transient int size; // 扩容阈值 = 容量 * 负载因子，超过则扩容 int threshold; // 负载因子，构造后不可变 final float loadFactor; // 修改次数，用于 fail-fast 机制 transient int modCount;

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; static final int MAXIMUM_CAPACITY = 1 << 30; static final float DEFAULT_LOAD_FACTOR = 0.75f; // 链表转红黑树阈值（链表长度≥8 触发） static final int TREEIFY_THRESHOLD = 8; // 红黑树转链表阈值（节点数≤6 触发） static final int UNTREEIFY_THRESHOLD = 6; // 树化最小容量（数组容量≥64 才树化，避免小容量频繁树化/退化） static final int MIN_TREEIFY_CAPACITY = 64; // 底层哈希桶数组，存储 Node/TreeNode transient Node<K,V>[] table; static final Node<?,?>[] EMPTY_TABLE = {}; transient int size; int threshold; final float loadFactor; transient int modCount;

public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } // 调用带参构造，初始化负载因子和阈值 public HashMap(int initialCapacity, float loadFactor) { this.loadFactor = loadFactor; threshold = initialCapacity; init(); // 空方法，供子类重写 }

public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // 仅初始化负载因子，无其他计算 }

public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } // 核心：调用 tableSizeFor 修正容量 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; // JDK1.7：直接赋值阈值，1.8：延迟计算，此处仅临时存储容量 this.threshold = tableSizeFor(initialCapacity); } // 容量修正核心方法：向上取整为最近的 2 的幂 static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); putAll(m); } // 逐个调用 put 插入，无容量预计算 public void putAll(Map<? extends K, ? extends V> m) { int numKeysToAdd = m.size(); if (numKeysToAdd == 0) return; if (table == EMPTY_TABLE) { inflateTable(threshold); // 初始化数组 } for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { put(e.getKey(), e.getValue()); } }

public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); // 批量插入核心方法 } // 批量插入，预计算容量避免多次扩容 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) { if (table == null) { // 数组未初始化 float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); if (t > threshold) threshold = tableSizeFor(t); } else if (s > threshold) { // 数组已初始化，需扩容 resize(); } // 批量插入键值对 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }

public V put(K key, V value) { // 数组未初始化则先初始化 if (table == EMPTY_TABLE) { inflateTable(threshold); } // key 为 null 时，单独处理，哈希桶索引固定为 0 if (key == null) return putForNullKey(value); // 1. 计算 key 的哈希值（扰动处理，减少冲突） int hash = hash(key); // 2. 计算哈希桶索引 int i = indexFor(hash, table.length); // 3. 遍历链表，判断 key 是否存在 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; // 覆盖旧值 e.recordAccess(this); return oldValue; } } modCount++; // 4. key 不存在，头插法新增节点 addEntry(hash, key, value, i); return null; } // 哈希值扰动计算：4 次位运算 +1 次异或，让高位参与运算 final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } // 计算桶索引：利用 2 的幂特性，高效寻址 static int indexFor(int h, int length) { return h & (length - 1); } // 头插法新增节点，插入链表头部 void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); // 扩容为原 2 倍 hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; // 头插法：新节点 next 指向原头节点，桶索引指向新节点 table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } // 哈希值扰动优化：1 次异或 +1 次无符号右移，简化但效果相当 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } // 插入核心方法，整合扩容、树化、尾插法 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. 数组未初始化则先扩容（初始化） if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 2. 桶为空，直接新增节点插入 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 3. 头节点 key 匹配，直接覆盖 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 4. 头节点是红黑树，树插入 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 5. 遍历链表，尾插法新增 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 链表长度≥8，触发树化判断 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } // key 存在，跳出循环覆盖 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // key 存在，覆盖旧值并返回 if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } modCount++; // 6. 超过扩容阈值，触发扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } // 树化方法：数组容量≥64 才树化，否则仅扩容 final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }

void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // 1. 新建 2 倍容量的新数组 Entry[] newTable = new Entry[newCapacity]; // 2. 头插法迁移节点，可能导致链表反转 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; // 3. 更新扩容阈值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } // 节点迁移核心：头插法 void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); // 头插法：新节点 next 指向新桶当前头节点 e.next = newTable[i]; newTable[i] = e; e = next; } } }

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 1. 计算新容量和新阈值 if (oldCap > 0) { // 原容量达最大值，不再扩容 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 容量翻倍，阈值也翻倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; } // 初始化时的阈值（如无参构造首次扩容） else if (oldThr > 0) newCap = oldThr; // 无参构造首次扩容，默认容量 16，阈值 12 else { newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 计算新阈值 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY) ? (int)ft : Integer.MAX_VALUE; } threshold = newThr; // 2. 新建 2 倍容量的新数组 @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; // 3. 迁移原节点到新数组 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; // 桶内仅单个节点，直接计算新索引插入 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; // 红黑树节点，拆分红黑树 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 链表节点，尾插法迁移（无需重算哈希） else { Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // 关键：通过 hash & oldCap 判断新索引，无需重算 hash if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 低位节点：原索引插入 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 高位节点：原索引+oldCap 插入 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

public V remove(Object key) { Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.value); } final Entry<K,V> removeEntryForKey(Object key) { if (size == 0) return null; int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; // 遍历链表，找到待删除节点 while (e != null) { Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; // 头节点删除：桶指向 next if (prev == e) table[i] = next; // 中间节点删除：prev.next 指向 next else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; }

public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } // 删除核心方法，支持链表/红黑树删除 final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null, e; K k; V v; // 头节点匹配 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; // 桶非空，遍历查找 else if ((e = p.next) != null) { // 红黑树节点，树查找 if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); // 链表节点，遍历查找 else { do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } // 找到节点，执行删除 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { // 红黑树删除，删除后调整结构，节点数≤6 则退化 if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); // 链表头节点删除 else if (node == p) tab[index] = node.next; // 链表中间节点删除 else p.next = node.next; modCount++; size--; afterNodeRemoval(node); return node; } } return null; }

public void clear() { Node<K,V>[] tab; modCount++; if ((tab = table) != null && size > 0) { size = 0; // 遍历数组，置空所有桶，让 GC 回收节点 for (int i = 0; i < tab.length; ++i) tab[i] = null; } }

public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } final Entry<K,V> getEntry(Object key) { int hash = (key == null) ? 0 : hash(key); // 哈希计算→桶定位→遍历链表匹配 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; } // key 为 null 单独处理，桶索引 0 private V getForNullKey() { if (size == 0) return null; for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; }

public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } // 查询核心方法，支持链表/红黑树查询 final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 头节点直接匹配，快速返回 if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 桶非空，继续查找 if ((e = first.next) != null) { // 红黑树查询，时间复杂度 O(logn) if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 链表查询，时间复杂度 O(n) do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> { // 双向链表的头节点（最早插入/最早访问的节点） transient LinkedHashMap.Entry<K,V> head; // 双向链表的尾节点（最新插入/最新访问的节点） transient LinkedHashMap.Entry<K,V> tail; // 有序模式标识：true=访问顺序，false=插入顺序（默认） final boolean accessOrder; // 序列化版本号 private static final long serialVersionUID = 3801124242820219131L; }

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 的构造方法 } }

// 哈希表结构（数组 + 链表，与 HashMap 一致） 数组索引：0 1 2 ... 8 ... 15 ↓ ↓ ↓ ↓ ↓ 桶结构： - A - ... B→C ... - （B、C 哈希冲突，next 指针串联） // 双向链表结构（维护插入顺序：A→B→C，before/after 指针串联） head → A (before:null, after:B) → B (before:A, after:C) → C (before:B, after:null) → tail

public LinkedHashMap() { // 调用 HashMap 空参构造（默认容量 16，加载因子 0.75） super(); // 默认插入顺序 accessOrder = false; }

public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; }

public LinkedHashMap(Map<? extends K, ? extends V> m) { super(); accessOrder = false; // 调用 putAll 批量添加，双向链表按传入 Map 的迭代顺序构建 putAll(m); }

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); // 手动指定有序模式：true=访问顺序，false=插入顺序 this.accessOrder = accessOrder; }

// HashMap 中的钩子方法，默认空实现，供子类重写 // 1. 新节点插入哈希表后调用 void afterNodeInsertion(boolean evict) {} // 2. 节点被访问后调用（get/put 已存在键） void afterNodeAccess(Node<K,V> e) {} // 3. 节点被删除后调用 void afterNodeRemoval(Node<K,V> e) {}

// LinkedHashMap 重写：将节点链接到双向链表尾部 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; } } // 重写 HashMap 的 newNode，创建 LinkedHashMap.Entry 节点并链接到尾部 Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<>(hash, key, value, e); linkNodeLast(p); return p; } // 红黑树节点的创建，同样链接到双向链表尾部 TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { TreeNode<K,V> p = new TreeNode<>(hash, key, value, next); linkNodeLast((LinkedHashMap.Entry<K,V>)p); return p; }

// 重写 HashMap 的 afterNodeAccess：访问节点后处理 void afterNodeAccess(Node<K,V> e) { // move node to last 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; else // 否则，更新前驱的后继为当前节点的后继 b.after = a; if (a != null) // 更新后继的前驱为当前节点的前驱 a.before = b; else // 若后继为空，更新 last 为前驱（防止空指针） last = b; if (last == null) // 双向链表为空，当前节点作为头节点 head = p; else { // 否则，将当前节点插入尾部 p.before = last; last.after = p; } tail = p; // 更新尾节点为当前节点 modCount++; // 修改次数 +1，触发快速失败 } }

// 重写 HashMap 的 afterNodeRemoval：删除节点后处理 void afterNodeRemoval(Node<K,V> e) { // unlink LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; // 清空当前节点的前驱后继，便于 GC 回收 p.before = p.after = null; if (b == null) // 当前节点是头节点，更新头节点为后继 head = a; else // 否则，更新前驱的后继为后继 b.after = a; if (a == null) // 当前节点是尾节点，更新尾节点为前驱 tail = b; else // 否则，更新后继的前驱为前驱 a.before = b; }

public V get(Object key) { Node<K,V> e; // 调用 HashMap 的 getNode 方法查找节点（O(1)） if ((e = getNode(hash(key), key)) == null) return null; // 访问顺序模式，调用 afterNodeAccess 将节点移到尾部 if (accessOrder) afterNodeAccess(e); return e.value; }

public boolean containsValue(Object value) { // 基于双向链表遍历，无需遍历哈希表的空桶，效率远高于 HashMap 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; }

LinkedHashMap<String, String> lhm = new LinkedHashMap<>(); lhm.put("a", "1"); lhm.put("b", "2"); lhm.put("c", "3"); lhm.put("a", "4"); // 重复 put，顺序不变 // 遍历顺序：a→b→c（与首次插入顺序一致） for (Map.Entry<String, String> entry : lhm.entrySet()) { System.out.println(entry.getKey() + "=" + entry.getValue()); // a=4, b=2, c=3 }

// 构建访问顺序的 LinkedHashMap LinkedHashMap<String, String> lhm = new LinkedHashMap<>(16, 0.75f, true); lhm.put("a", "1"); lhm.put("b", "2"); lhm.put("c", "3"); // 双向链表：a→b→c（head→tail） lhm.get("a"); // 访问 a，a 移到尾部 → b→c→a lhm.put("b", "5"); // 访问 b，b 移到尾部 → c→a→b lhm.containsKey("c"); // 访问 c，c 移到尾部 → a→b→c // 遍历顺序：a（最久未访问）→b→c（最新访问） for (Map.Entry<String, String> entry : lhm.entrySet()) { System.out.println(entry.getKey()); // a, b, c }

// 自定义 LRU 缓存，继承 LinkedHashMap，重写 removeEldestEntry public class LruCache<K, V> extends LinkedHashMap<K, V> { private final int MAX_CAPACITY; // 缓存最大容量 // 构造方法：指定容量，访问顺序模式 public LruCache(int maxCapacity) { super(maxCapacity, 0.75f, true); this.MAX_CAPACITY = maxCapacity; } // 重写：当元素数超过最大容量时，删除最久未访问的节点 @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { // 关键：size() > 最大容量时返回 true，触发自动删除 return size() > MAX_CAPACITY; } // 测试 public static void main(String[] args) { LruCache<String, String> cache = new LruCache<>(3); // 最大容量 3 cache.put("a", "1"); cache.put("b", "2"); cache.put("c", "3"); // 容量 3，正常存储：a→b→c System.out.println(cache); // {a=1, b=2, c=3} cache.put("d", "4"); // 容量超 3，删除最久未访问的 a → b→c→d System.out.println(cache); // {b=2, c=3, d=4} cache.get("b"); // 访问 b，b 移到尾部 → c→d→b cache.put("e", "5"); // 容量超 3，删除最久未访问的 c → d→b→e System.out.println(cache); // {d=4, b=2, e=5} } }

Map<String, String> syncLruCache = Collections.synchronizedMap(new LruCache<>(3));

// Guava 的 LRU 缓存，线程安全，支持过期时间等 Cache<String, String> guavaCache = CacheBuilder.newBuilder() .maximumSize(3) // 最大容量 3 .build(); guavaCache.put("a", "1"); guavaCache.getIfPresent("a"); // 获取值

// 包装为线程安全的 LinkedHashMap，所有方法加 synchronized 全局锁 Map<String, String> syncLhm = Collections.synchronizedMap(new LinkedHashMap<>()); // 遍历需手动加锁，避免快速失败 synchronized (syncLhm) { for (Map.Entry<String, String> entry : syncLhm.entrySet()) { System.out.println(entry); } }

LinkedHashMap<String, String> lhm = new LinkedHashMap<>(); ReentrantLock lock = new ReentrantLock(); // 加锁 put lock.lock(); try { lhm.put("a", "1"); } finally { lock.unlock(); } // 加锁 get lock.lock(); try { lhm.get("a"); } finally { lock.unlock(); }

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable { // 存储键值对的 Entry 数组，哈希表的'桶' private transient Entry<?,?>[] table; // 哈希表中实际存储的键值对个数 private transient int count; // 扩容阈值 = 容量 × 加载因子，元素数≥阈值时触发扩容 private int threshold; // 加载因子，固定 0.75（不可自定义，JDK 硬编码） private float loadFactor; // 修改次数，用于快速失败机制 private transient int modCount = 0; // 序列化版本号 private static final long serialVersionUID = 1421746759512286392L; }

private static class Entry<K,V> implements Map.Entry<K,V> { final int hash; // 键的哈希值（缓存，避免重复计算） final K key; // 键，final 修饰不可修改 V value; // 值，可修改 Entry<K,V> next;// 下一个 Entry 节点，单向链表指针 Entry(int hash, K key, V value, Entry<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } // 重写 equals、hashCode、setValue 等方法 }

数组索引：0 1 2 3 4 5 6 7 8 9 10 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 桶结构： - A - B→C - D - - - E -

public Hashtable() { // 调用指定容量 + 加载因子构造，初始容量 11，加载因子 0.75 this(11, 0.75f); }

public Hashtable(int initialCapacity) { // 调用指定容量 + 加载因子构造，加载因子固定 0.75 this(initialCapacity, 0.75f); }

public Hashtable(int initialCapacity, float loadFactor) { // 校验参数：容量不能为负，加载因子必须>0 且≤1 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal Load: " + loadFactor); if (initialCapacity == 0) initialCapacity = 1; this.loadFactor = loadFactor; // 初始化 Entry 数组，容量为指定值（无需是 2 的幂） table = new Entry<?,?>[initialCapacity]; // 计算扩容阈值：容量×加载因子，向下取整 threshold = (int)Math.min(initialCapacity * loadFactor, Integer.MAX_VALUE + 1); }

public Hashtable(Map<? extends K, ? extends V> t) { // 初始化容量：取 t.size()×2 和 11 的最大值，避免频繁扩容 this(Math.max(2*t.size(), 11), 0.75f); // 批量添加 Map 中的所有键值对（调用 putAll） putAll(t); }

Hashtable<String, String> ht = new Hashtable<>(); ht.put("name", null); // 抛 NullPointerException（value 为 null） ht.put(null, "Java"); // 抛 NullPointerException（key 为 null）

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % table.length;

// 扩容核心方法，加 synchronized 锁 protected void rehash() { int oldCapacity = table.length; // 保存原数组 Entry<?,?>[] oldMap = table; // 计算新容量：原容量×2 + 1（保证奇数） int newCapacity = (oldCapacity << 1) + 1; // 处理容量溢出，设置为 Integer.MAX_VALUE if (newCapacity - Integer.MAX_VALUE > 0) { if (oldCapacity == Integer.MAX_VALUE) return; // 容量已达最大值，不再扩容 newCapacity = Integer.MAX_VALUE; } // 创建新容量的 Entry 数组 Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; modCount++; // 修改次数 +1，触发快速失败 // 计算新阈值：新容量×加载因子，向下取整 threshold = (int)Math.min(newCapacity * loadFactor, Integer.MAX_VALUE + 1); table = newMap; // 核心：重新哈希所有元素，从原数组复制到新数组 for (int i = oldCapacity ; i-- > 0 ;) { for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) { Entry<K,V> e = old; old = old.next; // 先保存下一个节点，避免链表断裂 // 重新计算新数组的索引 int index = (e.hash & 0x7FFFFFFF) % newCapacity; // 头插法：新节点插入到新数组索引的链表头部 e.next = (Entry<K,V>)newMap[index]; newMap[index] = e; } } }

public synchronized V put(K key, V value) { // 步骤 1：检查 value 是否为 null，抛 NPE if (value == null) { throw new NullPointerException(); } // 步骤 2：检查 table 数组是否为空，首次 put 则初始化 Entry<?,?> tab[] = table; // 计算 key 的哈希值和数组索引（key 为 null 时 hashCode() 抛 NPE） int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; // 步骤 3：遍历对应桶的链表，检查键是否已存在 @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; for(; entry != null ; entry = entry.next) { // 哈希值相同且键 equals，覆盖旧值 if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = value; return old; } } // 步骤 4：键不存在，添加新节点（头插法） addEntry(hash, key, value, index); return null; } // 添加新 Entry 节点的私有方法 private void addEntry(int hash, K key, V value, int index) { modCount++; // 修改次数 +1 Entry<?,?> tab[] = table; // 检查是否需要扩容：元素数≥阈值，且对应桶已有元素 if (count >= threshold) { rehash(); // 扩容 // 扩容后重新计算索引 tab = table; hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; } // 头插法：新节点插入到链表头部 @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>)tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++; // 元素数 +1 }

public synchronized V get(Object key) { Entry<?,?> tab[] = table; // 计算哈希值和索引（key 为 null 抛 NPE） int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; // 遍历链表，匹配哈希值和 equals for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { return (V)e.value; } } return null; }

public synchronized V remove(Object key) { Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>)tab[index]; Entry<K,V> prev = null; // 遍历链表，找到目标节点 while (e != null) { if ((e.hash == hash) && e.key.equals(key)) { modCount++; // 修改次数 +1 // 调整链表指针：删除当前节点 if (prev != null) { prev.next = e.next; } else { tab[index] = e.next; // 目标节点是头节点，直接替换桶的头 } count--; // 元素数 -1 V oldValue = e.value; e.value = null; // 清空引用，便于 GC 回收 return oldValue; } prev = e; e = e.next; } return null; }

public synchronized boolean isEmpty() { return count == 0; } public synchronized int size() { return count; }

public synchronized boolean containsKey(Object key) { // 逻辑与 get() 类似，仅返回是否存在 } public synchronized boolean containsValue(Object value) { // 遍历整个哈希表（所有桶 + 所有链表），时间复杂度 O(n) if (value == null) { throw new NullPointerException(); } Entry<?,?>[] tab = table; for (int i = tab.length ; i-- > 0 ;) { for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) { if (e.value.equals(value)) { return true; } } } return false; }

public synchronized void clear() { Entry<?,?>[] tab = table; modCount++; // 遍历所有桶，清空 Entry 节点的引用，便于 GC 回收 for (int i = tab.length ; i-- > 0 ;) tab[i] = null; count = 0; // 元素数置 0，数组容量不变 }

Hashtable<String, String> ht = new Hashtable<>(); ht.put("name", "Java"); ht.put("age", "25"); ht.put("gender", "male"); // 遍历所有键值对（推荐） for (Map.Entry<String, String> entry : ht.entrySet()) { String key = entry.getKey(); String value = entry.getValue(); System.out.println(key + "=" + value); } // 迭代器方式，支持边遍历边删除 Iterator<Map.Entry<String, String>> it = ht.entrySet().iterator(); while (it.hasNext()) { Map.Entry<String, String> entry = it.next(); if (entry.getKey().equals("age")) { it.remove(); // 安全删除，无异常 } }

// 遍历所有键 for (String key : ht.keySet()) { System.out.println(key); } // 遍历所有值 for (String value : ht.values()) { System.out.println(value); }

// 遍历所有键 Enumeration<String> keyEnum = ht.keys(); while (keyEnum.hasMoreElements()) { String key = keyEnum.nextElement(); System.out.println(key); } // 遍历所有值 Enumeration<String> valueEnum = ht.elements(); while (valueEnum.hasMoreElements()) { String value = valueEnum.nextElement(); System.out.println(value); }

Map<String, String> map = new HashMap<>(); map.put("name", "Java"); map.put(null, "nullKey"); // 支持 null 键 map.put("age", null); // 支持 null 值

Map<String, String> concurrentMap = new ConcurrentHashMap<>(); concurrentMap.put("name", "Java"); concurrentMap.put("age", "25"); // 高并发下安全操作，无需手动加锁

// 包装 HashMap 为线程安全 Map Map<String, String> syncMap = Collections.synchronizedMap(new HashMap<>()); syncMap.put("name", "Java"); // 遍历需手动加锁 synchronized (syncMap) { for (Map.Entry<String, String> entry : syncMap.entrySet()) { System.out.println(entry); } }

public class Properties extends Hashtable<Object, Object> { // 父配置集合：若当前 Properties 无指定键，会从父配置中查找（多层配置兜底） protected Properties defaults; // 序列化版本号 private static final long serialVersionUID = 4112578634029874840L; // 构造方法 public Properties() { this(null); } public Properties(Properties defaults) { this.defaults = defaults; } }

// 设置键值对，强制 String 类型 public Object setProperty(String key, String value) { return put(key, value); // 调用 Hashtable 的 put(Object, Object) } // 获取键值对，返回 String，键不存在返回 null public String getProperty(String key) { Object oval = super.get(key); // 调用 Hashtable 的 get(Object) String sval = (oval instanceof String) ? (String)oval : null; // 自身无值 → 查父配置 defaults → 查系统属性 System.getProperties() return (sval == null && defaults != null) ? defaults.getProperty(key) : sval; }

// 哈希表结构（继承 Hashtable，数组 + 链表，线程安全） 数组索引：0 1 2 ... 5 ... 10 ↓ ↓ ↓ ↓ ↓ 桶结构： k1=v1 - k2=v2 k3=v3→k4=v4 ... - （所有 k/v 均为 String，底层存储为 Object，获取时隐式转换） // 双向链表（JDK1.6+，维护加载/插入顺序） head → k1=v1 → k2=v2 → k3=v3 → k4=v4 → tail // 三级兜底引用 当前 Properties → defaults（父配置）→ System.getProperties()（系统属性）

public Properties() { this(null); // 父配置 defaults 为 null，关闭多层兜底 }

public Properties(Properties defaults) { this.defaults = defaults; // 指定父配置，开启多层兜底 }

Properties props = new Properties(); // 1. 添加/修改配置项 props.setProperty("db.url", "jdbc:mysql://localhost:3306/test"); props.setProperty("db.username", "root"); props.setProperty("db.password", "123456"); // 2. 获取配置项（带默认值，推荐） String url = props.getProperty("db.url", "jdbc:mysql://localhost:3306/default"); String port = props.getProperty("db.port", "3306"); // 键不存在，返回默认值 3306 // 3. 获取配置项（无默认值） String username = props.getProperty("db.username"); // root // 4. 判断是否包含键 boolean hasPwd = props.containsKey("db.password"); // true // 5. 删除配置项 props.remove("db.password");

# 这是注释（#/!开头为注释） db.url=jdbc:mysql://localhost:3306/test db.username=root db.password=123456 # 多行值：末尾加\，下一行继续 db.params=useUnicode=true&characterEncoding=utf8\ &autoReconnect=true # 键值分隔符：= / : / 空格（推荐用=） db.driverClass com.mysql.cj.jdbc.Driver

Properties props = new Properties(); // 从文件加载，使用 FileReader 指定 UTF-8 编码，解决中文乱码 try (Reader reader = new FileReader("src/main/resources/config.properties", StandardCharsets.UTF_8)) { props.load(reader); // 加载配置，保留文件中的顺序 } catch (IOException e) { e.printStackTrace(); }

Properties props = new Properties(); props.setProperty("name", "张三"); props.setProperty("age", "20"); props.setProperty("gender", "男"); // 写入文件，UTF-8 编码，注释为"用户配置" try (Writer writer = new FileWriter("user.properties", StandardCharsets.UTF_8)) { props.store(writer, "User Config"); } catch (IOException e) { e.printStackTrace(); }

#User Config #Mon Jan 29 10:00:00 CST 2026 name=张三 age=20 gender=男

<?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE properties SYSTEM "http://java.sun.com/dtd/properties.dtd"> <properties> <comment>数据库配置</comment> <entry key="db.url">jdbc:mysql://localhost:3306/test</entry> <entry key="db.username">root</entry> </properties>

Properties props = new Properties(); // 加载 XML 配置 try (InputStream in = new FileInputStream("config.xml")) { props.loadFromXML(in); } catch (IOException e) { e.printStackTrace(); } // 写入 XML 配置（UTF-8，注释为"数据库配置"） try (OutputStream out = new FileOutputStream("db.xml")) { props.storeToXML(out, "数据库配置", StandardCharsets.UTF_8.name()); } catch (IOException e) { e.printStackTrace(); }

Properties props = new Properties(); props.setProperty("a", "1"); props.setProperty("b", "2"); props.setProperty("c", "3"); // 推荐：获取 String 类型键集，增强 for 遍历 Set<String> keys = props.stringPropertyNames(); for (String key : keys) { String value = props.getProperty(key); System.out.println(key + "=" + value); // 顺序与插入/加载顺序一致 } // 调试：打印所有配置项到控制台 props.list(System.out);

// 正确：InputStreamReader 指定 UTF-8 编码（兼容所有流场景） try (InputStream in = new FileInputStream("config.properties"); Reader reader = new InputStreamReader(in, StandardCharsets.UTF_8)) { props.load(reader); } // 简化：FileReader 直接指定 UTF-8（JDK11+ 支持，推荐） try (Reader reader = new FileReader("config.properties", StandardCharsets.UTF_8)) { props.load(reader); }

// 正确：OutputStreamWriter 指定 UTF-8 编码 try (OutputStream out = new FileOutputStream("config.properties"); Writer writer = new OutputStreamWriter(out, StandardCharsets.UTF_8)) { props.store(writer, "中文配置"); } // 简化：FileWriter 直接指定 UTF-8（JDK11+ 支持） try (Writer writer = new FileWriter("config.properties", StandardCharsets.UTF_8)) { props.store(writer, "中文配置"); }

// 加载 resources/config/db.properties 配置文件（UTF-8） Properties dbProps = new Properties(); // 类加载器获取资源流（推荐，适配 jar 包） try (InputStream in = PropertiesDemo.class.getClassLoader().getResourceAsStream("config/db.properties"); Reader reader = new InputStreamReader(in, StandardCharsets.UTF_8)) { dbProps.load(reader); // 获取数据库配置 String url = dbProps.getProperty("db.url"); String username = dbProps.getProperty("db.username"); String password = dbProps.getProperty("db.password"); } catch (IOException e) { throw new RuntimeException("加载数据库配置失败", e); }

// 1. 加载全局公共配置 Properties globalProps = new Properties(); try (Reader reader = new FileReader("global.properties", StandardCharsets.UTF_8)) { globalProps.load(reader); // 含：app.name=JavaDemo, app.version=1.0 } // 2. 加载模块配置，指定全局配置为父配置 Properties userProps = new Properties(globalProps); try (Reader reader = new FileReader("user-module.properties", StandardCharsets.UTF_8)) { userProps.load(reader); // 含：user.maxAge=20，无 app.name/app.version } // 3. 获取配置：模块有则取模块，无则取全局 String userMaxAge = userProps.getProperty("user.maxAge"); // 20（模块配置） String appName = userProps.getProperty("app.name"); // JavaDemo（全局配置兜底） String appVersion = userProps.getProperty("app.version"); // 1.0（全局配置）

// 动态创建配置项 Properties userConfig = new Properties(); userConfig.setProperty("user.id", "1001"); userConfig.setProperty("user.name", "张三"); userConfig.setProperty("user.theme", "dark"); userConfig.setProperty("user.language", "zh-CN"); // 写入用户目录下的配置文件 String userHome = System.getProperty("user.home"); // 获取用户主目录 File configFile = new File(userHome, ".javademo/user.config"); // 确保父目录存在 if (!configFile.getParentFile().exists()) { configFile.getParentFile().mkdirs(); } // 写入文件（UTF-8） try (Writer writer = new FileWriter(configFile, StandardCharsets.UTF_8)) { userConfig.store(writer, "User Personal Config"); } catch (IOException e) { e.printStackTrace(); }

Properties sysProps = System.getProperties(); // 读取系统属性 String javaVersion = sysProps.getProperty("java.version"); // Java 版本 String userDir = sysProps.getProperty("user.dir"); // 项目运行目录 String osName = sysProps.getProperty("os.name"); // 操作系统名称 // 直接通过 System.getProperty 获取（更简洁） String javaHome = System.getProperty("java.home"); // JDK 安装目录

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { // 核心：存储 HashSet 元素的 HashMap 实例，元素作为键，值为 PRESENT private transient HashMap<E,Object> map; // 固定值：所有 HashMap 键对应的默认值，节省内存（静态常量，唯一实例） private static final Object PRESENT = new Object(); // 序列化版本号 private static final long serialVersionUID = -5024744406713321676L; }

// HashSet 的元素：A、B、C、null（对应 HashMap 的键） HashMap 键：null A - B→C - ... （数组 + 链表结构，与 HashMap 一致） HashMap 值：PRESENT PRESENT PRESENT ... （所有值均为同一个 PRESENT）

public HashSet() { // 创建默认的 HashMap 实例（容量 16，加载因子 0.75） map = new HashMap<>(); }

public HashSet(int initialCapacity) { // 创建指定容量的 HashMap（加载因子 0.75） map = new HashMap<>(initialCapacity); } public HashSet(int initialCapacity, float loadFactor) { // 创建指定容量 + 加载因子的 HashMap，参数直接透传 map = new HashMap<>(initialCapacity, loadFactor); }

public HashSet(Collection<? extends E> c) { // 创建 HashMap，容量取 c.size()/0.75 和 16 的最大值，避免扩容 map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); // 批量添加集合元素（调用 addAll，底层是 HashMap 的 put） addAll(c); }

public boolean add(E e) { // 委托给 HashMap 的 put 方法：将元素 e 作为键，PRESENT 作为值 // HashMap.put 返回 null：键不存在（添加成功），返回旧值：键已存在（添加失败） return map.put(e, PRESENT) == null; }

public boolean remove(Object o) { // 委托给 HashMap 的 remove 方法：删除键为 o 的键值对，返回对应的值 // 若返回 PRESENT：元素存在（删除成功），返回 null：元素不存在（删除失败） return map.remove(o) == PRESENT; }

public boolean contains(Object o) { // 直接委托给 HashMap 的 containsKey 方法（判断键是否存在） return map.containsKey(o); }

public boolean isEmpty() { // 委托给 HashMap 的 isEmpty（判断键值对数量是否为 0） return map.isEmpty(); } public int size() { // 委托给 HashMap 的 size（返回键值对数量，即 Set 的元素个数） return map.size(); }

public void clear() { // 委托给 HashMap 的 clear（清空所有键值对，哈希表容量不变） map.clear(); }

public Object[] toArray() { // 委托给 HashMap 的 keySet().toArray（将 HashMap 的键集转为数组） return map.keySet().toArray(); } public <T> T[] toArray(T[] a) { // 泛型版数组转换，同样委托给 HashMap 的键集 return map.keySet().toArray(a); }

HashSet<String> set = new HashSet<>(); set.add("Java"); set.add("Python"); set.add("C++"); set.add(null); // 支持一个 null // 增强 for 循环：底层基于 HashMap 键集的迭代器，无序遍历 for (String s : set) { System.out.println(s); // 输出顺序不固定，可能为：null, Java, C++, Python }

Iterator<String> it = set.iterator(); while (it.hasNext()) { String s = it.next(); if (s == null || s.equals("Python")) { it.remove(); // 迭代器删除，无 ConcurrentModificationException } }

// forEach：底层基于迭代器，支持 Lambda 表达式，语法简洁 set.forEach(s -> System.out.println(s));

// 自定义类：未重写 hashCode() 和 equals() class Student { private String name; private int age; public Student(String name, int age) { this.name = name; this.age = age; } } // 测试：属性相同的两个对象被认为是不同元素 public static void main(String[] args) { HashSet<Student> set = new HashSet<>(); set.add(new Student("张三", 20)); set.add(new Student("张三", 20)); // 未重写，会被存入，Set 大小为 2 System.out.println(set.size()); // 输出：2（错误，预期为 1） }

class Student { private String name; private int age; public Student(String name, int age) { this.name = name; this.age = age; } // 重写 equals：基于 name 和 age 判断相等 @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; return age == student.age && Objects.equals(name, student.name); } // 重写 hashCode：基于 name 和 age 计算哈希值 @Override public int hashCode() { return Objects.hash(name, age); // JDK7+ 的 Objects 工具类，简洁高效 } }
// 测试：重复元素被过滤 public static void main(String[] args) { HashSet<Student> set = new HashSet<>(); set.add(new Student("张三", 20)); set.add(new Student("张三", 20)); // 重写后，添加失败，Set 大小为 1 System.out.println(set.size()); // 输出：1（正确） }

// 包装为线程安全的 HashSet Set<String> syncSet = Collections.synchronizedSet(new HashSet<>()); // 并发操作：add/remove/get 均为线程安全 syncSet.add("Java"); syncSet.remove("Python"); syncSet.contains("C++"); // 遍历需手动加锁（迭代器非线程安全，避免快速失败） synchronized (syncSet) { for (String s : syncSet) { System.out.println(s); } }

// 基于 ConcurrentHashMap 构建线程安全的 Set（推荐，高并发首选） Set<String> concurrentSet = Collections.newSetFromMap(new ConcurrentHashMap<>()); // 高并发操作：无需手动加锁，遍历也无需加锁（弱一致性，不抛异常） concurrentSet.add("Java"); concurrentSet.remove("Python"); for (String s : concurrentSet) { System.out.println(s); }

// 写时复制的线程安全 Set Set<String> cowSet = new CopyOnWriteArraySet<>(); cowSet.add("Java"); cowSet.forEach(s -> System.out.println(s));

// LinkedHashSet 无新增属性，所有属性均来自 HashSet public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { private static final long serialVersionUID = -2851667679971038690L; } // 父类 HashSet 的核心属性 public class HashSet<E> { private transient HashMap<E,Object> map; // 实际指向 LinkedHashMap 实例 private static final Object PRESENT = new Object(); }

// 哈希表结构（数组 + 链表，与 HashMap/LinkedHashMap 一致） 数组索引：0 1 2 ... 5 ... 15 ↓ ↓ ↓ ↓ ↓ 桶结构：null A - ... B→C ... - （键：Set 元素，值：PRESENT） // 双向链表结构（维护插入顺序：null→A→B→C，LinkedHashMap 的核心） head → null (before:null, after:A) → A (before:null, after:B) → B (before:A, after:C) → C (before:B, after:null) → tail

public LinkedHashSet() { // 调用父类 HashSet 的构造方法，初始化 LinkedHashMap（容量 16，加载因子 0.75） super(16, 0.75f, true); }

public LinkedHashSet(int initialCapacity) { // 初始化 LinkedHashMap（指定容量，加载因子 0.75） super(initialCapacity, 0.75f, true); } public LinkedHashSet(int initialCapacity, float loadFactor) { // 初始化 LinkedHashMap（指定容量 + 加载因子，透传参数） super(initialCapacity, loadFactor, true); }

public LinkedHashSet(Collection<? extends E> c) { // 初始化 LinkedHashMap，容量取 c.size()/0.75 和 16 的最大值，避免扩容 super(Math.max((int) (c.size()/.75f) + 1, 16), 0.75f, true); // 复用 HashSet 的 addAll 方法，批量添加并去重，双向链表按传入集合的迭代顺序构建 addAll(c); }

// 直接继承 HashSet 的 add 方法，无任何修改 public boolean add(E e) { return map.put(e, PRESENT) == null; }

// 直接继承 HashSet 的 remove 方法 public boolean remove(Object o) { return map.remove(o) == PRESENT; }

// 直接继承 HashSet 的 contains 方法 public boolean contains(Object o) { return map.containsKey(o); }

LinkedHashSet<String> lhs = new LinkedHashSet<>(); lhs.add("Java"); lhs.add("Python"); lhs.add("C++"); lhs.add(null); lhs.add("Python"); // 重复添加，顺序不变 // 遍历顺序：Java → Python → C++ → null（与首次插入顺序完全一致） for (String s : lhs) { System.out.println(s); }

Iterator<String> it = lhs.iterator(); while (it.hasNext()) { String s = it.next(); if (s == null || s.equals("C++")) { it.remove(); // 安全删除，不破坏双向链表结构 } } // 删除后遍历：Java → Python（仍保持剩余元素的插入顺序）

// 底层基于迭代器，按插入顺序遍历，语法简洁 lhs.forEach(s -> System.out.println(s));

class User { private String id; private String name; public User(String id, String name) { this.id = id; this.name = name; } // 基于业务主键 id 重写 equals @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; User user = (User) o; return Objects.equals(id, user.id); } // 基于 id 重写 hashCode @Override public int hashCode() { return Objects.hash(id); } }
// 测试：属性 id 相同的 User 会被去重，保留首次插入顺序 public static void main(String[] args) { LinkedHashSet<User> lhs = new LinkedHashSet<>(); lhs.add(new User("1", "张三")); lhs.add(new User("1", "张三")); // 重复，添加失败 lhs.add(new User("2", "李四")); System.out.println(lhs.size()); // 输出：2（正确去重） }

// 包装为线程安全的 LinkedHashSet，保留插入顺序 Set<String> syncLhs = Collections.synchronizedSet(new LinkedHashSet<>()); // 并发操作：add/remove/contains 均为线程安全 syncLhs.add("Java"); syncLhs.remove("Python"); // 遍历必须手动加锁（迭代器非线程安全，避免快速失败） synchronized (syncLhs) { for (String s : syncLhs) { System.out.println(s); } }

// 引入 Guava 依赖，创建 ConcurrentLinkedHashMap 实例 Map<String, Object> concurrentLinkedMap = new ConcurrentLinkedHashMap.Builder<String, Object>() .initialCapacity(16) .build(); // 基于高并发有序 Map 构建线程安全的 LinkedHashSet Set<String> concurrentLhs = Collections.newSetFromMap(concurrentLinkedMap); // 高并发操作：无需手动加锁，保留插入顺序，遍历无快速失败 concurrentLhs.add("Java"); concurrentLhs.add("Python"); for (String s : concurrentLhs) { System.out.println(s); // 仍为插入顺序 }

// 写时复制的线程安全有序 Set Set<String> cowSet = new CopyOnWriteArraySet<>(); cowSet.add("Java"); cowSet.add("Python"); cowSet.add("C++"); // 高并发遍历：无锁，效率极高，顺序为插入顺序 cowSet.forEach(s -> System.out.println(s)); // 写操作：复制整个数组，成本较高，适合修改少的场景 cowSet.remove("Python");

对比维度	JDK1.7	JDK1.8
底层结构	数组 + 链表	数组 + 链表 + 红黑树
链表插入方式	头插法（多线程成环风险）	尾插法（避免成环，保持顺序）
扩容节点迁移	头插法（链表反转，重算哈希）	尾插法（保持顺序，无需重算哈希）
哈希计算	4 次扰动 +1 次异或（复杂）	1 次异或 +1 次无符号右移（简化）
桶索引计算	封装`indexFor`方法	内联`(n-1) & hash`，取消方法
树化机制	无	链表≥8 且容量≥64 时树化
退化机制	无	红黑树≤6 时退化为链表
初始化逻辑	构造时计算阈值，数组懒加载	极致懒加载，首次 put 才初始化数组 + 阈值
批量插入	遍历逐个 put，无容量预计算	`putMapEntries`预计算容量，减少扩容
查询效率	链表 O(n)，长链表性能差	红黑树 O(logn)，长链表性能大幅提升
核心统一方法	增删查各有独立逻辑	新增`putVal/removeNode/getNode`，统一处理链表/红黑树

特性	LinkedHashMap	HashMap
有序性	有序（插入/访问顺序）	无序（由哈希值决定）
底层结构	数组 + 链表/红黑树 + 双向链表	数组 + 链表/红黑树
节点类型	Entry（继承 HashMap.Node，新增 before/after 指针）	Node/TreeNode
遍历方式	基于双向链表（高效，无空桶）	基于哈希表（需遍历空桶）
重复 put 已存在键	不改变有序性	无有序性概念
访问节点后行为	访问顺序模式下移到尾部	无特殊行为
时间复杂度	平均 O(1)（略高于 HashMap，维护双向链表）	平均 O(1)
内存占用	稍高（节点多 2 个指针）	稍低
适用场景	需保留顺序、LRU 缓存	纯键值对存储，追求极致性能
核心优势	有序且哈希表效率	极致的单线程性能

特性	LinkedHashMap	TreeMap
有序实现	双向链表（插入/访问顺序，无需排序）	红黑树（键的自然顺序/自定义 Comparator）
时间复杂度	平均 O(1)（增删查）	O(logn)（增删查，红黑树操作）
键要求	无要求（无需实现 Comparable）	需实现 Comparable 或自定义 Comparator
null 键支持	允许 1 个 null 键	不支持 null 键（会抛 ClassCastException）
底层结构	哈希表 + 双向链表	纯红黑树
遍历效率	高（双向链表直接遍历）	中（红黑树中序遍历）
适用场景	保留插入/访问顺序、LRU 缓存	需按键排序（升序/降序）的场景
性能开销	低（仅维护双向链表）	高（红黑树旋转平衡）

特性	LinkedHashMap	ConcurrentLinkedHashMap
线程安全	否（JDK 原生）	是（第三方扩展，Guava 提供）
LRU 实现	重写`removeEldestEntry`即可	原生支持 LRU，无需自定义
底层结构	哈希表 + 双向链表	哈希表 + 双向链表
null 支持	支持	不支持
适用场景	单线程 LRU 缓存	高并发 LRU 缓存

特性	Hashtable	HashMap
线程安全	是（synchronized 全局锁）	否（单线程高效）
null 支持	键/值均不支持（抛 NPE）	键允许 1 个 null、值允许多个 null
底层结构	数组 + 单向链表（JDK1.0 至今）	数组 + 链表 + 红黑树（JDK1.8+，链表≥8 转红黑树）
默认初始容量	11	16（2 的幂）
扩容机制	原容量×2+1（保证奇数）	原容量×2（保证 2 的幂，位运算优化索引）
哈希计算	直接用 hashCode()，hash%length	哈希扰动（hashCode() 高 16 位^低 16 位），hash&(length-1)
加载因子	固定 0.75	默认 0.75，支持自定义
继承/实现	继承 Dictionary+ 实现 Map	实现 Map，继承 AbstractMap
遍历方式	迭代器/Enumeration	迭代器/forEach（JDK8+）
并发效率	极低（全局锁串行执行）	无锁，单线程效率极高
扩容触发	元素数 ≥ 容量×加载因子	元素数 ≥ 容量×加载因子
官方态度	弃用（仅兼容旧代码）	推荐（单线程 Map 首选）

特性	Hashtable	ConcurrentHashMap
线程安全实现	synchronized 全局锁（方法级）	JDK1.7：分段锁（Segment）；JDK1.8+：CAS+synchronized（节点级）
并发效率	极低（所有操作串行）	极高（多线程并行操作，无全局锁）
null 支持	键/值均不支持	键/值均不支持
底层结构	数组 + 单向链表	JDK1.8+：数组 + 链表 + 红黑树
扩容机制	原容量×2+1	原容量×2（2 的幂）
快速失败	支持（遍历抛异常）	弱一致性（遍历不抛异常，允许脏读）
适用场景	低并发兼容旧代码	高/低并发线程安全场景

特性	Properties	Hashtable	LinkedHashMap	HashMap
键值类型	强制 String（底层隐式转换）	Object/Object	Object/Object	Object/Object
核心定位	配置文件读写	通用线程安全 Map	通用有序 Map	通用高性能 Map
线程安全	是（继承 Hashtable）	是（方法加 synchronized）	否	否
有序性	是（JDK1.6+，插入/加载顺序）	否（JDK1.6 前）	是（插入/访问顺序）	否
配置专属方法	有（load/store/XML）	无	无	无
默认值获取	支持（getProperty）	无	无	无
系统属性关联	支持	无	无	无
平均时间复杂度	O(1)（继承哈希表）	O(1)	O(1)	O(1)
空键/空值支持	不支持 null 键/值	不支持 null 键/值	支持 1 个 null 键/多 null 值	支持 1 个 null 键/多 null 值
适用场景	配置文件（.properties）读写	高并发通用键值存储	有序通用键值存储	非并发通用键值存储

方法名	功能	核心特点
`setProperty(String key, String value)`	添加/修改配置项	键存在则覆盖值，返回旧值；键不存在则添加，返回 null
`getProperty(String key)`	获取配置项	三级兜底（当前→父配置→系统属性），无则返回 null
`getProperty(String key, String defaultValue)`	获取配置项（带默认值）	最常用！键不存在时直接返回默认值，避免空指针
`remove(Object key)`	删除配置项	继承 Hashtable，键为 Object，实际建议传 String
`containsKey(Object key)`	判断是否包含键	继承 Hashtable，线程安全

特性	Properties	Yml/Yaml
结构	扁平键值对（key=value）	层级化（缩进表示层级）
可读性	简单配置友好，复杂配置繁琐	复杂层级配置友好，可读性高
数据类型	仅支持 String，需手动转换	原生支持 String/int/bool/list/map
解析工具	JDK 原生支持（Properties 类）	需第三方依赖（如 Spring Boot 的 snakeyaml）
适用场景	轻量级、简单、无层级的基础配置	复杂、层级化、多数据类型的业务配置

特性	HashSet	LinkedHashSet
底层实现	基于 HashMap	基于 LinkedHashMap
有序性	无序（哈希表顺序）	有序（插入顺序/访问顺序）
底层结构	数组 + 链表/红黑树	数组 + 链表/红黑树 + 双向链表
遍历效率	中（需遍历哈希表空桶）	高（基于双向链表，无空桶）
内存占用	低	稍高（节点多 2 个指针）
插入性能	极致 O(1)（无额外维护）	略低（维护双向链表）
适用场景	纯去重，无需有序	去重 + 保留插入顺序
重复元素处理	覆盖键，返回 false	覆盖键，返回 false

特性	HashSet	TreeSet
底层实现	基于 HashMap（哈希表）	基于 TreeMap（红黑树）
有序性	无序	有序（自然顺序/自定义 Comparator）
不可重复实现	哈希值 +equals	自然比较/Comparator
null 元素支持	允许 1 个 null	不支持 null（抛 ClassCastException）
时间复杂度	平均 O(1)，最坏 O(n)	O(logn)（红黑树操作）
元素要求	重写 hashCode+equals	实现 Comparable/自定义 Comparator
遍历方式	哈希表遍历	红黑树中序遍历
适用场景	纯去重，追求极致性能	去重 + 按键排序
扩容机制	哈希表扩容（×2）	无扩容，动态平衡红黑树

特性	HashSet	ArraySet（Android）
底层实现	哈希表	有序数组
时间复杂度	平均 O(1)	O(logn)（二分查找）
内存占用	高（哈希表冗余）	低（无冗余）
数据量适配	大数据量	小数据量（<1000）
插入性能	大数据量更优	小数据量更优
有序性	无序	有序（自然顺序）

HashSet 特性	底层 HashMap 的实现依据
不可重复	HashMap 的键唯一性（hashCode+equals）
无序	HashMap 的哈希表遍历顺序（由 hashCode 决定）
支持一个 null 元素	HashMap 允许一个 null 键
平均 O(1) 时间复杂度	HashMap 的哈希表增删查效率
快速失败机制	继承 HashMap 的 modCount
扩容机制（默认 16，0.75）	复用 HashMap 的扩容规则

维度	HashSet	LinkedHashSet	TreeSet
底层实现	HashMap（哈希表）	LinkedHashMap（哈希表 + 双向链表）	TreeMap（红黑树）
有序性	无序	有序（插入顺序）	有序（自然/自定义顺序）
唯一性实现	hashCode+equals	hashCode+equals	Comparable/Comparator
null 支持	允许 1 个 null	允许 1 个 null	不支持 null
时间复杂度	平均 O(1)	平均 O(1)	O(logn)
内存占用	低	稍高	中
元素要求	重写 hashCode+equals	重写 hashCode+equals	实现 Comparable/自定义 Comparator

LinkedHashSet 特性	底层实现依据
不可重复	HashSet 的包装逻辑+LinkedHashMap 的键唯一性（hashCode+equals）
插入有序	LinkedHashMap 的双向链表维护插入顺序
支持一个 null 元素	LinkedHashMap 允许一个 null 键
平均 O(1) 时间复杂度	LinkedHashMap 的哈希表结构
遍历效率高	LinkedHashMap 的双向链表遍历（无空桶）
快速失败机制	继承 LinkedHashMap 的 modCount
扩容不破坏有序	LinkedHashMap 扩容时保留双向链表顺序

方法名	功能	时间复杂度
`size()`	获取元素个数	O(1)
`isEmpty()`	判断是否为空	O(1)
`clear()`	清空所有元素	O(n)
`toArray()`	转换为数组（插入顺序）	O(n)
`iterator()`	获取迭代器（插入顺序）	O(1)

JDK 核心哈希容器源码深度解析：HashMap、LinkedHashMap 等

HashMap

前置基础：核心成员变量

JDK1.7

JDK1.8

一、初始化：4 个构造方法

1. 无参构造：public HashMap()

核心作用

JDK1.7 源码 + 解析

JDK1.8 源码 + 解析

阅读重点

2. 指定初始容量：public HashMap(int initialCapacity)

核心作用

JDK1.7/1.8 通用源码 + 解析

阅读重点

3. 指定初始容量 + 负载因子：public HashMap(int initialCapacity, float loadFactor)

核心作用

核心源码

阅读重点

4. 传入 Map 构造：public HashMap(Map<? extends K, ? extends V> m)

核心作用

JDK1.7 源码 + 解析

JDK1.8 源码 + 解析

阅读重点

二、添加/修改：核心方法

1. 核心插入：public V put(K key, V value)

核心作用

JDK1.7 源码 + 解析

JDK1.8 源码 + 解析（核心简化，新增树化）

核心差异&阅读重点

2. 批量添加：public void putAll(Map<? extends K, ? extends V> m)

核心作用

核心源码

阅读重点

三、容量管理：扩容核心方法 final Node<K,V>[] resize()

核心作用

JDK1.7 源码 + 解析

JDK1.8 源码 + 解析（优化迁移，新增红黑树拆分）

核心差异&阅读重点

四、删除元素：核心方法

1. 核心删除：public V remove(Object key)

核心作用

JDK1.7 源码 + 解析

JDK1.8 源码 + 解析

阅读重点

2. 清空集合：public void clear()

核心源码 + 解析（JDK1.7/1.8 逻辑一致）

阅读重点

五、查询元素：核心方法

1. 核心查询：public V get(Object key)

核心作用

JDK1.7 源码 + 解析

JDK1.8 源码 + 解析

核心差异&阅读重点

2. 包含判断：public boolean containsKey(Object key)

核心源码

阅读重点

六、JDK1.7/1.8 核心差异总表

LinkedHashMap

前置基础：核心特性&设计定位

核心定位

核心特性

与核心 Map 的对比（开发/面试必问）

1. LinkedHashMap vs HashMap（核心继承关系，有序 vs 无序）

2. LinkedHashMap vs TreeMap（有序 Map 的两大实现）

3. LinkedHashMap vs ConcurrentLinkedHashMap

一、底层核心原理：HashMap+ 双向链表

1. 核心底层属性

2. 节点定义：继承 HashMap.Node 并新增双向链表指针

3. 底层结构示意图（插入顺序，容量 16）

4. 有序模式核心逻辑

（1）插入顺序（默认，accessOrder=false）

（2）访问顺序（accessOrder=true）

二、核心构造方法

1. 空参构造：new LinkedHashMap<>()

2. 指定初始容量/加载因子：new LinkedHashMap(int initialCapacity)/new LinkedHashMap(int initialCapacity, float loadFactor)

3. 传入 Map 初始化：new LinkedHashMap(Map<? extends K, ? extends V> m)

4. 核心构造：new LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

关键注意点

三、核心底层逻辑：双向链表的维护（新增/访问/删除）

1. 无参构造：`public HashMap()`

2. 指定初始容量：`public HashMap(int initialCapacity)`

3. 指定初始容量 + 负载因子：`public HashMap(int initialCapacity, float loadFactor)`

4. 传入 Map 构造：`public HashMap(Map<? extends K, ? extends V> m)`

1. 核心插入：`public V put(K key, V value)`

2. 批量添加：`public void putAll(Map<? extends K, ? extends V> m)`

三、容量管理：扩容核心方法 `final Node<K,V>[] resize()`

1. 核心删除：`public V remove(Object key)`

2. 清空集合：`public void clear()`

1. 核心查询：`public V get(Object key)`

2. 包含判断：`public boolean containsKey(Object key)`

1. 空参构造：`new LinkedHashMap<>()`

2. 指定初始容量/加载因子：`new LinkedHashMap(int initialCapacity)`/`new LinkedHashMap(int initialCapacity, float loadFactor)`

3. 传入 Map 初始化：`new LinkedHashMap(Map<? extends K, ? extends V> m)`

4. 核心构造：`new LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)`

1. 查询方法：`get(Object key)`（重写，支持访问顺序）

2. 包含值判断：`containsValue(Object value)`（重写，效率更高）

4. LRU 缓存实现：重写 `removeEldestEntry(Map.Entry<K,V> eldest)`

1. 空参构造：`new Hashtable<>()`

2. 指定初始容量：`new Hashtable(int initialCapacity)`

3. 指定初始容量 + 加载因子：`new Hashtable(int initialCapacity, float loadFactor)`

4. 传入 Map 初始化：`new Hashtable(Map<? extends K, ? extends V> t)`

1. 新增/修改键值对：`put(K key, V value)`（核心）

2. 查询键值对：`get(Object key)`（核心）

3. 删除键值对：`remove(Object key)`（核心）

（1）判空/获取大小：`isEmpty()`/`size()`

（2）包含判断：`containsKey(Object key)`/`containsValue(Object value)`

（3）清空哈希表：`clear()`