洗塵齋

三懸明鏡垂鴻韻，九撩清泉洗塵心

導(dǎo)航

公告

lmlf001.blog.sohu.com/

留言簿(6)

隨筆分類(lèi)(41)

隨筆檔案(40)

閱讀排行榜

評(píng)論排行榜

常用鏈接

統(tǒng)計(jì)

隨筆 - 40
文章 - 0
評(píng)論 - 41
引用 - 0

哈希表的一個(gè)實(shí)現(xiàn)

今天寫(xiě)了一個(gè)哈希表的實(shí)現(xiàn)，采用了陣列加開(kāi)鏈表的形式
看了一下別人的寫(xiě)法，只用陣列，行數(shù)=100的時(shí)候空間利用率竟然達(dá)到97%

http://lmlf001.blog.sohu.com/

#ifndef _STORMLI_HASH_TABLE_H_
#define _STORMLI_HASH_TABLE_H_

#include<cstdlib>
#include<cmath>
#include<cassert>
#include<iostream>

template<typename valueType>
class HashTable
{
    enum KindOfNode{Active,Empty,Deleted}; //節(jié)點(diǎn)狀態(tài)，活躍/空/已刪除
public:
    int find(unsigned long _key);    //查找_key是否在表中，若在，返回0；否則返回-1；找到時(shí)，m,n為節(jié)點(diǎn)的位置
    int insert(unsigned long _key,const valueType &_value);    //插入節(jié)點(diǎn)，若該節(jié)點(diǎn)已在表中，返回1；若插入成功，返回0，表滿(mǎn)，返回-1
    int remove(unsigned long _key);    //刪除節(jié)點(diǎn) 若節(jié)點(diǎn)不存在，返回-1，成功時(shí)返回0
public:
    double getFullRate()const;    //返回Hash表空間利用率
    bool isFull()const{return currentSize==maxSize+maxList;}    //表是否為滿(mǎn)
    void clear();            //清除表內(nèi)容
    void setList(int len=5){if(listLen==-1) listLen=len;}    //default 5,the better one
    double getOverflowRate()const{return double(maxList)/currentSize;}
public:
    HashTable(unsigned long maxline,unsigned short line=5);    //構(gòu)造函數(shù)line default 5,a better range
    ~HashTable();
private:
    struct HashNode        //哈希節(jié)點(diǎn)
    {
        unsigned long key;    //name
        valueType value;    //value
        KindOfNode state;    //節(jié)點(diǎn)狀態(tài)
        HashNode():state(Empty){}
        ~HashNode(){}
    };

    struct list_node{        //鏈表節(jié)點(diǎn) 存儲(chǔ)溢出數(shù)據(jù)
        unsigned long key;
        valueType value;
        list_node *next;
        list_node():next(NULL){}
    };


    unsigned long currentSize;    //當(dāng)前數(shù)據(jù)量
    unsigned long maxSize;        //最大數(shù)據(jù)量
    unsigned long maxLine;        //每行最大值
    unsigned short lines;        //行數(shù)
    HashNode **ht;            //哈希陣列
    unsigned long *modTable;    //每行的模數(shù)
    unsigned long m,n;        //查找時(shí)存儲(chǔ)節(jié)點(diǎn)位置，否則做為臨時(shí)變量使用
    HashNode *mem;            //哈希表的實(shí)際存儲(chǔ)空間
    list_node * *Overflow_list;    //溢出鏈
    unsigned long maxList;    //list current size
    int listLen;    //list length  default -1---no limit

private:
    void getMode();            //生成模數(shù)
    void clear_Overflow();    //清除溢出鏈數(shù)據(jù)
};

template<typename valueType>
HashTable<valueType>::HashTable(unsigned long maxline,unsigned short line)
{
    maxLine=maxline;
    lines=line;
    currentSize=0;
    ht=new HashNode *[lines];
    assert(ht!=NULL);

    mem=new HashNode[maxLine*lines];    //實(shí)際空間
    assert(mem!=NULL);
    int i;
    for(i=0;i<lines;i++)        //分配空間到哈希陣列
        ht[i]=mem+maxLine*i;
    /*
    for(i=0;i<lines;i++){                //申請(qǐng)存儲(chǔ)空間
        ht[i]=new HashNode[maxLine];
        if(ht[i]==NULL){                //申請(qǐng)失敗，釋放已申請(qǐng)空間，退出
            for(j=i-1;i>=0;j++)
                delete []ht[j];
            delete []ht;
            exit(-1);
        }
    }
    */

    modTable=new unsigned long[lines+1];//modTable[lines]  Overlist
    assert(modTable!=NULL);
    getMode();
/*-----------not must need--------------------------------*/
    long temp=modTable[0];
    for(i=0;i<lines+1;i++)
        modTable[i]=modTable[i+1];
    modTable[lines]=temp;
/*------------------------------------------------------*/
    maxSize=0;
    for(i=0;i<lines;i++)
        maxSize+=modTable[i];//最大值

    Overflow_list=new list_node *[modTable[lines]];//Overflow head list ,all NULL pointer
    assert(Overflow_list!=NULL);
    listLen=-1;
    maxList=0;
}

