Xử lý các danh sách Chuỗi lớn trong java

Question

Tôi có một nhiệm vụ, nơi tôi đã phải trải qua vài tỷ dòng chuỗi và kiểm tra xem mỗi chuỗi có duy nhất hay không. Tất cả các dòng chính họ không thể được cung cấp trong bộ nhớ RAM của PC. Ngoài ra, số lượng dòng có thể lớn hơn Integer.MAX_VALUE.

Tôi giả định rằng cách tốt nhất để xử lý lượng dữ liệu này là đặt mã băm của từng chuỗi vào một số loại HashTable.

Vì vậy, đây là những câu hỏi của tôi:

1. Tôi nên sử dụng thay vì String.hashCode()? (giá trị trả về là int, nhưng có lẽ tôi sẽ cần lâu)
2. Cách/khung làm việc nhanh nhất để làm việc với danh sách kích thước này là gì? Những gì tôi chủ yếu cần là khả năng nhanh chóng kiểm tra xem danh sách có chứa phần tử hay không

Answer 1

Bạn đang suy nghĩ về vấn đề, tất cả điều này có thể được thực hiện rất đơn giản với một bảng MySQL lưu dữ liệu vào đĩa thay vì giữ mọi thứ trong bộ nhớ. Dữ liệu đó không bao giờ được xử lý một cách hiệu quả bởi một ứng dụng độc lập.

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

Chỉ cần lặp qua các giá trị (giả sử danh sách được phân tách bằng dấu phẩy ở đây) và cố gắng chèn từng mã thông báo. Mỗi mã thông báo không thành công là một bản sao.

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; 
} 

Đừng quên xóa bảng khi bạn làm xong, có rất nhiều dữ liệu.

Answer 2

Không đủ để lưu trữ mã băm 32 hoặc 64 bit vì hai chuỗi riêng biệt (trong số ít tỷ) có thể dễ dàng có cùng một hashcode. Khi bạn có hai chuỗi với cùng một mã băm, bạn cần phải so sánh các chuỗi thực tế để xem chúng có thực sự bằng nhau hay không.

Dưới đây là cách tôi muốn giải quyết vấn đề này:

1. Đọc tập tin/dòng chuỗi:

   1. đọc mỗi dòng

   2. Tính mã băm cho dòng

   3. Viết mã băm và chuỗi vào một thời gian tập tin ry với một tách lĩnh vực phù hợp ở giữa

2. Sử dụng một chương trình loại bên ngoài phong nha để sắp xếp các tập tin tạm thời sử dụng các lĩnh vực hashcode là chìa khóa sắp xếp đầu tiên và lĩnh vực chuỗi như là chìa khóa loại thứ yếu.

3. Đọc từng dòng một tập tin tạm thời. Nếu hai dòng kế tiếp có cùng trường hashcode và các trường chuỗi khác nhau thì bạn đã tìm thấy một chuỗi trùng lặp.

Lưu ý: Cách tiếp cận này sẽ hoạt động tốt như nhau với mã băm 32 hoặc 64 bit.