比特币简易网站开发,旅行社英文模板网站,珠海做网站公司,成都网站建设 3eC 简单实现哈希查找
1. 哈希冲突 哈希表中可能会出现哈希冲突#xff0c;即多个数据项映射到相同的桶。 常见的冲突解决方法包括链地址法#xff08;Chaining#xff09;和线性探测法#xff08;Linear Probing#xff09;。
使用链地址法时#xff0c;每个桶维护一个链…C 简单实现哈希查找
1. 哈希冲突 哈希表中可能会出现哈希冲突即多个数据项映射到相同的桶。 常见的冲突解决方法包括链地址法Chaining和线性探测法Linear Probing。
使用链地址法时每个桶维护一个链表哈希冲突的数据项被插入到链表中。查找时遍历链表以查找目标数据项。使用线性探测法时如果一个桶已经被占用算法会线性地探测下一个可用的桶直到找到目标数据项或空桶。这种方法需要特别处理删除操作。
2. 算法执行过程
初始化哈希表创建一个固定大小的数组将每个元素的值设置为其索引。插入元素根据要插入的元素计算其哈希值然后将该元素插入到对应索引的位置。如果发生哈希冲突即两个不同的元素具有相同的哈希值则在相应索引位置存储一个链表链表中存储具有相同哈希值的所有元素。查找元素首先计算要查找元素的哈希值然后根据哈希值找到对应的索引位置。如果该位置没有其他元素说明找到了目标元素否则在对应索引位置的链表中继续查找。删除元素如果要删除的元素恰好等于目标元素那么直接删除即可否则需要找到该元素所在的链表并从链表中删除该元素。扩容当哈希表的大小超过了数组的最大容量时需要对数组进行扩容即创建一个新的更大的数组并将原数组中的元素重新插入到新数组中。同时还需要重新计算所有元素的哈希值并将它们插入到新数组的相应位置。****
3. 例题 例题 有序表 A[20] {4612202838507088100}使用哈希查找算法找出元素 20 4. 步骤
为了使用哈希查找方法实现有序表A[20]
我们需要首先定义哈希表的大小。哈希表的大小通常比表中元素的最大值要大以确保所有元素都能被存储并且有足够的空间来解决哈希冲突。接下来我们需要定义一个哈希函数。一个简单的哈希函数可以是将元素值除以哈希表大小然后取整数部分。在这个例子中我们的哈希表大小为10所以哈希函数可以是 h(x) x % 10。对于整数这个函数将把每个元素映射到一个在0到9之间的位置。现在我们可以开始将元素插入哈希表中。由于我们使用线性探索来解决冲突当冲突发生时我们将在哈希表中的当前位置开始线性搜索直到找到一个空位置为止。
以下是插入过程的步骤
初始化哈希表hashTable[10] {NULL}其中 NULL 表示空位置。对于表A中的每个元素x 计算哈希值h(x) x % 10确定哈希位置index h(x)如果 hashTable[index] 为 NULL则将x插入到 hashTable[pos]如果 hashTable[index]不为 NULL则进行线性探索寻找空位置。线性探索可以从 index 1 开始直到找到空位置。 重复步骤2直到表A中的所有元素都被插入到哈希表中。 下面是具体的插入过程
对于4h(4) 4 % 10 4, hashTable[4] 为空插入。对于20h(20) 12 % 10 0hashTable[0] 为空插入。对于50h(50) 50 % 10 0但 hashTable[0] 已被占用进行线性探索hashTable[1] 为空插入。依此类推直到所有元素都被插入到哈希表中。
最终的哈希表 hashTable 将包含有序表 A 的元素可能有一些位置为 NULL表示在插入过程中没有发生冲突。
为了查找表中的一个元素x我们同样使用哈希函数计算其哈希值然后在哈希表中定位该值。
如果在定位的位置找到了元素 x则查找成功如果找到了 NULL则说明元素 x 不在表中。
需要注意的是线性探索虽然简单但在高负载情况下即哈希表的装载因子较高会导致性能下降因为可能会出现较长的查找链。
在实际应用中可能会采用更复杂的哈希函数和冲突解决策略来提高效率。
5. 代码
#include iostream
#include vectorusing namespace std;// 哈希表的大小
const int HASH_TABLE_SIZE 10;
// 哈希表
vectorint hashTable(HASH_TABLE_SIZE, 0); // 初始化为NULL
// 哈希函数
int hashFunction(int key) {return key % HASH_TABLE_SIZE;
}
// 线性探查
int linearProbing(int key) {int index hashFunction(key);while (hashTable[index] ! 0 hashTable[index] ! key) {index (index 1) % HASH_TABLE_SIZE; // 线性探查}return index;
}// 插入键值对
void insert(int key) {int index linearProbing(key);if (hashTable[index] 0) {hashTable[index] key;} else {cout 冲突发生键 key 已存在。 endl;}
}// 查找键
int search(int key) {int index hashFunction(key);while (hashTable[index] ! 0) {if (hashTable[index] key) {return index;}index (index 1) % HASH_TABLE_SIZE; // 线性探查}return -1; // 未找到键
}int main() {// 初始化有序表int A[10] {4, 6, 12, 20, 28, 38, 50, 70, 88, 100};// 插入元素for (int i 0; i 10; i) {insert(A[i]);}for (int i 0; i 10; i) {cout hashTable[i] ;}cout endl;// 搜索元素int keyToSearch 20;int index search(keyToSearch);if (index ! -1) {cout 键 keyToSearch 在哈希表中的位置是 index endl;} else {cout 键 keyToSearch 在哈希表中未找到。 endl;}return 0;
}6. 使用场景
字典和关联数组:哈希表常用于实现字典和关联数组其中键映射到值。这样可以快速查找特定键对应的值。缓存:哈希表用于数据缓存允许快速访问已经检索的数据以减少对慢速存储介质如磁盘的访问。数据库索引:在数据库管理系统中哈希表用于构建索引以便快速检索和访问数据库中的数据。这在大型数据库中非常有用。散列集合:编程语言中的集合Set和散列集合HashSet通常使用哈希表来实现以便快速查找成员。数据去重:哈希表可用于检测和删除重复数据项。通过将数据插入哈希表并检查是否已经存在可以有效去重。认证和授权:哈希表可用于存储用户凭据如用户名和密码或授权令牌以便快速验证用户身份。编译器符号表:编程语言编译器使用哈希表来管理符号表以便快速查找变量、函数和其他符号的定义和引用。数据分布:在分布式计算中哈希表用于确定数据项应该存储在哪个节点或分片以实现均匀的数据分布。缓存管理:缓存管理系统通常使用哈希表来跟踪缓存的内容以加速数据检索。路由表:网络路由器使用哈希表来管理路由表以确定数据包的转发路径。文件系统索引:文件系统通常使用哈希表来维护文件索引以加速文件查找和访问。编码查找表:在编码和解码中哈希表可用于存储查找表以实现快速的字符或编码查找。