template<typename valueType>
void HashTable<valueType>::getMode()
{        //采用 6n+1 6n-1 素?cái)?shù)集中原理
    if(maxLine<5){this->~HashTable();exit(-1);}

    unsigned long t,m,n,p;
    int i,j,a,b,k;
    int z=0;

    for(t=maxLine/6;t>=0,z<=lines;t--)
    {
        i=1;j=1; k=t%10;
        m=6*t;                                        /**i,j的值是是否進(jìn)行驗(yàn)證的標(biāo)志也是對(duì)應(yīng)的6t-1和6t+1的素性標(biāo)志**/
        if(((k-4)==0)||((k-9)==0)||((m+1)%3==0))j=0;/*此處是簡(jiǎn)單驗(yàn)證6*t-1,6*t+1 是不是素?cái)?shù)，借以提高素?cái)?shù)純度**/
        if(((k-6)==0)||((m-1)%3==0))i=0;            /***先通過(guò)初步判斷去除末尾是5，及被3整除的數(shù)***/
        for(p=1;p*6<=sqrt(m+1)+2;p++ )
        {
            n=p*6;                                    /**將6*p-1和6*p+1看作偽素?cái)?shù)來(lái)試除*****/
            k=p%10;
            a=1;b=1;                                /**同樣此處a,b的值也是用來(lái)判斷除數(shù)是否為素?cái)?shù)提高除數(shù)的素?cái)?shù)純度**/
            if(((k-4)==0)||((k-9)==0))a=0;
            if(((k-6)==0))b=0;
            if(i){                            /*如果i非零就對(duì)m-1即所謂6*t-1進(jìn)行驗(yàn)證，當(dāng)然還要看除數(shù)n+1,n-1,素性純度*/
                if(a){if((m-1)%(n+1)==0)i=0;}        /***一旦被整除就說(shuō)明不是素?cái)?shù)故素性為零即將i 賦值為零***/
                if(b){if((m-1)%(n-1)==0)i=0;}
            }
            if(j){                           /**如果j非零就對(duì)m+1即所謂6*t+1進(jìn)行驗(yàn)證，當(dāng)然還要看除數(shù)n+1,n-1,素性純度*/
                if(a){if((m+1)%(n+1)==0)j=0;}         /***一旦被整除就說(shuō)明不是素?cái)?shù)故素性為零即將j 賦值為零***/
                if(b){if((m+1)%(n-1)==0)j=0;}
            }
            if((i+j)==0)break;                     /**如果已經(jīng)知道6*t-1,6*t+1都不是素?cái)?shù)了那就結(jié)束試除循環(huán)***/
        }
        if(j){modTable[z++]=m+1;if(z> lines)return;}
        if(i){modTable[z++]=m-1;if(z> lines)return;}
    }
}

template<typename valueType>
HashTable<valueType>::~HashTable()
{
    delete []mem;    //釋放空間
    delete []ht;
    delete []modTable;

    clear_Overflow();
    delete []Overflow_list;
    /*
    for(int i=0;i<lines;i++)
        delete []ht[i];
    delete []ht;
    delete []modTable;
    */
}

template<typename valueType>
int HashTable<valueType>::find(unsigned long _key)
{
    int i;
    for(i=0;i<lines;i++){
        m=i;n=(_key+maxLine)%modTable[m];
        if(ht[m][n].key==_key&&ht[m][n].state==Active)
            return 0;
    }
    if(listLen==0)return -1;
    m=lines;n=(_key+maxLine)%modTable[m];
    list_node *pre=Overflow_list[n];
    while(pre!=NULL){
        if(pre->key==_key)return 0;
        pre=pre->next;
    }
    return -1;
}

