Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris

Re: Re: Re: A short meditation about hash search performance

by Boots111 (Hermit)
on Nov 16, 2003 at 20:40 UTC ( #307496=note: print w/replies, xml ) Need Help??

in reply to Re: Re: A short meditation about hash search performance
in thread A short meditation about hash search performance


I am just refering to the two posts immediately above this, but I must point out that pg is correct. Despite what the points on either node may say...

The size of a hashtable is a variable (usually n), and the pathelogical case of inserting everything into the same bucket provides O(n) access for a simple hashtable.

The only way in which Abigail would be correct is if there were guarantee that the overflow chain would NEVER exceed one billion entries.

It is possible that the rehashing will prevent overflow chains from growing too large, but then one must consider the cost of rehashing the table. While that cost is not paid every time, it is likely a very large cost, and thus must be amortized across all calls to insert.

In general, one could get O(1) access to a hash by ensuring that the overflow chains reach at most a constant length, but this will require rehashing when chains get too long. This would cause hash insertions to be greater than O(1).

At heart it is a question of trading one cost for another...

Computer science is merely the post-Turing decline of formal systems theory.
  • Comment on Re: Re: Re: A short meditation about hash search performance

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://307496]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (11)
As of 2019-04-23 13:55 GMT
Find Nodes?
    Voting Booth?
    I am most likely to install a new module from CPAN if:

    Results (118 votes). Check out past polls.