4

我有一个场景，我将值存储在哈希图中。

键是字符串，如

fruits
fruits_citrus_orange
fruits_citrus_lemon
fruits_fleshly_apple
fruits_fleshly
fruits_dry

等等。

值是一些对象。现在对于给定的输入说 fruits_fleshly 我需要检索它以“fruits_fleshly”开头的所有情况在上述情况下我需要获取

fruits_fleshly_apple
fruits_fleshly

一种方法是对所有键执行 String.indexOf 。有没有其他有效的方法来做到这一点，而不是遍历地图中的所有键

4

5 回答 5

2

迭代地图似乎非常简单直接。但是，由于您不想自己迭代密钥，如果您可以使用 3rd 方库，则可以使用Guava's 。 Maps#filterEntries

以下是它的工作原理：

Map<String, Object> = Maps.filterEntries(
                   yourMap, 
                   Predicate.containsPattern("^fruits_fleshly"));

但是，这也将在后院的地图上进行迭代。因此，如果您担心效率，迭代仍然存在。

于 2013-08-01T18:52:23.407 回答
2

虽然这些是字符串，但对我来说，看起来这些是某些类别和子类别，如水果、新鲜水果、水果柑橘等。

如果是这种情况，您可以改为实现 Tree 数据结构。这对于搜索操作最有效。

由于Tree具有父子结构，因此存在根节点和子节点。你可以有这样的结构：

(0)   (1)        (2)
fruit
|_____citrus
|          |_____lemon
|          |_____orange
|
|_____freshly
           |_____apple
           |_____

在这个结构中，假设你想搜索柑橘类水果，你可以去柑橘类，并列出它的所有孩子。最后，您可以通过将名称连接为从根到叶的路径来构造全名。

于 2013-08-01T18:57:12.897 回答
1

由于 HashMap 不维护其键的任何顺序，因此它不是解决此问题的好选择。更好的选择是 TreeMap：它具有检索一系列键的子映射的方法。这些方法在 O(log n) 时间（n 个条目）内运行，因此它比遍历键更好。

Map subMap = myMap.subMap("fruits_fleshly", true, "fruits_fleshly\uffff", true);
于 2013-08-02T05:06:06.337 回答
0

hashmap 的性质意味着没有办法对键进行“喜欢”比较 - 您必须遍历它们才能找到 where key.startsWith(input)。

我想您可以嵌套哈希图并拆分您的密钥。例如，

{
  "fruits":{
    "citrus":{
      "orange":(value), 
      "lemon":(value)
    }, 
    "fleshly":{
      "apple":(value), 
      "":(value)
    }
  }
}

...ETC。

性能影响在小范围内可能是可怕的，但这在家庭作业环境中可能无关紧要，但如果您正在处理大量数据并且只有几层嵌套，则可能不是那么糟糕。

或者，创建具有类别列表（子类别）和条目列表的类别对象。

于 2013-08-01T18:52:56.387 回答
0

我相信Radix Trie是您正在寻找的。这与@ay89 解决方案的想法相似。

您可以只使用这个开源库Radix Trie 示例。它的性能优于 O(log(N))。通过 Radix Trie.fruits fruits_citrus_orange fruits_citrus_lemon fruits_fleshly_apple fruits_fleshly fruits_dry 的良好实现，您将能够在平均恒定时间（搜索关键字字符串中的下划线数量）中找到分配给键的哈希图

Trie<String, Map> trie = new PatriciaTrie<>;
trie.put("fruits", hashmap1);
trie.put("fruits_citrus_orange", hashmap2);
trie.put("fruits_citrus_lemon", hashmap3);
trie.put("fruits_fleshly_apple", hashmap4);
trie.put("fruits_fleshly", hashmap5);

Map.Entry<String, Map> entry = trie.select("fruits_fleshy");

如果您只想通过选择返回一个哈希图，那么如果您实现自己的 Radix Trie，则可能会获得更好的性能。

于 2013-08-02T16:01:09.403 回答