实现Hash Table的方法

实现Hash Table的方法

 

hash-table是一种非常有用的数据结构,hash所带来的查找和插入效率(特别是前者),都是让人十分满意的。因此很多的符号表的组织都采用这种方式来实现,k_eckel在实现Visual CMCS的符号表的时候采用的也是这种方式。hash-table需要考虑的问题主要是有两个:1hash函数的选择,2)冲突的解决方案对于后者有很多种解决策略,但是最为常见的是链地址法,也就是hash值相同的元素采用链表的方式组织起来

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;

}