создайте уникальное число для строки в Java
У нас есть требование чтения/записи больше чем 10 миллионов строк в файл. Также мы не хотим дубликаты в файле. Так как строки были бы сброшены в файл, как только они читаются, мы не поддерживаем его в памяти.
Мы не можем использовать хэш-код из-за коллизий в хэш-коде, из-за которого мы могли бы пропустить строку как дубликат. Два других подхода я нашел в своем поиске с помощью Google:
1. Используйте алгоритм выборки сообщений как MD5 - но это могло бы быть слишком дорогостоящим, чтобы вычислить и сохранить.
2. Используйте алгоритм контрольной суммы. [я не уверен, производит ли это уникальный ключ для строки - может кто-то подтверждать]
Есть ли любой другой avaiable подход.Спасибо.
6 ответов
Если вас устраивает микроскопический риск коллизий, вы можете использовать некоторую хеш-функцию, такую как MD5, как вы предлагаете, и полагаться на хеши.
Другой альтернативой, возможно, с большим объемом памяти, является сохранение уже встреченных строк в дереве (особом типе дерева).
Обновление: Еще одна альтернатива - использовать фильтр Блума . Однако это по-прежнему зависит от хеширования, но может быть настроено так, чтобы вероятность коллизий была сколь угодно малой.
Если строки взяты из фиксированного пула возможных строк (N), то вы можете использовать минимальное идеальное хеширование для создания массива 0 ... N-1. Ноль в слоте, определяемом идеальной хеш-функцией, означает, что строка еще не была видна.
В противном случае, единственное эффективное правильное средство за пределами большого количества памяти и предложенных до сих пор решений - это перечитать файл перед принятием решения о записи в него строки.
Вы можете сделать это максимально эффективно, отображая части файла в память.
Хранить 10 миллионов строк в памяти действительно много, поэтому я понимаю причину, по которой нужно сразу записывать их в файл, а не хранить, например, в a TreeSet сначала, но где вы хотите сохранить 10 миллионов уникальных цифровых ключей, с которыми вы хотите сравнить? Если вы хотите сохранить его уникальным и числовым (который имеет гораздо меньшее основание / основание системы счисления, чем буквы), вы не можете сделать ключ короче, чем сама строка уже есть, поэтому вы не сохранит память. Или, может быть, в лучшем случае со сжатием данных, например GZIP, но это только добавит много накладных расходов. MD5 также не подходит, поскольку две разные строки могут давать один и тот же хэш.
Я действительно не вижу лучшего решения для этого, чем использование приличной СУБД (базы данных SQL), в которой вы устанавливаете столбец как UNIQUE и соответствующим образом обрабатываете нарушение ограничения. РСУБД оптимизирована для такого рода задач.
Если вы действительно не можете рассматривать базу данных, вам нужно перечитать файл для любой существующей записи перед записью / сбросом. Может быть, не очень быстро, но зато эффективно с памятью.
Надежно удалить дубликаты так же сложно, как отсортировать файл. Как указывает другой ответ, нет гарантированного способа точного обнаружения дубликатов без сохранения полной копии каждой строки в памяти, что, похоже, именно то, чего вы пытаетесь избежать.
Вы можете сохранить индекс хэш-кодов в памяти или на диске и использовать их для извлечения фактических строк из файлового хранилища для сравнения, но это по существу дублирует то, что база данных может сделать для вас.
Альтернативой является пост-обработка файла после его завершения. Команда сортировки UNIX довольно хороша для больших файлов ( Как команда сортировки UNIX может сортировать очень большой файл? ), поэтому я ожидаю, что стандартный подход командной строки UNIX будет работать разумно:
sort my-file-of-strings.txt | uniq > my-filtered-file-of-strings.txt
(Обратите внимание, что файлы необходимо сначала отсортировать, прежде чем переходить к uniq для удаления дубликатов).
Если у вас нет этих инструментов (или эквивалентов), вы всегда можете попробовать реализовать какой-либо вариант внешней сортировки слиянием самостоятельно.
Я действительно думаю, что лучшим решением является - как уже предлагал кто-то другой - использование базы данных.
Если по какой-то причине вы не можете использовать базу данных, вы все равно можете использовать хэш-код. Конечно, будут столкновения. Просто добавьте код, чтобы при обнаружении дублирующегося хэш-кода ваша программа проверяла файл, чтобы определить, является ли он подлинным дубликатом или столкновением.
Невозможно создать функцию, которая создала бы уникальный ключ для строки, которая короче этой строки.
Существуют структуры данных, которые могут решить вашу задачу. B-дерево может подойти, если у вас достаточно большие данные. В зависимости от характера вашего вклада могут быть более эффективные способы.