Java，确定哈希图中的任何值是否与值匹配的最快方法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5721084/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java, quickest way to determine if any values in hashmap match a value?
提问by Rick
Pardon my newbie-ness to Java as I am not experienced enough to know the most efficient way to do this. I have a hashmap like below, but it would have like 40,000 entries:
请原谅我对 Java 的新手，因为我没有足够的经验来知道最有效的方法来做到这一点。我有一个如下所示的哈希图，但它可能有 40,000 个条目：
Map <String, String> someHashmap = new HashMap <String, String> ();
someHashmap.put("filepath1", null);
someHashmap.put("filepath2", "tag1");
someHashmap.put("filepath3", "tag2");
I want to determine how many value match nullso that I can determine if any are null. Of course I could do a regular loop to check but am wondering if there is a more efficient way, thanks
我想确定有多少值匹配，null以便我可以确定是否有任何值为空。当然我可以做一个常规循环来检查，但我想知道是否有更有效的方法，谢谢
回答by Mike Lewis
You can use the containsValuemethod, which states:
您可以使用该containsValue方法，该方法指出：
Returns true if this map maps one or more keys to the specified value.
如果此映射将一个或多个键映射到指定值，则返回 true。
somHashmap.containsValue(null);
However keep in mind, that if you have a large dataset(and it seems you do), you should create a separate data structure to keep track of the values that allow for O(1) lookup time, rather than O(n) time, as suggested in other answers.
但是请记住，如果您有一个大型数据集（而且看起来确实如此），您应该创建一个单独的数据结构来跟踪允许 O(1) 查找时间而不是 O(n) 时间的值，正如其他答案中所建议的那样。
回答by jprete
Here's an alternative solution, designed for speed.
这是一个替代解决方案，专为速度而设计。
Call your original HashMap a. Have a second HashMap<String, Integer> aCount. The aCounthash map is going to store a count of how many of each value is in your original hash map.
调用您的原始 HashMap a。等一下HashMap<String, Integer> aCount。该aCount哈希表将要存储的每个值的多是如何在你原来的哈希表的计数。
Every time you insert a key kand value vinto the first HashMap, check to see if aCount.containsKey(v). If it does, then increment the value: aCount.put(v, aCount.get(v) + 1). Otherwise, add a new entry: aCount.put(v, 1).
每次将键k和值v插入到第一个中时HashMap，请检查是否aCount.containsKey(v). 如果是，则增加值：aCount.put(v, aCount.get(v) + 1)。否则，添加一个新条目：aCount.put(v, 1)。
Every time you remove a key kand value vfrom the first HashMap, check the count using aCount.get(v). If the count is greater than one, then use aCount.put(v, aCount.get(v) - 1)to decrement the count. Otherwise (i.e. the count is exactly one) use aCount.remove(v).
每次从第一个中删除键k和值时，请使用. 如果计数大于 1，则用于递减计数。否则（即计数正好是一）使用.vHashMapaCount.get(v)aCount.put(v, aCount.get(v) - 1)aCount.remove(v)
Then, you need only call aCount.contains(v)to find out whether or not a given value is in your HashMap a.
然后，您只需要调用aCount.contains(v)来确定给定的值是否在您的 HashMap 中a。
Why do all this? Because, this way, instead of having an O(n) query time to find out if a value exists in your HashMap, you get O(1) time. If this is valuable to you, then the above solution will work. If this doesn't matter to you, then you can easily use Mike Lewis's answer.
为什么要做这一切？因为，通过这种方式，无需 O(n) 查询时间来确定 HashMap 中是否存在某个值，而是获得 O(1) 时间。如果这对您有价值，那么上述解决方案将起作用。如果这对您来说无关紧要，那么您可以轻松使用 Mike Lewis 的答案。
回答by leonbloy
If you really need speed, you will neeed to store the used values in a HashSet, apart from the HashMap. For example (not tested!).
如果您确实需要速度，则除了 HashMap 之外，您还需要将使用过的值存储在 HashSet 中。例如（未测试！）。
public class MapWithVals<K, V> extends HashMap<K, V> {
protected final Set<V> vals = new HashSet<V>();
public MapWithVals() {
super();
}
public MapWithVals(Map<? extends K, ? extends V> m) {
super(m);
vals.addAll(m.values());
}
@Override
public void clear() {
super.clear();
vals.clear();
}
@Override
public V put(K arg0, V arg1) {
vals.add(arg1);
return super.put(arg0, arg1);
}
@Override
public V remove(Object arg0) {
V val = get(arg0);
super.remove(arg0);
if( ! super.containsValue(val) ) vals.remove(val);
return val;
}
@Override
public boolean containsValue(Object value) {
return vals.contains(value);
}
@Override
public void putAll(Map<? extends K, ? extends V> arg0) {
super.putAll(arg0);
vals.addAll(arg0.values());
}
@Override
public Object clone() {
throw new RuntimeException("not implemented");
}
}
回答by coolest_head
Since you are only interested in null, everytime you putinto the HashMap, you can check if the value is nulland store the keyin a HashSet.
由于您只对 感兴趣null，因此每次put进入 时HashMap，您可以检查该值是否null并将其存储key在 a 中HashSet。
Then you'd have to take care of sync'ing all CRUDs from the Map <--> HashSet
然后，您必须负责同步 Map <--> HashSet 中的所有 CRUD
