对于含有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），则会重散列，以提高性能，降低平均链上长度。