C++チェーンアドレス法によるハッシュテーブルの実現

ハッシュ・テーブルは、ハッシュ・リストとも呼ばれ、キー値(Key value)に基づいて直接アクセスするデータ構造である.つまり、キー値をテーブルの1つの場所にマッピングすることでレコードにアクセスし、検索を高速化します.このマッピング関数をハッシュ関数と呼び,記録を格納する配列をハッシュテーブルと呼ぶ.
ハッシュ関数の最も主要な設計はハッシュ関数と衝突処理の解決にあり、その中でハッシュ関数の設計方法は主に直接アドレス法と残留残数法がある.衝突処理の方法は主にオープンアドレス法とチェーンアドレス法がある.本論文では,競合処理にチェーンアドレス法を用いた基本格納文字列のハッシュテーブルを主に実現した.
コードは次のとおりです.

#include 
#include

#define HASHSIZE 19

using namespace std;

struct hashnode{
    char *key;
    char *value;
    hashnode *next;
};


char *strcopy(char *s)
{
    int len=strlen(s)+1;
    char *res=new char[len];
    strcpy(res,s);
    if(res==NULL)
        return NULL;
    return res;
}


class hashtable
{
public:
    hashtable();
    ~hashtable();
    unsigned int hasher(char *s);
    hashnode *hashfind(char *keys);
    bool hashinsert(char *keys,char *values);
    bool hashdelete(char *keys);
    void display();
private:
    hashnode *hashdata[HASHSIZE];
};

hashtable::hashtable()
{
    for(int i=0;inext;
                delete p->key;
                delete p->value;
                delete p;
                p=q;
            }
        }
    }

}

//hash        
unsigned int hashtable::hasher(char *s)
{
    unsigned int res=0;
    for(;*s!='\0';++s)
        res=*s+res;
    return res%HASHSIZE;
}

hashnode* hashtable::hashfind(char *keys)
{
    unsigned int res=hasher(keys);
    hashnode *p=hashdata[res];
    for(;p!=NULL;p=p->next)
        if(strcmp(p->key,keys)==0)
            return p;
    return NULL;
}

bool hashtable::hashinsert(char *keys,char *values)
{
    unsigned int res;
    if(keys==NULL)
        return 0;
    hashnode *p;
    if((p=hashfind(keys))==NULL)
    {
        res=hasher(keys);
        p=new hashnode;
        if(p==NULL)
            return 0;
        p->key=strcopy(keys);
        p->value=strcopy(values);
        if(p->key==NULL)
            return 0;

        p->next=hashdata[res];  //     
        hashdata[res]=p;
    }
    else
    {
        delete p->value;  //  key     ，     value 
        p->value=strcopy(values);
    }
    if(p->value==NULL)
        return 0;
    return 1;
}

bool hashtable::hashdelete(char *keys)
{
    hashnode *p=NULL,*q=NULL;
    unsigned int res=hasher(keys);
    p=hashdata[res];
    if(!p)
        return 0;
    if(strcmp(p->key,keys)==0)
     {
         hashdata[res]=p->next;
         delete p->key;
         delete p->value;
         delete p;
     }
    q=p;p=q->next;
    while(p&&(strcmp(p->key,keys)!=0))
    {
        q=p;
        p=p->next;
    }
    if(p)
    {
        q->next=p->next;
        delete p->key;
        delete p->value;
        delete p;
    }
    return 1;
}

void hashtable::display()
{
    hashnode *p;
    for(int i=0;inext)
                cout<key<value<value<