php 手写哈希表需用数组 + 链地址法实现：定义 hash 函数取模定位桶，插入时查重更新或追加，查找时遍历桶比对 key；负载因子超 0.75 时扩容至 2 倍并 rehash 迁移。
PHP 中如何手写一个简单的哈希表（Hash Table）
PHP 数组本身就是底层基于哈希表实现的，但面试中常要求“不依赖内置数组”，手动模拟哈希表的核心逻辑：插入、查找、扩容、处理冲突。关键不是造轮子，而是考察对哈希原理、数组 + 链表 / 开放寻址、负载因子等概念的理解。
核心结构设计：数组 + 链地址法
用一个固定大小的数组存储桶（bucket），每个桶是一个链表（可用 PHP 的数组或自定义节点类模拟），解决哈希冲突。
- 定义哈希函数：比如 hash($key) = crc32((string)$key) % $capacity，确保结果落在数组索引范围内
- 每个桶存键值对数组，如 [$key => $value]，或更规范地用关联数组列表：[[‘key’=>’a’,’val’=>1], [‘key’=>’b’,’val’=>2]]
- 插入时先算 hash，再遍历对应桶检查 key 是否已存在（更新值），否则追加新项
- 查找时同样先 hash 定位桶，再线性遍历比对 key
支持动态扩容与负载因子控制
当元素总数 / 桶数量 > 负载因子（如 0.75），就重建哈希表：新建更大容量（如 ×2）的桶数组，把所有旧数据 rehash 迁移过去。
- 初始化容量建议设为 16（2 的幂），方便位运算优化（但面试中用取模也完全可接受）
- 扩容后必须重新计算每个 key 的 hash 值，因为 % 新容量 结果变了
- 注意迁移过程要保持键值对完整，不能漏掉某个桶里的任意一项
简化可运行示例（无类封装，突出逻辑）
以下是一个去除了工程细节、仅保留主干逻辑的 PHP 实现，适合白板或快速编码环节：
立即学习 “PHP 免费学习笔记（深入）”；
$capacity = 16; $table = array_fill(0, $capacity, []); // 初始化空桶数组 $size = 0; $loadFactor = 0.75; <p>function hash($key, $cap) {return abs(crc32((string)$key)) % $cap; }</p><p>function put(&$table, &$size, &$capacity, $key, $value) {global $loadFactor; if ($size >= $capacity <em> $loadFactor) {// 扩容：复制旧数据到新表 $oldTable = $table; $capacity </em>= 2; $table = array_fill(0, $capacity, []); $size = 0; foreach ($oldTable as $bucket) {foreach ($bucket as $pair) {put($table, $size, $capacity, $pair['key'], $pair['val']); } } }</p><pre class='brush:php;toolbar:false;'>$index = hash($key, $capacity); $bucket = &$table[$index]; // 查重并更新 foreach ($bucket as &$pair) {if ($pair['key'] === $key) {$pair['val'] = $value; return; } } // 新增 $bucket[] = ['key' => $key, 'val' => $value]; $size++;}
function get($table, $key, $capacity) {$index = hash($key, $capacity); foreach ($table[$index] as $pair) {if ($pair[‘key’] === $key) {return $pair[‘val’]; } } return null; // 未找到 }
// 使用示例 put($table, $size, $capacity, “name”, “Alice”); put($table, $size, $capacity, “age”, 30); echo get($table, “name”, $capacity); // Alice
面试加分点提醒
说完基础实现后，可简要提一嘴进阶方向，展现深度：
- 开放寻址法（线性探测 / 二次探测）相比链地址法，内存局部性更好，但删除复杂（需墓碑标记）
- PHP 8.0+ 的 WeakMap 是真正的哈希表应用案例，键只能是对象，自动回收
- 真实 Array 的底层还做了 cache line 对齐、混合结构（小数组用紧凑 C 数组，大数组转哈希）等优化
