Adaptives Hashing in SBCL: Schnellere und robustere Hashtabellen
Ein Vortrag auf der ELS 2024 konzentrierte sich auf adaptives Hashing mit dem Ziel, allgemeine Hashtabellen schneller und robuster zu machen. Die traditionelle Hashtabellentheorie befasst sich hauptsächlich mit asymptotischen Worst-Case-Kosten und vernachlässigt den Einfluss von konstanten Faktoren auf die reale Leistung. Diese Forschung stellt einen online adaptiven Ansatz vor, der die Hashfunktion basierend auf der tatsächlichen Schlüsselverteilung anpasst, um Kollisionen zu reduzieren und die Cache-Auslastung zu verbessern. Experimente zeigen signifikante Verbesserungen bei der Reduzierung der erwarteten Vergleiche und der Beschleunigung von PUT-Operationen, insbesondere bei bestimmten Schlüsselverteilungen. Die integrierten Hashtabellen von SBCL verwenden jetzt diese Technik und wechseln dynamisch zwischen Hashfunktionen (einschließlich linearer Suche, Bit-Shift-Hash und MurmurHash) basierend auf Kollisionszahlen und der Größe der Hashtabelle. Für zusammengesetzte Schlüssel wie Strings und Listen wird eine Truncation-Strategie verwendet, die die Truncation-Länge dynamisch anpasst, wenn zu viele Kollisionen auftreten. Diese Verbesserung erhöht die Geschwindigkeit der SBCL-Hashtabellen in häufigen Fällen und die Robustheit in anderen.