ハッシュ表

はじめに

perlのプログラムをc++に移したいという話で、連想配列をどうするかでハッシュの話が出てきたので調べてみた。

ハッシュ関数とは

  • あるデータ(key)に対応する数値(value)を得るための関数
    • 例えば、文字列(key)に対応する数字(value)、など
  • 優れたハッシュ関数とは、「計算に時間がかからず(低コスト)」「同じキーに対して常に同じハッシュ値を返し(決定性)」「等確率でハッシュ値を出力する(一様性)」ような関数
完全ハッシュ関数
  • ありうる入力に対し、ハッシュ関数単射であるようなハッシュ関数
  • 衝突が起きないが、あらかじめ入力となるキー集合がわかっていてしかも静的でなければならない
  • 文字列に対し完全ハッシュ関数を返してくれる生成器に「gnu gperf」がある(らしい)
最小完全ハッシュ関数
多くのハッシュ関数

ハッシュ表とは

  • 衝突問題
    • あるハッシュ関数において、「HOGE」という文字列と「MOGE」という文字列が同じハッシュ値を返した場合、同じ要素へアクセス(衝突)が発生してしまう
チェイン法
  • 衝突を避けるため、リストを要素に持つような配列を使い、衝突が生じたらリストに追加する
  • 実装例
    • 各要素がリスト形式のサイズがNの配列(ルート配列)を用意する
    • 追加したいkeyのハッシュ値を計算し、そのハッシュ値をインデックスとして配列にアクセスする
    • その要素のリストの中からkeyが存在すれば検索成功(または、key-valueを挿入する)
オープンアドレス指定法
  • チェイン法のように、リストを要素にもつようなことはせず、衝突が生じた場合は配列の空いている別な場所を計算で求めていく方法
  • すべてが埋まってしまった場合、データが格納できなくなる
  • 線形探査法、2次関数探査法、ダブルハッシュ法など
完全ハッシュ法
  • 必ず1回の探索で必要なメモリアクセス回数がO(1)であるようなハッシュ法
    • 格納したいkey集合に対して、必ず衝突が起きないようなハッシュ関数を選ぶ方法
  • 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