十一、从头到尾彻底解析 Hash
Hash
Hash
Hash 表算法
作者： July 、 wuliming 、 pkuoliver
出处： http://blog.csdn.net/v_JULY_v
http://blog.csdn.net/v_JULY_v
http://blog.csdn.net/v_JULY_v
http://blog.csdn.net/v_JULY_v 。
说明：本文分为三部分内容，
第一部分为一道百度面试题 Top K 算法的详解 ； 第二部分为关于 Hash 表算法的详细阐
述；第三部分为打造一个最快的 Hash 表算法。
------------------------------------
第一部分：
Top
Top
Top
Top
K
K
K
K 算法详解
问题描述
百度面试题：
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来 ， 每个查询串的
长度为 1-255 字节。
假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是 1 千万，但如果除
去重复后，不超过 3 百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越
热门 。 ） ，请你统计最热门的 10 个查询串，要求使用的内存不能超过 1G 。
必备知识：
什么是哈希表？
哈希表（ Hash table ，也叫散列表 ） ，是根据关键码值 (Key value) 而直接进行访问的数据
结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度
。
这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希表的做法其实很简单，就是把 Key 通过一个固定的算法函数既所谓的哈希函数转
换成一个整型数字 ， 然后就将该数字对数组长度进行取余 ， 取余结果就当作数组的下标 ， 将
value 存储在以该数字为下标的数组空间里。
而当使用哈希表进行查询的时候，就是再次使用哈希函数将 key 转换为对应的数组下
标，并定位到该空间获取 value ，如此一来，就可以充分利用到数组的定位性能进行数据定
位 （ 文章第二、三部分，会针对 Hash 表详细阐述 ） 。
问题解析：
要统计最热门查询 ， 首先就是要统计每个 Query 出现的次数 ， 然后根据统计结果 ， 找 出
Top 10 。所以我们可以基于这个思路分两步来设计该算法。
即，此问题的解决分为以下 俩个步骤 ：
