哈希表的使用场景-大数据中的前k大 堆排序 归并

哈希表的使用场景--大数据中的前k大 堆排序 归并

    今年看到学长面试的时候，还是会问到一下基本的算法问题，在这之前对于这些还是有一定的理解，只是不能很透彻的清楚其中的原理、奥妙，在这之前也转载过关于hash表使用的文章，成这个星期天，想从头到尾把一个问题搞清楚，现在觉得这个越来越重要了，抓住一段时间，搞清楚一个问题，比泛泛的知道很多更加实在，尤其是在读书的时候更是这样，在这段时间里，自己也看了不少书，但是回头一想，还是什么都没明白，到不如在某一块上非常清楚，逐个击破！！！下面就以一个网上很常见的面试题作为分析对象：

   一个10G的关键词的log，找出词频最高的前K个词，设可用内存为2G左右

    分析：

    本题的难点主要有两处，一是如何在有限内存下对大文件进行词频统计；二是如何在有限内存的下找出词频的前K大个词。

1）词频统计

    词频统计，我们很自然的会想到使用hash。但是直接hash内存是放不下的啊…怎么办？其实对于有限内存下的大文件处理，都可总结为归并的思想，不过要注意归并时的分段亦是有学问的。请比较归并a与归并b方法

    问题：表面看来不错的主意，实则有很大问题，稍微想一下，a方法存在一个主要的困难就是，hash合并的时候相当于同时在5个文件中判断是否有相同的词，要这样做会非常繁琐。

    怎么解决呢？我当时是受编程珠玑中第一题（排序一千万个32位整数）启发的，它在归并分段的时候，不是直接的简单分段，而是每段取一个范围比如第一段取0~249000之间的数，这样有什么好处？将来的各段数彼此间是没有交集（重复）的。所以我们的思想就是要让这10G的关键词分段后各小段没有交集，这样hash合并就没有问题了。请看归并b

    分析：使用hash分段，保证各小段没有重复的词。我当时想的方法是将词语的首字拼音打头一样的分在一段中，例如“五谷丰登”、“万箭齐发”分到一起，都是w打头的拼音，其实这仅仅只是hash的一种。  

   归并a中的思路的弊端是这样的：

    在分段的时候，只是单纯的把10亿数据一刀切的分割，并没有多考虑其他的问题，在一刀切的时候，就可能会有两端中有相同的词条，也就是说在第一段和第二段中都会有相同的词条，将5段统计的hash结果都存储到文件中，再对五个hash结果合并，这个时候就需要检查hash各个结果中对相同词条统计的结果，也就是说对这五个hash结果进行再查找比对，相当于对这五个hash结果合并。这也是很繁琐的问题。

   但是在归并b中的思想是这样的：
    在分段的时候就限定这个问题的出现，具体方法就是，在分段的时候稍做处理，每个段中都没有重复的hash值，每个段中是一定范围的hash值。这样对每一段分别hash计算出现的频率，将最终的结果存放到文件中。这样对最后的五个hash结果进行比对，在这5*k（对每个段中分别查找相应的前k个，五段总共为5*k个）个结果中查找出现次数最多的前k个词条。

（ps:请注意！！！上面的问题并没有结束，这是在考虑hash的时候找到了比较好的思路，但是对于最终真正解决问题并没有起到用处，将5个hash结果存放到文件中，还是没有找出前k大，这个时候需要用到堆的问题，在第一个结果中建立k的最小堆（首先找到第一个hash结果的前k大，也就是第一个hash结果中出现频率最高的k个词条，然后从剩下的hash结果中更新这个堆），然后在剩下的堆中查找，如果有出现更频繁的词条，说明需要替换堆中元素，在整个过程中，需要N+Nlogk的时间复杂度，hash查询需要N，调整堆需要logK,可能需要调整N次）

    下面来看看关于这类问题的所有：

    散列表（HashTable）又称为哈希表，是一种快速的数据查找结构，它通常是为一个（组）要记录的数据设计一个哈希函数H(x)，依据这个函数进行给数据定位，如果是闭散列，那就是直接存到数组的H(x)下标处，如果是开散列，就是存到指针数组H(x)下标的链表处。对于闭散列，使用hash的问题就简单很多，这里只谈开散列，也就是需要链表的那种。比如在上面的那个题目，虽说数据非常多，但是可以分开再使用hash。

    一般情况下先规定一个hash函数H(x)，x是要记录的对象，我们以H(x)来确定对象的记录的链的位置。下面看下基本的hash的实现和应用，

    hash结构封装

