算法学习：从头到尾彻底解析Hash-表算法资源-CSDN文库

版权申诉

哈希算法

176 浏览量 2023-09-20 19:29:57 上传评论收藏 118KB DOCX 举报

资源推荐

资源详情

资源评论

从头到尾彻底解析 Hash 表算法

说明：本文分为三部分内容，

第一部分为一道百度面试题 Top K 算法的详解；第二部分为关于 Hash 表算法的详细阐

述；第三部分为打造一个最快的 Hash 表算法。

第一部分：Top K 算法详解

问题描述

百度面试题：

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的

长度为1-255字节。

假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除

去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越

热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

必备知识：

什么是哈希表？

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据

结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希表的做法其实很简单，就是把 Key 通过一个固定的算法函数既所谓的哈希函数转

换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将

value 存储在以该数字为下标的数组空间里。

而当使用哈希表进行查询的时候，就是再次使用哈希函数将 key 转换为对应的数组下

标，并定位到该空间获取 value，如此一来，就可以充分利用到数组的定位性能进行数据定

位（文章第二、三部分，会针对 Hash 表详细阐述）。

问题解析：

要统计最热门查询，首先就是要统计每个 Query 出现的次数，然后根据统计结果，找出

Top 10。所以我们可以基于这个思路分两步来设计该算法。

即，此问题的解决分为以下俩个步骤：

第一步：Query 统计

Query 统计有以下俩个方法，可供选择：

1、直接排序法

首先我们最先想到的的算法就是排序了，首先对这个日志里面的所有 Query 都进行排

序，然后再遍历排好序的 Query，统计每个 Query 出现的次数了。

但是题目中有明确要求，那就是内存不能超过1G，一千万条记录，每条记录是255Byte，

很显然要占据2.375G 内存，这个条件就不满足要求了。

让我们回忆一下数据结构课程上的内容，当数据量比较大而且内存无法装下的时候，我

们可以采用外排序的方法来进行排序，这里我们可以采用归并排序，因为归并排序有一个比

较好的时间复杂度 O(NlgN)。

排完序之后我们再对已经有序的 Query 文件进行遍历，统计每个 Query 出现的次数，再

次写入文件中。

综合分析一下，排序的时间复杂度是 O(NlgN)，而遍历的时间复杂度是 O(N)，因此该

算法的总体时间复杂度就是 O(N+NlgN)=O（NlgN）。

2、Hash Table 法

在第1个方法中，我们采用了排序的办法来统计每个 Query 出现的次数，时间复杂度是

NlgN，那么能不能有更好的方法来存储，而时间复杂度更低呢？

题目中说明了，虽然有一千万个 Query，但是由于重复度比较高，因此事实上只有300

万的 Query，每个 Query255Byte，因此我们可以考虑把他们都放进内存中去，而现在只是需

要一个合适的数据结构，在这里，Hash Table 绝对是我们优先的选择，因为 Hash Table 的查

询速度非常的快，几乎是 O(1)的时间复杂度。

那么，我们的算法就有了：维护一个 Key 为 Query 字串，Value 为该 Query 出现次数的

HashTable，每次读取一个 Query，如果该字串不在 Table 中，那么加入该字串，并且将 Value

值设为1；如果该字串在 Table 中，那么将该字串的计数加一即可。最终我们在 O(N)的时间

复杂度内完成了对该海量数据的处理。

本方法相比算法1：在时间复杂度上提高了一个数量级，为 O（N ），但不仅仅是时间复

杂度上的优化，该方法只需要 IO 数据文件一次，而算法1的 IO 次数较多的，因此该算法2

比算法1在工程上有更好的可操作性。

第二步：找出 Top 10

算法一：普通排序

我想对于排序算法大家都已经不陌生了，这里不在赘述，我们要注意的是排序算法的时

间复杂度是 NlgN，在本题目中，三百万条记录，用1G 内存是可以存下的。

算法二：部分排序

题目要求是求出 Top 10，因此我们没有必要对所有的 Query 都进行排序，我们只需要维

护一个10个大小的数组，初始化放入10个 Query，按照每个 Query

的统计次数由大到小排序

，

然后遍历这300万条记录，每读一条记录就和数组最后一个 Query 对比，如果小于这个 Query，

