HackerNews

現代の完璧なハッシング

Modern Perfect Hashing

https://blog.sesse.net/blog/tech/2025-10-23-21-23_modern_perfect_hashing.html


この記事では、文字列のための現代の完璧なハッシングの実装について述べています。著者は、固定された文字列の集合を事前に定義された整数にマッピングし、それ以外を拒否するという課題に取り組みました。一般的なハッシュテーブルよりも効率的に処理できる方法について説明されており、特に長さで分けるテクニックが紹介されています。また、PEXT命令を利用したり、衝突を避けるために「マジックナンバー」を用いる方法が提案されています。具体例として、CSSの長さ4のキーワードに対するハッシングが示され、メモリ操作や数値計算の詳細も含まれています。全体として、効率的なハッシングアルゴリズムの設計に関する洞察が提供されています。