实现Hash Table的方法
实现Hash Table的方法
hash-table 在SGI-STL中是提供了的一个模板类，但是VC 6.0中支持的STL却并不是使用SGI-STL，因此也没有不能直接使用hash-table了。
hash最重要的一点就是牺牲空间换取时间，通常要采用一个很大的数组。这点有些像是内联函数（inline），也是空间换时间实现。
这里给出一个简单的hash-table的实现，本来准备用模板写，但是懒得去整理，达到自己的目的就算了。
实现源码为：
|
//hash_table.h
#ifndef _HASH_TABLE_H_ #define _HASH_TABLE_H_
#include <string> using namespace std;
struct node { node():_next(NULL) { } //string _key; string _value; node* _next; };
typedef node* hash_node; const int MULT = 31; const int TABLE = 10000;
class hash_table { public: hash_table(hash_node* table); ~hash_table(); public: void Insert(const string& word); //hash_node Search(const string word); int Search(const string& word);
private: unsigned int hash(const string& word); private: hash_node* _table; };
#endif //~_HASH_TABLE_H_ |
|
//hash_table.cpp
#include "hash_table.h"
#include <iostream> using namespace std;
hash_table::hash_table(hash_node* table) { _table = table; }
hash_table::~hash_table() { delete[] _table; }
unsigned int hash_table::hash(const string& word) { const char* p = word.c_str(); unsigned int h = 0;
for (; *p; p++) { h = (h*MULT) % TABLE + (*p) % TABLE; }
return h; }
void hash_table::Insert(const string& word) { int h = hash(word);
//new item,insert directly if (_table[h] == NULL) { hash_node n = new node(); n->_value = word; n->_next = NULL;
_table[h] = n;
return ; }
for (hash_node p = _table[h];p != NULL;p = p->_next) { if (p->_value == word) { return ; //已经插入了 } }
//没有插入，但是发成了冲突 hash_node n = new node(); n->_value = word; n->_next = _table[h]; _table[h] = n; }
int hash_table::Search(const string& word) { int h = hash(word);
if (_table[h] == NULL) { return -1; }
for (hash_node p = _table[h];p != NULL;p = p->_next) { if (p->_value == word) { return 1; } }
return -1; } |
测试程序为：
|
//main.cpp
#include "hash_table.h"
#include <iostream> using namespace std;
int main(int argc,char* argv[]) { hash_node bin[TABLE] = {NULL};
hash_table* ht = new hash_table(bin);
ht->Insert("IBM"); ht->Insert("金山"); ht->Insert("microsoft"); ht->Insert("ATC"); ht->Insert("dsgg"); ht->Insert("MSRA INTERN");
cout<<"ATC"<< " : "<<ht->Search("ATC")<<endl; cout<<"华为"<< " : "<<ht->Search("华为")<<endl; cout<<"金山"<< " : "<<ht->Search("金山")<<endl; return 0; } |