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.
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.
Aber wir kommen vom Thema ab.