最初に

趣味でプログラミングをやっています。間違いなどあったら指摘してほしいです。
グラフや図を作る方法を知らないのですべて手書きです。ハンドメイドな記事です。
説明が下手かもしれないです。

こんな人に読んでほしい

みんな

経緯

結構前にこんなブログに出会いました（ブログの説明がわかりやすすぎるのでここでは説明しません）

要は、1ビットだけ立っている64ビット整数にハッシュ値をかけたりしてテーブルに代入するとビットが立っている位置（何桁目か）がわかるよ！ってことです。頭良すぎですね。

このブログで、すごい！すごすぎる！この値はどうやって求めたんだろう？と、ハッシュ値の求め方への疑問だけが投げかけられていて、求め方が載っていなかったので自分で求めちゃおうというのが経緯というか今回の内容です。

求めてみる

前準備

関数名とコメントの説明一瞬見るだけでなんとなくわかると思います。

main.cpp

#include <iostream>
#include <array>
#include <bitset>
#include <algorithm>

constexpr std::size_t BIT_SIZE = 64;
constexpr std::size_t INDEX_SIZE = 6;

using bit_t = std::uint64_t;
using array_t = std::array<bool, BIT_SIZE>;


const bit_t MASK = 0b111111; //tableのindexに収めるためのマスク

//bitを6桁切り出して0～63が含まれているかどうかを確認する。
bool isHash(bit_t bit) {
	bool checkArr[BIT_SIZE]; //重複をチェックする配列
	std::fill(std::begin(checkArr), std::end(checkArr), false);

	for (bit_t checkBit = 0b1; checkBit; checkBit <<= 1) {
		std::size_t index = (bit * checkBit) >> (BIT_SIZE - INDEX_SIZE); //tableのindexに変換

		if (checkArr[index]) {
			return false;
		}
		else {
			checkArr[index] = true;
		}
	}

	return true;
}


void getTable(bit_t hash, int table[BIT_SIZE]) {
	for (int i = 0; i < BIT_SIZE; ++i) {
		table[hash >> (BIT_SIZE - INDEX_SIZE)] = i;
		hash <<= 1;
	}
}

//実際にtableを用意し、桁を計算して答えと照らし合わせることで整合性をチェックする
bool checkHash(bit_t hash) {
	int table[BIT_SIZE];
	getTable(hash, table);

	int i;
	bit_t bit;
	for (i = 0, bit = 1; bit; bit <<= 1, ++i) {
		//bitをindexに変換したものをtableに代入し、i（正当）と照らし合わせる
		if (table[(bit * hash) >> (BIT_SIZE - INDEX_SIZE)] == i) {
			continue;
		}
		else {
			return false;
		}
	}

	return true;
}

安直すぎる方法

最初は何も深く考えずに求めてみようと思います。

main.cpp

//安直な実装
void getHash_antyoku() {
	for (bit_t bit = 1; bit; ++bit) { //bitがオーバーフローしたら終了
		if (isHash(bit)) {
			std::cout << std::bitset<BIT_SIZE>(bit) << std::endl;
		}
	}
}

最悪ですね。だいたい2の64乗通りを求めるプログラムです。全然計算が終わりません。

速そうな方法を考える

64ビット整数のままだとわかりずらいので8ビット整数規模にしてみましょう。

ハッシュを8ブロックで表して、桁を0から7でラベルします。
ビット位置を求める手順を視覚化すると、まずhash * bitをして、その次に>>(8-3)しているのがわかると思います。
8ビットの場合、indexは0から7なので二進数で3桁になります。つまり、最後に残った下3桁がtableのindexとなります。

試しにbit = 1 << (8-1)としてみましょう。すると、桁0のビットだけが残ります。

今度はbit = 1 << (8-2)としてみましょう。すると、桁0と桁1のビットだけが残ります。

お気づきでしょうか、桁0のビットを0にするか1にするかで分岐すると、桁1のビットも0か1に、それ以降の桁も芋づる式に0か1に分岐できるじゃないですか。これで、総当たりだったものが計画的に分岐できるようになります。

具体的な方法は以下のようになります。
indexに変換して、被りがないかを確認しながら桁0から順に0か1かで分岐していきます。

そして8ビットでの探索の結果がこちらです。
?はまだ分岐していないところです。切り出した数が重複しないように一桁ずつ増やしていきます。

result.txt

