概要

暗号技術で有名な MD5 や SHA-1, SHA-2 (SHA-256など) はハッシュ関数です。ハッシュ関数はある集合 A から別のある集合 B への写像関数のようなもので、集合 A の要素 a を入力として実行すると集合 B の要素 b が出力されます。このとき要素 b のことを要素 a のハッシュ値とよびます。また、集合 A の要素と集合 B の要素の対応表をハッシュ表とよびます。一般に集合 A をハッシュ関数に通すと、圧縮された集合 B が出力されます。つまり、集合 A の異なる a1 と a2 を入力すると集合 B の同じ値 b が出力されることがあります。

二分探索木 (集合や連想配列) などのデータ構造とハッシュ関数を組み合せると、データ構造だけを利用してデータを管理する場合と比較して検索性を向上させることができます。これをハッシュ法とよびます。ハッシュ法におけるハッシュ関数には処理時間がかからないことが求められます。

ハッシュ法の実装例

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

class MyHash {
public:
    static const size_t HASH_TBL_SIZE = 23;
    static size_t Get(const string& value);

public:
    string& operator[](const string& key);

private:
    map<string, string> m_hashTable[HASH_TBL_SIZE];
};

size_t MyHash::Get(const string& value) {
    size_t size = value.size();
    const unsigned char* p // https://www.qoosky.io/techs/d5709e9878
        = reinterpret_cast<const unsigned char*>(value.data());
    return (p[0] + p[size /2] + p[size - 1]) % HASH_TBL_SIZE;
}

string& MyHash::operator[](const string& key) {
    return m_hashTable[Get(key)][key];
}

int main() {
    MyHash h;
    h["one"] = "ichi";
    h["two"] = "ni";
    cout << h["one"] << endl; //=> ichi
    cout << h["two"] << endl; //=> ni
    return 0;
}