我有一个面试问题是在哈希表中搜索一个值并返回最小的键。
我的方法是按键对哈希表进行排序,然后遍历它以找到与搜索值对应的键。
我用 Python 写了这个函数:
def smallestKey(x):
my_dict = {10:20, 5:30, -2:25, 1:20}
for key in sorted(dict.iterkeys()):
if (my_dict[key] == x):
print key
有更好的方法吗?我怎样才能在 Java 中做同样的事情?
最佳答案
我愿意打赌你可以,如果你可以保证你正在检查的内容以及你的 key 的类型是Number
。
这是一个代码示例。排序成本为 O(n log(n)),线性搜索为 O(n),因此其性能约为 O(n log(n))。
public <K extends Number & Comparable<K>, V extends Number> K findSmallestKey(Map<K, V> values, V searchItem) {
// Grab the key set, and sort it.
List<K> keys = new ArrayList<>(values.keySet());
Collections.sort(keys);
for(K key : keys) {
if(values.get(key).doubleValue() == searchItem.doubleValue()) {
return key;
}
}
return null;
}
Guava offers BiMap
,这可能是一个更有用的现实案例;但是,它不允许在不覆盖重复值的情况下出现重复值。
这是一个例子。
public <K extends Number, V extends Number> K findSmallestKeyWithBimap(BiMap<K, V> values, V searchItem) {
return values.inverse().get(searchItem);
}
它更加简洁,并且不需要与前一个相同的泛型(这个只需要是一个Number
,而不是同时是一个Number
和 Comparable
)。它的灵 active 也低得多,并且由于其性质,您明确保证在键和值之间具有一对一的映射。
关于java - 哈希表反向查找以找到最小的键,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22395398/