チェインハッシュ(Chain Hash)

概要

ハッシュテーブルと連結リストを組み合わせた構造。

ハッシュ

キーをハッシュ関数からハッシュ値を取ってグループ化する。
ハッシュ関数はキーの分布によって衝突が発生しにくくするとよい。

例：キー：int型ハッシュ関数:剰余

unsigned int hash(int key){ return (key<0?-key:key)%16; }

例：キー：string型ハッシュ関数:剰余

unsigned int hash(std::string key){ return key.length()%3; }

ハッシュ関数によって取り出される値をハッシュ値と呼ぶ。
ハッシュ値の値の範囲はハッシュテーブルに合わせる。
一般的に範囲を制限できる剰余が用いられることが多いです。

const int MAX_N = 128;

int gHashTable[MAX_N];

unsigned int hash(int key){ return (key<0?-key:key)%MAX_N; }

データの割り当て領域（取得や挿入する場所）はgHashTable[hash(key)]となる。
ハッシュ関数によって一意に決定されるので検索がO(1)でできる。(ハッシュ関数分の時間はかかるけど)

const int MAX_N = 10;
int gHashTable[MAX_N];

int hash(int key){ return key%10; }

gHashTable[hash(5)] = 128;   // 挿入
int a = gHashTable[hash(5)]; // 検索

しかし、問題はシノムニ（衝突）である。
例えば、x%10をハッシュ関数とするとhash(0)==hash(10)==0となってしまう。
このような衝突が発生しないようにする必要がある。

連結リストの可能性

シノムニが発生すると挿入や検索ができなくなってしまいます。
そこで、連結リストを使って対処することをチェインハッシュと呼びます。

ハッシュテーブルがそのまま値でしたが、ラッピングしてリスト構造にします。

キー:int データ:int

struct Node
{
	int key;
	int value;
	
	Node* next;
};

const int MAX_N = 64;

Node gHashTable[MAX_N]; // 先頭はダミーです

ハッシュ値が同一のキーはリスト構造にして、どんどん伸ばしていきます。
検索には、O(1) + O(m) = O(m)かかります。*mはハッシュ値あたりのシノムニ数
ハッシュ検索してから線形リスト検索になります。

ここのO(m)からも分かるように、シノムニが発生しにくいハッシュ関数を作ることが大きなテーマになります。

また、リスト構造ではなくて2分木で構成するともっと効率がよくなります。
(ヒープにしてみるといいね)

サンプルコード

キー：string型
データ：int型

宣言とハッシュテーブル・ハッシュ関数

#include <iostream>
#include <string>

#define SAFE_DELETE(p) { delete p; p=0; }

using namespace std;

//---------------------------------------------------------
// chain hash
//---------------------------------------------------------
struct Node { string key; int data; Node* next; };

const int MAX_N = 32;

Node gHashTable[MAX_N];

//---------------------------------------------------------
// function
//---------------------------------------------------------
unsigned int hash(const string key)
{
    string::const_iterator it  = key.begin();
    string::const_iterator end = key.end();

    unsigned int h = 0;

    while( it != end ){ h += (*it); ++it; }

    return h % MAX_N;
}

初期化とクリア処理

void init()
{
    for(int i=0;i<MAX_N;i++) gHashTable[i].next = 0;
}

void clear()
{
    Node* p;
    Node* q;

    for(int i=0;i<MAX_N;i++)
    {
        p = gHashTable[i].next;

        while( p )
        {
            q = p->next;
            SAFE_DELETE(p);
            p = q;
        }

        gHashTable[i].next = 0;
    }
}

更新挿入

int update(string key,int data)
{
    unsigned int h = hash(key);

    //-----------------------------------------------------
    // search and update
    //-----------------------------------------------------
    for(Node* p=gHashTable[h].next;p;p=p->next)
    {
        if( p->key == key ){ p->data = data; return 1; }
    }

    //-----------------------------------------------------
    // not found and insert
    //-----------------------------------------------------
    Node* ptr = new Node();

    ptr->key  = key;
    ptr->data = data;

    ptr->next = gHashTable[h].next;

    gHashTable[h].next = ptr;

    return 0;
}

検索

bool find(const string key,int& data)
{
    unsigned int h = hash(key);

    for(Node* p=gHashTable[h].next;p;p=p->next)
    {
        if( p->key == key )
        {
            data = p->data;
            return true;
        }
    }

    return false;
}

削除

bool remove(const string key)
{
    unsigned int h = hash(key);

    for(Node* p=&gHashTable[h];p->next;p=p->next)
    {
        if( p->next->key == key )
        {
            Node* q = p->next->next;
            SAFE_DELETE(p->next);
            p->next = q;

            return true;
        }
    }

    return false;
}

使い方

int main()
{
    init();

    update("hello",128);
    update("olleh",256);

    int data;

    while(true)
    {
        cout << ">>";

        string input1; cin >> input1;

        if( input1 == "quit"   ) break;

        else if( input1 == "update" )
        {
            cout << "key:";  string key; cin >> key;
            cout << "data:"; int data;   cin >> data;
            update(key,data);

            cout << "updated" << endl;
        }

        else if( input1 == "find" )
        {
            cout << "key:"; string key; cin >> key;

            if( find(key,data) ) cout << "find " << data << endl; else cout << "not found" << endl;
        }

        else if( input1 == "remove" )
        {
            cout << "key:"; string key; cin >> key;

            if( remove(key) ) cout << "removed" << endl; else cout << "not found" << endl;
        }
        else
        {
            cout << "command is quit, update, find and remove" << endl;
        }


    }

    clear();

    return 0;
}