complexityhashing
Hash table lookup is not always constant time
Anonymous
A basic hash table with n entries is often O(1) on average when hashes spread keys well, but lookup can reach O(n) if many keys collide. The average-case claim depends on the hashing assumptions and load factor. A balanced search tree gives O(log n) lookup when keys have a comparison order.
0