template<typename valueType>
int HashTable<valueType>::insert(unsigned long _key,const valueType &_value)
{
    if(find(_key)==0)return 1;    //已存在

    int i,len=0;
    for(i=0;i<lines;i++){
        m=i;n=(_key+maxLine)%modTable[m];
        if(ht[m][n].state!=Active){    //陣列中找到空位,插入數(shù)據(jù)
            ht[m][n].key=_key;
            ht[m][n].value=_value;
            ht[m][n].state=Active;
            currentSize++;
            return 0;
        }
    }
    if(listLen==0)return -1;

    //陣列已滿(mǎn),插入溢出鏈表
    m=lines;n=(_key+maxLine)%modTable[m];
    list_node *pre=Overflow_list[n];

    list_node *now=new list_node;
    now->key=_key;
    now->value=_value;

    if(pre==NULL){
        Overflow_list[n]=now;
    }
    else{
        len=1;
        while(pre->next!=NULL){pre=pre->next;len++;}
        if(listLen>0&&len>=listLen)return -1;    // full  ;if listLen<0  no limit ,continue the left operation
        pre->next=now;
    }
    currentSize++;
    maxList++;

    return 0;
}

template<typename valueType>
int HashTable<valueType>::remove(unsigned long _key)
{
    if(find(_key)!=0)return -1;
    if(m<lines){            //節(jié)點(diǎn)在陣列中
        ht[m][n].state=Deleted;        //節(jié)點(diǎn)狀態(tài)置為Deleted
        currentSize--;
    }
    else{            //節(jié)點(diǎn)在溢出鏈中
        list_node *pre=Overflow_list[n],*now;
        if(pre->key==_key){
            Overflow_list[n]=pre->next;
            delete pre;
        }
        else{
            while(pre->next->key!=_key&&pre->next!=NULL)
                pre=pre->next;
            now=pre->next;
            pre->next=now->next;
            delete now;
        }
        currentSize--;maxList--;
    }
    return 0;
}

template<typename valueType>
double HashTable<valueType>::getFullRate()const
{
    return double(currentSize)/(maxSize+maxList);    //空間使用率
}

template<typename valueType>
void HashTable<valueType>::clear()
{
    int i,j;
    for(i=0;i<lines;i++)        //把所有節(jié)點(diǎn)狀態(tài)置為Empty
        for(j=0;j<modTable[i];j++)
            ht[i][j].state=Empty;
    if(listLen!=0)clear_Overflow();
    maxList=0;
    currentSize=0;
}

template<typename valueType>
void HashTable<valueType>::clear_Overflow()
{
    list_node *pre=NULL,*now=NULL;
    for(int i=0;i<modTable[lines];i++)
    {
        pre=Overflow_list[i];
        if(pre==NULL)continue;
        while(pre->next!=NULL){
            now=pre->next;
            pre->next=now->next;
            delete now;
        }
        delete pre;
        Overflow_list[i]=NULL;
    }
}

#endif

//-----------test.cpp

#include"HashTable.h"
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<unistd.h>
#include<cstdio>
using namespace std;

int main(int argc,char **argv)
{
    HashTable<int> HT(10000,6);
    HT.setList(5);

    int i=0,j;
    double sum=0.0,sum2=0.0;
    volatile unsigned long temp;
    volatile unsigned long seed;
    while(i++<1000){
            seed=time(NULL);
            srand(i+seed);
            while(true)
            {
                    temp=rand();
                    if(HT.insert(temp,0)<0)break;
            }
            cout<<HT.getFullRate()<<"\t"<<HT.getOverflowRate()<<endl;
            sum+=HT.getFullRate();
            sum2+=HT.getOverflowRate();
            HT.clear();
    }
    cout<<"\n\n\n"<<sum/1000<<"\t  "<<sum2/1000<<endl;

    return 0;
}

posted on 2007-09-08 21:07 芥之舟閱讀(5322) 評(píng)論(1) 編輯收藏引用所屬分類(lèi): 數(shù)據(jù)結(jié)構(gòu)和算法

評(píng)論

# re: 哈希表的一個(gè)實(shí)現(xiàn) 2014-10-13 10:50 abc

p*6<=sqrt(m+1)+2 這個(gè)是怎么回事回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 使用共享內(nèi)存的多級(jí)哈希表的一種實(shí)現(xiàn) 哈希表的一個(gè)實(shí)現(xiàn) 素?cái)?shù)算法

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理