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

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

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

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

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

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

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

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

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

Я бы использовать Set в большинстве случаев HashSet это нормально.

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

выполнив упражнение вот мои результаты.

private static final int TEST_CYCLES = 4000;
private static final long RAND_ELEMENT_COUNT = 1000000l;
private static final int RAND_STR_LEN = 20;
//Mean time
/*
Array list:18.55425
Array list not contains:17.113
Hash set:5.0E-4
Hash set not contains:7.5E-4
*/

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

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

возможно, это не требуется для вашего случая, но я думаю, что полезно знать, что есть некоторые пространственно-эффективные вероятностные алгоритмы. Например Bloom filter.

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

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

1. hashCode ()
2. равна()

иногда вы хотите проверить, находится ли объект в списке/наборе, и в то же время вы хотите, чтобы список/набор был упорядочен. Если вы хотите также легко извлекать объекты без использования перечисления или итератора, вы можете рассмотреть возможность использования обоих ArrayList<String> и HashMap<String, Integer>. Список подкрепляется картой.

пример из какой-то работы, которую я недавно сделал:

public class NodeKey<K> implements Serializable, Cloneable{
private static final long serialVersionUID = -634779076519943311L;

private NodeKey<K> parent;
private List<K> children = new ArrayList<K>();
private Map<K, Integer> childrenToListMap = new HashMap<K, Integer>();

public NodeKey() {}

public NodeKey(Collection<? extends K> c){
    List<K> childHierarchy = new ArrayList<K>(c);
    K childLevel0 = childHierarchy.remove(0);

    if(!childrenToListMap.containsKey(childLevel0)){
        children.add(childLevel0);
        childrenToListMap.put(childLevel0, children.size()-1);
    }

    ...

в этом случае, параметр K будет String для вас. Карта (childrenToMapList) магазинов Strings вставить в список (children) как ключ, так и Значения карты являются позицией индекса в списке.

причина для списка и карты заключается в том, что вы можете получить индексированные значения списка, не выполняя итерацию над HashSet<String>.