Re^5: "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()).
 */
[download]

Comment on Re^5: "Just use a hash": An overworked mantra? Download Code

Replies are listed 'Best First'.
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]


more useful options
	PerlMonks