C++鏈地址法實現哈希表

哈希表，也叫散列表，是根據關鍵碼值(Key　value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做哈希函數，存放記錄的數組叫做哈希表。

哈希函數最主要的設計在於哈希函數和沖突處理的解決，其中哈希函數的設計方法主要有直接定址法和除留余數法；沖突處理的方法主要有開放定址法和鏈地址法。本文主要實現了一個基本存放字符串的哈希表，沖突處理采用鏈地址法。

代碼如下：

#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<<")";
            cout<<")"<value<