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

Question

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

Answer 1

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

数组值没有散列，因此搜索它们需要线性搜索。这是 O(N)，所以 Y 搜索是 O(N*Y)。

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

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