[算法]hash table 与 hash map 实现

通过一个哈希函数建立值与存储位置的一个对应关系，在寻找该值时，可以直接通过该函数计算得出其存储位置，而不需要像其它数据结构一样通过比较来查找。理想情况下查找的时间复杂度为o(1)。
哈希函数的构造方法有很多种，一个好的哈希函数应该让数据地址平均分布，并且避免冲突。此处通过除留余数法来构造哈希函数：
key = value % p （p不大于哈希表长度）

哈希表的长度应远大于数据存储量。当存储量接近哈希表长度时，哈希表的搜索效率将非常低。原因是冲突太多。这里使用解决冲突的办法是链地址法。就是当HASH函数计算的KEY已经存储值时，在该KEY位置上再开辟一个位置存储新值。搜索时，要检查存放在新开辟空间的数据要检查VALUE==要搜索的VALUE才能返回。

 

#include <map>
#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <list>
using namespace std;

const int table_length=11;

class element
{
public:
int key;
int value;
element *pNext;
element()
{
this->pNext=NULL;
}
};

class HashTable
{
public:
element *hash_table;
HashTable()
{
hash_table=new element[table_length];
for(int i=0;i<table_length;++i)
{
hash_table[i].key=-1;//代表空
}
}
~HashTable()
{
for(int i=0;i<table_length;++i)
{
element *pNext=hash_table[i].pNext;
while(NULL!=pNext)
{
element *tmp=pNext;
pNext=pNext->pNext;
delete tmp;
}
}
delete []hash_table;
}
void insert(int value);
void find(int value);
};

inline inthash(int value)
{
return value%table_length;
}

void HashTable::insert(int value)
{
int key=hash(value);
element newEle;
newEle.key=key;
newEle.value=value;

if(hash_table[key].key==-1)
{
hash_table[key]=newEle;
}
else
{
if(hash_table[key].value==value)
{
cout<<"value: "<<value<<" already exists"<<endl;
return;
}
element *pNext=hash_table[key].pNext;
if(pNext==NULL)
{
hash_table[key].pNext=new element;
hash_table[key].pNext->key=key;
hash_table[key].pNext->value=value;
return;
}
element *lastP;
while(pNext!=NULL)
{
lastP=pNext;
if(pNext->value==value)
{
cout<<"value: "<<value<<" already exists"<<endl;
return;
}
pNext=pNext->pNext;
}
lastP->pNext=new element;
lastP->pNext->key=key;
lastP->pNext->value=value;
}
}

void HashTable::find(int value)
{
int key=hash(value);
if(hash_table[key].value==value)
{
cout<<key<<" : "<<value<<endl;
return;
}
if(hash_table[key].key==-1)
{
cout<<"value: "<<value<<" not exist"<<endl;
return;
}
element *pNext=hash_table[key].pNext;
while(pNext!=NULL)
{
if(pNext->value==value)
{
cout<<pNext->key<<" : "<<pNext->value<<endl;
return;
}
else
{
pNext=pNext->pNext;
}
}
cout<<"value: "<<value<<" not exist"<<endl;
}



void main()
{
HashTable myTable;

myTable.insert(30);
myTable.insert(23);
myTable.insert(34);
myTable.insert(45);
myTable.insert(45);
myTable.insert(30);


myTable.find(12);
myTable.find(30);
myTable.find(23);
myTable.find(0);
myTable.find(34);
myTable.find(45);

}

 

只需在element中新增一个成员，就可以将上程序改为hash map，当插入数据时，如此KEY已经存在，就更新VALUE。

 

#include <map>
#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <list>
using namespace std;

const int table_length=11;

class element
{
public:
int key;
int value;
string strValue;
element *pNext;
element()
{
this->pNext=NULL;
}
};

class HashTable
{
public:
element *hash_table;
HashTable()
{
hash_table=new element[table_length];
for(int i=0;i<table_length;++i)
{
hash_table[i].key=-1;//代表空
}
}
~HashTable()
{
for(int i=0;i<table_length;++i)
{
element *pNext=hash_table[i].pNext;
while(NULL!=pNext)
{
element *tmp=pNext;
pNext=pNext->pNext;
delete tmp;
}
}
delete []hash_table;
}
void insert(int value,string strValue);
void find(int value);
};

inline inthash(int value)
{
return value%table_length;
}

void HashTable::insert(int value,string strValue)
{
int key=hash(value);
element newEle;
newEle.key=key;
newEle.value=value;
newEle.strValue=strValue;

if(hash_table[key].key==-1)
{
hash_table[key]=newEle;
}
else
{
if(hash_table[key].value==value)
{
//cout<<"value: "<<value<<" already exists"<<endl;
hash_table[key].strValue=strValue;
return;
}
element *pNext=hash_table[key].pNext;
if(pNext==NULL)
{
hash_table[key].pNext=new element;
hash_table[key].pNext->key=key;
hash_table[key].pNext->value=value;
hash_table[key].pNext->strValue=strValue;
return;
}
element *lastP;
while(pNext!=NULL)
{
lastP=pNext;
if(pNext->value==value)
{
//cout<<"value: "<<value<<" already exists"<<endl;
pNext->strValue=strValue;
return;
}
pNext=pNext->pNext;
}
lastP->pNext=new element;
lastP->pNext->key=key;
lastP->pNext->value=value;
lastP->pNext->strValue=strValue;
}
}

