Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?

Re^5: "Just use a hash": An overworked mantra?

by vkon (Deacon)
on Dec 24, 2011 at 21:20 UTC ( #945040=note: print w/ replies, xml ) Need Help??

in reply to Re^4: "Just use a hash": An overworked mantra?
in thread "Just use a hash": An overworked mantra?

yes, they are O(n x log n)

how do the hashes work.

ok, hash is computed (some say these are O(log n) i do not know but this time I trust the links provided to me by davido) and then - based on computed hash - it could be hash hit or miss: either "luck" - (this is what usually happens) - this was different on all previous values.
or - otherwise - hash sum equality with earlier cases of that hash (rare in practice, but this is what is used on hash complexity attack)

in that latter case - insertion/search happens (based on exact operation), which is O(n)

otherwise this hunk of hv.c code is what for:

* The "hash seed" feature was added in Perl 5.8.1 to perturb the resu +lts * to avoid "algorithmic complexity attacks". * * If USE_HASH_SEED is defined, hash randomisation is done by default * If USE_HASH_SEED_EXPLICIT is defined, hash randomisation is done * only if the environment variable PERL_HASH_SEED is set. * For maximal control, one can define PERL_HASH_SEED. * (see also perl.c:perl_parse()). */

Comment on Re^5: "Just use a hash": An overworked mantra?
Download Code
Re^6: "Just use a hash": An overworked mantra?
by BrowserUk (Pope) on Dec 24, 2011 at 22:08 UTC
    I'd like to see you demonstrate that Perl's hashes are O(log N), let alone "worse than that"

    That is not a demonstration.

    Just you expounding your own theory based upon your misunderstanding of a) what you've read; b) what O(N) & O(N log N) mean.

    Merry Xmas. :)

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

    The start of some sanity?

Re^6: "Just use a hash": An overworked mantra?
by JavaFan (Canon) on Dec 25, 2011 at 09:58 UTC
    Even if you manage to construct an insert sequence that, with a particular hash seed, results in Ω(N2) time to insert N keys, that still doesn't prove insertion isn't O(1) amortized time, with the amortization taken over all insert sequences, and/or all hash seeds.

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (7)
As of 2014-07-30 01:20 GMT
Find Nodes?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:

    Results (229 votes), past polls