Re^5: Combining arrays with grep/unless?

Doesn't the number of buckets grow with the number of elements in the hash? If so, why would it take longer as more elements are added? The number of elements in a bucket should remain less than some bound, no? O(bound) = O(1). I don't know how hashes are implemented specifically in Perl, but I heard they were O(1) for lookup. (Again, not worse case.) Wikipedia says the same for hashes in general:

Hash tables are often used to implement associative arrays, sets and caches. Like arrays, hash tables provide constant-time O(1) lookup on average, regardless of the number of items in the table. (O(1) means that it takes a constant amount of time independent of the number of items involved.)

From where did you get O(log N)?

Comment on Re^5: Combining arrays with grep/unless?

Replies are listed 'Best First'.
Re^6: Combining arrays with grep/unless? by polettix (Vicar) on Feb 11, 2007 at 15:38 UTC
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 :) Flavio perl -ple'$_=reverse' <<<ti.xittelop@oivalf Don't fool yourself.	[reply]