7

我有一个任务，我必须遍历数十亿行并检查每一个是否都是唯一的。PC 的 RAM 内存中不能容纳所有的行本身。此外，行数可能大于 Integer.MAX_VALUE。

我假设处理大量数据的最佳方法是将每个字符串的哈希码放入某种哈希表中。

所以，这是我的问题：

  1. 我应该用什么代替String.hashCode()？（返回值为int，但我可能需要long）
  2. 处理这种大小的列表的最快方式/框架是什么？我最需要的是能够快速检查列表是否包含元素
4

2 回答 2

4

你想多了这个问题，这一切都可以通过一个 MySQL 表非常简单地完成，该表将数据保存到磁盘而不是将所有内容保存在内存中。这么多数据从来都不是由独立应用程序有效处理的。

CREATE TABLE TONS_OF_STRINGS
(
  unique_string varchar(255) NOT NULL,
  UNIQUE (unique_string)
)

只需遍历值（假设此处为逗号分隔列表）并尝试插入每个标记。每个失败的令牌都是重复的。

public static void main(args) {
  Connection con = DriverManager.getConnection("jdbc:mysql://localhost/database","username","password");
  FileReader file = new FileReader("SomeGiantFile.csv");
  Scanner scan = new Scanner(file);
  scan.useDelimiter(",");
  String token;
  while ( scan.hasNext() ) {
    token = scan.next();
    try {
      PreparedStatement ps = con.prepareStatement("Insert into TONS_OF_STRING (UNIQUE_STRING) values (?)");
      ps.setString(1, token);
      ps.executeUpdate();
    } catch (SQLException e) {
      System.out.println("Found duplicate: " + token );
    }
  }
  con.close();
  System.out.println("Well that was easy, I'm all done!");
  return 0;
}

完成后不要忘记清除表格，这是很多数据。

于 2011-10-02T00:05:43.177 回答
3

仅仅存储 32 位或 64 位哈希码是不够的，因为两个不同的字符串（几十亿个）很容易具有相同的哈希码。一旦你有两个具有相同哈希码的字符串，你需要比较实际的字符串，看看它们是否真的相等。

这是我解决这个问题的方法：

  1. 读取文件/字符串流：

    1. 阅读每一行

    2. 计算行的哈希码

    3. 将哈希码和字符串写入临时文件，中间有合适的字段分隔符

  2. 使用像样的外部排序程序对临时文件进行排序，使用哈希码字段作为主排序键，字符串字段作为辅助排序键。

  3. 一次读取一行临时文件。如果两个连续的行具有相同的哈希码字段和不同的字符串字段，那么您发现了一个重复的字符串。

注意：这种方法同样适用于 32 位或 64 位哈希码。

于 2011-10-01T23:36:38.960 回答