哈希表

1、哈希函数

关键字(key)————>记录在表中的位置，关键字到记录在表中的位置需要一个函数来确定，即f(key)哈希函数

2、哈希表基本思想

哈希表中的每个元素的关键字key为自变量，通过哈希函数，计算出函数值，这个值作为数组下标，将元素存入数组对应位置

3、哈希表构建

• 构造哈希函数
• 处理异常

4、构造哈希函数

• 直接定址法
• 数字分析法
• 平方取中法
• 折叠法
• 除留余数法

这里选比较常用的作为分析——————除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址即：H(key)=key MOD p<=m,p是不大于m的素数(选择p很重要，选择不当的话，会产生大量冲突)

5、处理哈希冲突

1、开放定址法

Hi=(H(key)+di) MOD m(m是表长）（i=1,2,3,….m) (H(key)=H0,第一次算出的值，一直不会变)

• 线性探测再散列 （di=1,2,3,…m-1）(发生冲突往后补位即可)
• 二次探测再散列 （di=1^2,-1^2,2^2,-2^2…+-k^2 ）(k<=m/2)(先比后一个位，若后一个位被占，就比较前一位，若前一位被占，就比后面第二位，依次)
• 再哈希法

再哈希法求解步骤

H0=key%m

Hi=(H(key)+di)%m (注：H(key)=H0)

di=i*f(key)

f(key)=(3*key)MOD%10+1(此函数需要自己得出)

例：采用线性探测再散列处理

例：再哈希法

2、链地址法

数组与链表共同组成的哈希表结构(将所有哈希地址相同的都链接在同一链表中)

6、代码（采用线性探测再散列）

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define HashLen 13//哈希表长度
#define Tablelen 8//数据元素个数
int hash[HashLen]={0};
int data[Tablelen]={1,14,27,13,4,5,6,7};
void InsertHash(int hash[],int m,int key)///////采用线性探测再散列
{
    int i;
    i=key%HashLen;
    while(hash[i])
    {
        i=(++i)%m;
    }
    hash[i]=key;
}
void CreatHash(int hash[],int data[],int m,int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        InsertHash(hash,m,data[i]);
    }
}
void SearchHash(int hash[],int m,int key)
{
    int i;
    i=key%HashLen;
    while(hash[i]&&hash[i]!=key)
    {
        i=(++i)%m;

    }
    if(hash[i]==0)
    {
        printf("查找失败");
    }
    else if(hash[i]==key)
    {
        printf("查找成功");
    }
}
int main()
{
    int key;
    CreatHash(hash,data,HashLen,Tablelen);
    printf("Hash结构:");
    for(int i=0;i<HashLen;i++)
    {
        printf("%d ",hash[i]);
    }
    printf("\n");
    printf("输入查找关键字:");
    scanf("%d",&key);
    SearchHash(hash,HashLen,key);
    return 0;
}