Du willst zu einem Namen sofort die Telefonnummer finden – egal, wie viele Einträge gespeichert sind. Welche Datenstruktur schafft das im Normalfall in konstanter Zeit, also O(1)?

Eine Hashtabelle (HashMap, in Python Dictionary) rechnet den Schlüssel direkt in eine Fachnummer um und springt dorthin – das dauert gleich lang, egal wie viele Einträge es gibt: O(1). In einer unsortierten Liste muss man Eintrag für Eintrag suchen (O(n)), in einem sortierten Array geht es mit binärer Suche in O(log n). Ein Stack gibt nur das oberste Element direkt heraus und ist nicht zum Suchen gedacht.