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

[vkon]

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()).
 */

[JavaFan]

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.

[BrowserUk]

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