janqii

散列表是普通数组的推广。

设计散列表主要是对哈希函数和处理冲突碰撞的选择和设计，好的哈希函数h可以使关键字比较均匀的散列在哈希表中，冲突较少。所谓“好”的哈希函数的主导思想，是使h尽可能地随机，减少碰撞，但是不可能完全避免碰撞，因为关键字域的势 |U|>m，m为散列表的槽数，总会有两个不同的关键字映射到同一个槽中，产生碰撞。

1、哈希函数

一个好的哈希函数应（近似地）满足简单一致散列的假设：每个关键字都等可能的散列到m个槽位的任何一个中去，并与其他的关键字已被散列到哪个槽位中无关。

不幸的是，一般情况下不太可能检查这一条件是否成立，因为人们很少能知道关键字所符合的概率分布，而各关键字可能并不是完全相互独立的。

算法导论中列举了四种哈希函数：直接定址法、除法散列法、乘法散列法和全域散列法。

其中除法散列法和乘法散列法利用了启发式的方法，第三个利用了随机化的技术。

a、除法散列法（模除法）

h(k)=k mod m

m的取值常常是与2的整数幂不太接近的质数（m是指散列表的槽数）。

b、乘法散列法

h(k)=|m*(k*A mod 1)| （取底）

用关键字k乘以常数A（0<A<1），并取出kA的小数部分。然后用m乘以这个值，对结果取底。

对 m 的选择没有特别的要求，一般选择为 2 的整数次幂

Knuth认为 A=（sqrt（5）-1）=0.6180339887......，取这个值比较理想

c、全域散列

h(k)=((a*k+b) mod p) mod m   （哈希函数族）

选择一个足够大的质数p，使得每一个可能的关键字k都落到0到p-1之间（包括0和p-1）。

Zp表示集合｛0，1，……，p-1｝，Zp*表示集合｛1，2，……，p-1｝。

容易知道p>m（p>=|U|>m）

a属于Zp*，B属于Zp

从函数族中随机的选取一个作为哈希函数

d、在严蔚敏的数据结构中还介绍了其他的构造哈希函数的方法（比如平方取中法，折叠法等）

2、处理碰撞的方法

a、哈希链接法

把冲突的关键字存储在冲突槽的链表中

在简单一致散列的假设下，一次不成功查找的期望时间为O（1+α），平均情况下一次成功的查找也需要同样的时间

b、开放寻址法

线性探测    h(k,i)=(h'(k)+i) mod m,i=0,1,……，m-1

二次探测   h(k,i)=(h'(k)+c1*i+c2*i*i) mod m     严蔚敏的数据结构中 c1=0，c2=-1

双重哈希（再哈希法） h(k,i)=(h1(k)+i*h2(k)) mod m

每一个关键字的探查序列

<h(k,0)，h（k,1）,……，h(k,m-1)>    

直到探寻到合适的位置为止

c、完全散列法

基本思想比较简单，采用两级的散列方案，每一级都采用全域散列。

有点类似哈希链接法，只不过，在冲突槽的链表上再采用一次全域哈希。

d、严蔚敏的数据结构中还介绍了 建立一个公共溢出区 的方法

------------------------------------一个小例子（哈希链接法 处理冲突）-------------------------------------------------

/*
* 算法导论 第十一章 散列表
*
* 哈希函数：模除散列法
* 冲突避免：哈希链接法
* */

/* 输出：14 1

               1   0

*/

#include<stdio.h>
#include<stdlib.h>

struct hash_node{
struct hash_node *next;
int data;
};

struct hash_table{
struct hash_node *base;
unsigned int count;
unsigned int size;
};

unsigned int hash1(int key, int m)
{
/*int rt=-1;*/
return key%m;
}

unsigned int hash2(int key, int m)
{
return 1+(key%(m-1));
}

unsigned int hash(int key, int m, int i)
{
return (hash1(key,m)+i*hash2(key,m))%m;
}

void chain_insert(struct hash_table *tbl, int key)
{
unsigned int pos=-1;
struct hash_node *new_node=NULL;

new_node=(struct hash_node *)malloc(sizeof(struct hash_node));
new_node->data=key;
new_node->next=NULL;

pos=hash(key,tbl->size,0);

if(tbl[pos].count==0)
{
   tbl[pos].base=new_node;
   tbl[pos].count += 1;
}
else
{
   new_node->next=tbl[pos].base;
   tbl[pos].base=new_node;
   tbl[pos].count += 1;
}
}

void chain_search(struct hash_table *tbl, int key, unsigned int *row,unsigned int *col)
{
int i=0;
int idx=-1;
struct hash_table tb;

idx=hash(key,tbl->size,0);

if(tbl[idx].count > 0)
{
   tb=tbl[idx];
   while(tb.base!=NULL && tb.base->data!=key)
   {
    tb.base=tb.base->next;
    i += 1;
   }
  
   *row=idx;
   *col=i;
  
   if(tb.base==NULL)
   {
    *row=-1;
    *col=-1;
   }
}
else
{
   *row=-1;
   *col=-1;
}
}

#define m 13

int main()
{
int i=0;
int row, col;
struct hash_table tbl[m];

for(i=0;i<m;i++)
{
   tbl[i].base=NULL;
   tbl[i].count=0;
   tbl[i].size=m;
}
chain_insert(tbl,1);
chain_insert(tbl,14);
chain_search(tbl,14,&row,&col);

printf("%d ",tbl[1].base->data);
printf("%d ",tbl[1].base->next->data);
printf("\n%d %d\n",row,col);

return 0;
}