построить уникальный номер для строки в java

Question

У нас есть требование чтения/записи более 10 миллионов строк в файл. Также мы не хотим дубликатов в файле. Поскольку строки будут сбрасываться в файл, как только они будут прочитаны, мы не будем их хранить в памяти.

Мы не можем использовать hashcode из-за столкновений в хеш-коде, из-за которого мы могли бы пропустить строку как дубликат. Два других подхода, которые я нашел в моем поиске:

1.Используйте алгоритм дайджеста сообщений, например MD5, - но это может быть слишком дорогостоящим для расчета и хранения.

2.Используйте алгоритм контрольной суммы. [Я не уверен, что это дает уникальный ключ для строки - может кто-то подтвердит подтверждение)

Есть ли какой-либо другой подход. Спасибо.

Answer 1

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

Другой альтернативой, возможно, с большим объемом памяти, является сохранение уже встречающихся строк в trie (особый тип дерева).

---

Update: Еще одна альтернатива, будет использовать Bloom filter. Это, однако, все еще зависит от хеширования, но может быть скорректировано с учетом сколь угодно малой вероятности столкновений.

Answer 2

Хранение 10 миллионов строк в памяти действительно много, поэтому я понимаю причину, чтобы записать ее в файл немедленно, а не хранить в, например, a TreeSet<String> сначала, но где Вы хотели бы сохранить 10 миллионов уникальных числовых ключей, с которыми вы хотите сравнить? Если вы хотите оставить его уникальным и численным (который имеет много слабой базы/радиуса, чем буквы), вы не можете сделать ключ короче, чем сама строка, так что вы не сохраните какую-либо память. Или, может быть, на самом высоком уровне с сжатием данных, например GZIP, но это только добавит много накладных расходов. MD5 также неуместен, так как две разные строки могут дают тот же хеш.

Я действительно не вижу лучшего решения для этого, кроме использования приличной СУБД (базы данных SQL), в которой вы устанавливаете столбец как UNIQUE и соответствующим образом обрабатываете нарушение ограничения. RDBMS высоко оптимизирована для таких задач.

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

Answer 3

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

Answer 4

Если строки взяты из фиксированного пула возможных строк (N), вы можете использовать минимальное идеальное хеширование для создания массива 0 ... N-1. Нуль в слоте, определяемом идеальной хэш-функцией, означает, что строка пока не видна.

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

Вы можете сделать это как можно эффективнее с помощью частей отображения памяти.

Answer 5

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

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

Альтернативой является последующая обработка файла после его завершения. Команда UNIX вроде довольно хорошо на больших файлах (How could the UNIX sort command sort a very large file?), так что я бы ожидать, что стандарт UNIX командной строки подход к работе разумно:

sort my-file-of-strings.txt | uniq > my-filtered-file-of-strings.txt 

(Обратите внимание, что файлы должны быть отсортированы сначала, прежде чем перейти к Uniq для удаления дубликатов).

Если у вас нет доступных инструментов (или эквивалентов), вы всегда можете попробовать реализовать какой-либо вариант внешнего слияния.

Answer 6

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

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