Is there a scenario where array_search is faster than sequential array_flip and direct search?

Question

Imagine that you had to look for an array of N elements and execute Y Looks for the values ​​of the array to find the corresponding keys; you can do Y array_search or do one array_flip and Y direct search. Why is the first method much slower than the second? Is there a scenario when the first method becomes faster than the second? You can assume that keys and values ​​are unique.

Answer 1

The keys of the array are hashed, so looking at them simply requires calling the hash function and indexing into the hash table. So array_flip() is O (N), and the search for the array key is O (1), so Y searches O (Y) + O (N).

Array values ​​are not hashed, so a linear search is required to find them. This is O (N), so Y is looking for O (N * Y).

Assuming that the search for values ​​is evenly distributed across the array, the average case of a linear search should compare N / 2 elements. Thus, array_flip() should take the time to call 2 array_search() , since it should check for N elements.

There are additional overheads in creating a hash table. However, PHP uses copy-on-write, so it does not need to copy keys or values ​​during array_flip() , so this is not so bad. For a small number of searches, the first method may be faster. You will need to compare it to find a breakeven point.