Эффективный поиск строк в Java

Question

Я работаю с двумя большими списками данных, и мне нужно эффективно проверять совпадения между ними. Это сценарий:

• Чтение из файла построчно (в этом файле 1 миллион строк)
• Для каждой строки проверьте в ArrayList строк, имеет ли она совпадение (этот ArrayList также содержит огромное количество элементов)
• Если совпадение найдено, замените строку из файла новым значением

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

Спасибо за любую помощь!

ОБНОВЛЕНИЕ Стоит отметить, я не говорю, что мне нужно использовать ArrayList, это то, что я использовал для тестирования. Любые предложения более эффективных коллекций будут приветствоваться.

Answer 1

Вы должны использовать HashMap, это примерно O(1), или если в ваших строках много коллизий, чем вам нужно использовать TreeSet O(logN) или фильтр Блума.

Answer 2

Вы можете рассмотреть чтение файла частично различными потоками. Подобная проблема обсуждается здесь.

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

Answer 3

Без более подробной информации (такой как природа клавиш) трудно быть уверенным, но использование фильтра Блума может оказаться полезным для минимизации количества выполненных вами действий. check within an ArrayList of strings whether it has a match,

Очевидно, что это не очень поможет, если список поиска меняется со временем.

Вы должны использовать фильтр Блума, чтобы выполнить предварительную проверку перед поиском в списке, потому что он может очень быстро дать вам прямой no ответьте, если ключ не существует в списке. Вам все равно придется искать в вашем списке, если фильтр Bloom сообщает maybe,