5

我目前有一个字符串数组，我需要多次搜索以找到精确匹配。什么是最好的数据结构？

Example - String array with elements

cat
dog
squirrel
raccoon
aardvark

java 代码接收对字符串的搜索并遍历数组：

  1. 查询“dogg” - 不返回任何内容
  2. 查询“浣熊” - 返回浣熊

我当前的代码执行以下操作：

for (String element : myList) {
      if (element.equals(searchTerm)) {
            return searchTerm;
      }
}

有没有更有效的方法来做这个搜索？我考虑过使用地图，但我想不出一个好的价值（关键是'狗'/'猫'/等等......）。我应该为键和值使用相同的值吗？有没有更好的数据结构可以使用？

4

7 回答 7

11

在此处使用 aHashSet以获得最佳查找性能。请注意，这Set不允许任何重复。在这里使用 aMap没有多大意义，因为您只对搜索键感兴趣，即您没有任何与它相关的东西。

示例代码：

Set<String> animals = new HashSet<String>(
                          Arrays.asList("cat", "dog", "squirrel", "raccoon"));
if (animals.contains("dog")) {
    System.out.println("Yep, dog's here!"); // prints
}
if (!animals.contains("aardvark")) {
    System.out.println("Ah, aardvark's missing!"); // prints
}

请注意， aList也有一个contains()方法，但它会遍历其所有元素以检查一个项目是否存在几乎与您在使用 for 循环时要避免的相同的低性能。

于 2013-07-05T13:54:36.580 回答
4

您可以使用 Trie 数据结构

这是guava trie中的一个实现。搜索的复杂度是O(L) where L = stringToSearch.length();

于 2013-07-05T13:59:35.540 回答
1 
return myList.contains(searchTerm) ? searchTerm : null;
于 2013-07-05T13:56:20.883 回答
1

尝试这个

    String[] arr = new String[]{"cat", "dog", "squirrel", "raccoon", "aardvark"};
    List<String> list=new ArrayList<String>(Arrays.asList(arr));
    System.out.println(list.contains("dog") ? "found" : "not found");
于 2013-07-05T14:09:33.240 回答
1

您可以使用 aSet而不是 a Map（或者，在 a 的情况下Map，只需对键使用任何值）：

if (mySet.contains(element)) {
    return element;
} else {
    return null;
}
于 2013-07-05T13:54:34.783 回答
0

如果你只想返回你的搜索词，你可以这样做

String result = myList.contains(searchTerm) ? result : "";
于 2013-07-05T13:58:34.107 回答
0

把它们放进去，HashSet因为它使用散列，这是一种快速检索元素的技术，因为它使用散列码来存储它们。

Sub obj = new Sub();
obj.items.add("one");
obj.items.add("two");
obj.items.add("three");

System.out.println(obj.items.contains("one"));
于 2013-07-05T13:55:22.153 回答