Appearance
源码：labs/java/runtime-concurrency/map-concurrency-compare/src/HashMapIndexAlgorithmDemo.java
- 原始路径：
labs/java/runtime-concurrency/map-concurrency-compare/src/HashMapIndexAlgorithmDemo.java - 类型：
java
java
/**
* 演示 JDK 8 HashMap 如何把 key 映射到 table 下标：
* 1) hashCode()
* 2) 扰动：h ^ (h >>> 16)
* 3) 下标：(n - 1) & hash （n 为 2 的幂）
*
* 运行：
* cd labs/java/runtime-concurrency/map-concurrency-compare
* 位运算前置：labs/foundations/bitwise-operators-demo（见
* docs/00-foundations/01-bitwise-operators.md）
* javac -d out src/HashMapIndexAlgorithmDemo.java
* java -cp out HashMapIndexAlgorithmDemo
*/
public class HashMapIndexAlgorithmDemo {
public static void main(String[] args) {
System.out.println("提示：位运算 >>> ^ & 不熟请先读 docs/00-foundations/01-bitwise-operators.md");
System.out.println(" 可运行 Demo：labs/foundations/bitwise-operators-demo\n");
System.out.println("====== HashMap 桶下标计算三步走 ======\n");
demoSingleKey("hello", 16);
System.out.println();
demoSingleKey("world", 16);
System.out.println();
System.out.println("====== 同一 key，不同 table 长度（均为 2 的幂）======\n");
demoTableSizes("android", new int[] { 8, 16, 32, 64 });
System.out.println("\n====== 扰动有无对下标分布的影响（table 长度 n=16）======\n");
demoPerturbationEffect();
System.out.println("\n====== 扩容 rehash：为何 n 为 2 的幂时只需看「多出来的一位」======\n");
demoResizeRehashBit("kotlin", 16);
System.out.println("\n====== 何时扩容？loadFactor 与 threshold ======\n");
demoResizeThreshold();
System.out.println("\n====== 为何 table 长度必须是 2 的幂？======\n");
demoWhyPowerOfTwo();
}
/** 与 JDK 8 HashMap.hash(Object key) 一致（非 null key）。 */
static int hashLikeHashMap(Object key) {
int h = key.hashCode();
return h ^ (h >>> 16);
}
static int indexFor(int hash, int tableLength) {
return (tableLength - 1) & hash;
}
static void demoSingleKey(String key, int tableLength) {
int h = key.hashCode();
int shifted = h >>> 16;
int hash = h ^ shifted;
int index = indexFor(hash, tableLength);
System.out.println("key = \"" + key + "\", table.length n = " + tableLength);
printlnStep("① hashCode()", h);
printlnStep("② h >>> 16", shifted);
printlnStep("③ 扰动 h ^ (h>>>16)", hash);
System.out.println(" 说明：把高 16 位「拌」进低 16 位，让桶下标更分散，减少碰撞。");
printlnMask(tableLength);
printlnStep("④ (n-1) & hash → index", index);
System.out.println(" → 结论：\"" + key + "\" 应放入 table[" + index + "]");
}
static void demoTableSizes(String key, int[] tableLengths) {
int h = key.hashCode();
int hash = h ^ (h >>> 16);
System.out.println("key = \"" + key + "\", 扰动后 hash = " + hash + " (0x" + toHex(hash) + ")");
System.out.println("┌────────┬──────────┬───────────────┬───────────────┐");
System.out.println("│ n │ n - 1 │ 保留低位 bit │ index │");
System.out.println("├────────┼──────────┼───────────────┼───────────────┤");
for (int n : tableLengths) {
int mask = n - 1;
int index = indexFor(hash, n);
int bits = 31 - Integer.numberOfLeadingZeros(n); // log2(n)
System.out.printf("│ %6d │ %8d │ 低 %2d 位 │ %6d │%n",
n, mask, bits, index);
}
System.out.println("└────────┴──────────┴───────────────┴───────────────┘");
System.out.println("n 越大，参与下标的低位越多，桶越细，碰撞概率越低。");
}
/**
* 两个 hashCode 低位相同、高位不同的 key：
* 不做扰动时 (n-1)&h 只低位相同 → 一定进同一桶；
* 扰动后高位参与 XOR → 下标可能分开。
*/
static void demoPerturbationEffect() {
int tableLength = 16;
int lowBits = 0x0000_00AB; // 低 16 位固定
int h1 = 0x1234_00AB; // 高位不同
int h2 = 0x5678_00AB; // 高位不同
int rawIndex1 = indexFor(h1, tableLength);
int rawIndex2 = indexFor(h2, tableLength);
int mixed1 = indexFor(h1 ^ (h1 >>> 16), tableLength);
int mixed2 = indexFor(h2 ^ (h2 >>> 16), tableLength);
System.out.println("构造两个 hashCode：低位相同 (…00AB)，高位不同");
printlnStep("keyA hashCode", h1);
printlnStep("keyB hashCode", h2);
System.out.println();
System.out.println("【不做扰动】index = (n-1) & hashCode");
System.out.println(" keyA → table[" + rawIndex1 + "]");
System.out.println(" keyB → table[" + rawIndex2 + "]"
+ (rawIndex1 == rawIndex2 ? " ← 低位相同，必然同桶碰撞" : ""));
System.out.println();
System.out.println("【JDK8 扰动后】index = (n-1) & (h ^ (h>>>16))");
System.out.println(" keyA → table[" + mixed1 + "]");
System.out.println(" keyB → table[" + mixed2 + "]"
+ (mixed1 != mixed2 ? " ← 高位参与后，下标分开" : ""));
}
/**
* 扩容 2 倍时：新下标要么是 oldIndex，要么是 oldIndex + oldCap。
* 判断依据： (hash & oldCap) == 0 留原桶，否则进 oldIndex + oldCap。
*/
static void demoResizeRehashBit(String key, int oldCap) {
int hash = hashLikeHashMap(key);
int oldIndex = indexFor(hash, oldCap);
int newCap = oldCap * 2;
int newIndex = indexFor(hash, newCap);
int highBit = hash & oldCap; // 等价于看「多出来的那一位」
System.out.println("key = \"" + key + "\", 从 n=" + oldCap + " 扩容到 n=" + newCap);
printlnStep("扰动后 hash", hash);
System.out.println(" 扩容前 index = (n-1) & hash = " + oldIndex);
System.out.println(" hash & oldCap = " + highBit
+ (highBit == 0 ? " → 留在 table[" + oldIndex + "]" : " → 迁到 table[" + (oldIndex + oldCap) + "]"));
System.out.println(" 扩容后 index = (2n-1) & hash = " + newIndex
+ " （应与上面推断一致）");
/*
* 静态阅读参考输出（kotlin, oldCap=16）：
* 扩容前 index = 8
* hash & oldCap = 0 → 留在 table[8]
*/
}
/**
* 默认 loadFactor=0.75：threshold = capacity * 0.75。
* 当 put 后 size > threshold 时，capacity 扩为 2 倍并 rehash。
*/
static void demoResizeThreshold() {
int capacity = 16;
float loadFactor = 0.75f;
int threshold = (int) (capacity * loadFactor);
System.out.println("比喻：16 个柜子，管理员规定「放满 75% 就换一排更大的柜子」");
System.out.println(" capacity = " + capacity + " （当前柜子数 n）");
System.out.println(" loadFactor= " + loadFactor + " （负载因子，默认 0.75）");
System.out.println(" threshold = capacity × loadFactor = " + threshold + " （扩容红线）");
System.out.println();
for (int sizeAfterPut = 10; sizeAfterPut <= 14; sizeAfterPut++) {
boolean needResize = sizeAfterPut > threshold;
System.out.printf(" 第 %2d 次 put 后 size=%d → %s%n",
sizeAfterPut, sizeAfterPut,
needResize ? "⚠️ size > " + threshold + "，触发扩容：16 → 32" : "未超红线，不扩容");
}
System.out.println();
System.out.println("扩容时：newCap = oldCap * 2；每个桶内节点按 hash&oldCap 迁到原位或 原index+oldCap。");
}
/**
* n 不是 2 的幂时，(n-1) 的掩码中间会出现 0，无法干净映射 0..n-1。
*/
static void demoWhyPowerOfTwo() {
int hash = 0b0000_0000_0000_0000_0000_0000_0010_1011; // 43
int indexPow2 = (16 - 1) & hash;
int indexBad = (15 - 1) & hash; // n=15，非 2 的幂
System.out.println("同一个 hash，不同 table 长度：");
printBits("hash", hash);
printBits("n=16, mask=15", 15);
printBits("index (16-1)&hash", indexPow2);
System.out.println(" → n=16 时 mask 低 4 位全 1，index 一定在 0~15");
System.out.println();
printBits("n=15, mask=14", 14);
printBits("index (14)&hash", indexBad);
System.out.println(" → n=15 时 mask=...1110 中间有 0，(n-1)&hash 不能等价于 %15，");
System.out.println(" 会出现「跳号」浪费槽位，所以 HashMap 强制 capacity 为 2 的幂。");
}
static void printBits(String label, int value) {
System.out.printf(" %-18s = %3d 二进制: %s%n", label, value, toBinary32(value));
}
static void printlnStep(String label, int value) {
System.out.printf(" %-22s = %11d (0x%08X)%n", label, value, value);
System.out.println(" 二进制: " + toBinary32(value));
}
static void printlnMask(int tableLength) {
int mask = tableLength - 1;
System.out.printf(" 掩码 (n-1) = %11d (0x%08X)%n", mask, mask);
System.out.println(" 二进制: " + toBinary32(mask)
+ " ← 低 " + (31 - Integer.numberOfLeadingZeros(tableLength)) + " 位为 1，& 运算只保留 hash 低位");
}
static String toBinary32(int value) {
String raw = Integer.toBinaryString(value);
return String.format("%32s", raw).replace(' ', '0');
}
static String toHex(int value) {
return String.format("%08X", value);
}
}