Ich glaube, es wurde mal darüber nachgedacht, Red-Black-Trees zu verwenden, weil die Performance im ungünstigsten Fall besser wäre als bei Hashtables.

Durch das Zufallselement in der Hashfunktion vermeidet man aber auch mit großer Wahrscheinlichkeit Komplexitätsprobleme. Und in weniger pathologischen Fällen können Hashtables halt auch schneller als Red-Black-Trees sein.