php - 是否存在 array_search 比连续 array_flip 和直接查找更快的情况？

Question

假设您要搜索一个包含 N 个元素的数组，并对数组值执行 Y 次搜索以找到相应的键；您可以执行 Y array_search 或执行一个 array_flip 和 Y 直接查找。为什么第一种方法比第二种方法慢很多？是否存在第一种方法比第二种方法更快的情况？您可以假设键和值是唯一的

Answer 1

数组键是散列的，所以查找它们只需要调用散列函数并索引到散列表中。所以 array_flip() 是 O(N) 并且查找数组键是 O(1)，所以 Y 搜索是 O(Y)+O(N)。

数组值未经过哈希处理，因此搜索它们需要线性搜索。这是 O(N)，所以 Y 搜索是 O(N*Y)。

假设要搜索的值在数组中均匀分布，线性搜索的平均情况必须比较 N/2 个元素。所以 array_flip() 应该花费大约 2 次 array_search() 调用的时间，因为它必须检查 N 个元素。

创建哈希表有一些额外的开销。但是，PHP 使用写时复制，因此它不必在 array_flip() 期间复制键或值，因此还算不错。对于少量查找，第一种方法可能更快。您必须对其进行基准测试才能找到盈亏平衡点。