散列表（哈希表）查找：
散列技术是在记录的存储位置和他的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)
f：哈希函数、散列函数
这块连续存储空间：散列表、哈希表
步骤：
1.当存储时，通过散列函数计算出记录的散列地址
2.当查找记录时，通过同样的散列计算记录的散列地址，进行访问
#缺点：关键词很多重复的情况、查找范围的情况，都不大实用
散列函数的构造方法：
计算简单+分布均匀（计算出来的散列函数）
1.直接定址法：f(key)=a*key+b
2.数字分析法：抽取--只用关键字的一部分作为地址
3.平方取中法：关键字平方后取中间若干位数字作为散列地址
4.折叠法：将关键字从左到右分割成位数相等的几部分，几部分叠加求和，取最后几位
5.除留余数法：-f(key)=key mod p(p<=m) (最常用的)
6.随机数法：f(key)=random(key)
处理散列冲突的方法：
1.开放定址法：一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入
#fi(key)=(f(key)+di) mod m，就是往后推一位
--堆积问题必不可免--可以采用改变di的方法->不妨让di=q^2，或是采用随机函数计算得到
2.再散列函数法：fi(key)=RHi(key)--多尝试各种函数
3.链地址法：存在冲突，不妨弄个单链表，地址指向这个单链表
4.公共溢出法：多弄一个表-溢出表，基本表中找不到，就到溢出表中找
//散列表代码实现
#define hashsize 12
#define hullkey -32768
typedef struct
{
int *elem; //数据元素的基址，动态分配数组
int count; //存放当前数据元素的个数
} hashtable;
int inithashtable(hashtable *h)
{
h->count = hashsize;
h->elem = (int *)malloc(hashsize * sizeof(int));
if(!h->elem )
{
return -1;
}
for(i=0 ; i<hashsize ; i++)
{
h->elem[i] = hullkey;
}
return 0;
}
//使用除留余数法
int hash(int key)
{
return key % hashsize;
}
//插入关键字到散列表的代码
void inserthash(hashtable *h,int key)
{
int addr;
addr=hash(key);
while(h->elem [addr] != nullkey) //产生冲突
{
addr=(addr+1) % hashsize; //开放定址法的线性探测
}
h->elem [addr]= key;
}
//在散列表查找关键字
int searchhash(hashtable h, int key, int *addr)
{
*addr = hash(key);
while(h.elem [*addr] !=key)
{
*addr = (*addr+1) % hashsize;
if(h.elem [*addr]== nullkey || *addr == hash(key));
{
return -1;
}
}
return 0;
}
