Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

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

All~

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...

Boots
---
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?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (6)
As of 2014-07-13 19:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (251 votes), past polls