8.5计算式查找（哈希查找及性能分析）

2024-06-26 16:42| 来源: 网络整理| 查看: 265

8.5计算式查找（哈希查找及性能分析）一、哈希表的查找过程

哈希表的查找过程与哈希表的创建过程是一致的。假设要查找关键字为 K 的元素，则查找过程如下： [算法思想]：

（1）首先计算 h0= hash（K）；（2）如果单元 h0为空，则所查元素不存在；（3）如果单元 h0中元素的关键字为 K，则找到所查元素；（4）否则重复下述解决冲突的过程： a. 按解决冲突的方法，找出下一个哈希地址 hi ； b. 如果单元 hi为空，则所查元素不存在； c. 如果单元 hi中元素的关键字为 K，则找到所查元素。

下面以线性探测再散列为例，给出哈希表的查找算法。 [算法描述]：哈希表的查找算法

#define m #define NULLKEY typedef int KeyType; /* 假设关键字为整型 */ typedef struct { KeyType key; …… /* 记录中其它分量按需求确定 */ …… } RecordType ; typedef RecordType HashTable[m] ; int HashSearch( HashTable ht, KeyType K) { h0=hash(K); if (ht[h0].key==NULLKEY) return (-1); else if (ht[h0].key==K) return (h0); else /* 用线性探测再散列解决冲突 */ { for (i=1; i

【本文地址】

公司简介

联系我们