算法技术手册 – 查找 – 散列查找(Hash查找)

对于含有n个元素的集合C,我们先构造一个Hash函数,让n映射到b个桶内,当选择合理时,速度会很快,时间复杂度O(1)。

完美哈希函数:不会产生冲突,是存在的。

对于>=1个值映射到同一个桶的情况下,就会发生碰撞。处理方法:

  • 链表:每个桶拉一个链表,第一遍散列后,在链表中查找是否存在元素。
  • 开放定址:构造双变量散列函数h(u, j)。h(u, 0) = h(u),此时退化为原始散列函数。

开放定址,分两类:

  • 线性探测h(u, j)=(h(u)+j) mod n
  • 二次探测h(u, j)=(h(u) + f(j)) mod m,其中f(j)是二次方函数

主要算法:

1、load:读取元素,构造散列表(使用链表)

2、search:查找,hash(val)算出slot,然后在slot的链表上查找是否存在。

源代码:

#include <stdio.h>
#include <stdlib.h>

typedef int TYPE;

typedef struct Node
{
    TYPE elem;
    struct Node* next;
}Node;

//Hash Buckets
#define B 11
Node buckets[B];

int hash(TYPE val)
{
    return val%B;
}

//Load Hash Table
int load(TYPE* arr, int n)
{
    int i;
    Node *cur, *p;
    //Null all buckets
    for(i=0; i<B; i++)
    {
        buckets[i].next = NULL;
    }   

    //Load sll elems
    for(i=0; i<n; i++)
    {
        int bucket = hash(arr[i]);
        cur = &buckets[bucket];
        while(cur->next != NULL)
        {
            cur = cur->next;
        }
        //Insert new node
        p = (Node*)malloc(sizeof(Node));
        if(!p)
        {
            return -1;
        }
        else
        {
            p->elem = arr[i];
            p->next = NULL;
            cur->next = p;
        }
    }
}

//Search
int search(TYPE t)
{
    int bucket = hash(t);
    Node* cur;
    cur = (buckets[bucket].next);
    while(cur!=NULL)
    {
        if(cur->elem==t)
        {
            return 1;
        }
        cur = cur->next;
    }
    return 0;
}

int main()
{
    TYPE arr[10] = {1,2,3,4,5,6,7,8,12,13};
    TYPE t = 100;
    load(arr, sizeof(arr)/sizeof(TYPE));
    printf("Is %d in array: %d\n", t, search(t));
    return 0;
}

Java提供了Hashtable类,比我们实现的散列查找具有更好的性能。它引入了负载因子的概念。a=n/b,即每个链上的平均元素数量。当a过高(默认超过0.75),则会重散列,以提高性能,降低平均链上长度。

Leave a Reply

Your email address will not be published.