C++ ハッシュ 書いて覚えるための初心者自己中記事

検索しやすいデータ構造の１つ

データを保管する際ハッシュ関数を通す。

ハッシュ関数は様々なデータに対して、良い感じにグループ的な値を出してくれる関数。

ハッシュ関数を通ったデータはハッシュ関数が導き出したグループに所属する。

何かデータを検索するときは、同じようにハッシュ関数を通せばそのデータが所属するグループがわかるので、すべてのデータを検索するより早くなる。

 ハッシュ関数内の処理は、送られてきたデータに同一の処理をしてなるべく均等に一定範囲内の値が出るようにする。

ハッシュ関数が出すハッシュ値は配列のインデックスとして管理できる。

ハッシュ値を管理するものをハッシュ表を呼ぶ。

ハッシュ表の先のデータ構造は前回勉強した二分検索木のデータ構造にするといい。

今回も考えながらだな。

template <typename TYPE>
class HashFn {
public:
	static size_t Get(const TYPE& value);
	static const size_t SIZE = 23;//ハッシュ表のサイズ
};
 
template<>
size_t HashFn<string>::Get(const string& value) {
	size_t size = value.size();
	const unsigned char* p = reinterpret_cast<const unsigned char*>(value.data());
	return (p[0] + p[size / 2] + p[size - 1]) % SIZE;
}

まず、ハッシュ関数をメンバに持ったクラステンプレートを作る。

といっても、特殊化したstring 以外は実装されていない。

string のハッシュ関数の中身は

const unsigned char* にキャストして

１バイト目の値

中間バイトの値

最後の値

の合計をハッシュ表のサイズで割ったあまり。

サイズの中のどれかの数値になる。

次、別のクラステンプレート

template<
	typename KEY,
	typename VALUE,
	typename HASH_FN = HashFn<KEY>
>
class Hash {
private:
	typedef map<KEY, VALUE> Map;
	typedef typename Map::const_iterator CIterator;

private:
	Map m_hashTable[HASH_FN::SIZE];//ハッシュ表
};

テンプレートの型はKEY と VALUE

そして、さっき作ったハッシュ関数を持つクラステンプレートにKEYの型を指定したもの。

クラステンプレートHashではtypedefでクラステンプレートmapに型を指定したMap、そのMapのconst_iterator   CIteratorを命名。

そして、Map型（map<KEY,VALUE>)のメンバ変数m_hashTableを用意。

要素数はHASH_FN::SIZE の値を指定。

これはつまり？

クラステンプレートmap が配列になったということだな。

つぎ、

public:
	//キーに対応する値を取得
	VALUE& operator[](const KEY& key) {
		size_t hashValue = HASH_FN::Get(key); //ハッシュ値
		return m_hashTable[hashValue][key];
	}

演算子オーバーロードでは、KEYを引数にして、ハッシュ関数に引数を送っている。

戻り値であるハッシュ値をhashValue に代入。

m_hashTableの配列の要素番号にハッシュ値を入れて、さらにkeyを引数にしたのでクラステンプレートmapでもともとキーを入れたらvalueの参照が返ってくる。でいいのかな。

次、

//キーに対応する値を取得
//キーが見つからなければ　out_of_range 例外を投げる
const VALUE& operator[](const KEY& key)const {
	size_t hashValue = HASH_FN::Get(key);//ハッシュ値
	const Map& map = m_hashTable[hashValue];
	CIterator it = map.find(key);
	if (it == map.end()) {
		throw out_of_range("見つかりませんでした");
	}
	return it->second;
}

こっちはハッシュ値使ってm_hashTableの配列の一つを別に用意したmapに渡してクラステンプレートmapのメンバ関数findを使って探している。

findは見つからない場合に終端ノードを返すのでその後のifになる。

テンプレートクラスHashはここまで。

使用例は以前の二分探索木と一緒。

typedef Hash<string, string> HashSS;
bool Input(string& str) {
	cout << "文字列を入力してください > " << flush;
	str = "";
	getline(cin, str);
	return !str.empty();
}
 
void Check(const HashSS& assoc, string str) {
	try {
		cout << assoc[str] << endl;
	}
	catch (const out_of_range& e) {
		cerr << e.what() << endl;
	}
} 
int main() {
	HashSS hashss;
	hashss["Type"] = "Rectangle";
	hashss["Size"] = "1024×768";
	hashss["Color"] = "Green";
	string str;
	while (Input(str)) {
		Check(hashss, str);
	}
	system("pause");
}

ハッシュ部分はテンプレートクラス内で完結していて、外側からは使っているのかわからないのか。

ここまで。