C/C++: 文字列をキーとする自作ハッシュ関数を作る

本記事では、文字列をキーとしてハッシュ化するハッシュ関数について簡単にまとめてみました。

手法1) 各文字の文字コードの和を求める

一番シンプルな方法です。ハッシュ化対象の文字列の各文字の文字コード（ここではACIIコードとします）の和を求めて、ハッシュテーブルのサイズ (TABLE_SIZE) の mod を取る方法です。当然、ハッシュキーの衝突（コリジョン）が起きる可能性があるため、ハッシュ関数として利用する場合にはチェーン法やオープンアドレス法での実装が必要になります（今回の対象外）。

constexpr int TABLE_SIZE = 19;

int create_hash_key(string key) {
  int hash = 0;
  for (auto c : key) {
    hash = (hash + c) % TABLE_SIZE;
  }
  return hash;
}

手法2) 線形合同法

入力の文字列に対して出来るだけ均一にランダムで重複しないようにした手法1の改良版です。アルゴリズム自体は、乱数発生の線形合同法の流用です。

constexpr int P = 124901413; // 素数
constexpr int TABLE_SIZE = 19; // テーブルサイズも素数が良いと言われているが、場合によっては2^nが良いこともありそう

int create_hash_key(string key) {
  int hash = 0;
  for (auto c : key) {
    hash = (hash * P + c) % TABLE_SIZE;
  }
  return hash;
} 

手法3) ローリングハッシュ

あまり理解出来てないですが、ローリングハッシュという手法もあります。詳しくは蟻本片手に学ぶアルゴリズム ~ローリングハッシュ~を参照してみて下さい。