Самый быстрый способ проверить, содержит ли Список <Строка> уникальную строку

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

Однако для строк размером 1M производительность hashSet все еще может быть неоптимальной. Большое количество промахов в кэше замедлит поиск набора. Если все строки одинаково вероятны, это неизбежно. Однако, если одни строки запрашиваются чаще, чем другие, то вы можете поместить общие строки в небольшой hashSet и сначала проверить это, прежде чем проверять более крупный набор. Размер небольшого хэш-набора должен соответствовать размеру кеш-памяти (например, максимум несколько сотен КБ). В этом случае обращения к маленькому хеш-набору будут очень быстрыми, тогда как обращения к большему хэш-набору будут выполняться со скоростью, ограниченной пропускной способностью памяти.

Прежде чем идти дальше, примите во внимание следующее: почему вы беспокоитесь о производительности? Как часто вызывается эта проверка?

Что касается возможных решений:

• Если список уже отсортирован, вы можете использовать java.util.Collections.binarySearch , который предлагает те же характеристики производительности, что и java.util.TreeSet .

• В противном случае вы можете использовать java.util.HashSet , который является характеристикой производительности O (1). Обратите внимание, что вычисление хэш-кода для строки, которая еще не рассчитана, представляет собой операцию O (m) с m = string.length () . Также имейте в виду, что хэш-таблицы работают хорошо только до тех пор, пока не достигнут заданного коэффициента загрузки, то есть хэш-таблицы будут использовать больше памяти, чем простые списки. Коэффициент загрузки по умолчанию, используемый HashSet, равен 0,75, что означает, что внутри HashSet для объектов 1e6 будет использоваться массив с записями 1,3e6.

• Если HashSet не работает для вас (например, из-за большого количества хеш-коллизий, из-за нехватки памяти или из-за большого количества вставок), рассмотрите возможность использования Trie . Поиск в Trie имеет сложность наихудшего случая O (m), где m = string.length () . У Trie есть также некоторые дополнительные преимущества, которые могут быть вам полезны: например, он может дать вам наиболее подходящий для строки поиска. Но имейте в виду, что лучший код - это отсутствие кода, поэтому используйте собственную реализацию Trie только в том случае, если преимущества перевешивают затраты.

• Рассмотрите возможность использования базы данных, если вам нужны более сложные запросы, например соответствует подстроке или регулярному выражению.

Не только для String, вы можете использовать Set для любого случая, когда вам нужны уникальные элементы.

Если тип элементов - примитив или обертка, вы можете не беспокоиться. Но если это класс, вы должны переопределить два метода:

1. hashCode()
2. equals()

Я бы использовал Set , в большинстве случаев HashSet подойдет.

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

С таким огромным количеством строк я сразу думаю о Trie . Он лучше работает с более ограниченным набором символов (например, букв) и / или когда начало многих строк перекрывается.