今天寫了一個哈希表的實現，采用了陣列加開鏈表的形式
看了一下別人的寫法，只用陣列，行數=100的時候空間利用率竟然達到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}; //節點狀態，活躍/空/已刪除
public:
int find(unsigned long _key); //查找_key是否在表中，若在，返回0；否則返回-1；找到時，m,n為節點的位置
int insert(unsigned long _key,const valueType &_value); //插入節點，若該節點已在表中，返回1；若插入成功，返回0，表滿，返回-1
int remove(unsigned long _key); //刪除節點 若節點不存在，返回-1，成功時返回0
public:
double getFullRate()const; //返回Hash表空間利用率
bool isFull()const{return currentSize==maxSize+maxList;} //表是否為滿
void clear(); //清除表內容
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); //構造函數line default 5,a better range
~HashTable();
private:
struct HashNode //哈希節點
{
unsigned long key; //name
valueType value; //value
KindOfNode state; //節點狀態
HashNode():state(Empty){}
~HashNode(){}
};
struct list_node{ //鏈表節點 存儲溢出數據
unsigned long key;
valueType value;
list_node *next;
list_node():next(NULL){}
};
unsigned long currentSize; //當前數據量
unsigned long maxSize; //最大數據量
unsigned long maxLine; //每行最大值
unsigned short lines; //行數
HashNode **ht; //哈希陣列
unsigned long *modTable; //每行的模數
unsigned long m,n; //查找時存儲節點位置，否則做為臨時變量使用
HashNode *mem; //哈希表的實際存儲空間
list_node * *Overflow_list; //溢出鏈
unsigned long maxList; //list current size
int listLen; //list length default -1---no limit
private:
void getMode(); //生成模數
void clear_Overflow(); //清除溢出鏈數據
};
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]; //實際空間
assert(mem!=NULL);
int i;
for(i=0;i<lines;i++) //分配空間到哈希陣列
ht[i]=mem+maxLine*i;
/*
for(i=0;i<lines;i++){ //申請存儲空間
ht[i]=new HashNode[maxLine];
if(ht[i]==NULL){ //申請失敗，釋放已申請空間，退出
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 素數集中原理
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的值 是是否進行驗證的標志也是對應的6t-1和6t+1的素性標志**/
if(((k-4)==0)||((k-9)==0)||((m+1)%3==0))j=0;/*此處是簡單驗證6*t-1,6*t+1 是不是素數，借以提高素數純度**/
if(((k-6)==0)||((m-1)%3==0))i=0; /***先通過初步判斷去除末尾是5，及被3整除的數***/
for(p=1;p*6<=sqrt(m+1)+2;p++ )
{
n=p*6; /**將6*p-1和6*p+1看作偽素數來試除*****/
k=p%10;
a=1;b=1; /**同樣此處a,b的值也是用來判斷除數是否為素數提高除數的素數純度**/
if(((k-4)==0)||((k-9)==0))a=0;
if(((k-6)==0))b=0;
if(i){ /*如果i非零就對m-1即所謂6*t-1進行驗證，當然還要看除數n+1,n-1,素性純度*/
if(a){if((m-1)%(n+1)==0)i=0;} /***一旦被整除就說明不是素數故素性為零即將i 賦值為零***/
if(b){if((m-1)%(n-1)==0)i=0;}
}
if(j){ /**如果j非零就對m+1即所謂6*t+1進行驗證，當然還要看除數n+1,n-1,素性純度*/
if(a){if((m+1)%(n+1)==0)j=0;} /***一旦被整除就說明不是素數故素性為零即將j 賦值為零***/
if(b){if((m+1)%(n-1)==0)j=0;}
}
if((i+j)==0)break; /**如果已經知道6*t-1,6*t+1都不是素數了那就結束試除循環***/
}
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){ //陣列中找到空位,插入數據
ht[m][n].key=_key;
ht[m][n].value=_value;
ht[m][n].state=Active;
currentSize++;
return 0;
}
}
if(listLen==0)return -1;
//陣列已滿,插入溢出鏈表
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){ //節點在陣列中
ht[m][n].state=Deleted; //節點狀態置為Deleted
currentSize--;
}
else{ //節點在溢出鏈中
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++) //把所有節點狀態置為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;
}