【C-查找】哈希查找

本文主要是介绍【C-查找】哈希查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原理

• 建哈希表（哈希表下标是原数组元素经过哈希函数处理后的哈希值，哈希表值是原数组元素的下标或地址）

• 将待查找值，经过哈希函数处理后，在哈希表中查询

有可能会触发哈希冲突

哈希冲突：两个不同数组元素，对应的哈希值是一样的，在哈希表的同一位置上

解决哈希冲突：开放寻址法、链表法

性能

时间复杂度：建哈希表O(n)，查询O(1)

代码

1.0 哈希表在查找函数内

输入：数组地址，数组长度，待查找的目标

输出：找到就返回目标值的下标，找不到返回-1

#include <string.h>
//哈希表大小
#define MAXKEY 1000//哈希函数，处理数组元素返回哈希表下标
int hash(char *key) {int h = 0, g;while (*key) {h = (h << 4) + *key++;g = h & 0xf0000000;if (g)h ^= g >> 24;h &= ~g;}return h % MAXKEY;
}//输入：数组地址，数组长度，查询值
//输出：找到返回查询值在数组中的下标，或-1
int hash_search(char (*pArr)[100], int len, char *target)
{//建立哈希表//如果需要多次查询，可以将哈希表放在主函数内, 然后用参数引进来int hashTable[MAXKEY] = {0};    //初始化哈希表，所有元素设为-1memset(hashTable, -1, MAXKEY * sizeof(int));//给哈希表赋值//哈希表的下标，是经过哈希函数处理过的数组元素//哈希表的值，是数组元素的下标for (int i = 0; i < len; ++i) {hashTable[hash(pArr[i])] = i;}return hashTable[hash(target)];
}

这篇关于【C-查找】哈希查找的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---