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

Question

В принципе у меня около 1000 000 строк, для каждого запроса мне нужно проверить, принадлежит ли строка к списку или нет.

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

Answer 1

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

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

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

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

Answer 6

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

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

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

Answer 7

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

Answer 8

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

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

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 быстрее.

Answer 10

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

https://en.wikipedia.org/wiki/Bloom_filter