PHP哈希表与冲突解决

PHP哈希表与冲突解决哈希表是PHP数组的底层实现。哈希冲突是不可避免的PHP用链地址法解决冲突。今天说说哈希表的工作原理。PHP的HashTable结构。php// HashTable底层结构// arBuckets: 存储桶数组// nTableSize: 哈希表大小(2的幂)// nTableMask: 哈希掩码// nNumOfElements: 元素数量// nNextFreeElement: 下一个空闲索引$arr [];$arr[key1] value1;$arr[key2] value2;// 插入过程:// 1. 计算键的哈希值 h hash(key1)// 2. 计算槽位 nIndex h nTableMask// 3. 如果槽位为空直接插入// 4. 如果槽位有元素链到冲突链表末尾// 5. 如果冲突太多触发rehash?冲突链的性能影响。phpfunction testCollision(int $size): void{$arr [];$start microtime(true);for ($i 0; $i $size; $i) {$arr[key_{$i}] $i;}$insertTime (microtime(true) - $start) * 1000;$start microtime(true);for ($i 0; $i 10000; $i) {$x $arr[key_ . rand(0, $size - 1)];}$lookupTime (microtime(true) - $start) * 1000;echo 插入{$size}个: {$insertTime}ms, 查找10000次: {$lookupTime}ms\n;}testCollision(1000);testCollision(100000);?Rehash机制。php// 当负载因子超过阈值时// PHP会自动扩容并重新哈希所有元素// 新容量是原来的2倍// 重新计算所有元素的槽位$arr [];$oldSize memory_get_usage(true);for ($i 0; $i 100000; $i) {$arr[$i] $i;}$newSize memory_get_usage(true);echo 100000个元素的数组: . round(($newSize - $oldSize) / 1024, 2) . KB\n;unset($arr);?SplFixedArray没有哈希开销。php$size 500000;$start microtime(true);$fixed new SplFixedArray($size);for ($i 0; $i $size; $i) {$fixed[$i] $i;}echo SplFixedArray: . (microtime(true) - $start) . 秒\n;$memFixed memory_get_usage(true);unset($fixed);$start microtime(true);$arr [];for ($i 0; $i $size; $i) {$arr[$i] $i;}echo 普通数组: . (microtime(true) - $start) . 秒\n;$memArr memory_get_usage(true);unset($arr);?PHP的哈希表设计在灵活性和性能之间做了权衡。普通数组支持任意键名、保持插入顺序、动态扩容。SplFixedArray没有哈希开销性能更好内存更省。理解这些原理可以在写代码时做出更好的选择。