連想配列実装第二弾～ハッシュテーブル編～

今回のアルゴリズム

今回は、ハッシュテーブルを試したいと思います。

#ソースコード

ソースコード

main.cpp

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <sstream>
#include <openssl/md5.h>

template<class T>
class Hash_Table{	
	
public:

struct myuint24_t{
	unsigned long v : 24;	
};

long n;
MD5_CTX md5_data;

T* data;

unsigned long Get_hash(std::string data){
	myuint24_t v;
	
if(MD5_Init(&md5_data)!=1){
		exit(-1);
	};
	unsigned char md[MD5_DIGEST_LENGTH];
	MD5_Update(&md5_data, data.c_str(), strlen(data.c_str()));
	MD5_Final(md, &md5_data);
	
	v.v=(*(unsigned long*)(md));
	return (unsigned long)(v.v);
}

Hash_Table(){

	n=pow(2,24);

	data=new T[n];
	
	if(data==NULL)exit(-1);
	
};


T& operator [](std::string n) {
	 return data[Get_hash(n)]; 
}

~Hash_Table(){
	delete[] data;
}
	
};

解説

まず、2の24乗個の配列を定義しています。
添え字で文字列を入れた時に、その文字列のmd5の下位24bitの部分を取得してそのハッシュ値で配列にアクセスしています。
ライブラリはopenSSLを使っています。

使い方

main.cpp

//main.cppの続き

int main(){

Hash_Table<long> a;

a["key"]=100L;

std::cout<<a["key"]<<std::endl;//100

};

その他

衝突処理は実装していません。