那么继续遍历，否则，将数组中最后一条数据淘汰，加入当前的 Query。最后当所有的数据

都遍历完毕之后，那么这个数组中的10个 Query 便是我们要找的 Top10了。

不难分析出，这样，算法的最坏时间复杂度是 N*K，其中 K 是指 top 多少。

算法三：堆

在算法二中，我们已经将时间复杂度由 NlogN 优化到 NK，不得不说这是一个比较大的

改进了，可是有没有更好的办法呢？

分析一下，在算法二中，每次比较完成之后，需要的操作复杂度都是

K，因为要把元素插

入到一个线性表之中，而且采用的是顺序比较。这里我们注意一下，该数组是有序的，一次

我们每次查找的时候可以采用二分的方法查找，这样操作的复杂度就降到了

logK，可是

，

随

之而来的问题就是数据移动，因为移动数据次数增多了。不过，这个算法还是比算法二有了改

进。

基于以上的分析，我们想想，有没有一种既能快速查找，又能快速移动元素的数据结构

呢？回答是肯定的，那就是堆。

借助堆结构，我们可以在 log 量级的时间内查找和调整/移动。因此到这里，我们的算

法可以改进为这样，维护一个 K(该题目中是10)大小的小根堆，然后遍历300万的 Query，分

别和根元素进行对比。

思想与上述算法二一致，只是算法在算法三，我们采用了最小堆这种数据结构代替数组

，

把查

找目标元素的时间复杂度有

O（K）降到了

O（logK）。

那么这样，采用堆数据结构，算法三，最终的时间复杂度就降到了 N‘logK，和算法二

相比，又有了比较大的改进。

总结：

至此，算法就完全结束了，经过上述第一步、先用 Hash

表统计每个 Query

出现的次数

，

O（N）；然后第二步、采用堆数据结构找出 Top 10，N*O（logK）。所以，我们最终的时间

复杂度是：O（N） + N'*O（logK）。（N 为1000万，N’为300万）。如果各位有什么更好的

算法，欢迎留言评论。第一部分，完。

第二部分、Hash 表算法的详细解析

剩余13页未读，继续阅读

评论收藏

内容反馈

版权申诉

小小哭包

粉丝: 1899
资源: 3860

算法学习：从头到尾彻底解析Hash-表算法

从头到尾彻底解析Hash_表算法

从头到尾彻底解析hash

从头到尾彻底解析Hash_表算法.zip_K._againstzvw_hash

官网下载：Windows-KB841290-x86-ENU.zip

shiro-crypto-hash-1.4.0-API文档-中文版.zip

shiro-crypto-hash-1.4.0-API文档-中英对照版.zip

python_geohash-0.8.5-cp39-cp39-win_amd64

从头到尾彻底理解KMP算法

从头到尾彻底理解傅里叶变换算法 上

从头到尾彻底理解傅里叶变换算法、上

从头到尾彻底理解傅里叶变换算法

从头到尾彻底理解傅里叶变换算法、下

实验五：安全Hash算法SHA-1的实现

python_geohash-0.8.5-cp37-cp37m-win_amd64

java源码：哈希计算工具 java-hash.7z

最快的排序算法 计算机最快的算法-史上14个最快速算法：孩子的计算能力爆表！大脑堪比计算机！...，排序算法数据结构

nginx_upstream_hash-0.3.1.tar.gz

Java语言Consistent Hash算法学习笔记（代码示例）

实验五：安全Hash算法SHA-1的实现.doc

counter-hash-js:counter-hash-js npm 库的主页

hashcat + john-1.9.0-jumbo-1-win64

算法导论 答案 （英文版）

最快的排序算法 最快的内容查找算法-----暴雪的Hash算法，排序算法数据结构

Java第十五届蓝桥杯大赛软件JavaB组真题

SwitchHosts

安卓期末大作业（AndroidStudio开发），垃圾分类助手app，分为前台后台，代码有注释，均能正常运行

Notepad++安装包

最新资源

从头到尾彻底理解傅里叶变换算法上

最快的排序算法计算机最快的算法-史上14个最快速算法：孩子的计算能力爆表！大脑堪比计算机！...，排序算法数据结构

算法导论答案（英文版）

最快的排序算法最快的内容查找算法-----暴雪的Hash算法，排序算法数据结构