Oh, man - wir sollten mal das Design unserer Links ändern. Hab nicht gemerkt, daß das 'hier' ein Link war.

Im _ungünstigsten_ Fall hat man O(n) - schon klar. Die wahrscheinlichkeit dafür, daß ein Hash maximal ungünstig ist, wäre schonmal verdammt klein (ca. 1/n^n, glaub ich), abgesehen davon nimmt Perl eine Umordnung vor, wenn ein Hash beginnt ungünstig angeordnet zu werden. Und O(1) hat man nur im Falle der günstigsten Anordnung, allerdings ist der Aufwand für eine Optimale Anordnung enorm. Und bei einer halbwegs vernünftigen Anordnung kommst du eben im Schnitt auf O(log n) (Man halte sich immer bewusst, daß Hashes eine sehr heuristische Angelegenheit sind). Und mit Optimierungen bekommst du höchstens deine Konstannte runter, nicht dein Laufzeitverhalten besser.

Und als Beweis der Tatsache diene dir ein ausgiebiger Benchmark.\n\n

<!--EDIT|Ishka|1082647584-->