概述
哈希表的查询是通过计算的方式获取数据的地址,而不是依次比较。在哈希表中,有一个键值key,通过一些函数转换为哈希表的索引值。
其中:这个函数被称为哈希函数、散列函数、杂凑函数,记为:H(key)
哈希函数构造与冲突:
直接地址法、平方取中法、叠加法、保留余数法、随机函数法
- 保留除数法(质数除余法):
设哈希表空间长度为m,则哈希函数为:H(key) = key%p 其中:p<=m 且 p为最大质数。
- 冲突:
冲突是指表中某个地址已经存放了记录,但新的记录通过计算之后也要存放在这个地址。比如:p=3,key1=3,key2=6,key1、key2取余之后都是0,这就产生了冲突。
哈希函数一定会存在冲突,选择随机度好的哈希函数可以减少冲突但是不能消除冲突。
对于顺序存储哈希保留除数法的处理冲突的哈希函数:Hi = (H(key)+di)%m 即:加一个步长。
对于di,线性探查法di = 1,2,3.... 二次探查法di = 1^2,-1^2,2^2,-2^2....
对于链式存储哈希保留除数法的处理冲突的方法:将冲突的位置连成一个链表。下一章详细分析。
- 装填因子:
装填因子α = n/m ,代表总数据个数n,所占总哈希表空间m的值。一般α = 0.7~0.8这代表30%~20%的哈希表空间为空闲状态,用于存储冲突的数据。
- 举例
例:有8个数据要存,装填因子α=0.8,这8个数据的键值为{0,1,2,3,4,5,6,7,8}。以线性探查法处理冲突设计一个哈希表。
解:哈希表的空间m = n/α = 10。那么哈希函数中的p的值就是不大于10的最大质数,就是7。
对八个键值求H(key)=key%7得:{0,1,2,3,4,5,6,0,1},因此7,8冲突
key=7 7%7=0,与0冲突,线性探查法依次为1,2,3,4,5,6,7,位置7不再冲突,因此存放在7处
key=8 8%7=1,与1冲突,线性探查法依次为2,3,4,5,6,7,8,位置8不再冲突,因此存放在8处
最终的哈希表数据分布如下:
链式哈希的实现
1、基本内容
链式哈希的构成是:将冲突结点构成一个链表,在哈希表中存放着这个冲突结点的冗余头结点。
具体的链式哈希结构如下:
哈希表及冲突数据结点结构体声明如下:
typedef int keyType;
typedef int data_t;
//数据冲突结点
typedef struct node{keyType key; data_t data;struct node* pNext;
}listnode,*linklist;
//哈希表
typedef struct hash{listnode* pArr; //存放链表结点指针,该指针为数组指针int len; //哈希表的长度
}hash;
哈希表代码的文件构成:
- hash.h:数据结构的定义、运算函数接口
- hash.c:运算函数接口的实现
- test.c:使用数据结构实现的应用功能代码
2、哈希表代码实现
2.1 哈希表创建
哈希表的创建就是开辟一个空间,初始化全部的元素,使得该冗余头的pNext = NULL
具体代码实现如下:
/** hash_create:创建哈希表* param len:哈希表的长度* @ret NULL--err other--哈希表的指针* */
hash* hash_create(int len){hash* pHash = NULL;//1.申请空间//1.1 申请哈希结构体空间pHash = (hash*)malloc(sizeof(hash));if(pHash == NULL){printf("hash malloc err\n");return NULL;}//1.2 申请存放链表结点指针的数组空间pHash->pArr = (linklist)malloc(sizeof(listnode)*len);if(pHash->pArr == NULL){printf("pArr malloc err\n");free(pHash);return NULL;}//2.初始化memset(pHash->pArr,0,sizeof(linklist)*len);pHash->len = len;return pHash;
}
2.2 冲突数据节点创建
这个创建与普通节点的创建完全一致
具体代码实现如下:
/** hashNode_create:创建哈希结点* param key:结点的键值* param data:结点的数据* @ret NULL--err other--结点地址* */
linklist hashNode_create(keyType key,data_t data){linklist pHashNode = NULL;//1.申请空间pHashNode = (linklist)malloc(sizeof(listnode));if(pHashNode == NULL){printf("malloc err\n");return NULL;}//2.初始化pHashNode->key = key;pHashNode->data = data;pHashNode->pNext = NULL;return pHashNode;
}
2.3 插入哈希表
将数据插入哈希表,先利用哈希函数算出在哈希表的哪个位置,之后以key递增的方式有序插入
具体代码实现如下:
/** hash_insert:在哈希表中插入数据* param pHash:哈希表的指针* param pHashNode:新数据的指针* @ret -1--err 0--success* */
int hash_insert(hash* pHash,linklist pHashNode){int hash_i;//数据哈希表中的位置linklist pHead = NULL;//同一位置的链表头linklist pIn = NULL;//插入点linklist pAhead = NULL;//插入点前一个结点//1.判断参数有效性if(pHash == NULL || pHashNode == NULL){printf("param err\n");return -1;}//2.获取结点在哈希表中的位置hash_i = pHashNode->key % pHash->len;pHead = &(pHash->pArr[hash_i]);pIn = pHead->pNext;pAhead = pHead;//3.在指定哈希表位置处插入//3.1 指定位置出为空if(pHead->pNext == NULL){pHead->pNext = pHashNode;}//3.2 指定位置有数据,键值小的放前面else{//3.2.1 遍历插入while(pIn != NULL){if(pHashNode->key < pIn->key){//插入到当前结点前面pAhead->pNext = pHashNode;pHashNode->pNext = pIn;break;}pAhead = pIn;pIn = pIn->pNext;}//3.2.2 遍历之后依旧没插入,将结点尾插if(pIn == NULL){pAhead->pNext = pHashNode;}}return 0;
}
2.4 查询哈希表
查询哈希表,先利用哈希函数算出所在位置,之后遍历链表找到数据。
具体代码实现如下:
/** hash_search:根据键值查找元素* param pHash:哈希表的指针* param pHashNode:找到的数据存放的位置* param key:键值* @ret -1--err 0--find it* */
int hash_search(hash* pHash,linklist* ppHashNode,keyType key){int hash_i;//数据哈希表中的位置linklist pHead = NULL;//同一位置的链表头linklist pTmp = NULL;//1.判断参数有效性if(pHash == NULL || ppHashNode == NULL){printf("param err\n");return -1;}//2.获取结点在哈希表中的位置hash_i = key % pHash->len;pHead = &(pHash->pArr[hash_i]);pTmp = pHead->pNext;//3.遍历查找while(pTmp != NULL){if(pTmp->key == key){*ppHashNode = pTmp;break;}pTmp = pTmp->pNext;}if(pTmp == NULL){//没找到printf("not find\n");return -1;}else{//找到了return 0;}
}