一、哈希表的基本原理
哈希表（Hash Table）是实现字典（Dictionary）抽象数据类型的最重要数据结构，它在平均情况下提供O(1)时间的插入、删除和查找操作。哈希表的核心思想是：通过哈希函数将键（Key）映射到数组中的索引（Index），从而可能直接定位到目标位置。
哈希表的设计围绕三个核心问题展开：哈希函数的设计（如何将键均匀地映射到索引）、冲突解决策略（当多个键映射到同一个索引时如何处理）、动态扩容（当装载的键值对过多时如何保持性能）。
装载因子（Load Factor）：α = n / m，其中n为已存储的键值对数量，m为哈希表的大小（槽位数量）。装载因子是衡量哈希表“拥挤程度”的关键指标。当α接近某个阈值（如开放寻址法中通常取0.5到0.7，链地址法中可以取到1或更高），哈希表需要进行扩容（Rehashing）——创建更大的数组，将所有元素重新哈希到新数组中。
二、哈希函数的设计
哈希函数h(k)将键k映射到整数{0, 1, ..., m-1}。一个好的哈希函数应满足：确定性（相同的键总是产生相同的哈希值）、均匀性（键被均匀地分布到所有槽位中）、计算高效。
除法哈希法（Division Method）：h(k) = k mod m。简单直观，但m的选择至关重要。如果m是2的幂（如1024），k mod m等价于取k的低位，而高位信息被完全忽略——如果键的分布有规律（如键都是偶数），某些槽位可能完全未被使用。最佳实践是选择m为一个不接近2的幂的素数，如701、1009、2017等。Java的HashMap采用了一种巧妙的替代方式——通过位运算避免取模（见后文）。
乘法哈希法（Multiplication Method）：h(k) = floor(m * (k * A mod 1))，其中A是一个常数（0 < A < 1）。Knuth建议取A ≈ (√5 - 1) / 2 ≈ 0.6180339887（黄金比例的倒数）。乘法哈希法对m的选择不敏感（m可以是任意值），但涉及浮点运算，在早期的整数CPU上较慢。
全域哈希（Universal Hashing）：随机选择哈希函数，使得对于任意两个不同的键，它们冲突的概率不超过1/m（与随机均匀映射相同）。这保证了在期望意义上没有“坏”的输入能导致最坏性能。全域哈希的一种实现：选择一个大素数p > 所有键的取值范围，随机选择a ∈ [1, p-1]和b ∈ [0, p-1]，定义h(k) = ((a * k + b) mod p) mod m。
对于非整数键（如字符串），需要先将其转化为整数。Java的String.hashCode()：s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]。31是一个质数，乘31可以被编译器优化为(i << 5) - i（移位与减法），计算速度快且分布较好。
三、冲突解决：链地址法
链地址法（Separate Chaining）：哈希表的每个槽位指向一个链表（或其他数据结构），所有哈希到同一槽位的键值对存储在该链表中。插入时直接插入链表头部（或尾部）；查找时遍历链表进行键的比对（使用equals()）；删除时从链表中移除。
链地址法的优点是简单直观，装载因子可以超过1（只是链表变长，性能渐进退化）。缺点是额外的内存开销（链表节点对象的头部和指针），以及链表遍历的缓存局部性差（节点在内存中不连续）。
Java的HashMap在JDK 7及之前使用纯链地址法。JDK 8进行了重要优化：当单个槽位的链表长度超过阈值（TREEIFY_THRESHOLD = 8）且哈希表总容量大于等于MIN_TREEIFY_CAPACITY（64）时，该槽位的链表被转化为红黑树，将最坏情况的查找时间从O(N)改善为O(log N)。当红黑树节点数减少到UNTREEIFY_THRESHOLD（6）以下时，重新转化为链表。这种混合结构应对了恶意构造大量哈希冲突进行DoS攻击的场景。
四、冲突解决：开放寻址法
开放寻址法（Open Addressing）：所有元素直接存储在哈希表数组中，没有链表。当插入时如果目标槽位已被占用，按照某种探查序列（Probe Sequence）寻找下一个空槽位。
线性探查（Linear Probing）：h(k, i) = (h'(k) + i) mod m。探查序列为连续的下一个槽位。优点是缓存局部性极好（访问相邻的内存地址），在现代CPU上非常高效。缺点是“一次集群现象”（Primary Clustering）——连续的占用槽位会形成“集群”，新元素插入集群中时，探查序列会扫过整个集群，集群越大越容易吸收新的插入，形成恶性循环。
二次探查（Quadratic Probing）：h(k, i) = (h'(k) + c1*i + c2*i²) mod m。探查的步长随探查次数增加而增大，减轻了一次集群现象。但如果两个键初始哈希值相同，它们的探查序列完全相同，产生“二次集群现象”（Secondary Clustering）。
双重哈希（Double Hashing）：h(k, i) = (h1(k) + i * h2(k)) mod m。使用第二个哈希函数确定探查步长，使得不同键即使初始哈希值相同，探查序列也不同。双重哈希是开放寻址法中理论性质最好的方案——其探查序列分布最接近均匀随机探查。选择m为质数且确保h2(k)与m互质（通常取h2(k) = 1 + (k mod (m-1))），则探查序列覆盖整个哈希表。
开放寻址法要求装载因子严格小于1（通常控制在0.7以下以保证性能），且删除操作需要惰性删除（标记为“已删除”而非物理清除，否则探查序列会断裂）。
五、Java HashMap源码分析
Java的HashMap是工业级哈希表实现的典范。以下分析基于JDK 8。
哈希值计算：HashMap不直接使用key.hashCode()作为数组索引，而是进行了额外的“扰动”操作：hash = key.hashCode() ^ (key.hashCode() >>> 16)。将哈希值的高16位与低16位异或，使得高位的信息参与到低位的计算中——因为最终取模时（通过(n-1) & hash）只用到低位（n为2的幂时，n-1的二进制低位全为1），高位信息的参与使分布更均匀。
索引计算：HashMap使用index = (n - 1) & hash替代hash % n，其中n为2的幂。位与运算比取模运算快得多，这要求数组容量始终为2的幂（由扩容机制保证——每次扩容为原来的2倍）。
扩容机制：当size > threshold（threshold = capacity * loadFactor，默认loadFactor = 0.75）时触发resize()。新容量为旧容量的2倍。重哈希时，由于容量翻倍是乘2，每个键的索引要么保持不变，要么偏移一个旧容量的距离（newIndex = oldIndex 或 newIndex = oldIndex + oldCapacity）。JDK 8利用这个性质进行了优化：不需要重新计算哈希值，只需检查hash的某一位是否被新索引所用。这使扩容效率提升了约一倍。
树化（Treeify）：当链表长度达到8且table长度≥64时，链表转为红黑树。选择8作为阈值是基于泊松分布——在装载因子0.75和良好的哈希函数下，链表长度达到8的概率小于千万分之一（exp(-0.5) * pow(0.5, k) / k!在k=8时约6×10⁻⁸）。实际上，如果真的出现链表长度≥8的情况，极有可能是哈希函数被恶意利用（哈希碰撞DoS攻击），此时红黑树将查找时间从攻击者希望的O(N)降为O(log N)。
为什么线程不安全：HashMap在并发环境下的主要问题是resize时可能产生循环链表（JDK 7，在多线程并发resize时由于链表反转可能导致死循环）和元素丢失（put时覆盖其他线程的写入）。JDK 8修复了循环链表问题（resize时保持链表顺序），但仍然存在数据丢失问题。并发场景应使用ConcurrentHashMap。
六、Android的ArrayMap优化
Android的ArrayMap是对标准HashMap的内存优化方案，特别适合移动设备内存受限的环境。HashMap的每个Entry是一个独立的Node对象（包括hash、key、value、next指针四个字段），对象头开销（通常在12到16字节）甚至超过实际数据。对于存储几百个键值对的场景，HashMap的内存效率低下。
ArrayMap使用两个并行数组：一个int数组存储哈希值，一个Object数组存储键和值（交替存储：key1, value1, key2, value2, …）。两个数组在内存中连续存储，避免了大量小对象的开销。
ArrayMap的查找使用二分查找（在有序的哈希值数组上），时间复杂度为O(log N)而非HashMap的O(1)。但在N较小（<1000）时，连续内存的缓存友好性使得二分查找的实际性能与HashMap的哈希+链表遍历相差无几。当数据量超过约1000时，ArrayMap的性能开始下降，应切换为HashMap。
这是时间与空间的经典权衡——在移动端，内存往往比CPU更稀缺，ArrayMap用适量的CPU开销换取了显著的内存节省（对于小集合，内存占用仅为HashMap的1/3到1/2）。
七、完美哈希
完美哈希（Perfect Hashing）保证在最坏情况下的O(1)查找时间，没有任何冲突。如果键集合是静态的（预先已知且不变），可以使用两级哈希方案构建完美哈希表。
两层哈希方案（Fredman-Komlos-Szemeredi）：第一层使用全域哈希函数将键分到不同的桶中。对每个桶（假设有b个键），使用第二层哈希——选择一个哈希函数使其在该桶的b个键上无冲突。通过精心选择桶的大小和第二层哈希函数（每个桶的第二层哈希表大小为该桶键数量的平方，b²），可以保证在期望O(N)的构建时间内生成一个无冲突的完美哈希表，且总空间为O(N)。
Java的EnumMap在内部使用完美哈希——因为枚举的取值是编译时确定的，直接用该枚举值的序数（ordinal()）作为数组索引，确保O(1)查找且无冲突。
八、面试常见追问
问题一：为什么HashMap的容量必须是2的幂？
核心原因是索引计算使用了(n-1) & hash位运算替代取模。当n是2的幂时（n=2^k），n-1的二进制表示为k个1（如n=16时n-1=15=0b1111），与哈希值进行位与运算等价于取哈希值的低k位，结果均匀分布在[0, n-1]范围内。这个位运算比除法取模快一个数量级。另一个好处是扩容时元素的重新分布极为简单——原来的索引要么保持不变，要么加上旧容量，无需重新计算哈希值。
问题二：String的hashCode为什么选择31作为乘数？
31是一个奇素数（odd prime），素数能产生更均匀的哈希分布（与很多数的最大公约数为1，减少周期性模式）。31的大小适中——太小导致哈希值范围有限容易冲突，太大导致计算溢出（int范围内）太快。31可以被JVM优化为(i << 5) - i（移位减），比通用乘法快。历史上，Kernighan和Ritchie在早期C编译器中就使用31，后续语言沿用了这个选择。实际上，33、131等素数也是常用的乘数（如Java的Arrays.hashCode使用31，而某些库使用33）。
问题三：如何实现一个LRU缓存？
LRU（Least Recently Used）缓存可以使用LinkedHashMap（设置accessOrder=true）或手动结合HashMap和双向链表实现。HashMap提供O(1)查找，双向链表维护访问顺序——最近访问的元素移到链表头部，淘汰时移除链表尾部元素。LinkedHashMap的removeEldestEntry方法允许自定义淘汰策略。如果要求线程安全和高并发，可以使用ConcurrentHashMap加自定义的并发链表，或者直接使用Caffeine等高性能缓存库（使用Window TinyLFU算法，是现代LRU的高级替代）。
