40 Jahre alte Vermutung über Hashtabellen widerlegt

Vierzig Jahre lang haben Informatiker die Vermutung von Andrew Yao aus dem Jahr 1985 über die Effizienz von Suchanfragen in Hashtabellen akzeptiert. Krapivin und sein Team haben jedoch eine neue Hashtabelle entwickelt, die Yaos Worst-Case-Grenze deutlich übertrifft. Ihr neuer Algorithmus erreicht eine viel schnellere Abfrage- und Einfügezeit und überraschenderweise ist die durchschnittliche Abfragezeit konstant, unabhängig von der Füllmenge der Tabelle. Dieses bahnbrechende Ergebnis widerlegt nicht nur eine lang gehegte Annahme, sondern eröffnet auch neue Wege zur Optimierung von Hashtabellen.