Пользователь
И для больших массивов, она будет ближе к, O(n)
средствами php
Собственно, это – все.
mysql_*
Дело не в величине массива, а в том сколько будет совпадающих хэшей в хэштаблице: Supercolliding a PHP array
Плохо ищите. Есть несколько всяких разных реализаций, под разные версии PHP.
Что касается кода, то он корявенький.
mysql_*на что-нибудь более современное. Хватит уже даже в качестве примера упоминать это расширение.