Stack, Queue und Map

[alzaimar]

Nein.

Erstmal ist eigentlich kein Unterschied zwischen einem Array und einer Liste. Eine Liste ist eine geordnete Menge von Elementen, ein Array eine Implementierung auf einem Rechner (Wieso gibt es denn eine TList, müsste das nicht TArray heißen?). Aber das ist Wortklauberei. Einige meinen, eine Liste ist verkettet, bei mir ist eine Liste aber mathematisch definiert. Und in der Mathematik gibt es, soweit ich das beurteilen kann, keine Arrays.

Ein sortierte Liste hat mit binary search einen Zugriffsaufwand von O(log n). Minimal und maximal gibt es da nicht. Im Mittel (darum geht's bei 'Big Oh') wird sich also die Zugriffszeit sublinear (log 2) erhöhen: Das ist schon mal nicht schlecht, aber eben miserabel im Vergleich zu einer Hash-map.

Eine Hash-Map hat einen Zugriffsaufwand von O(1), dort ist die Zugriffszeit eigentlich gar nicht von der Anzahl der Elemente abhängig! Eine Hash-Map mit 100.000.000 Elementen verhält sich performancetechnisch auch nicht anders als eine Hashmap mit 2 Elementen.

Wenn Du nur 256 Elemente in deinem Listenarray hast, ist es wurscht, wie du suchst, aber ich hatte dich so verstanden, das Du allgemeingültige Containerklassen entwickeln willst, und die müssen (oder: sollten) eben auch bei 100.000.000 Elementen schnell sein, sofern Du die Verwendung nicht explizit eingrenzt.

Beim Einfügen, Löschen und Suchen hat eine Hashmap einen Aufwand von O(1), wohingegen eine sortierte Liste mit O(n), O(n) und O(log n) dagegen hält. Was ist nun besser?

@Chewie: Die Kollisionen sind bei geeignetem Füllfaktor (bis zu 5/4) absolut zu vernachlässigen.

Zitat von himitsu:

Wobei man aber auch auf einen Schwups verschieben kann, wenn man die innere Struktur des Arrays kennt und beachtet ^^
MOVE

Autsch, es bleibt bei dem Aufwand O(n), egal welche Befehle ich verwende. Es wird zwar schneller, weil sich die Konstante (also die Zeit pro element) verringert, aber doppelt so viele Elemente zu verschieben benötigt eben auch doppelt so viel Zeit, egal, ob ich MOVE oder sonstwas nehme.