ハッシュ表
ハッシュ関数とは
- あるデータ(key)に対応する数値(value)を得るための関数
- 例えば、文字列(key)に対応する数字(value)、など
- 優れたハッシュ関数とは、「計算に時間がかからず(低コスト)」「同じキーに対して常に同じハッシュ値を返し(決定性)」「等確率でハッシュ値を出力する(一様性)」ような関数
完全ハッシュ関数
最小完全ハッシュ関数
ハッシュ表とは
チェイン法
オープンアドレス指定法
- チェイン法のように、リストを要素にもつようなことはせず、衝突が生じた場合は配列の空いている別な場所を計算で求めていく方法
- すべてが埋まってしまった場合、データが格納できなくなる
- 線形探査法、2次関数探査法、ダブルハッシュ法など
実装
- 簡単なチェイン法を書いてみた
- 要素はリストの代わりにsetを使った
コード
#include <iostream> #include <set> #include <algorithm> #include <utility> using namespace std; //ハッシュテーブル的なもの template<int M> class Hash { typedef std::string key_type; typedef int val_type; typedef std::pair<key_type,val_type> pair_key_value; typedef std::set<pair_key_value> set_pair; set_pair hash_table[M]; struct match_str{ key_type str; match_str(const key_type& str):str(str){} bool operator()(const pair_key_value& rhs) const { return rhs.first == str; } }; public: Hash(){} val_type search(key_type str){ int key = getHashKey(str); set_pair::iterator itr = std::find_if(hash_table[key].begin(), hash_table[key].end(), match_str(str)); if(itr != hash_table[key].end()) return (*itr).second; return 0; } void insert(key_type str, val_type value){ int key = getHashKey(str); set_pair::iterator itr = std::find_if(hash_table[key].begin(), hash_table[key].end(), match_str(str)); if(itr != hash_table[key].end()) delstr(str); hash_table[key].insert(make_pair(str,value)); } void delstr(key_type str){ int key = getHashKey(str); set_pair::iterator itr = std::find_if(hash_table[key].begin(), hash_table[key].end(), match_str(str)); if(itr != hash_table[key].end()){ hash_table[key].erase(itr); } } int getHashKey(key_type str){ int ret = 0; for(int v=0; v < str.length(); v++) ret = (64*ret + (size_t)(str[v])) % M; return ret; } }; //乱数 // 注意: longではなくint(32bit)にすべき unsigned long xor128(){ static unsigned long x=123456789,y=362436069,z=521288629,w=88675123; unsigned long t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } //適当な文字列を返す string get_random_text(){ string ret = ""; for(int i=0; i<10; i++){ ret += 'a' + xor128() % 26; } return ret; } int main(){ Hash<101> hash; for(int i=0; i<10; i++){ string str = get_random_text(); int val = xor128()%100; hash.insert(str, val); cout << str << "'s hash is " << hash.getHashKey(str) << " and value is " << val << endl; cout << "search: " << str << "'s value is " << hash.search(str) << endl; cout << endl; } return 0; }
結果
$ ./a.exe ewkwgebeyn's hash is 56 and value is 72 search: ewkwgebeyn's value is 72 dqvyrkgcou's hash is 66 and value is 44 search: dqvyrkgcou's value is 44 iorrzowdvk's hash is 46 and value is 46 search: iorrzowdvk's value is 46 opxgirlgmw's hash is 85 and value is 53 search: opxgirlgmw's value is 53 lwfugxgrtm's hash is 17 and value is 0 search: lwfugxgrtm's value is 0 yzqewelucp's hash is 28 and value is 60 search: yzqewelucp's value is 60 eebsmexoem's hash is 73 and value is 12 search: eebsmexoem's value is 12 umbxixsyna's hash is 0 and value is 17 search: umbxixsyna's value is 17 xsxqovsjud's hash is 3 and value is 4 search: xsxqovsjud's value is 4 nhowahxgpz's hash is 46 and value is 69 search: nhowahxgpz's value is 69