> ????????
|--> ???????0
|  |--> ??????10
|  |  |--> ?????010
|  |  |  |--> ????0010
|  |  |  |--> ????1010
|  |  |  |  |--> ???11010
|  |  |  |  |  |--> ??011010
|  |  |  |  |  |  |--> ?0011010
|  |  |  |  |  |--> ??111010
|  |  |  |  |  |  |--> ?0111010
|  |  |  |  |  |  |  |--> 00111010 <-Hash
|  |  |--> ?????110
|  |  |  |--> ????0110
|  |  |  |  |--> ???00110
|  |  |  |  |--> ???10110
|  |  |  |  |  |--> ??010110
|  |  |  |  |  |  |--> ?0010110
|  |  |  |--> ????1110
|  |  |  |  |--> ???01110
|  |  |  |  |  |--> ??001110
|  |  |  |  |  |--> ??101110
|  |  |  |  |  |  |--> ?0101110
|  |  |  |  |  |  |  |--> 00101110 <-Hash
|--> ???????1
|  |--> ??????01
|  |  |--> ?????001
|  |  |  |--> ????0001
|  |  |--> ?????101
|  |  |  |--> ????1101
|  |  |  |  |--> ???01101
|  |  |  |  |  |--> ??001101
|  |  |  |  |  |  |--> ?0001101
|  |  |  |  |--> ???11101
|  |  |  |  |  |--> ??011101
|  |  |  |  |  |  |--> ?0011101
|  |  |  |  |  |  |  |--> 00011101 <-Hash
|  |--> ??????11
|  |  |--> ?????011
|  |  |  |--> ????0011
|  |  |  |  |--> ???00011
|  |  |  |--> ????1011
|  |  |  |  |--> ???01011
|  |  |  |  |  |--> ??001011
|  |  |  |  |  |  |--> ?0001011
|  |  |--> ?????111
|  |  |  |--> ????0111
|  |  |  |  |--> ???00111
|  |  |  |  |  |--> ??000111
|  |  |  |  |--> ???10111
|  |  |  |  |  |--> ??010111
|  |  |  |  |  |  |--> ?0010111
|  |  |  |  |  |  |  |--> 00010111 <-Hash

<-Hashとなっているのがハッシュ値です。確かめてみてください。

もうここまで来たらあとは簡単ですね。64ビットに拡張するだけです。

速そうな実装

main.cpp

//速そうな実装
/*
* countで何回目の再帰なのかを確認する
* checkArrですでにbitに含まれる6桁indexを保存、重複の確認に用いる
*/
void getHash_fast(bit_t bit, std::size_t count, const array_t& checkArr) {
	if (count == BIT_SIZE) { //BIT_SIZEまで到達した
        //結果表示＆チェック
		std::cout << std::bitset<BIT_SIZE>(bit) << " " << (checkHash(bit) ? "OK" : "NG") << std::endl;
		return;
	}

	std::size_t leftShift = BIT_SIZE - 1 - count;
	std::size_t rightShift = BIT_SIZE - INDEX_SIZE;

	bit_t index = bit << leftShift >> rightShift; //indexに変換

	if (checkArr[index]) { //checkArrで重複しているかどうか
		array_t checkArr_copy = checkArr;
		checkArr_copy[index] = false;
		getHash_fast(bit, count + 1, checkArr_copy);
	}

	index |= (bit_t)0b1 << (INDEX_SIZE - 1); //1を追加してみる
	if (checkArr[index]) { //再びcheckArrで重複しているかどうか
		array_t checkArr_copy = checkArr;
		checkArr_copy[index] = false;
		getHash_fast(bit | ((bit_t)0b1 << count), count + 1, checkArr_copy);
	}
}

int main()
{
	array_t arr;
	std::fill(arr.begin(), arr.end(), true);
	getHash_fast(0, 0, arr);
}

そして結果がこちらです。

result.txt

0000011101101001011001001111001101111110101011100010100011000010 OK
0000011101100100101101001111001101111110101011100010100011000010 OK
0000011110011010011101100100101101111110101011100010100011000010 OK
0000011101100110100111100100101101111110101011100010100011000010 OK
0000011110011101100100110100101101111110101011100010100011000010 OK
0000011101100111100100110100101101111110101011100010100011000010 OK
0000011110010011101100110100101101111110101011100010100011000010 OK
0000011101100100111100110100101101111110101011100010100011000010 OK
0000011110011010010011101100101101111110101011100010100011000010 OK
0000011101100110100100111100101101111110101011100010100011000010 OK
0000011110010110011010010011101101111110101011100010100011000010 OK
0000011110011010010110010011101101111110101011100010100011000010 OK
（以下略）

実行してから爆速でこれでもかというほど大量のハッシュ値候補が出てきます。正直こんなにたくさんあると思っていませんでした。かっこよくて見てて飽きません。

まとめ

不安になるくらいハッシュ値が大量ですが、ハッシュ値を無事求めることができました。
お好きなハッシュ値を召し上がってください。
ここまで読んでくださりありがとうございました。