3

我有一个哈希图，其中包含约 8 亿个条目（字符串）。它实际上被序列化为一个我已经进入哈希映射的文件。

现在我有另一个巨大的字符串列表，大小约为 3500 万。我需要一个一个地读取这 3500 万个字符串，并以一种特定的方式对它们进行格式化，这种方式本身就是一个单独的方法（这是一个非常轻量级的处理）。

然后我需要检查对列表中的一个字符串进行格式化的结果是否已经存在于 hashMap 中。

在 Java 中执行此操作的最有效方法是什么？

4

3 回答 3

2

您可以尝试使用 Bloom 过滤器

一种节省空间的概率数据结构，用于测试元素是否是集合的成员。假阳性检索结果是可能的，但假阴性是不可能的；即查询返回“在集合内（可能是错误的）”或“绝对不在集合内”。

（引自维基百科）

Google Guava在 java 中提供了一个实现。

于 2013-03-19T15:04:21.820 回答
1

如果您的大型数据集已经在您正在从磁盘反序列化的哈希表中并且您无法更改它，那么我怀疑您是否会比仅仅做显而易见的事情并直接检查哈希表做得更好。任何将大型哈希表转换为另一种格式的方法都可能比按原样一次在表上进行所有查找更昂贵。（约 3500 万次恒定时间操作与至少 8 亿次 + 3500 万次恒定时间操作相比，另一个常数可能不会好多少，可能更多取决于您要使用的新格式。）

如果存储大型数据集的表已经是线程安全的，并且运行程序的计算机具有多个内核，则可以通过为每个内核运行单个查找线程来获得加速，但即使这样也可能不会加快速度由于协调开销以及每个单独的操作都非常便宜的事实，up（或者实际上可能会减慢速度）。

您是否有能力改变大型数据集的准备方式？例如，与其把它写成一个散列集，你能把它写成别的东西吗？你能改变默认的散列函数吗？你知道你正在散列的字符串的属性，这些属性可以用来构建一个更便宜的散列函数吗？它们会在输入文件中以特定顺序出现吗？这类事情可能会用于进行更快的查找，但是相对于简单方法的显着加速可能将依赖于更多地了解您的问题的具体细节。

于 2013-03-19T19:57:04.157 回答
1

如果您必须将其放在内存中，我将从改进散列函数的开发方式开始。可以在dzone的文章中找到帮助解决此问题的好资源

如果您不关心维护排序结构时可能引入的延迟，那么更进一步的是使用 Map 接口的另一个实现

于 2013-03-19T15:08:53.640 回答