大数据算法＜一＞：hash函数分流 +文件建堆实现_hash分流

今天看左神讲的这个题目

首先考虑如何计数，也就是每一个url出现了多少次呢？

1. 使用布隆过滤。（还没学）
2. 使用hash函数进行分流，将相同的hash值取模的url放到同一个文件中。
   1. 每一个url对应一个字符串hash。
   2. 这个字符串hash对一个数取模
   3. 那么这样同一种url就会进入一个文件中去。

第二个问题,统计前100:

1. 先把100亿条数据使用hash函数进行分流，划分成不同文件。
2. 然后对于每一个文件建堆：
   1. 进行一个hashMap的统计，url作为key, 词频作为value。
   2. 按照value进行排序。
   3. 把排好的内容放入磁盘中。
3. 最后进行统计：
   1. 首先进行建堆：从每个文件中读取第一条数据，然后将他们从文件中删除，把<文件名，文件数据> 存入大根堆中。
   2. 然后在cnt < N 且 堆不空时：
      1. 堆顶加入答案。
      2. 堆顶对应的文件，如果不空，读取第一条数据加入堆，并且删除第一条数据。
   3. 知道满足统计了N条，或者堆为空(没有这么多种的url)的时候返回统计的答案。

这里记录下一些其他问题

1. 文件统计之后是放在磁盘中，还是存储在内存中呢？
   • 放在磁盘中，因为建立就算统计完成之后，url的数量依旧很多，可能到达10亿条。
2. 如何更少的读取磁盘？
   • 败者树(还没学)

详细代码请转到

这里写一下测试类与结果

package leetcode.categories.bigData;

import javafx.util.Pair;

import java.util.*;

public class Main {

    public static void main(String[] args) {

        // 划分文件，得到划分好的文件
        Division div = new Division();
        HashMap<String, List<String>>files = div.divInM();

        // 为每个文件建立堆
        BigHeap bg = new BigHeap(files);
        // 在内存中建立每一个文件的heap
        HashMap<String, Queue> mp = new HashMap<>();
        for (String file : files.keySet()) {
            Queue que = bg.build(file);
            mp.put(file, que);
        }
        // 进行统计
        CountTopN cnt = new CountTopN(3);
        List<Pair<String, Integer>> ans = cnt.workInMemory(mp);
        for (Pair<String, Integer> p : ans) {
            System.out.println(p.getKey() + " " + p.getValue());
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

获取前三名