关于 HashMap 方法 containsValue 的困惑

Question

我正在尝试找到我的方法的简化版本，我想知道您是否有更好的意见。

基本上我有一个将键值存储为 String-String[] 的 HashMap

我想要一种方法来查找新插入的 String[]-值是否包含已存在于已存储的 String[]- 中的字符串价值。

我写的“并且显然工作正常”是以下方法：

static Map<String,String[]> myMap=new HashMap<String,String[]>();

    public static boolean kijkContains(String[] syn){

for(String s:myMap.keySet()){

    String[]temp=myMap.get(s);

    for(int i=0; i<temp.length; i++){

        for(int k=0; k<syn.length; k++){

            if(temp[i].equals(syn[k])){

                return true;
            }
        }
    }
  }
return false;
}

我的疑问是循环次数，这显然是一个高内存消耗的方法，我想知道你是否能想到任何更好的版本。

我尝试过使用 Map 的 containsValue() 方法，但由于该方法将 String[] 视为值而不是读取数组，因此我无法真正将其用作比较器。

Answer 1

对于您当前拥有的数据结构，没有比循环所有这些值更好的方法了（至少您在第一次点击时就提前突破了）。

如果性能确实成为一个问题，您可能需要保留第二个数据结构来索引已有的数据结构。如果您只需要知道给定的字符串是否在映射中（而不是位置）（而不是位置），那么 HashSet 可能会起作用。

这是一个内存权衡：添加的索引结构将占用额外的空间。 （顺便说一句，除了地图已经占用的空间之外，您现在所做的不使用任何空间，您只是通过引用迭代数组，没有创建额外的副本）。

Answer 2

您的代码不会使用特别大量的内存，因为您没有创建任何 String[] 的副本（您只是复制对它们的引用，这非常便宜）。

但是，您需要循环遍历HashMap中的所有值，这使得这个O(n)（或者简单地说：慢）。

如果这是一个相对罕见的操作，那么这可能是可以接受的，我不会担心。

如果插入是一种常见操作，那么您绝对应该为此考虑更好的数据结构（您需要告诉我们更多有关实际用例的信息，以便我们在这里提出好的建议）。

Answer 3

好吧，除了循环遍历值之外，我不知道还有什么不同的方法，但我建议使用更简单的代码：

Map<String, String[]> map = new HashMap<String, String[]>();
for (String[] strings : map.values()) {
    ArrayUtils.contains(strings, "foo");
}

ArrayUtils 是来自 apache commons 的辅助类，但当然您也可以循环遍历字符串数组并调用 equalseach时间。请注意，这是区分大小写的。

Map<String, String[]> map = new HashMap<String, String[]>();
for (String[] strings : map.values()) {
    for (String string : strings) {
        if (string.equals("foo")) {
            return true;
        }
    }
}

Answer 4

您可以通过将 syn 数组复制到 HashSet 来降低时间复杂度。然后，您可以使用 HashSet#contains 方法，而不是一遍又一遍地迭代 syn，该方法的复杂度为 O(1)：

public static boolean kijkContains(String[] syn){
  if (syn == null || syn.length == 0) return false; // that was missing
  Set<String> input = new HashSet<String>();
  for (String s:syn)
    input.add(s);         // will remove duplicates, another perfo improvement

  for(String key:myMap.keySet()){
    for(String s:myMap.get(key)){  // we don't need the loop variable
      if (input.contains(s)) {
        return true;
      }
    }
  }
  return false;
}

复杂度为 < code>O(i*j*k) 并且我将其减少为 O(i*j+k) （其中 i 是地图的大小，j 是 值数组的平均大小和 k syn 数组的大小）

Answer 5

所以你想要的是HashMap中的每个字符串的值必须是唯一的。
我认为如果你使用 HashSet 而不是 String[] 作为 Map 的值，它会起作用。

导入 java.util.*;

公共类 TestHashMap {
公共静态无效主（字符串参数[]）{

System.out.println("Hashmap Test");
HashMap<String, HashSet> myMap = new HashMap<String, HashSet>();

HashSet<String> s1 = new HashSet<String>();
s1.add("one");
s1.add("two");
s1.add("three");

myMap.put("1", s1);
System.out.println("Value for key 1" + myMap.get("1"));

}
我希望

这是您想要的方式。

Answer 6

您可以使用 containsValue() 方法来执行此操作。您不必迭代抛出整个 HashMap。

http://msdn.microsoft.com/en -us/library/aa989118%28v=vs.80%29.aspx

http://www.javadocexamples.com/java/util/HashMap /containsValue%28Object%20value%29.html