大话数据结构—散列表查找（哈希表）

一、基本概念

散列技术：在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。

f：散列函数/哈希函数；
采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。
关键字对应的记录存储位置称为散列地址。

散列技术既是一种存储方法，也是一种查找方法。
散列技术适合求解问题是查找与给定值相等的记录。查找速度快。
散列技术不适合范围查找，不适合查找同样关键字的记录，不适合获取记录的排序，最值。

冲突：关键字key1不等于key2，但f(key1)=f(key2)。
把key1和key2称为散列函数的同义词。

二、散列函数构造

两个原则：

1. 计算简单
2. 散列地址分布均匀

1. 直接定址发

f(key)=a x key+b(a、b为常数)

简单，均匀，不会冲突，但是事先知道关键字的分布情况，适合查找表小且连续。

2. 数字分析法

关键字位数多，比如手机号，可能前几位一样，只是后几位不同，抽取关键字的一部分计算散列存储位置。事先知道关键字分布且若干位分布均匀。

3. 平方取中法

不知道关键字分布，且位数不是很大。1234，平方1522756，抽取中间227作为散列地址。

4. 折叠法

不知道关键字分布，位数多。
从左到右分割成位数相等的几部分，这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

5. 除留余数法

散列表长m

f(key)=key mod p(p<=m)

p选取不好，产生冲突。
通常p为<=m（最好接近m）的最小质数或者不包含小于20质因子的合数。

6. 随机数法

关键字长度不等。

f(key)=random(key),random随机函数

当关键字为字符串，转化为某种数字来对待，比如ASCLL码或者Unicode码等。

三、散列冲突处理

1. 开放定址法

又叫线性探测法：一旦冲突，寻找下一个空的散列地址。散列表大。

优化：二次探测法

双向寻找，防止后面没空，但前面有空。
增加平方，不让关键字聚集在某一块区域。

还有对位移量d随机函数计算，称之为随机探测法。

2. 再散列函数法

RHi不同散列函数，随机使用除留、折叠、平方，每次冲突换种散列函数。

3. 链地址法

将所有关键字为同义词的记录存储在一个单链表（同义词字表）中。
散列表中只存储所有同义词字表的头指针。
{12,67,56,16,25,37,22,29,15,47,48,34} mod 12

缺点：单链表查找遍历耗时。

4. 公共溢出区法

冲突关键字存储到溢出表中

散列计算后，先基本表比较。不等，到溢出表进行顺序查找。

四、散列表查找

1. 附加源码

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */

#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 /* 定义散列表长为数组的长度 */
#define NULLKEY -32768 

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ 

typedef struct
{
   int *elem; /* 数据元素存储基址，动态分配数组 */
   int count; /*  当前数据元素个数 */
}HashTable;

int m=0; /* 散列表表长，全局变量 */

/* 初始化散列表 */
Status InitHashTable(HashTable *H)
{
    int i;
    m=HASHSIZE;
    H->count=m;
    H->elem=(int *)malloc(m*sizeof(int));
    for(i=0;i<m;i++)
        H->elem[i]=NULLKEY; 
    return OK;
}

/* 散列函数 */
int Hash(int key)
{
    return key % m; /* 除留余数法 */
}

/* 插入关键字进散列表 */
void InsertHash(HashTable *H,int key)
{
    int addr = Hash(key); /* 求散列地址 */
    while (H->elem[addr] != NULLKEY) /* 如果不为空，则冲突 */
    {
        addr = (addr+1) % m; /* 开放定址法的线性探测 */
    }
    H->elem[addr] = key; /* 直到有空位后插入关键字 */
}

/* 散列表查找关键字 */
Status SearchHash(HashTable H,int key,int *addr)
{
    *addr = Hash(key);  /* 求散列地址 */
    while(H.elem[*addr] != key) /* 如果不为空，则冲突 */
    {
        *addr = (*addr+1) % m; /* 开放定址法的线性探测 */
        if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) /* 如果循环回到原点 */
            return UNSUCCESS;   /* 则说明关键字不存在 */
    }
    return SUCCESS;
}

int main()
{
    int arr[HASHSIZE]={12,67,56,16,25,37,22,29,15,47,48,34};
    int i,p,key,result;
    HashTable H;

    key=39;

    InitHashTable(&H);
    for(i=0;i<m;i++)
         InsertHash(&H,arr[i]);

    result=SearchHash(H,key,&p);
    if (result)
        printf("查找 %d 的地址为：%d \n",key,p);
    else
        printf("查找 %d 失败。\n",key);

    for(i=0;i<m;i++)
    {
        key=arr[i];
        SearchHash(H,key,&p);
        printf("查找 %d 的地址为：%d \n",key,p);
    }

    return 0;
}

2. 查找性能

如果无冲突，O(1)。
查找平均长度取决于：

• 散列函数是否均匀
• 处理冲突的方法
• 散列表的装填因子
  装填因子=填入表中的记录个数/散列表长度。（表示散列表的装满的程度）
  当填入表中的记录越多，装填因子越大，产生冲突可能性越大。

通常将散列表的空间设置的比查找集合大，牺牲空间换时间。