今年看到学长面试的时候，还是会问到一下基本的算法问题，在这之前对于这些还是有一定的理解，只是不能很透彻的清楚其中的原理、奥妙，在这之前也转载过关于hash表使用的文章，成这个星期天，想从头到尾把一个问题搞清楚，现在觉得这个越来越重要了，抓住一段时间，搞清楚一个问题，比泛泛的知道很多更加实在，尤其是在读书的时候更是这样，在这段时间里，自己也看了不少书，但是回头一想，还是什么都没明白，到不如在某一块上非常清楚，逐个击破！！！下面就以一个网上很常见的面试题作为分析对象：
一个10G的关键词的log，找出词频最高的前K个词，设可用内存为2G左右
分析：
本题的难点主要有两处，一是如何在有限内存下对大文件进行词频统计；二是如何在有限内存的下找出词频的前K大个词。
1）词频统计
词频统计，我们很自然的会想到使用hash。但是直接hash内存是放不下的啊…怎么办？其实对于有限内存下的大文件处理，都可总结为归并的思想，不过要注意归并时的分段亦是有学问的。请比较归并a与归并b方法
- 归并a：将数据分为5段，分别对每段在内存中hash统计并将统计结果写入文件，然后合并分段的hash。
问题：表面看来不错的主意，实则有很大问题，稍微想一下，a方法存在一个主要的困难就是，hash合并的时候相当于同时在5个文件中判断是否有相同的词，要这样做会非常繁琐。
怎么解决呢？我当时是受编程珠玑中第一题（排序一千万个32位整数）启发的，它在归并分段的时候，不是直接的简单分段，而是每段取一个范围比如第一段取0~249000之间的数，这样有什么好处？将来的各段数彼此间是没有交集（重复）的。所以我们的思想就是要让这10G的关键词分段后各小段没有交集，这样hash合并就没有问题了。请看归并b
- 归并b：将数据分为5段，分段时对每个词hash，hash值在一个范围中的词语分到一个段中，然后对于每个分段统计的hash结果直接都写入一个文件即可。
分析：使用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+N'logk的时间复杂度，hash查询需要N，调整堆需要logK,可能需要调整N'次,这里的N'就是没有所有的词条的种类）
下面来看看关于这类问题的所有：
散列表（HashTable）又称为哈希表，是一种快速的数据查找结构，它通常是为一个（组）要记录的数据设计一个哈希函数H(x)，依据这个函数进行给数据定位，如果是闭散列，那就是直接存到数组的H(x)下标处，如果是开散列，就是存到指针数组H(x)下标的链表处。对于闭散列，使用hash的问题就简单很多，这里只谈开散列，也就是需要链表的那种。比如在上面的那个题目，虽说数据非常多，但是可以分开再使用hash。
一般情况下先规定一个hash函数H(x)，x是要记录的对象，我们以H(x)来确定对象的记录的链的位置。下面看下基本的hash的实现和应用，
hash结构封装
template<class T>
struct t_node
{
public:
T key;
//other info
t_node* next;
};
关于hash的基本操作：
template<class T>
class hashtable
{
public:
hashtable();
int hash(const T &sr);
void insert();
t_node *find(const T &sr);
//add more functions
private:
t_node *ht[t_size];//you should define t_size as sth before
//add more things
};
hashtable<T>::hahstable()
{
memset(ht,0,sizeof(ht));
}
void hashtable<T>::insert(const T &sr)
{
int loc = hash(sr);
if (ht[loc] == 0)
{
//此处为空，插入一个新链表
ht[loc] = new t_node();
ht[loc]-> key = T;
}
else
{
t_node *now = ht[loc];
while (true)
{
if (now->key == sr)
{
//元素已经存在。
return;
}
else if (now->next == 0)
{
//链里面没有该元素，就地插入
now->next = new t_node();
now->next->key = T;
return;
}
else now = now->next;
}
}
}
t_node *hashtable<T>::find(const T &st)
{
int loc = hash(sr);
if (ht[loc] == 0)
{
//此处为空，木有~ 返回空指针
return 0;
}
else
{
t_node *now = ht[loc];
while (true)
{
if (now->key == sr)
{
//找到了
return now;
}
else if (now->next == 0)
{
//遍历完了整个链还是木有。。
return 0;
}
else now = now->next;//看这个链的下一个元素
}
}
}
散列表本质思想就是把数组与链表的优势结合起来，数组的访问复杂度是O(1)，链表的插入复杂度是O(1)，然而数组的插入复杂度和链表的访问复杂度都比较高，所以就产生了散列表。
数据结构：hash_map原理
hash_map基于hash table（哈希表）。哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。
其基本原理是：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。
hash_map，首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。其插入过程是：
- 得到key
- 通过hash函数得到hash值
- 得到桶号(一般都为hash值对桶数求模
- 存放key和value在桶内。
其取值过程是:
- 得到key
- 通过hash函数得到hash值
- 得到桶号(一般都为hash值对桶数求模
- 比较桶的内部元素是否与key相等，若都不相等，则没有找到。
- 取出相等的记录的value。
hash_map中直接地址用hash函数生成，解决冲突，用比较函数解决。这里可以看出，如果每个桶内部只有一个元素，那么查找的时候只有一次比较。当许多桶内没有值时，许多查询就会更快了(指查不到的时候).
由此可见，要实现哈希表,和用户相关的是：hash函数和比较函数。这两个参数刚好是我们在使用hash_map时需要指定的参数。
/**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);
}