大数据处理之哈希表（二）--出现频率最多的top xxx 位_哈希表存每个字符出现的个数如何对次数最大的

作者：神奇cpp | 2024-07-15 16:10:38

踩

哈希表存每个字符出现的个数如何对次数最大的

上篇文章中只是求了出现频次最高的值，可是大数据处理往往需求的是top 10 ，top 100或者某一段区间的数据。

显然只定义一个Hash a是不能放下的。如果是求出现频次top100呢？最起码定义 Hash arr[100]吧。

比如拿计数器10000长度和数据范围为32767来说。

我们最少要分4次，分别是数据取余4后 0 1 2 3的四种情况

第一次余数为0，即4的倍数这一组，我们是不是要先算出这组的top100，然后再和下组余数为1的top100相比，

这时候你应该想起的什么吧。这组的top100是有序的，而下组的top100也是有序的，两个有序数列合成一个有序数列，归并算法应该为首选。

上面说的只是如何把各分组top100变成整个top100。

但并没有说每组的top100该如何选择。每组的top100都要从10000万个计数器数据里提取出来，我们学习过的众多内部排序谁最适合做这种选出前几位的事情？印象中最快的归并或快排吗？显然不是，他俩都是整体处理全部数据，而我们的需求是什么？只要前面的100个最大的，其他9900个数据的死活我们不管。

是不是选择排序很适合？每次选出最大的或最小的？而选择排序里的堆排序是不是对简单选择排序的进一步升级？因此我们就使用堆排序来做这件事。

可是。如果使用堆排序，还能使用整型数组的计数器吗？我们知道我们是靠计数器的下标和原始数据确立某种关系的。这种关系就是i*r+j。可是堆排序的堆调整把计数器的计数次数调整了，下标却不会动。

具体来说就是如果使用int数组计数器，10000个计数器元素排下来，最后100个数据的确是最大的。可是这100个数据的下标原先对应的数据我们根本找不到了，因为我们之前是靠下标确定数据多少的。如果按照原先代码运行。得到的结果始终会是出现频次最高的100数据是该组最大的100个数据。这显然是错误的。

因此为了解决这种问题，我们必须再添加一个元素保存原始数据是多少。那么计数器的类型是不是可以更改为

Hash count[10000]; 既记录的数据的出现次数。也记录了数据是多少。使用堆排序后。count最后100位的

count[n].num 可以获取到原先的数据。

定义下代码头

这个全局变量Hash a[100]数组就是我们最终要的top100所在地。

思路说完了，那么该从何入手呢。

我们先开始修改堆排序把，修改有2个内容，一是让它适应hash，二是只让它算出100位后停止。

不清楚堆排序的可以看看堆排序。在此不多赘述

heapsort里加了第三个参数n。这个n就代表要求出n个最大数放在传入的arr数组中的后100位。

每组的top100出来后，并不是真正的top100，要与之前确定好的top100归并。

归并算法老生常谈了。无需多述。

然后是主要代码，（一些具体说明在图中）

结果如下：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/神奇cpp/article/detail/830129

大数据处理之哈希表（二）--出现频率最多的top xxx 位_哈希表存每个字符出现的个数 如何对次数最大的