/**PROGRAM :哈希表的综合操作 **//**CONTENT :Insert,Search,Deltet **//* * * * * * * * * * * * * * * * * * * * * * * **/#include <math.h>#include <stdio.h>#include <stdlib.h>#define MAXSIZE 30 /*哈希表的最大容量，与所采用的哈希函数有关*/typedef enum{False,True}  BOOL;typedef enum{NULLKEY,HAVEKEY,DELKEY} HAVEORNOT;/*哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除*/typedef struct /*定义哈希表的结构*/{int elem[MAXSIZE]; /* 数据元素体 */HAVEORNOT elemflag[MAXSIZE]; /*元素状态标志，没有记录、有记录、有过记录但已被删除*/int count; /*哈希表中当前元素的个数 */}HashTable;typedef struct{int keynum; /*记录的数据域，只有关键字一项*/}Record;void InitialHash(HashTable*); /*初始化哈希表*/void CreateHash(HashTable*);/* 根据从键盘上输入的一系列整数建立哈希表 */void PrintHash(HashTable); /*显示哈希表中的所有元素*/BOOL SearchHash(HashTable,int,int*); /*在哈希表中查找元素*/BOOL InsertHash(HashTable*,Record); /*在哈希表中插入元素*/BOOL DeleteHash(HashTable*,Record); /*在哈希表中删除元素*/int Hash(int); /*哈希函数*/void main(){       HashTable H; /*声明哈希表H*/       char ch,j='y';      int position;       Record R;       BOOL temp;       //textbackground(3); /*设定屏幕颜色*/       //textcolor(15);       //clrscr();       InitialHash(&H);       CreateHash(&H);       /*-------------------------程序说明-------------------------------*/       printf("This program will show how to operate to a HashTable./n");       printf("You can display all elems,search a elem,/ninsert a elem,delete a elem./n");       /*----------------------------------------------------------------*/     while(j!='n')       {              printf("1.display/n");              printf("2.search/n");              printf("3.insert/n");              printf("4.delete/n");             printf("5.exit/n");             scanf(" %c",&ch); /*输入操作选项*/              switch(ch)              {              case '1':if(H.count) PrintHash(H); /*哈希表不空*/                    else printf("The HashTable has no elem!/n");                     break;              case '2':if(!H.count) printf("The HashTable has no elem!/n"); /*哈希表空*/                     else                     {printf("Please input the keynum(int) of the elem to search:");                     scanf("%d",&R.keynum); /*输入待查记录的关键字*/                     temp=SearchHash(H,R.keynum,&position);                     /*temp=True:记录查找成功；temp=False:没有找到待查记录*/                     if(temp) printf("The position of the elem is %d/n",position);                     else printf("The elem isn't exist!/n");                     }                     break;              case '3':if(H.count==MAXSIZE) /*哈希表已满*/                     {printf("The HashTable is full!/n");                     break;                     }                     printf("Please input the elem(int) to insert:");                     scanf("%d",&R.keynum); /*输入要插入的记录*/                     temp=InsertHash(&H,R);                     /*temp=True:记录插入成功；temp=False:已存在关键字相同的记录*/                     if(temp) printf("Sucess to insert the elem!/n");                     else printf("Fail to insert the elem.The same elem has been exist!/n");                     break;              case '4':printf("Please input the keynum of the elem(int) to delet:");                     scanf("%d",&R.keynum); /*输入要删除记录的关键字*/                     temp=DeleteHash(&H,R);                     /*temp=True:记录删除成功；temp=False:待删记录不存在 */                     if(temp) printf("Sucess to delete the elem!/n");                     else printf("The elem isn't exist in the HashTable!/n");                     break;              default: j='n';              }       }       printf("The program is over!/nPress any key to shut off the window!/n");       getchar();} void InitialHash(HashTable *H){/*哈希表初始化*/       int i;       (*H).count=0;       for(i=0;i<MAXSIZE;i++) (*H).elemflag[i]=NULLKEY;} void CreateHash(HashTable *H){/* 根据从键盘上输入的一系列整数（不超过12个，以-1结束）建立哈希表 */ Record e; printf("请输入的一系列整数(不超过12个，以-1结束)以建立哈希表:/n"); scanf("%d",&e.keynum); while(e.keynum!=-1)    if(InsertHash(H,e))  scanf("%d",&e.keynum);    else      {printf("请输入不重复的数据！");       return;       }    } void PrintHash(HashTable H){     /*显示哈希表所有元素及其所在位置*/       int i;       for(i=0;i<MAXSIZE;i++) /*显示哈希表中记录所在位置*/       if(H.elemflag[i]==HAVEKEY) /*只显示标志为HAVEKEY(存放有记录)的元素*/       printf("%-4d",i);       printf("/n");       for(i=0;i<MAXSIZE;i++) /*显示哈希表中记录值*/       if(H.elemflag[i]==HAVEKEY)       printf("%-4d",H.elem[i]);       printf("/ncount:%d/n",H.count); /*显示哈希表当前记录数*/} BOOL SearchHash(HashTable H,int k,int *p){/*在开放定址哈希表H中查找关键字为k的数据元素，若查找成功，以p指示待查数据元素在表中的位置，并返回True；否则，以p指示插入位置，并返回False*/       int p1;       p1=(*p)=Hash(k); /*求得哈希地址*/       while(H.elemflag[(*p)]==HAVEKEY&&k!=H.elem[(*p)])       /*该位置中填有记录并且关键字不相等*/       {              (*p)++; /*冲突处理方法：线性探测再散列*/              if((*p)>=MAXSIZE) (*p)=(*p)%MAXSIZE; /*循环搜索*/              if((*p)==p1) return False; /*整个表已搜索完，没有找到待查元素*/       }       if(k==H.elem[(*p)]&&H.elemflag[(*p)]==HAVEKEY) /*查找成功，p指示待查元素位置*/              return True;       else return False; /*查找不成功*/} BOOL InsertHash(HashTable *H,Record e){/*查找不成功时插入元素e到开放定址哈希表H中，并返回True，否则返回False*/       int p;       if(SearchHash((*H),e.keynum,&p)) /*表中已有与e有相同关键字的元素*/       return False;       else       {(*H).elemflag[p]=HAVEKEY; /*设置标志为HAVEKEY，表示该位置已有记录*/       (*H).elem[p]=e.keynum; /*插入记录*/       (*H).count++; /*哈希表当前长度加一 */       return True;       }} BOOL DeleteHash(HashTable *H,Record e){/*在查找成功时删除待删元素e，并返回True，否则返回False*/       int p;       if(!SearchHash((*H),e.keynum,&p)) /*表中不存在待删元素*/       return False;       else       {(*H).elemflag[p]=DELKEY; /*设置标志为DELKEY，表明该元素已被删除*/       (*H).count--; /*哈希表当前长度减一*/       return True;       }} int Hash(int kn){/*哈希函数：H(key)=key MOD 11*/       return (kn%11);}