Algorithm 問題を解く 6 - ハッシュ

ハッシュ

ハッシュはバイナリサーチよりも効率的に検索をしたい場合に必須になるアルゴリズムである．
手短にハッシュを説明すれば，

1. 一程度のメモリ領域をハッシュバケットとして確保
2. ハッシュコードを要素から算出し，そのハッシュコードを検索キーとしてハッシュバケット中の１スロットに挿入

となる．例えば以下のハッシュバケット領域があったとして
0x0000 .. NO DATA
0x0001 .. NO DATA
0x0002 .. NO DATA
あるデータ X を保存したいとする．Xのハッシュキーが2だったらば，上記のハッシュバケットは
0x0000 .. NO DATA
0x0001 .. NO DATA
0x0002 .. { X }
となる．
検索はハッシュキーを元にデータを検索し，計算量はO(1)であり，２分検索の平均O(logN)より効率的である．

ハッシュコリジョン

当然，別のデータが同じハッシュキーを持つことがある．そういった場合はそのハッシュキーのスロットは大抵は循環リストのデータ構造を持つか，または別の空きスロットを見つける(オープンアドレッシング)する．最悪の場合の計算量はO(n)となる．


問題

Given a dictionary of English words, return the set of all words grouped into subsets of words that are all anagrams of each other.

Algorithms for Interviews より引用．


解答

#include <iostream>
#include <map>
#include <list>
using namespace std;

list<string> dict;

void init_dict() {

 dict.push_back( string("dog") );
 dict.push_back( string("god") );
 dict.push_back( string("redrum") );
 dict.push_back( string("murder") );
 
}

void analyze( list<list<string>> ls ) {

 list<string> l;
 string s;
 map<int,list<string>> m;
 list<string>::iterator iter;

 for( iter = dict.begin();iter != dict.end();iter++ ) {

  int sum = 0;
  s = *iter;
  for( int i = 0;i < s.length();i++ ) {
   sum += s[i];
  }
  if( m.find(sum) == m.end() ) {
  
   l.clear();
   l.push_back(*iter);
   m[sum] = l;

  }
  else {

   l = m[sum];
   l.push_back(*iter);
   m[sum] = l;

  }

 }

 map<int,list<string>>::iterator mapIter;
 pair<int,list<string>> t;
 for( mapIter = m.begin();mapIter != m.end();mapIter++ ) {
  t = *mapIter;
  cout << t.first << ":{";
  list<string>::iterator li = t.second.begin();
  for(;li != t.second.end();li++)
   cout << li->data() << ",";
  cout << "}" << endl;

 }



}


int main() {

 init_dict();
 list<list<string>> ls;
 analyze(ls);
 list<string>::iterator iter;
 for( iter = dict.begin();iter != dict.end();iter++) {
  cout << (*iter).c_str() << endl;
 }

 return 0;
}