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

Ответ 1

Лучше всего использовать HashSet и проверить, существует ли строка в наборе с помощью метода contains(). HashSets создаются для быстрого доступа с использованием методов Object hashCode() и equals(). В Javadoc для HashSet указано:

Этот класс предлагает постоянную производительность по времени для основных операций (добавлять, удалять, содержать и размер),

HashSet хранит объекты в хэш-кодах, то есть значение, возвращаемое методом hashCode, определяет, какое ведро хранит объект Таким образом, количество проверок равенства, которое HashSet должно выполнять с помощью метода equals(), сводится только к другим объектам в том же ведро хеширования.

Чтобы эффективно использовать HashSets и HashMaps, вы должны соответствовать контракту equals и hashCode, указанному в javadoc. В случае java.lang.String эти методы уже реализованы для этого.

Ответ 2

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

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

Ответ 3

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

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

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

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

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

Запуск упражнения здесь - мои результаты.

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
*/

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

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

• хэш-код()
• равна()

Ответ 10

Иногда вы хотите проверить, находится ли объект в списке/наборе и в то же время вы хотите, чтобы список/набор был заказан. Если вы также хотите легко извлекать объекты без использования перечисления или итератора, вы можете рассмотреть возможность использования как 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>.