注意：本文分为三个部分

第一部分是百度面试题Top K算法的详细讲解;第二部分是哈希表算法的详细说明。第三部分是构建最快的哈希表算法。

------------------------------------

第 1 部分：Top K 算法的详细说明

问题描述

百度面试题：

搜索引擎将通过日志文件记录用户每次搜索使用的所有搜索字符串，每个查询字符串的长度为 1-255 个字节。

假设当前有 1000 万条记录（这些查询字符串具有高度的重复性，尽管总数为 1000 万条，但如果删除重复项，则不超过 300 万条。查询字符串的重复性越强，查询它的用户就越多，也就是说，它就越受欢迎。请统计最常用的 10 个查询字符串，所需内存不能超过 1G。

基本会话：

什么是哈希表？

哈希表（也称为哈希表）是一种基于键值直接访问的数据结构。也就是说，它通过将键值映射到表中的某个位置来访问记录，以加快查找速度。此映射函数称为哈希函数，保存记录的数组称为哈希表。

哈希表的方法其实很简单，就是通过固定的算法函数，也就是所谓的哈希函数，把Key转换成一个整数，然后把这个数字留作数组长度的余数，把余数结果作为数组的下标，以数字为下标，被存储在数组空间里。

在使用哈希表进行查询时，再次使用哈希函数将键转换为对应的数组下标，并将其定位到空间来获取它，以便可以充分利用数组的定位性能进行数据定位（本文的第二和第三部分将对哈希表进行详细说明）。

问题解决：

要计算最受欢迎的查询，首先需要统计每个查询的出现次数，然后根据统计结果找到前 10 个。因此，我们可以根据这个想法分两步设计算法。

也就是说，这个问题的解决分为以下两个步骤：

第 1 步：统计信息

您可以选择两种统计方法：

1.直接分拣方式

首先，我们想到的算法是排序，首先对这个日志中的所有内容进行排序，然后遍历有序的，计算每个序列的出现次数。

但是标题中有明确的要求，那就是内存不能超过1G，1000万条记录，每条记录都是，明显占用2.55G内存，这个条件不符合要求。

我们回想一下数据结构课程的内容，当数据量比较大，内存无法加载时，我们可以使用外部排序方法进行排序，这里我们可以使用合并排序，因为合并排序具有更好的时间复杂度O（NlgN）。

排序之后，我们将遍历有序的文件，计算每个文件的出现次数搜索多少次会被百度记录，然后再次将它们写入文件。

在综合分析中，排序的时间复杂度为O（NlgN），遍历的时间复杂度为O（N），因此算法的整体时间复杂度为O（N+NlgN）=O（NlgN）。

2. 哈希法

在第一种方法中，我们使用排序方法来统计每次出现的出现次数，时间复杂度为NlgN，那么有没有更好的方法来存储它，并且时间复杂度更低？

标题说明虽然有1000万个，但由于重复程度高，实际上每个只有300万个，所以我们可以考虑把它们全部放到内存里，现在我们只需要一个合适的数据结构，在这里，Hash绝对是我们的首选，因为Hash的查询速度非常快， 几乎O（1）时间复杂度。

然后，我们的算法有它：将一个键维护为字符串，即出现的次数，一次读取一个，如果字符串不在其中，则将字符串相加，并将值设置为 1;如果字符串在 中，则将字符串的计数相加 1。最终，我们在O（N）的时间复杂度内完成了对如此海量数据的处理。

与算法1相比，所提方法的时间复杂度提高了一个数量级，即O（N），但不仅仅是时间复杂度的优化，该方法只需要IO数据文件一次，且算法1的IO次数更多，因此算法2在工程上的可操作性优于算法1。

第 2 步：找出前 10 名

算法 1：正常排序

我想大家对排序算法并不陌生，所以这里就不赘述了，但是我们应该注意的是，排序算法的时间复杂度是NlgN，在这个话题中，用1G内存可以存储300万条记录。

算法 2：部分排序

问题的要求是找到前 10 个，所以我们不需要对它们全部进行排序，我们只需要维护一个 10 个大小的数组，初始化并放置 10 个，根据每个统计的数量从大到小排序，然后遍历 300 万条记录，每条记录都被读取并与数组中的最后一条进行比较， 如果小于此值，则继续遍历，否则，数组中的最后一个数据将被消除并添加到当前数据中。最后，当遍历所有数据时，此数组中的 10 就是我们正在寻找的。不

