Vielleicht eine Hashmap und die einzelnen Buckets noch mal sortiert? Dadurch hat man eine bessere Worst-Case-Laufzeit als bei einer „normalen“ Hashmap.
... Bucketsort wird beim -on-the-fly- 'indizieren' verwendet, um kleinere Datenmengen zu sortieren und dadurch ein besseres Ergebnis zu erzielen. Eine Hashmap hat erst einmal keine Buckets, weil nicht klar ist, wie die Hashmap umgesetzt wurde (open hashing vs. separate chaining). Falls sie als
separate chainging umgesetzt wurde, sind die einzelnen 'Buckets' bereits sortiert.
Meistens wird Separate Chaining verwendet. Und nein, da sind die Einträge normalerweise nicht sortiert, weil das bei einer verketteten Liste auch gar keinen Sinn ergeben würde: Auf einer verketteten Liste kann man keine binäre Suche durchführen. Neue Elemente werden einfach unsortiert am Anfang der Liste eingefügt.
Und von Bucketsort war überhaupt nicht die Rede...?
PS: Bei PHP wurde offenbar eine Hashmap mit fester Größe verwendet. Die Problematik kann durch eine dynamische Hashmap vermieden werden. Diese würde ihre Größe ggf. (zu viele Kollisionen) einfach verdoppeln. Da dadurch die Hashfunktion verändert wird, sollten die Angriffe ins Leere laufen.
Je nach Hashfunktion ist es durchaus möglich, dass die Elemente immer noch im selben Bucket landen, egal in welcher Größe die Hashmap (neu-)angelegt wird. Dass die Hashmap von PHP eine konstante Größe hat, kann ich mir ehrlich gesagt auch nicht vorstellen.