哈希表查找 — 开放定址法

散列表(也叫哈希表)，是根据关键字值而直接进行访问的数据结构。

通过把关键字值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

散列函数的构造方法：
（1）直接定址法
（2）除留余数法
（3）平方取中法
（4）折叠法
（5）数值分析法

本文采用除留余数法构造散列函数。
H(K) = (H(k) + i) % m; 其中i = 1, 2, …， m为哈希表大小。

构造散列函数的目的是减少冲突，但要完全避免冲突是不可能的，只能尽可能减少冲突。
处理冲突的方法：
（1）开放定址法
（2）二次探测法
（3）链地址法（拉链法）

根据原始数组建立一个哈希表，哈希表也为一个数组，且要求哈希表有固定大小。
本文采用开放定址法处理冲突。
当由H(k)算出的位置不为空时，则通过已经构造的散列函数来寻找新的空位置。
从H(k)开始往后逐个搜索空位置，如果后面没有空位置，则从头开始搜索，直到搜索到空位置，或者回到H(k)停止搜索。(回到H(k)则说明搜索失败)

举例：取H(K) = (H(k) + i) %11，将关键字序列20， 30， 70， 15， 8， 12， 18， 63， 19存储到哈希表中，如下图：

平均搜索长度可以用来衡量一个搜索算法，在上图中有:
平均查找长度 = （1 x 5 + 2 x 1 + 3 x 1+ 4 x 1+ 5 x 1）/ 9 = 19/9

具体c++实现代码如下，在vs2010测试通过：

#include <iostream>
using namespace std;

void ArrayHashTableSearch(int arr[], int searchValue)
{
    int const tableSize = 10;
    typedef int hashTable[tableSize];//哈希表有固定大小

    hashTable table;
    memset(table, 0, sizeof(table));//初始化

    //除留余数法构造哈希函数
    int nIndex;//元素下标
    int compareTimes;//比较次数，避免死循环

    //插入元素
    for(int i = 0; i < tableSize; i++)
    {
        nIndex = arr[i] % tableSize;
        if(0 == table[nIndex])//哈希表中nIndex处还没有存储元素
            table[nIndex] = arr[i];
        else//要重新寻找地址
        {
            compareTimes = 1;
            while(compareTimes <= tableSize)
            {
                nIndex = (arr[i] + compareTimes)% tableSize;
                if(0 == table[nIndex]) 
                {
                    table[nIndex] = arr[i];
                    break;//找到地址后退出
                }
                else
                    compareTimes++;
            }
            cout<<"Fail to insert the element: "<<arr[i]<<endl;//哈希表已满，则插入失败
        }
    }

    //查找
    nIndex = searchValue % tableSize;
    if(searchValue == table[nIndex])
        cout<<"Find the searchValue: "<<searchValue<<endl;
    else
    {
        compareTimes = 1;
        while(compareTimes <= tableSize)
        {
            nIndex = (searchValue + compareTimes) % tableSize;//线性探测法定地址
            if(searchValue == table[nIndex])
            {
                cout<<"Find the searchValue: "<<searchValue<<endl;
                break;
            }
            else   
                compareTimes++;
        }
        cout<<"Fail to find the search value!"<<endl;//查找失败
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    int arr[] = {1, 5, 2, 3, 6, 9, 8, 7, 0, 4, 120};

    //哈希表
    ArrayHashTableSearch(arr, 5);
    ArrayHashTableSearch(arr, 10);

    return 0;
}