难分析，这样一来，算法最差的时间复杂度是N*K，其中K指的是最大的量。

算法 3：堆

在算法 2 中，我们从 NK 优化了时间复杂度，这不得不说是一个比较大的改进，但是有没有更好的方法呢？

分析时，在算法 2 中，每次比较完成后，所需的复杂度为 K，因为需要将元素插入到线性表中，并使用顺序比较。这里我们注意到数组是有序的，我们可以使用二进制方法在每次查找时找到它，这样就把运算的复杂度降低到logK，但是随之而来的问题是数据被移动了，因为数据被移动的次数。但是，该算法仍然是对算法 2 的改进。

基于上述分析，我们来思考一下是否存在一种数据结构，不仅可以快速找到元素，而且可以快速移动元素。答案是肯定的，这就是堆。

通过堆结构，我们可以查找并调整/移动日志时间量。因此，在这一点上，我们的算法可以改进，以保持 K 大小的小根堆（本例中为 10），然后迭代超过 300 万个根堆，每个根堆都与根元素进行比较。

这

Idea 与上述算法 2 相同，但在算法 3 中，我们使用最小堆的数据结构而不是数组，找到目标元素的时间复杂度从 O（K） 降低到 O（logK）。

这样，利用堆数据结构和算法3，最终时间复杂度降低到N'logK，相比算法2有较大的提升。

总结：

至此，算法就完全结束了，在上述第一步之后，首先使用哈希表来计算每次出现的出现次数，O（N）;然后，第二步是使用堆数据结构找到前 10，N*O（logK）。因此，我们的最终时间复杂度为：O（N） + N*O（logK）。（N为1000万，N'为300万）。如果您有更好的算法，请发表评论。第一部分，完。

第二部分是哈希表算法的详细分析

什么是哈希

Hash，一般翻译为“hash”，也直接音译为“hash”，是通过哈希算法将任意长度的输入（也称为pre-，pre--）转换为固定长度的输出，输出即为哈希值。这种变换是一种压缩映射，即哈希值的空间通常比输入的空间小得多，不同的输入可能会被哈希到相同的输出中，并且无法从哈希值中唯一地确定输入值。简单地说，它是一个函数搜索多少次会被百度记录，它将任何长度的消息压缩为固定长度的消息摘要。

HASH主要应用于信息安全加密算法领域，将一些不同长度的信息转换成杂乱无章的128位编码，这些编码值被称为HASH值。也可以说，哈希就是在数据内容和数据存储地址之间找到一种映射关系。

数组的特点是：易于寻址，难以插入和删除;另一方面，链表的特点是寻址困难，容易插入和删除。那么我们能否将两者的特点结合起来，做出一个易于寻址、易于插入和删除的数据结构呢？答案是肯定的，这就是我们要提到的哈希表，实现哈希表的方法有很多种，我接下来讲解的就是最常用的方法——法，我们可以把它理解为一个“链表数组”，如图所示。

左边显然是一个数组，数组的每个成员都包含一个指向链表头的指针，该链表的标题可能是空的，也可能有许多元素。我们根据元素的一些特性，把元素赋给不同的链表，也根据这些特性找到正确的链表，然后从链表中找到这个元素。

将元素的特征转换为数组下标的方法是哈希。当然，哈希方法不止一种，下面列出了三种比较常用的方法

1.除法、散列

最直观的一个，上图使用了这种哈希方法，公式为：

= % 16

学过编译的人都知道，求模量其实是通过除法运算得到的，所以被称为“除法哈希法”。

2. 平方哈希法

求法是一个非常频繁的操作，乘法比除法更耗时（对于今天的CPU来说下拉优化软件★64xl.com霸屏顶掉=删除效果，下拉关键词排名，我们认为我们感觉不到），所以我们考虑用乘法和位移运算代替除法。公式：

= （ * ） >> 28 （向右移动，除以 2^28。表示法：左移变大，即乘法。右移位变小，被分割。）

如果值均匀分布，这种方法会产生很好的结果，但是我上面绘制的图中元素的值都被计算为 0 - 非常不成功。也许你还有一个问题，如果它很大，*会不会溢出？