I was evidently absent at the lessons about hashes, the only things that remained in my memory were the best O(1) and worst O(N), and thougth that the average case should be somewhere in the middle. The O(log N) was there in my head due to binsearch, I presume. Time to eat more fish and improve memory :)