arrays - 确定一个非常大的数组是否包含重复项

Question

对于一个正常大小的数组，我们可以通过排序或者使用hashset等方式来判断它是否包含重复项。但是如果我们有一个非常大的数组，比如长度是 100 亿，我们如何确定它是否包含重复项？

跟进:如果我们知道这个大数组中一定存在一个重复项，我们如何确定它是哪一个？

我的想法是使用排序，但如果有更好的方法来处理这些情况，我不会这样做。

Answer 1

首先，使用如下代码将您的数据存储到 K 个存储桶中。

files = array of K file handles
for each d in data {
    write d to files[hash(d) % K]
}
close each file

如果您选择的 K 足够大，每个桶都可以轻松放入 RAM 中。确保选择一个好的哈希函数，否则桶将不平衡。实际代码还取决于您使用的存储系统。例如，如果您使用的是普通硬盘，寻道的成本很高，需要注意避免磁盘抖动。一种方法是读入适合 RAM 的尽可能多的数据，然后对其进行迭代 K 次，每次遍历仅附加到一个输出文件。

接下来，简单地依次遍历每个桶，看看它是否包含任何重复项。您可以使用任何有效的算法来检测重复项。

for each f in the K files {
    data = read f into RAM
    detect duplicates in data
}

另一种解决方案是使用 map-reduce framework .

map 步骤将如下所示:

map(value) {
    emit(key=hash(value), value=value)
}

减少步骤将如下所示:

reduce(key, values) {
    if there's a duplicate in values {
        emit the duplicate value.
    }
}

请注意，每个 reducer 只会在存在重复值或存在哈希冲突时看到多个值。如果您选择了一个合理的哈希函数，后者将极为罕见。