SBCLにおける適応的ハッシング：ハッシュテーブルの高速化と堅牢性の向上
2025-05-11
2024年のELSカンファレンスで行われた発表では、汎用ハッシュテーブルの高速化と堅牢性の向上を目指す適応的ハッシングが取り上げられました。従来のハッシュテーブル理論は主に最悪ケースの漸近的なコストに焦点を当てており、現実的なパフォーマンスへの定数因子の影響を無視していました。この研究では、キーの実際の分布に基づいてハッシュ関数を調整することで、衝突を減らし、キャッシュの利用効率を向上させるオンライン適応アプローチが導入されています。実験の結果、期待される比較回数の削減とPUT操作の高速化において顕著な改善が示され、特に特定のキー分布において効果的であることが分かりました。SBCLの組み込みハッシュテーブルは現在この技術を採用しており、衝突回数とハッシュテーブルのサイズに基づいて、線形探索、ビットシフトハッシュ、MurmurHashなどのハッシュ関数を動的に切り替えています。文字列やリストなどの複合キーに対しては、切り詰め戦略が使用され、衝突が多すぎる場合は切り詰め長が動的に調整されます。この改善により、SBCLハッシュテーブルの一般的なケースでの速度とその他のケースでの堅牢性が向上しています。
開発
適応的ハッシング