Michael G Schwern writes:
>On Thu, Nov 29, 2001 at 03:22:42PM -0500, Uri Guttman wrote:
>> >>>>> "MGS" == Michael G Schwern <[EMAIL PROTECTED]> writes:
>> MGS> A Crash Course On BigO Notation As Presented By A Guy Who Failed
>> MGS> Fundamental Data Structures And Algorithms 1 *
>>
>> MGS> O(1) means it runs in a fixed amount of time regardless of how mu
>ch
>> MGS> data is to be processed. A hash is an O(1) algorithm.
>>
>> actually given linear searches in buckets, most hashes are not truely
>> O(1) but close enough.
>
>Given a "perfect" hash algorithm which evenly distributes the data
>over all buckets it is. Of course, there is no such thing. Even so,
>most hash algorithms reorder the buckets as they grow to avoid the
>worst of the collisions, but that reordering is O(n), so you're right.
Even with a "perfect" hash algorithm it won't be O(1). If there are m buckets
and n items in the hash there are n/m items per bucket with this "perfect"
hash. If you used a linear search in the buckets you are O(n/m).
If m is constant you are O(n) (of course since you don't have a "perfect"
hash function a hash is always O(n) since every element could end up in
the same bucket - just like a binary tree can degenerate to a linked list if
no balancing is done - big-O is worst case right?)
If m increases as n increases (which is the case in most hashes I've seen) then
it depends on how m increases.
If m increases linearly with n then you get O(1) with a "perfect" hash
function.
In practice hashes are O(1), in theory they are O(n) or O(log N) if you are
mad and hang a binary tree off the buckets...
Or you could go insane and have each bucket be another hash with a
different hash function.
Anyone want to patch perl so that hashes are implemented as a hash of hashes of
binary trees? ;)
--
Sam
About the only thing most people know about black holes is they are
black, and now we have stuffed that up
-- Dr Paul Francis (after reporting finding 'pink' holes)
