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

real-life alhorithms are O(log N) in best case, but I afraid Perl's one is worse than that

I'd like to see you demonstrate that Perl's hashes are O(log N), let alone "worse than that"?

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.

Comment on Re^4: "Just use a hash": An overworked mantra?

Replies are listed 'Best First'.
Re^5: "Just use a hash": An overworked mantra? by vkon (Curate) on Dec 24, 2011 at 21:20 UTC
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()). */` [download]	[reply] [d/l]
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 Ω(N²) 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.	[reply]
Re^6: "Just use a hash": An overworked mantra? by BrowserUk (Patriarch) 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?	[reply]