void HashTable::find(int value)
{
int key=hash(value);
if(hash_table[key].value==value)
{
cout<<value<<" : "<<hash_table[key].strValue<<endl;
return;
}
if(hash_table[key].key==-1)
{
cout<<"value: "<<value<<" not exist"<<endl;
return;
}
element *pNext=hash_table[key].pNext;
while(pNext!=NULL)
{
if(pNext->value==value)
{
cout<<pNext->value<<" : "<<pNext->strValue<<endl;
return;
}
else
{
pNext=pNext->pNext;
}
}
cout<<"value: "<<value<<" not exist"<<endl;
}



void main()
{
HashTable myTable;

myTable.insert(30,"yjh");
myTable.insert(23,"abc");
myTable.insert(34,"tom");
myTable.insert(45,"ele");
myTable.insert(45,"cmd");
myTable.insert(30,"bbb");


myTable.find(12);
myTable.find(30);
myTable.find(23);
myTable.find(0);
myTable.find(34);
myTable.find(45);

}

 

如果想要用字符串作为关键字，则需要把字符串的一部分转换成INT来计算HASH值。

 

例如：

inline inthash(string value)
{
int tmp;
if(value.size()==1)
{
tmp=value[0];
}
if(value.size()==2)
{
tmp=value[0]+value[1];
}
if(value.size()>=3)
{
tmp=value[0]+value[1]+value[2];
}

return tmp%table_length;
}

完整实现如下：

 

#include <map>
#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <list>
using namespace std;

const int table_length=5000;

class element
{
public:
int key;
string value;
string strValue;
element *pNext;
element()
{
this->pNext=NULL;
}
};

class HashTable
{
public:
element *hash_table;
HashTable()
{
hash_table=new element[table_length];
for(int i=0;i<table_length;++i)
{
hash_table[i].key=-1;//代表空
}
}
~HashTable()
{
for(int i=0;i<table_length;++i)
{
element *pNext=hash_table[i].pNext;
while(NULL!=pNext)
{
element *tmp=pNext;
pNext=pNext->pNext;
delete tmp;
}
}
delete []hash_table;
}
void insert(string value,string strValue);
void find(string value);
};

inline inthash(string value)
{
int tmp;
if(value.size()==1)
{
tmp=value[0];
}
if(value.size()==2)
{
tmp=value[0]+value[1];
}
if(value.size()>=3)
{
tmp=value[0]+value[1]+value[2];
}

return tmp%table_length;
}

void HashTable::insert(string value,string strValue)
{
int key=hash(value);
element newEle;
newEle.key=key;
newEle.value=value;
newEle.strValue=strValue;

if(hash_table[key].key==-1)
{
hash_table[key]=newEle;
}
else
{
if(hash_table[key].value==value)
{
//cout<<"value: "<<value<<" already exists"<<endl;
hash_table[key].strValue=strValue;
return;
}
element *pNext=hash_table[key].pNext;
if(pNext==NULL)
{
hash_table[key].pNext=new element;
hash_table[key].pNext->key=key;
hash_table[key].pNext->value=value;
hash_table[key].pNext->strValue=strValue;
return;
}
element *lastP;
while(pNext!=NULL)
{
lastP=pNext;
if(pNext->value==value)
{
//cout<<"value: "<<value<<" already exists"<<endl;
pNext->strValue=strValue;
return;
}
pNext=pNext->pNext;
}
lastP->pNext=new element;
lastP->pNext->key=key;
lastP->pNext->value=value;
lastP->pNext->strValue=strValue;
}
}

void HashTable::find(string value)
{
int key=hash(value);
if(hash_table[key].value==value)
{
cout<<value<<" : "<<hash_table[key].strValue<<endl;
return;
}
if(hash_table[key].key==-1)
{
cout<<"value: "<<value<<" not exist"<<endl;
return;
}
element *pNext=hash_table[key].pNext;
while(pNext!=NULL)
{
if(pNext->value==value)
{
cout<<pNext->value<<" : "<<pNext->strValue<<endl;
return;
}
else
{
pNext=pNext->pNext;
}
}
cout<<"value: "<<value<<" not exist"<<endl;
}



void main()
{
HashTable myTable;

myTable.insert("yjh","a");
myTable.insert("nhq","b");
myTable.insert("abc","c");
myTable.insert("you","ele");
myTable.insert("yjh","cmd");
myTable.insert("yjh","bbb");


myTable.find("yjh");
myTable.find("nhq");
myTable.find("abc");
myTable.find("you");


}