查找字符串值的最快方法

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 具有更好的查找性能（contains 的恒定时间与对数时间）。

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 实现的全速和零编写的与集合相关的代码（例如 Collat​​or、比较器等）。

已编辑
感谢 Jon Skeet 指出，某些土耳其语字符在调用 toLowerCase() 时表现得很奇怪，但如果您不打算支持土耳其语输入（或者可能是其他具有非标准大小写问题的语言），那么这种方法很适合你。

Answer 2

在大多数情况下，我通常会从 HashSet 开始 - 但由于您想要不区分大小写，这使得它稍微困难一些。

您可以尝试使用 TreeSet

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

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

请注意，您无法创建 TreeSet，因为 Collat​​or 仅实现 Comparator

编辑：虽然上述版本仅适用于字符串，但创建 TreeSet可能会更快：

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));
}

那就nice有一种方法可以存储所有被忽略的值的排序规则键，但在测试时避免创建新的排序规则键，但我不知道有什么方法可以做到这一点。

Answer 3

将要忽略的单词添加到列表中，然后检查该单词是否在该列表中。

这使它成为动态的。

Answer 4

如果使用 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 5

看来 String[] 比建议的其他方法稍微好一些（性能方面），所以我将使用它。

它就像这样：

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

        return false;
    }

IGNORED_VALUES 对象只是一个 String[] ，其中包含所有被忽略的值。