java - 哈希表反向查找以找到最小的键

Question

我有一个面试问题是在哈希表中搜索一个值并返回最小的键。

我的方法是按键对哈希表进行排序，然后遍历它以找到与搜索值对应的键。

我用 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 中做同样的事情？

Answer 1

我愿意打赌你可以，如果你可以保证你正在检查的内容以及你的 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 也低得多，并且由于其性质，您明确保证在键和值之间具有一对一的映射。