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

初めに

勝手にシリーズ化しました

前回
二分探索木のサンプルコード
二分探索木で自作の連想配列を作りました。
しかし、二分探索木はウィキペディアによると

二分探索木

平衡（左右のバランスがとれている状態）している状態では木の高さは O(log2 N) となる。ただし最悪の場合は、事実上の 線形リスト になり、木の高さは O(N) となる。

まぁ、よくよく考えたら当たり前ですよね...

対策

AVL木やB木を使うと平衡になるのでO(log2 N)になります。

今回のアルゴリズム

AVL木やB木はまた今度やるとして、
今回は、ハッシュテーブルを試したいと思います。

ソースコード

ソースコード

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

};

衝突処理どうするの?

自作しましょう...