様々なハッシュテーブルたち

Robin Hood Hashing

ハッシュテーブルのinsertクエリにおける衝突処理をオープンアドレス法でやるとします。具体的にはハッシュ値を1ずつ増やして見ていくとします。このとき、既に入っている要素のほうが「本来の場所からの距離が短い」ならば、それを今入れようとしている要素と交換して、取り出した要素を別の場所に入れるために衝突処理を続けるというのがRobin Hood Hashing（ロビンフッドハッシュ法）です。

ロビンフッドは裕福な人の財産を盗んで貧しい人に与えた伝説の人物で、この命名においては本来の場所からの距離が短いことを裕福さに例えています。

（google scholarで"Robin Hood Hashing"で調べたところ）初出は1985年の学会論文のようで、その筆頭著者の学位論文が1986年だったようです。後の人々は学位論文のほうを引用していることが多いです。

ja.wikipedia.org

codecapsule.com

insertクエリでRobin Hood Hashingを採用すると、insertクエリ自体の処理は遅くなりますが、findクエリは速くなります。要素が見つかるまでの探索距離が短くなる（＝比較回数が減る）からです。

tombstone法

ハッシュテーブルの衝突処理をオープンアドレス法でやるとすると、eraseクエリ（Keyを引数として、それがテーブル中にあれば削除する）をどう処理するかが問題になります。findして見つけた番地を単に空白にしてしまってはいけません。なぜなら、「その番地を通り過ぎる形でinsertされた要素」が存在する場合、今後その要素をfindしようとしたとき、途中の番地に空白ができていると辿り着けなくなるからです。

対処法は2通りあります。一つはその番地に「削除済み」の印をつけておく方法です。findでは通り過ぎることにして、insertでは再代入可能とします。これをtombstone法と呼びます。（tombstoneは墓石のことです）

もう一つは、次の番地に「本来の場所からずれた要素」が入っているかを調べ、Yesなら交換してまた次を見るという処理をノームソートのように繰り返す方法です。この方法だとfindクエリが少し速くなりますが、交換回数が非常に多くなる可能性があります。（リハッシュの条件などによりますが）たぶんtombstone法のほうが良いと思います。

Swiss Tables

まず歴史的背景として、C++の標準ライブラリは（互換性と引き換えに）ハッシュテーブルの処理速度が遅いことで知られていました。そのためGoogle内部ではC++標準ライブラリの代用とするための高速なライブラリを内製していて、後にAbseilという名前で公開されました。

Swiss Tablesは、Abseilのハッシュテーブルの実装で使われているテクニックです。ハッシュテーブル本体とは別に、各要素8bitのメタデータのテーブルを持っておくというものです。（複数形なのはたぶんそのためでしょう）

8bitのうち最上位ビットはその要素が空白なら1で埋まっているなら0とします。残りの7ビットは（添字番号とは独立な）ハッシュ値とします。こうすることで、x86の拡張命令を上手く使って高速にスクリーニングでき、findクエリを高速化できます。

Swiss Tablesでtombstone法を使う場合（というか、Swiss Tablesを用いたハッシュテーブルを自作するときにeraseクエリをtombstone法で受け付けることにした場合）、メタデータ上で空白と墓石を区別する必要があることに注意しましょう。

abseil.io

コード例

ハッシュテーブルとメタデータ（signatureと呼ぶことにします）とハッシュ関数が以下のようにあるとします。

std::vector<std::pair<Key, Val>>hash_table;
std::vector<uint8_t>signature_table;
extern uint64_t hashfunc(const Key &k);

ただし、両テーブルの大きさ(vectorのsize)は $2^{N}+31$ だとします。空っぽのテーブルを作る初期化処理は以下のように書けます。最小値を10にしたのは何となくです。57にしたのは一応理由があって、ハッシュ値の上位7bitをsignatureに使うからです。

uint64_t bitmask, tablesize;
constexpr uint8_t EMPTY_SIGNATURE = 0x80;
void init(int N) {
	N = std::clamp(N, 10, 57);
	bitmask = (1ULL << N) - 1;
	tablesize = (1ULL << N) + 31;
	hash_table = std::vector<std::pair<Key, Val>>(tablesize);
	signature_table = std::vector<uint8_t>(tablesize, EMPTY_SIGNATURE);
}

insertクエリのコードは省略しますが、格納されている任意の要素について、本来の場所からの距離が31以下であることを仮定します。31以下にできない場合はリハッシュするとします。（Robin Hood Hashingは必須ではありませんが、採用すればテーブルがかなりギチギチになるまでリハッシュせずに済むでしょう）

そのうえで、findクエリは以下のように書けます。

