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

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

yes. I am sure.

first, the third link you've pointed reads:
Thus—formally—hash tables often run in time O(log n).

next, if the question is "is it possible to create an algorithm that, given arbitrary strings of finite length, make associative store/lookup for O(1)" - then the answer is "yes" but these are non-realistic algorithms.
but - back to reality - real-life alhorithms are O(log N) in best case, but I afraid Perl's one is worse than that
and - yet - have you ever heard of so-called "hash complexity attack" that was security-fixed by seed randomization in 5.8.0?
To inform you, pre-5.8.0 were looking like O(1) but actually were O(n) (or maybe even worse in worst case scenario)

next, your "stackoverflow.com" link contains simply wrong information.
IOW, I do not see any proof there that convinces me.

And - your last link does not even mention hashes.
Bother explain what is doing here? TIA!

and finally, do you see something strange in your phrase
hash operations are O(1) operations, where 'n' is the number of elements in the hash
?
I could be a bit joking, but I do not trust phrases like that.
you're explaining parameter 'n' that is not presents in your formulae - what other mistakes/typos have you made?
:)

Comment on Re^3: "Just use a hash": An overworked mantra?
Re^4: "Just use a hash": An overworked mantra? by BrowserUk (Pope) on Dec 23, 2011 at 21:34 UTC
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. The start of some sanity?	[reply]
Re^5: "Just use a hash": An overworked mantra? by vkon (Deacon) 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 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?	[reply]
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^4: "Just use a hash": An overworked mantra? by Anonymous Monk on Dec 24, 2011 at 12:38 UTC
And - your last link does not even mention hashes. Bother explain what is doing here? TIA! Look at the table Here are some well-known algorithms and their order functions (adapted from [2]): `Notation Name Example O(1) constant array or hash index` [download] ... 2. Kernighan, B. W. & Pike, R., (1999). The Practice of Programming, p. 41. Addison-Wesley. yes. I am sure. Great, prove it :)	[reply] [d/l]
Re^5: "Just use a hash": An overworked mantra? by vkon (Deacon) on Dec 24, 2011 at 21:11 UTC
kewl. thanks for the pointer in a table, I overlooked it - indeed - it takes a special care to find this place, since the only mention w/o any argumentation - not in line of overall text, easy to e\overlook, and - still - does not convince me - where is argumentation? a bit pity that O(1) for hashes actually do not reflects on what is actually going on inside perl. for a prove of my point - well, look into perl implementation of hashes - just read the comments - and you will see it. Convincing? Well, URLs provided to me are even less convincing..... :o	[reply]
Re^6: "Just use a hash": An overworked mantra? by Anonymous Monk on Dec 24, 2011 at 21:25 UTC
for a prove of my point - well, look into perl implementation of hashes - just read the comments - and you will see it. you know where to look? I don't believe it :p	[reply]

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

The best material for plates (tableware) is: