PHP数组底层：HashTable的深度剖析
什么是HashTable？
PHP中的数组（Array）在底层实现上是一个HashTable。它不仅仅是简单的数组，更是一个哈希表。理解HashTable是理解PHP性能优化的基石。它通过哈希函数将键（Key）映射到表中的位置，从而实现O(1)的平均时间复杂度查找。
Bucket与Bucket结构
在PHP源码（如PHP 7/8）中，数组元素存储在Bucket中。每个Bucket包含键、值、以及指向下一个冲突Bucket的指针（用于处理哈希冲突）。理解Bucket的结构有助于解释为什么数组索引和关联数组在性能上存在细微差异。
哈希冲突解决方案
PHP HashTable采用链地址法（Chaining）处理冲突。当两个不同的键映射到同一个索引时，它们会被链接到同一个链表上。面试官常问：如何优化冲突？答案是调整哈希表大小和哈希算法。
代码示例：PHP数组的内存布局
// PHP 7+ 数组底层结构示意
typedef struct _hashtable {
uint32_t nTableSize; // 哈希表大小，2的幂次
uint32_t nTableMask; // 用于快速取模 (nTableSize - 1)
uint32_t nNumOfElements; // 当前元素个数
Bucket pListHead; // 链表头，用于正向遍历
Bucket pListTail; // 链表尾，用于反向遍历
zend_ulong h; // 数值键的哈希值
union {
void p; // 数据指针
uint32_t n; // 数值
} d;
} HashTable;高频面试题：索引数组 vs 关联数组
在面试中，经常被问到“PHP数组是有序的吗？”答案是肯定的，但有序的方式不同。
- 索引数组：底层Bucket按插入顺序排列，哈希表主要利用数值键直接定位，速度极快。
- 关联数组：底层Bucket按哈希值排序存储，虽然查找也是O(1)，但在遍历时需要维护链表的顺序，内存开销略大。
树与图：递归与非递归的博弈
二叉树的三种遍历方式
二叉树是面试中最常见的数据结构。前序、中序、后序遍历是基础中的基础。面试官通常要求手写递归和非递归实现。
| 遍历方式 | 访问顺序 | 应用场景 |
|---|---|---|
| 前序 (Pre-order) | 根 -> 左 -> 右 | 复制树、序列化 |
| 中序 (In-order) | 左 -> 根 -> 右 | BST排序输出 |
| 后序 (Post-order) | 左 -> 右 -> 根 | 释放内存、目录树计算 |
// PHP 递归实现前序遍历
function preorderTraversal($root) {
if ($root === null) return [];
return [$root->val]
- preorderTraversal($root->left)
- preorderTraversal($root->right);
}二叉搜索树 (BST) 的性质
二叉搜索树是一种特殊的二叉树，其左子树所有节点值小于根节点，右子树所有节点值大于根节点。这种结构使得查找、插入和删除操作的时间复杂度为O(log n)。
面试陷阱：如果BST退化为链表（例如插入有序数据），复杂度将降为O(n)。因此，面试中常会引出平衡二叉树 (AVL) 或 红黑树 的讨论。
图的表示与遍历
图结构常用于解决社交网络推荐、路径规划等问题。PHP中常用邻接表（数组的数组）来表示图。
- DFS (深度优先搜索)：使用栈（Stack）实现，适合寻找连通分量。
- BFS (广度优先搜索)：使用队列（Queue）实现，适合寻找最短路径（无权图）。
排序算法：性能与稳定性的权衡
快速排序 (Quick Sort)
时间复杂度：平均O(n log n)，最坏O(n²)。
特点：原地排序，空间复杂度O(log n)。PHP的内置排序函数 sort() 在底层主要基于快速排序的变种（木桶排序/快速排序混合）。
归并排序 (Merge Sort)
时间复杂度：O(n log n) 始终成立。
特点：稳定排序，但需要O(n)的额外空间。适合处理大规模数据或链表排序。
堆排序 (Heap Sort)
时间复杂度：O(n log n)。
特点：不占用额外栈空间，适合解决“Top K”问题。利用最大堆或最小堆的特性，高效地找出最大或最小的K个元素。
PHP内置排序函数解析
在实际开发中，我们很少手动实现排序，但面试官会考察你对PHP内置函数的理解：
sort()：对数组排序，返回布尔值，破坏原数组索引。asort()：对数组排序，保持索引关联（按值排序）。usort()：使用用户自定义的比较函数排序，灵活性最高，但性能开销较大。