uint64_t find(const Key &k) {

	//ハッシュテーブルに引数Keyの情報があるか調べて、あればその添字番号を返し、なければ-1を返す。

	const uint64_t hashcode = hashfunc(k);
	const uint64_t index = hashcode & bitmask;
	const uint8_t signature = uint8_t(hashcode >> 57);

	const __m256i query_signature = _mm256_set1_epi8(int8_t(signature));
	const __m256i table_signature = _mm256_loadu_si256((__m256i*)&signature_table.data()[index]);

	//[index+i]の情報が ↑のsignature_table.i8[i]に格納されているとして、↓のi桁目のbitに移されるとする。

	const uint32_t is_empty = _mm256_movemask_epi8(table_signature);
	const uint32_t is_positive = _mm256_movemask_epi8(_mm256_cmpeq_epi8(query_signature, table_signature));

	//[index+i]がシグネチャ陽性かどうかがis_positiveの下からi番目のビットにあるとする。

	uint32_t to_look = (is_empty ^ (is_empty - 1)) & is_positive;

	//最初に当たる空白要素より手前にあるシグネチャ陽性な要素の位置のビットボードが計算できる。to_lookがそれである。

	for (uint32_t i = 0; bitscan_forward(to_look, &i); to_look &= to_look - 1) {
		const uint64_t pos = index + i;
		if (k == hash_table[pos].first)return pos;
	}

	return 0xFFFF'FFFF'FFFF'FFFFULL;
}

ひとつめの見どころはtable_signature変数です。signature配列のうち「本来の場所からの距離が31以下」の領域を_mm256_loadu_si256で一発でロードしています。

ふたつめは_mm256_movemask_epi8関数です。こいつは__m256i型変数を8bit変数32個の配列とみなしたうえで、最上位ビットをかき集めてint型にして返してくれる凄いやつです。空白の要素のメタデータ値を0x80にして、要素のシグネチャを7bitにした理由はこの関数があるからです。

これらにより「最大32要素の線形探索」を「7bitのシグネチャでスクリーニングして、陽性だった要素のうち空白より手前の領域だけの探索」にできます。しかも該当する要素のビットボードが得られるので、bsf命令で効率的になめることができます。

一気に構築するときにinsertクエリを使わずに済ます方法

KeyとValのペアが大量に与えられて、ハッシュテーブルを一気に構築することを考えます。コンストラクタがそのデータを受け取るみたいなケースもそうですが、リハッシュにもこの想定が当てはまります。

ナイーブに考えると、空っぽのハッシュテーブルを用意してから各要素についてinsertクエリを発行すれば構築できます。しかしinsertクエリは空白の番地を探す処理などを含むため、この方法は非常に重い処理になります。しかも構築可能な最小のNは非自明なので、insertが途中で失敗して更にリハッシュするみたいな事態も考えられます。

分布数えソートのように度数表を作ってからある種の動的計画法を計算することで、空白要素の探索を一切行わずに、最小の大きさで、かつあたかもRobin Hood Hashingされたかのような（距離の総和が最小な）構築ができます。

uint64_t pow2_ceiling_log2(uint64_t x) {
	//x以上の整数のうち最小の2べき数を返す。
	if (x == 0)return 1;
	--x;
	x |= x >> 1;
	x |= x >> 2;
	x |= x >> 4;
	x |= x >> 8;
	x |= x >> 16;
	x |= x >> 32;
	return x + 1;
}
void init(const std::vector<std::pair<Key, Val>> &data) {
	//引数dataが入っている状態のハッシュテーブルを構築する。

	//まず各データのハッシュ値を計算する。
	std::vector<uint64_t>hashcodes(data.size());
	for (int i = 0; i < data.size(); ++i) {
		hashcodes[i] = hashfunc(data[i].first);
	}

	for (int N = std::max(int(_mm_popcnt_u64(pow2_ceiling_log2(data.size()) - 1)), 10); N <= 57; ++N) {

		bitmask = (1ULL << N) - 1;

		//度数表を作る。
		std::vector<uint64_t>count((1ULL << N), 0);
		for (uint64_t i = 0; i < hashcodes.size(); ++i) {
			++count[hashcodes[i] & bitmask];
		}

		//各添字番号について、その要素が実際に格納され始める位置を求める。
		//32以上離れることがあれば、それはinsert失敗を意味するのでcontinueする。
		bool flag = true;
		std::vector<uint64_t>start_pos((1ULL << N), 0);
		for (uint64_t i = 1; i < (1ULL << N); ++i) {
			start_pos[i] = std::max(start_pos[i - 1] + count[i - 1], i); // main DP
			if (start_pos[i] - i >= 32) {
				flag = false;
				break;
			}
		}
		if (!flag)continue;
		if (start_pos[(1ULL << N) - 1] + count[(1ULL << N) - 1] >= (1ULL << N) + 32)continue;

		//
		//insertが失敗しないことが分かったので、ハッシュテーブルを構築する。
		//

		tablesize = (1ULL << N) + 31;
		hash_table = std::vector<std::pair<Key, Val>>(tablesize);
		signature_table = std::vector<uint8_t>(tablesize, EMPTY_SIGNATURE);

		for (int i = 0; i < data.size(); ++i) {
			const uint64_t hashcode = hashcodes[i] & bitmask;
			hash_table[start_pos[hashcode]] = data[i];
			signature_table[start_pos[hashcode]] = uint8_t(hashcodes[i] >> 57);
			assert(start_pos[hashcode] - hashcode < 32ULL);
			++start_pos[hashcode];
		}

		return;
	}

	throw std::exception("HashTable size > 2^58");
}