在java中处理大型字符串列表

我有一个任务，我必须经过几十亿字符串行并检查每个字符串是否是唯一的。所有的线路本身都不能容纳在PC的RAM内存中。此外，行数可能会大于Integer.MAX_VALUE。在java中处理大型字符串列表

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

所以，这里是我的问题：

我应该用什么来代替String.hashCode()？（返回值是int，但我可能需要很长时间）
处理此大小列表的最快方法/框架是什么？我最需要的是快速检查列表是否包含元素的能力

来源

2011-10-01 Arsen Zahray

为什么不利用数据库的力量？它是否需要在java中严格执行？ –

如果这是一个选项，“数据库”的想法是伟大的。此外，您需要考虑两个“最差情况”：a）每个字符串都是唯一的，b）每个字符串都是相同的。无论您提出哪种解决方案，您是否拥有磁盘/ RAM容量和时间/计算能力来处理这两种情况？ – paulsm4

线数有多大？我知道比MAX_VALUE更大 - 大于32 * MAX_VALUE？大于...？ –

你在想这个问题，这可以通过一个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-02 00:05:43 rwyland

+1我喜欢它！让数据库完成繁重的工作！ – Bohemian

究竟是什么忽必烈汗建议上面。 – paulsm4

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

这里就是我想要解决这个问题的办法：

阅读字符串的文件/流：
1. 阅读每一行
2. 计算的哈希码行
3. 将散列码和字符串写入临时在
  之间
使用体面外部排序程序中使用的哈希码字段作为主排序关键字和所述字符串字段作为二次排序关键字进行排序临时文件与合适的字段分隔符RY文件。
一次读取一行临时文件。如果两个连续的行具有相同的哈希码字段和不同的字符串字段，那么您已经找到了重复的字符串。

注意：这种方法在32位或64位散列码上工作得很好。

来源

2011-10-01 23:36:38

在java中处理大型字符串列表

回答

相关问题