poj 3320 Jessica's Reading Problem http://acm.pku.edu.cn/JudgeOnline/problem?id=3320
这道题目可以用哈希表法也可以用二分查找法，现在用哈希，二分查找将在后面的博客中推出。
这道题目用到的是数的哈希，对于不需要删除的字典，哈希表是一种理想的实现方式。
1.哈希表的插入和查找算法
(1)计算函数值h(k)
(2)从槽h(k)开始，使用冲突解决策略定位包含关键码k的纪录
(3)如果需要插入，再槽内插入即可
两种操作的复杂度在忽略冲突时是O(1)
2.哈希函数的选取
本题使用最简单的直接取余法，除数为PRIME，最好是质数，可减小冲突。
3.冲突解决方法
开散列法（这也是大多数情况下使用的）
开散列法也叫拉链法，通俗地说就是“既然元素a和b都该放在里面，只好挤一挤了”。即在每个槽里存放所有该放在里面的元素。那么怎么把很多的元素放在槽里呢？只在槽里放一个链表表头就行了，该链表中包含所有该放在槽里的元素。但在实际中并不是这样做的，而是自己维护一个大数组，给链表元素分配数组下标，这样既方便又节省时间和空间。那么链表中的元素的排列顺序怎样呢？如果按照查找成功时的效率，显然可以按照访问的频率；而如果按照查找失败的效率，则可以按照关键值排序，即使查找失败也不需要遍历整个链表。这就是数据结构中的相互矛盾的两个问题，应根据实际情况协调。
#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时，那么99999>8,需要给99999重新分配                                                                           一个下标，即hashl，即前面提到的开散列法解决冲突
            break;
        else if(num==a[a[i].next].key)    //例如hash表中已有8，后面又插入8时，这是只要num++
            return a[i].next;
        i=a[i].next;                               //这句用于查找，如果哈希表中已有8和99999，那么你要找8时a[8].next指向的是较大的99999，那么你就必须沿着next走下去，因为这个所谓的链表是按减小的顺序排序的。最终走到return a[i].next推出while 循环
    }
    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循环未执行）或while循环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)     //插入的数字以前没有出现过，肯定包含在ans里
            {
                ans=i-left+1;
                continue;
            }                        
            while(1)                     //对应于if的else,即a[tmp].num>=2，即插入的数字以前出现过。如果是在left位置出现过，则left右移；如果是在“left右边，i左边”出现过，则说明目前的i-left+1和ans都可以包括全部的知识点，当然取小的了！   
            {
                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;
}

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/cugbliang/archive/2008/06/01/2497376.aspx