【算法】- 查找 - 散列表查询（哈希表）

---

前言

散列技术：在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)

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

---

一、哈希表的思想

创建哈希表结构体：创建哈希表数据结构HashTable，用来存放散列地址和该散列表存放的数据个数。

//创建哈希表结构
typedef struct HashTable
{int count;//记录哈希表中元素个数int* elem;//创建哈希表
}HashTable;

初始化哈希表：初始化哈希表主要还是动态开辟存放数据的数组，再初始化count的个数，并将哈希表中的值赋值为空，这里用NULLKEY标志来表示为空。

//初始化哈希表
void InitHashTable(HashTable* HT)
{int i;m = MAXSIZE;//动态开辟内存HT->elem = (int*)malloc(m * sizeof(int));HT->count = MAXSIZE;for (i = 0; i < m; i++){HT->elem[i] = NULLKEY;}}

插入哈希表：插入哈希表，通过哈希函数Hash来计算出散列地址，判断该地址是否为NULLKEY，是的话就直接插入，不是的话就将散列地址赋值为下一个地址，继续判断，直到找到了就执行插入操作。

//哈希表的插入
void InsertHashTable(HashTable* HT, int key)
{int addr;addr = Hash(key);//求散列地址while (HT->elem[addr] != NULLKEY){addr = (addr + 1) % m;}HT->elem[addr] = key;
}

查询哈希表：先通过哈希函数获得散列地址，再通过散列地址查询访问。在查询时如果通过散列地址找到的值和key值不等，则散列地址找到下一个操作，直到循环一圈或则通过地址找到的地址为NULLKEY就返回查找失败，成功则返回查找成功。

//哈希表查找
int SearchHash(HashTable HT, int key)
{int addr = Hash(key);int begin = addr;while (HT.elem[addr] != key){addr = (addr + 1) % m;if (HT.elem[addr] == NULLKEY || addr == begin)return 0;}return 1;
}

二、哈希表

#define MAXSIZE 12
#define NULLKEY -32768
#include <iostream>
using namespace std;//哈希表查找//创建哈希表结构
typedef struct HashTable
{int count;//记录哈希表中元素个数int* elem;//创建哈希表
}HashTable;int m = 0;//初始化哈希表
void InitHashTable(HashTable* HT)
{int i;m = MAXSIZE;//动态开辟内存HT->elem = (int*)malloc(m * sizeof(int));HT->count = MAXSIZE;for (i = 0; i < m; i++){HT->elem[i] = NULLKEY;}}//散列函数
int Hash(int key)
{return key % m;
}//哈希表的插入
void InsertHashTable(HashTable* HT, int key)
{int addr;addr = Hash(key);//求散列地址while (HT->elem[addr] != NULLKEY){addr = (addr + 1) % m;}HT->elem[addr] = key;
}//哈希表查找
int SearchHash(HashTable HT, int key)
{int addr = Hash(key);int begin = addr;while (HT.elem[addr] != key){addr = (addr + 1) % m;if (HT.elem[addr] == NULLKEY || addr == begin)return 0;}return 1;
}int main()
{int i,result,key;HashTable HT;int arr[MAXSIZE] = { 12,67,56,16,25,37,22,29,15,47,48,34 };//初始化哈希表InitHashTable(&HT);key = 39;for (i = 0; i < m; i++){InsertHashTable(&HT, arr[i]);}result = SearchHash(HT,key);if (result)printf("查找 %d 成功 \n", key);elseprintf("查找 %d 失败。\n", key);for (i = 0; i < m; i++){key = arr[i];result = SearchHash(HT, key);if (result)printf("查找 %d 成功 \n", key);elseprintf("查找 %d 失败。\n", key);}return 0;
}

---

总结

散列表查找的效率是最高的，因为它的时间复杂度为O(1)。可惜在实际情况中，会产生冲突（不同的数据在同一地址的情况），但散列表查询还是非常值得的。