数据结构与算法-哈希表

1概念

1.1哈希

哈希（hash）也被称之为散列，是指将任意长度的输入的数据按照某种规则（哈希算法）来变为定长的输出的方式。这个输出也被称之为哈希（散列）值

1.2哈希函数

散列技术是记录存储位置和他的关键字之间建立一个确定的对应关系f 使得每个关键字key对应一个存储位置f(key).我们将这种对应关系称之为hash函数

1.3哈希表

采用散列技术将记录存储在一块连续的存储空间中，这块连续的空间就叫散列表或哈希表

1.4哈希表查找步骤

2构造哈希函数

2.1原则

1：计算简单
2：分布均匀

2.2方法

2.2.1直接定址法

2.2.2平方取中法

2.2.3折叠法

比如9876543210=000+321+654+987=1962 如果表长度3位 就取962

2.2.3除留余数法

2.2.3随机数法

!在这里插入图片描述

2.3采取不同的哈希函数的参考方向

1：计算哈希地址所需的时间
2：关键字的长度
3：散列表的大小
4：关键字的分布情况
5：记录查找的频率

3解决哈希函数冲突

3.1开放定址法

3.2链地址法

3.3公共溢出区法

4哈希表的应用

5代码实现

#define HASHSIZE 12
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<HSAHSIZE;i++){
		H->elem[i]=-32765；
	}
	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=Hash(addr+1);
	}
		H->elem[addr]=key;
}
//哈希表查找关键字
int SerachHash(HashTable *H,int key, int *addr){
		*addr=Hash(key);
		while(H.elem[*addr]!=key){
			*addr =(*addr+1)%HASHSIZE;
			//条件1：查到最后一个 条件2：表示回到上一个地址
			if(H.elem[*addr]==NULLKEY || *addr==Hash(key)){
				return -1;//表示没有
			}
		}
		return0；
}