in reply to A short meditation about hash search performance
A function f(n) is O(1) if there are constants K and N such that for all n>N, f(n)<K. Plenty of functions other than straightforward constants meet that definition.
An algorithm is not big-O of anything. Only functions are. When it comes to hashes, the following three statements can be correct:
- The average hash search performance is O(1).
- The worst case hash search performance is O(n).
- The average hash search performance is O(n).
I should note that technically speaking, Perl's hash performance isn't big-O of anything. Perl's hashing algorithms break down for datasets that do not fit in current memory and cannot be addressed by 32 or 64-bit pointers (depending on the platform). I would have to look, but I think that the hash function won't scale beyond a billion or so buckets. Good luck finding someone who cares though.
Silly trivia. Following a pointer is not really O(1). The amount of work taken depends on how long the pointer is, and therefore the size of the possible address space. People only notice this when they are on a platform where they have the choice of working with two different sizes of data representation, like 16 vs 32 bit. Or 32 vs 64 bit. Going to the larger size brings with it a necessary speed hit.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: A short meditation about hash search performance
by Anonymous Monk on Sep 09, 2007 at 23:13 UTC | |
by tilly (Archbishop) on Sep 12, 2007 at 01:09 UTC |