C++の高速なハッシュテーブルの実装を読んだ (ankerl::unordered_dense) - Qiita

m_bucketsがハッシュテーブルの管理データで、m_valuesが格納した要素の配列。 m_valuesは全要素が隙間なく詰められていて、イテレートする際はここを直接走査する。 dist_and_fingerprintは、名前の通り2つの値が一つの変数にパックされている。 この工夫で、いろいろと効率よく処理できる(後述) 上位3バイト: dist ハッシュ関数で求めた位置から、実際に要素が格納されている位置までの距離 基本アルゴリズムの解説でProbe Sequence Lengthと呼ばれているものと同じ 1から数えるので注意。つまりdist == 1ならハッシュ関数で求めた位置と実際に格納されている位置が等しい 下位1バイト: fingerprint ハッシュ値の下位1バイトを格納 dist_and_fingerprint == 0の場合はEmpty(その位置に要素が格納されていな