Какой самый быстрый способ определить, входит ли значение в набор значений в Java?

Question

Это, наверное, простой вопрос для вас, экспертов JAVA, но я относительно новичок, поэтому я решил спросить. Мне нужно проверить, существует ли строка X в наборе. Мне не нужны никакие связанные значения или индексы, и мне не нужен порядок. Мне просто нужно знать, существует ли он. Я знаю, что это может быть реализовано с использованием HashMap или ArrayList, но они кажутся излишними. Что делать? Просто список? Или есть что-то еще более простое, что послужит той же цели. Какой самый быстрый способ проверить, существует ли некоторая строка X в данном наборе?

Answer 1

Звучит так, как вы хотите HashSet<String>:

Set<String> set = new HashSet<String>();
set.add("foo");
set.add("bar");

boolean no = set.contains("baz");
boolean yes = set.contains("foo");

Конечно, существуют и другие Set реализации, но HashSet, пожалуй, здесь наиболее уместно.

Answer 2

У вас нет только ArrayList и HashMap, JDK поставляется с большим выбором классов, в которых вы также можете найти то, что ищете: наборы.

Например, один из них - HashSet, который имеет ту функциональность, о которой вы мечтаете.

Set<String> set = new HashSet<String>();

set.add("foo");
set.add("bar");

boolean b = set.contains("foo");

Answer 3

Не использовать содержит использование Collections.binarySearch (Список, Объект)

Не забудьте отсортировать, прежде чем использовать этот метод Collections.sort (Список)

Answer 4

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

Размер строк также имеет значение, потому что HashSet и т. Д. Будет использовать хеш-код строки, который вычисляется из всего содержимого строки (а затем кэшируется). Это может занять некоторое время, но, с другой стороны, оно может быть уже вычислено, в зависимости от вашего кода, поэтому не потребует дополнительных затрат.

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

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

Если вам действительно нужно быстрое решение (действительно ли это важно для вашего приложения?), То вам, возможно, придется мириться с «перебором»!

Answer 5

Я знаю, что это может быть реализовано с использованием HashMap или ArrayList, но они кажутся излишними.

Что именно является «излишним» в использовании встроенного класса, который предназначен для выполнения именно того, что вы хотите, и делать это очень быстро? Потому что это то, что HashMap. HashSet был бы немного более базовым в своем интерфейсе (не сопоставленные значения), но на самом деле он реализуется, имея HashMap с нулевыми значениями.

Answer 6

import java.util.Arrays;

...

if (Arrays.asList("foo", "bar", "baz").contains(myString)) {
    ...
}