インベント・大車輪（ハッシュテーブル）

あらすじ：連想配列を使いたければＳＴＬを使えばいいじゃない

で、実際にゲームに組み込んでみたところ、謎のリンクエラーが。_Xran()とか_Xlen()の実体が無いとかなんとか。もちろん、身に覚えなんてありましぇん。で、調べてみたのですが、そもそもXran()とかで引っかからない。めげずに調べてみると、ゲーム系の界隈でちらほらと話題が。確証はありませんが、DirectX系のライブラリとＳＴＬのstringの相性があんま良くないとかなんとか。のろわれてしまえ。

ならばと、stringを自作してもいいのですが、std::mapに組み入れるためには、イテレータとかそれなりに体裁を整える必要があるんか？面倒いなぁ…。

…ということで、いつもの通り車輪の再発明精神を発揮してフルスクラッチしてやりますとも

#define STRING_HASH_SIZE	31

class CHashList
{
public:
	CHashList(){ key=0;	data=0;	pNext = 0;};
	CHashList(const char* pKey, const char* pData);

	void        Init(){pNext = 0;};
	CHashList*  GetNext(){return pNext;};
	const char* GetData(){return data;};

	int         Hantei(const char* pKey);
	void        Add(CHashList* pNew){ pNew->pNext = pNext; pNext = pNew; };

	void        Release();

private:
	char*	key;
	char*	data;

	CHashList*	pNext;
};

class CHash
{
public:
	~CHash(){Release();};

	void            Set(const char* pKey, const char* pData);
	const char*     Get(const char* pKey);

	void            Release();

private:
	unsigned int    GetHash(const char* pKey);

	CHashList       mTable[STRING_HASH_SIZE];
};

つうことでつくりました、string,stringなハッシュ。文字列をキーで入れると、文字列のデータが出てくるハッシュテーブル。

CHash::mTable[]ってのが実際のテーブルです。ここにガスガスとデータを入れていきます。ハッシュテーブルのサイズは素数にするとよいと実験がされてるそうで、あと、一色さんが「３１」がパフォーマンスよい、とおっしゃってたので、とりあえず３１に。今回に限った実用で云うと、もうちょっと少なめでいいかな…？ともあれ、CHash::Set(pKey,pData)で突っ込んでいきます。

void CHash::Set(const char* pKey, const char* pData)
{
	CHashList* pNew = new CHashList(pKey, pData);
	mTable[GetHash(pKey)].Add(pNew);
}

限られたテーブルだと、満杯になっちゃうので、実際はリストにしておきます。CHash::Set()内で、CHashList（データを突っ込むリスト）をnewしてCHash::mTable[]に挿入します。で、３１個あるデータ受け口のどこにデータを突っ込むのか？を判定するのが「ハッシュ関数」CHash::GetHash()です。

unsigned int CHash::GetHash(const char* pKey)
{
	unsigned int Hash = 0;
	for(int idx=0; pKey[idx]; idx++)
	{
	    Hash += pKey[idx];
	}
	Hash %= STRING_HASH_SIZE;

	return Hash;
}

ハッシュ関数は、入力のキーからテーブルの添え字となるハッシュ値を算出します。適当な写像が得られれば、実用にはなるのですが、実際の入力に対してできるだけ均等に分布するような出力が得られれば、３１個のテーブルに満遍なくデータが入り、効率がよくなります。いかに性能の良い関数を作るかがキモになるのですが、一色さんがキー値の剰余をとってやれば十分実用になるとおっしゃってたので、右に倣っておきます。キー値の算出は文字コードを順番に足しこんでやってますが、もうちょっと抜粋してやってもＯＫっぽいです。

こんな感じで、データを次々にCHash::Set()してあげれば、テーブルにデータが貯まっていきます。データを格納し終わったら、次はキーからデータを抜き出す処理を行います。

const char* CHash::Get(const char* pKey)
{
	CHashList* pTmp;

	for( pTmp=mTable[GetHash(pKey)].GetNext(); pTmp; pTmp=pTmp->GetNext() )
	{
	    if(pTmp->Hantei(pKey) )
	        return pTmp->GetData();
	}
	return 0;
}

といっても、要はCHash::Set()したのと逆の操作をしてあげればいいわけです。先ず、mTable[GetHash()]としてやることで、キーをハッシュ関数に放り込んでデータが３１個のうちどこにあるのかがわかります。対象がわかったら、後はリストを辿って線形探索してあげます。CHashList::GetNext()で次々にリストを辿ってゆき、CHashList::Hantei(pKey)で判定した結果が真値をとったら終了です。こうして得られたデータは、めでたく、キー値でCHash::Set()してやったデータであるわけです。

つまり、

int main(int argc, char** argv)
{
    CHash tmpHash;

    tmpHash.Set( "hoge", "Hello! Hoge!!" );
    tmpHash.Set( "huga", "Hello! Huga!!" );
    tmpHash.Set( "piyo", "Hello! Piyo!!" );
    tmpHash.Set( "foo",  "Hello! Foo!!"  );
    tmpHash.Set( "bar",  "Hello! Bar!!"  );


    printf( "HashTest::%s\n", tmpHash.Get("piyo") );

    return 0;
}

というような使い方をすると、

    HashTest::Hello! Piyo!!

と結果が得られますね。めでたし、めでたし。

以下、ソースファイルを俯瞰で記しておきますよ。

#include "CHash.h"

CHashList::CHashList(const char* pKey, const char* pData)
{
	{
		int size;
		for(size=0; pKey[size]; size++);

		key = new char[size+1];
		key[size] = '\0';
		while( size-->0 )
		{
			key[size] = pKey[size];
		}
	}
	{
		int size;
		for(size=0; pData[size]; size++);

		data = new char[size+1];
		data[size] = '\0';
		while( size-->0 )
		{
			data[size] = pData[size];
		}
	}

	pNext = 0;
}

int CHashList::Hantei(const char* pKey)
{
	int idx;
	for( idx=0; pKey[idx] && key[idx] && pKey[idx]==key[idx]; idx++ );

	if( pKey[idx] || key[idx] )
		return 0;
	else
		return 1;
}

void CHashList::Release()
{
	delete[] key;
	delete[] data;
}

void CHash::Release()
{
	for(int idx=0; idx<STRING_HASH_SIZE; idx++)
	{
		CHashList*	pList;
		
		for( pList = mTable[idx].GetNext(); pList; )
		{
			pList->Release();

			CHashList* pTmp = pList;
			pList = pList->GetNext();

			delete pTmp;
		}
		mTable[idx].Init();
	}
}

unsigned int CHash::GetHash(const char* pKey)
{
	unsigned int Hash = 0;
	for(int idx=0; pKey[idx]; idx++)
	{
		Hash += pKey[idx];
	}
	Hash %= STRING_HASH_SIZE;

	return Hash;
}

void CHash::Set(const char* pKey, const char* pData)
{
	CHashList* pNew = new CHashList(pKey, pData);
	mTable[GetHash(pKey)].Add(pNew);
}

const char* CHash::Get(const char* pKey)
{
	CHashList* pTmp;

	for( pTmp=mTable[GetHash(pKey)].GetNext(); pTmp; pTmp=pTmp->GetNext() )
	{
		if(pTmp->Hantei(pKey) )
			return pTmp->GetData();
	}

	return 0;
}

うーん。ハッシュの自作にリストのフルスクラッチに、あそこに見えるはstrcpy()！！まごうことなき車輪の再発明！！