Dummerweise liegen die Daten im Array nicht sortiert vor
Doch, aber halt nach den Hashs und nicht dem Inhalt sortiert.
Nein. Hash modulo Listengröße = Index. Gleicher Index => Kollision => Verschiedene Strategien.
B+ Bäume sind hierfür
imho falsch, denn sie basieren auf festen Speicherblöcken (z.B. Dateiblöcken) und sind nichts anderes als binäre Arrays, die als N-ärer Baum untereinander hängen. Für die In-Memory Suche ist das
imho overkill.
Binäre Listen sind knackig und kurz in der Implementierung, dafür O(n) beim Einfügen (Listeninhalt muss verschoben werden). Das geht aber sehr schnell.
Binäre Bäume (RB oder AVL) komplexer in der Umsetzung, aber dafür für diesen Fall optimal.
Eine SkipList wäre noch eine Alternative.
Es gibt fertige Lösungen, auch hier im Forum, z.B. hier :
http://www.delphipraxis.net/55493-ve...eispielen.html