哈希表的基本概念与实现

前面我们讲过，当我们查找的时候，最终的目的还是为了使得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。。模仿着写了下没写出来，可忽略。