哈希查找-向日葵屋

哈希查找

哈希查找是一种通过设计所存储数据元素与其存放地址之间的映射关系（函数关系）来实现高效查找的方法。比如我需要查询一个数460，那么根据先前存储时所采取的映射关系就可以准确地得到460相应的存储地址，从而实现高效查找。这是一个给定自变量的值，通过指定函数关系，得到因变量的值的过程。所谓哈希冲突就是一个因变量出现多个自变量的情况。

传统上我们要在数据集中查找某一个数据，都是遍历它进行一一比对，而哈希查找不会执行遍历，它是寻址访问（查找），所以效率会高很多，不过在存储空间的利用率上就相对低一些。

如果存储的数据元素有重复的情况呢？就是同样的因变量有多个，这又应该怎样处理？

以下是几种常用的存储整型类型数据的哈希函数设计方法。

第一步：设计哈希函数

设数据元素为K，数据元素个数为n，申请的内存单元个数为m

除留余数法

h(K) = K mod m

理论研究表明，m取1.1n~1.7n之间的一个素数最好。

直接定址法

不是很好用

数字分析法

感觉也不是很好用

哈希表设计

typedef enum {Empty, Active, Deleted} KindOfItem;//表项状态的枚举类型 
//表项结构体 
typedef struct
{
    DataType data;
    KindOfItem info;
 } HashItem;
typedef struct
{
    HashItem *ht;    //哈希表数组 
     int tableSize;   //数组最大个数 
    int currentSize; //当前表项个数 
}HashTable;//哈希表结构体
//初始化
int Initiate(HashTable *hash, int mSize)
{
    hash->tableSize = mSize;
    hash->ht = (HashItem *)malloc(sizeof(HashItem)*mSize);
    if(hash->ht==NULL) return 0;
    else
    {
        hash->currentSize = 0;
        return 1;
    }
 } 
//查找函数
int Find(HashTable *hash, DataType x)
{
    int i = x.key % hash->tableSize;
    int j = i;
    while(hash->ht[j].info == Active && hash->ht[j].data.key != x.key)
    //说明存在冲突
    {
        j = (j + 1)%hash->tableSize;//哈希冲突函数继续查找
        if(j==i)//说明已遍历整个哈希表未找到且表已满
             return -hash->tableSize;
    }
    if(hash->ht[j].info == Active) return j;
    else return -j;
 } 
//把数据元素x插入到哈希表hash中
int Insert(HashTable *hash, DataType x)
{
    int i = Find(hash, x);
    if(i>=0) return 0;
    else if(i!= -hash->tableSize)
    {
        hash->ht[-i].data = x;
        hash->ht[-i].info = Active;
        hash->currentSize++;
        return 1;
    }
    else return 0;
 } 
//删除哈希表hash中的数据元素x
int Delete(HashTable *hash, DataType x)
{
    int i = Find(hash, x);
    if(i>=0)
    {
        hash->ht[i].info = Deleted;
        hash->currentSize--;
        return 1;
    }
    else return 0;
 } 
//撤销函数
void Destroy(HashTable *hash)
{
    free(hash->ht);
 }

测试：

#include <stdio.h>
#include <malloc.h>
typedef int KeyType;
typedef struct
{
    KeyType key;
}DataType;
#include "head.h"
int main()
{
    HashTable myHashTable;
    DataType a[] = {180,750,600,430,541,900,460}, item = {430};
    int i,j,k,n=7,m=11;
    Initiate(&myHashTable,m);
    for(i=0;i<n;i++)
    {
        Insert(&myHashTable,a[i]);
     } 
    for(i=0;i<n;i++)
    {
        j = Find(&myHashTable,a[i]);
        printf("j=%d  ht[]=%d\n",j,myHashTable.ht[j].data.key);
    }
    k = Find(&myHashTable, item);
    if(k>=0) printf("查找成功，元素%d的哈希地址为%d\n",item.key,k);
    else printf("查找失败\n");
    Delete(&myHashTable,item);
    k = Find(&myHashTable,item);
    if(k>=0) printf("查找成功，元素%d的哈希地址为%d\n",item.key,k);
    else printf("查找失败\n");
    Destroy(&myHashTable);
    return 0;
}