poj 3320 Jessica's Reading Problem http://acm.pku.edu.cn/JudgeOnline/problem?id=3320
這道題目可以用哈希表法也可以用二分查找法，現(xiàn)在用哈希，二分查找將在后面的博客中推出。
這道題目用到的是數(shù)的哈希，對(duì)于不需要?jiǎng)h除的字典，哈希表是一種理想的實(shí)現(xiàn)方式。
1.哈希表的插入和查找算法
(1)計(jì)算函數(shù)值h(k)
(2)從槽h(k)開(kāi)始，使用沖突解決策略定位包含關(guān)鍵碼k的紀(jì)錄
(3)如果需要插入，再槽內(nèi)插入即可
兩種操作的復(fù)雜度在忽略沖突時(shí)是O(1)
2.哈希函數(shù)的選取
本題使用最簡(jiǎn)單的直接取余法，除數(shù)為PRIME，最好是質(zhì)數(shù)，可減小沖突。
3.沖突解決方法
開(kāi)散列法（這也是大多數(shù)情況下使用的）
開(kāi)散列法也叫拉鏈法，通俗地說(shuō)就是“既然元素a和b都該放在里面，只好擠一擠了”。即在每個(gè)槽里存放所有該放在里面的元素。那么怎么把很多的元素放在槽里呢？只在槽里放一個(gè)鏈表表頭就行了，該鏈表中包含所有該放在槽里的元素。但在實(shí)際中并不是這樣做的，而是自己維護(hù)一個(gè)大數(shù)組，給鏈表元素分配數(shù)組下標(biāo)，這樣既方便又節(jié)省時(shí)間和空間。那么鏈表中的元素的排列順序怎樣呢？如果按照查找成功時(shí)的效率，顯然可以按照訪(fǎng)問(wèn)的頻率；而如果按照查找失敗的效率，則可以按照關(guān)鍵值排序，即使查找失敗也不需要遍歷整個(gè)鏈表。這就是數(shù)據(jù)結(jié)構(gòu)中的相互矛盾的兩個(gè)問(wèn)題，應(yīng)根據(jù)實(shí)際情況協(xié)調(diào)。
#include<stdio.h>
#define PRIME 99991
struct hashnode
{
    int key;
    int num;
    int next;
}a[1000005];
int b[1000005];
int hashl;
int hash(int num)
{
    int i;
    i=num%PRIME;
    while(a[i].next!=-1)
    {
        if(num>a[a[i].next].key)     //例如hash表中已有8，后面又插入99999時(shí)，那么99999>8,需要給99999重新分配                                                                           一個(gè)下標(biāo)，即hashl，即前面提到的開(kāi)散列法解決沖突
            break;
        else if(num==a[a[i].next].key)    //例如hash表中已有8，后面又插入8時(shí)，這是只要num++
            return a[i].next;
        i=a[i].next;                               //這句用于查找，如果哈希表中已有8和99999，那么你要找8時(shí)a[8].next指向的是較大的99999，那么你就必須沿著next走下去，因?yàn)檫@個(gè)所謂的鏈表是按減小的順序排序的。最終走到return a[i].next推出while 循環(huán)
    }
    a[hashl].key=num;
    a[hashl].next=-1;
    a[hashl].num=0;
    a[hashl].next=a[i].next;
    a[i].next=hashl;
    hashl++;                                //以上6行用于第一次插入元素（即while循環(huán)未執(zhí)行）或while循環(huán)break退出的插入
    return hashl-1;
}

int main()
{
    int n,i,tmp,left,ans;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<PRIME;i++)
            a[i].next=-1;
        hashl=PRIME;
        left=0;
        ans=1;
        scanf("%d",&b[0]);
        tmp=hash(b[0]);
        a[tmp].num++;
        for(i=1;i<n;i++)
        {
            scanf("%d",&b[i]);
            tmp=hash(b[i]);
            a[tmp].num++;
            if(a[tmp].num<=1)     //插入的數(shù)字以前沒(méi)有出現(xiàn)過(guò)，肯定包含在ans里
            {
                ans=i-left+1;
                continue;
            }                        
            while(1)                     //對(duì)應(yīng)于if的else,即a[tmp].num>=2，即插入的數(shù)字以前出現(xiàn)過(guò)。如果是在left位置出現(xiàn)過(guò)，則left右移；如果是在“left右邊，i左邊”出現(xiàn)過(guò)，則說(shuō)明目前的i-left+1和ans都可以包括全部的知識(shí)點(diǎn)，當(dāng)然取小的了！   
            {
                tmp=hash(b[left]);
                if(a[tmp].num<=1)
                    break;
                a[tmp].num--;
                left++;
            }
            if(ans>i-left+1)
                ans=i-left+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/cugbliang/archive/2008/06/01/2497376.aspx