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

Question

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

Я беспокоюсь о производительности, так какой метод лучше?ArrayList?Hash

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

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

• Если список уже отсортирован, вы можете использовать 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 только в том случае, если выгоды перевешивают затраты.

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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

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

1. хэш-код ()
2. равен ()