C 實現(xiàn)哈希表 HashMap沖突鏈式解決

閑來看看 2013-02-25

展開全文

C++實現(xiàn)哈希表 HashMap沖突鏈式解決

簡述：

考慮到有大量數(shù)據(jù)的情況，所以使用Hash表

使用泛型實現(xiàn)

TypeA 是Key的類型，TypeB 是value的類型

1. 主要函數(shù)

1). TypeB Put(HashNode<TypeA,TypeB> 函數(shù)用來加入一個新的MapNode

2). TypeB Delete(const TypeA& key) 用來刪除一個鍵值為key的節(jié)點

3). TypeB GetValue(const TypeA& key) 通過key值來搜尋他的value

2. 主要算法

1) 使用一個函數(shù)類型指向用戶定義的哈希值計算函數(shù)，這里我用了GetKeyValue_1這個平方取中法

2）使用鏈式法解決沖突，首先是一個節(jié)點指針數(shù)組，table[index] ,其中index是哈希函數(shù)計算出來的

如果由于鍵值傳入哈希函數(shù)后計算出同一個index值，那么就以table[index]為頭節(jié)點，橫向建立鏈表避免沖突

3.類實現(xiàn)以及測試代碼

HashMap.cpp

[cpp] view plain copy ?

///***************************HashMap****************************/
//1.用數(shù)組形式建立哈希表
//2.使用鏈式方法解決沖突
//3.平方取中法通過字符串Hash函數(shù)求hash值（還有很多種其他的hash函數(shù)）
#include <iostream>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef unsigned long(*GetKeyValue)(const string& );
//該類用來處理沖突的節(jié)點
template<class TypeA,class TypeB>
struct HashNode{
TypeA key;
TypeB value;
HashNode *next;
HashNode(TypeA key,TypeB value){
HashNode::key = key;
HashNode::value = value;
next = NULL;
}
HashNode& operator=(const HashNode& node){
key = node.key;
value = node.key;
next = node.next;
return *this;
}
};
//該類是HashMap用來存放hash表
template<class TypeA,class TypeB,class FuncType>
class HashMap{
HashNode<TypeA,TypeB> **table;
unsigned long capacity;
FuncType GetKeyValue;
const TypeB TYPEB_NULL;
public:
HashMap(FuncType func,const TypeB& _null);
~HashMap();
TypeB Put(const HashNode<TypeA,TypeB>& hashNode); //插入一個HashNode 返回該節(jié)點的value值
TypeB GetValue(const TypeA& key); // 查找某個hashNode 其key為“key“的元素
TypeB Delete(const TypeA& key); // 查找某個hashNode 其key為“key“的元素
};
template<class TypeA,class TypeB,class FuncType> //在調(diào)用的時候指定函數(shù)
HashMap<TypeA,TypeB,FuncType>::HashMap(FuncType func,const TypeB& _null) : TYPEB_NULL(_null){
capacity = 10000000;
GetKeyValue = func;
table = new HashNode<TypeA,TypeB>*[capacity];
for(unsigned i = 0;i < capacity;i++)
table[i] = NULL;
}
template<class TypeA,class TypeB,class FuncType>
HashMap<TypeA,TypeB,FuncType>::~HashMap(){
for(unsigned i = 0;i < capacity;i++){
HashNode<TypeA,TypeB> *currentNode = table[i];
while(currentNode){
HashNode<TypeA,TypeB> *temp = currentNode;
currentNode = currentNode->next;
delete temp;
}
}
}
//新增節(jié)點操作，用鏈式法解決衝突
template<class TypeA,class TypeB,class FuncType>
TypeB HashMap<TypeA,TypeB,FuncType>::Put(const HashNode<TypeA,TypeB>& hashNode){
HashNode<TypeA,TypeB> *newNode = NULL;
unsigned long index = GetKeyValue(hashNode.key);
if(table[index] == NULL){
table[index] = new HashNode<TypeA,TypeB>(hashNode.key,hashNode.value);
newNode = table[index];
}
else{
newNode = table[index];
while(newNode->next){
newNode = newNode->next;
}
newNode->next = new HashNode<TypeA,TypeB>(hashNode.key,hashNode.value);
newNode = newNode->next;
}
return newNode->value;
}
//由鍵值獲得value
template<class TypeA,class TypeB,class FuncType>
TypeB HashMap<TypeA,TypeB,FuncType>::GetValue(const TypeA& key){
unsigned long index = GetKeyValue(key);
if(table[index] == NULL)
return TYPEB_NULL;
else{
HashNode<TypeA,TypeB> *currentNode = table[index];
while(currentNode){
if(currentNode->key == key)
return currentNode->value;
currentNode = currentNode->next;
}
}
return TYPEB_NULL;
}
//由鍵值查找后，刪除該節(jié)點，返回該刪除的節(jié)點的value
template<class TypeA,class TypeB,class FuncType>
TypeB HashMap<TypeA,TypeB,FuncType>::Delete(const TypeA& key){
TypeB deletedNodeValue = TYPEB_NULL;
unsigned long index = GetKeyValue(key);
if(table[index] == NULL)
return deletedNodeValue;
else{
HashNode<TypeA,TypeB> *currentNode = table[index];
if(currentNode->key == key){
table[index] = currentNode->next;
deletedNodeValue = currentNode->value;
delete currentNode;
return deletedNodeValue;
}
while(currentNode){
if(currentNode->next->key == key){
HashNode<TypeA,TypeB> *temp = currentNode->next;
currentNode->next = currentNode->next->next;
deletedNodeValue = temp->value;
delete temp;
return deletedNodeValue;;
}
currentNode = currentNode->next;
}
}
return deletedNodeValue;
}
/***************************************測試****************************/
//平方取中法
//實現(xiàn)，取字符串中間3個字母，不足3個用0補足
unsigned long GetKeyValue_1(const string& key){
unsigned long keyValue = 0;
int strSize = key.size();
string tempStr(key);
for(int i = strSize;i < 3;i++)
tempStr = "0" + tempStr;
//如果大于3就取中間3位
if(strSize >= 3){
tempStr[0] = key[strSize / 2 - 1];
tempStr[1] = key[strSize / 2];
tempStr[2] = key[strSize / 2 + 1];
}
tempStr = tempStr.substr(0,3);
unsigned long num = 10000 * (unsigned long)(48);
num += 100 * (unsigned long)(tempStr[1]);
num += (unsigned long)(tempStr[2]);
num *= num;
char *numStr = new char[15];
numStr = itoa(num,numStr,10) ;
int strLen = strlen(numStr);
tempStr = "000000";
for(int i = -2;i < 4;i++)
tempStr[2 + i] = numStr[strLen / 2 + i];
keyValue = atoi(tempStr.c_str());
delete []numStr;
return keyValue;
}
int main(){
clock_t start = clock();
//傳入一個求哈希散列值的方法GetKeyValue_1
HashMap<string,string,GetKeyValue> hashMap(GetKeyValue_1,"NULL");
for(int i = 0;i < 100000;i++){
char *ckey = new char[20];
char *cvalue = new char[20];
ckey = itoa(i,ckey,10);
cvalue = itoa(i,cvalue,10);
string key(ckey);
string value(cvalue);
if(i == 67){
key = "67";
value = "hello hash No.67";
}
HashNode<string,string> node1(key,value);
//插入該節(jié)點
hashMap.Put(node1);
// cout << "index: " <<GetKeyValue_1(key) << " nodeValue: "
// << hashMap.Put(node1) << endl;
}
clock_t end = clock();
cout << "Test Result: \n";
//調(diào)用了time.h文件的CLOCKS_PER_SEC，表示每過千分之一秒，clock()函數(shù)返回值加1
cout << "插入100000條數(shù)據(jù)耗時： "
<< double(end - start) / CLOCKS_PER_SEC << " 秒" << endl;
cout << "hashMap.GetValue(\"67\"): " << hashMap.GetValue("67") << endl;
cout << "hashMap.Delete(\"67\"): " << hashMap.Delete("67") << endl;
cout << "hashMap.GetValue(\"67\"): " << hashMap.GetValue("67") << endl;
return 0;
}