前面我们讲过，当我们查找的时候，最终的目的还是为了使得a[i] = key。那么当我们使用二分查找，插值查找或者二叉排序树查找的时候，我们只是利用表内有序，然后在表内利用规律不断地接近key值，那么这无形当中就增加了我们查找的开销。
本文代码已上传至本人Github : https://github.com/swordrada/HashTable，后文也会附上代码。
一、哈希表概述
哈希表，又称散列表。是利用关键字与地址的直接映射关系产生的列表。他的最大优势在于，一个关键字对应一个存储位置（理想情况下），而我们直接就可以由key值找到其在散列表中的位置，大大缩减了我们查找的时间。
思考：
- 这里的地址不是程序设计中的地址，而是我们把关键字存放的位置。比如我们可以将其存放在STL容器中，方便我们查找。
- 由于我们的关键字要尽量与通过函数关系计算出来的地址一一对应，那么要想快速查找到此地址，我们用的存储容器一定要支持随机访问，这样才能达到最快速度。在C++的程序设计中，建议使用支持随机访问的vector顺序容器。
哈希表查找步骤：
- 通过散列函数计算记录的散列地址。
- 按此散列地址存储该记录。
哈希表与树，图，线性表结构的区别：
- 后几种结构数据元素之间都有某种逻辑关系，而散列技术的记录之间不存在逻辑关系，它只与关键字有关。
由此我们可以得出结论：散列技术主要是面向查找的存储结构。
哈希表的构造方法
哈希表构造原则：1.计算简单，复杂算法将会影响查找上的优势 2.散列地址分布均匀，这样我们不需要过多的解决散列表冲突问题，提高效率。
构造具体方法：
- 由于是比较简单的哈希表，因此哈希函数我选择了简单的除留余数法f(key)=key mod p(p<=m)。
- 处理冲突的时候，我采用了开放定址法f(key) = (f(key)+di) mod m(di=1,2,3,4...m-1)。
具体代码：
//HashTable.h
#ifndef HASHTABLE_H_
#define HASHTABLE_H_
#include<vector>
#include<vector>
#include<string.h>
#include<string>
const int HASHSIZE = 20;
using std::vector;
class HashTable
{
private:
vector<int>VecNode;
int m;//哈希表表长
public:
HashTable();
~HashTable();
int Hash(int key);
void Insert(int key);
void Search(int key);
void SearchFor(int key);
//void Delete(int key);
};
#endif
//HashTable.cpp
#include<iostream>
#include"HashTable.h"
using std::cout;
using std::endl;
typedef vector<int>::iterator Iter;
HashTable::HashTable()
{
m = HASHSIZE;
for(int i=0;i<HASHSIZE;i++)
VecNode.push_back(-1);
}
HashTable::~HashTable()
{
for (int i=0;i<HASHSIZE;i++)
VecNode.clear();
}
int HashTable::Hash(int key)
{
return key % 19;
}
void HashTable::Insert(int key)//开放寻址法
{
int addr = Hash(key);//散列表计算出地址
while(VecNode[addr] != -1)//判断如果此时值不为-1，说明冲突
addr = (addr + 1) % HASHSIZE;
VecNode[addr] = key;
}
void HashTable::Search(int key)
{
int addr = Hash(key);
while(VecNode[addr] != key && VecNode[addr] != -1)
addr = (addr + 1) % HASHSIZE;
if(VecNode[addr] == -1)//有可能查的值还没有计入哈希表.结果是-1表示查找失败，表中无此值。
return;
}
void HashTable::SearchFor(int key)
{
int i;
for (i=0;i<HASHSIZE;i++)
{
if(VecNode[i] == key)
break;
}
}
#include<Windows.h>
#include<iostream>
#include"HashTable.h"
using std::cout;
using std::endl;
int main()
{
HashTable h1;
int a,b;
for(int i=0;i<HASHSIZE;i++)
h1.Insert(i);
for(int i=0;i<HASHSIZE;i++)
h1.Search(i);
for(int i=0;i<HASHSIZE;i++)
h1.SearchFor(i);
return 0;
}
注：引入Windows.h头文件本来是想做一个性能测试比较的，无奈没接触过Windows API。。模仿着写了下没写出来，可忽略。
网友评论