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

Question

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

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

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

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

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

Answer 1

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

---

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

Answer 2

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

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

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

Answer 3

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

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

Альтернативой является пост-обработайте файл, как только он будет завершен.Команда сортировки UNIX довольно хороша для больших файлов ( Как команда сортировки UNIX может сортировать очень большой файл? ), поэтому я ожидаю, что стандартный подход командной строки UNIX будет работать разумно:

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

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

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