Использовать хеш-коды для сравнения двух больших строк в Java?

Question

У меня есть два файла, из которых я читаю, у меня есть несколько строк, найденных в обоих файлах. Мне нужно написать функцию, которая будет определять, какие строки находятся в обоих файлах. Теперь я написал для этого код, который будет читать содержимое файла 1 и помещать записи в массив, затем читать файл 2, для каждой строки в файле2. Я проверяю, найден ли он в массиве, если он найден, я знаю это. повторяющаяся строка Теперь моя проблема в том, что я сохраняю полные строки в массиве, мне интересно, можно ли преобразовать прочитанную мной строку в хеш-код, затем я сохраню этот хеш-код в массиве, после чего я сравню этот хеш-код с хэш-код для строки, которую я читаю из file2, это лучший подход для экономии памяти?

Answer 1

Если два хеш-кода разные, строки разные. Если два хеш-кода совпадают, строки могут совпадать или не совпадать.

Если вы храните файлы в HashSet , поиск, существует ли строка, является очень быстрой операцией. HashSet использует внутренний хеш-код.

Answer 2

Это подход, который сохранит память, но не гарантирует совпадение.Определение хеш-кодов говорит, что они не будут уникальными.Если вы хотите сохранить уменьшенную версию строки, вам следует сохранить дайджест строки, такой как MD5.

Вот как вы получаете дайджест.

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
...
MessageDigest md = MessageDigest.getInstance("MD5");
byte[] digestBytes = md.digest(string.getBytes());

MD5 имеет длину 16 байт.так что это сэкономит вам память только в том случае, если ваши строки значительно длиннее, чем 8 символов (по 2 байта на символ).

Но если ваши файлы слишком велики, вам действительно не нужно беспокоиться о памяти иHashSet ответов дадут вам лучшие результаты.

Редактировать:

MD5 создает коллизии, но не в реальных условиях.Он не должен использоваться в качестве криптографического хэш-кода, но в этом случае он будет работать нормально.Существуют и другие функции дайджеста, такие как SHA256, у которых меньше шансов на столкновение, но размер их дайджеста больше.

Answer 3

Вы ищете HashSet<String> - он идеально подойдет вашим потребностям!

---

Пример:

Set<String> file1       = ....// read line by line from file1
ArrayList<String> file2 = ... //     -     "      -     file2

for (String line : file1)
    if (file2.contains(line))
        duplicate found

Answer 4

Если вас беспокоят проблемы с пространством / памятью, преобразуйте строки в base36 , прежде чем сохранять их в HashSet, как уже предлагалось несколькими людьми.Для стандартизации я предлагаю убрать все пробелы и знаки препинания из строки и преобразовать их в нижний регистр, прежде чем создавать эквивалент base36.Затем в HashSet вы получите HashSet<String>, где String содержит кодировку base36 строки вместо всей строки.

Answer 5

Вы не упомянули ограничение размера файлов, поэтому я предполагаю, что они могут быть достаточно большими, чтобы было невозможно сохранить все строки в памяти.

Итак, я бы предложил следующий подход:

1. Объедините два файла, чтобы создать один большой файл.

2. Используйте «внешний» алгоритм сортировки, например, http://code.google.com/p/externalsortinginjava/ для сортировки большого файла.

3. Считайте отсортированный файл, по одной строке за раз, и сравнивайте каждую строку со строкой перед ней (сохраняя в памяти только две строки - текущую и предыдущую строку). Если текущая и предыдущая строки совпадают, то эта строка встречается в обоих исходных файлах.

«Внешняя сортировка» часто была необходима в первые дни вычислений, когда было доступно гораздо меньше памяти. Одним из способов сделать это была / является сортировка слиянием, которая при использовании с лентами (помните ленты?) Известна как «сортировка на ленте». Да, я стар :-)

Answer 6

Если вы действительно беспокоитесь о памяти и хотите иметь более низкую производительность для обеспечения безопасности памяти, вы можете сделать следующее:

1. Создать HashSet значений хеш-функции для файла 1.
2. Создать HashSet значений хеш-функции из файла 2, которые соответствуют значению хеш-функции из файла 1.
3. Создайте HashSet строк из файла 1, значения хеша которых находятся в HashSet 2.
4. Проверка каждой строки из файла 2 относительно HashSet 3.