Самый быстрый способ поиска значения String

Question

У меня есть простое приложение, которое считывает данные небольшими строками из больших текстовых файлов и сохраняет их в базе данных.Чтобы фактически сохранить каждую такую ​​строку, приложение вызывает следующий метод несколько (может тысячи или более) раз:

setValue(String value)
{
    if (!ignore(value))
    {
         // Save the value in the database
    }
}

В настоящее время я реализую метод ignore(), просто последовательно сравнивая набор строк,например,

public boolean ignore(String value)
{
    if (value.equalsIgnoreCase("Value 1") || (value.equalsIgnoreCase("Value 2"))
    {
        return true;
    }

    return false;
}

Однако, поскольку мне нужно проверить множество таких «игнорируемых» значений, которые будут определены в другой части кода, мне нужно использовать структуру данных для этой проверки вместо несколькихпоследовательные if операторы.

Итак, мой вопрос: какая бы самая быстрая структура данных из стандартной Java для реализации этого?Хэш-карта?Множество?Что-то еще?

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

РЕДАКТИРОВАТЬ: предлагаемые к настоящему времени решения (включая HashSet) выглядят медленнеепросто используя String [] со всеми игнорируемыми словами и просто запуская «equalsIgnoreCase» для каждого из них.

Answer 1

Используйте HashSet , сохраняя значения в нижнем регистре, и его метод contains () , который имеет лучшую производительность поиска, чем TreeSet (постоянное время и время журнала для содержит).

Set<String> ignored = new HashSet<String>();
ignored.add("value 1"); // store in lowercase
ignored.add("value 2"); // store in lowercase

public boolean ignore(String value) {
    return ignored.contains(value.toLowerCase());    
}

Хранение значений в нижнем регистре и поиск входных данных в нижнем регистре позволяет избежать хлопот с регистром во время сравнения , поэтому вы получаете полную скорость реализации HashSet и сбор нулей.связанный с ним код для записи (например, Collator, Comparator и т. д.).

EDITED
Спасибо Джону Скиту за указание на то, что некоторые турецкие символы ведут себя странно при вызове toLowerCase(), но есливы не собираетесь поддерживать турецкий ввод (или, возможно, другие языки с нестандартными проблемами), тогда этот подход будет работать для вас.

Answer 2

В большинстве случаев я бы обычно начинал с HashSet<String> - но если вам нужна нечувствительность к регистру, это немного усложняет.

Вы можете попробовать использовать TreeSet<Object>, используя соответствующий Collator для нечувствительности к регистру.Например:

Collator collator = Collator.getInstance(Locale.US);
collator.setStrength(Collator.SECONDARY);

TreeSet<Object> set = new TreeSet<Object>(collator);

Обратите внимание, что вы не можете создать TreeSet<String>, так как Collator только реализует Comparator<Object>.

РЕДАКТИРОВАТЬ: хотя вышеприведенная версия работает только с строками может быть быстрее для создания TreeSet<CollationKey>:

Collator collator = Collator.getInstance(Locale.US);
collator.setStrength(Collator.SECONDARY);

TreeSet<CollationKey> set = new TreeSet<CollationKey>();
for (String value : valuesToIgnore) {
    set.add(collator.getCollationKey(value));
}

Тогда:

public boolean ignore(String value)
{
    return set.contains(collator.getCollationKey(value));
}

Было бы приятно иметьспособ хранения ключей сопоставления для всех игнорируемых значений, но при этом избегайте создания новых ключей сопоставления при тестировании, но я не знаю, как это сделать.

Answer 3

При использовании Java 7 это быстрый способ сделать это:

public boolean ignore(String value) {
  switch(value.toLowerCase()) { // see comment Jon Skeet
    case "lowercased_ignore_value1":
    case "lowercased_ignore_value2":
      // etc
      return true;
    default:
      return false;
  }
}

Answer 4

Добавьте слова для игнорирования в список и просто проверьте, есть ли слово в этом списке.

Это делает его динамически.

Answer 5

Кажется, что String [] немного лучше (с точки зрения производительности), чем другие предложенные методы, поэтому я буду использовать это.

Это просто что-то вроде этого:

public boolean ignore(String value)
{
    for (String ignore:IGNORED_VALUES)
    {
        if (ignore.equalsIgnoreCase(value))
        {
            return true;
        }

        return false;
    }

Объект IGNORED_VALUES - это просто строка [] со всеми игнорируемыми значениями там.