Обратный поиск в хэш-таблице для поиска наименьшего ключа

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

Я готов поспорить, что вы можете, если вы можете гарантировать, что то, против чего вы проверяете, а также тип ваших ключей 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;
}

Гуава предлагаетBiMap, который может быть более пригодным для использования в реальном мире; однако, это не позволит присутствовать дублирующимся значениям без их перезаписи.

Вот пример этого.

public <K extends Number, V extends Number> K findSmallestKeyWithBimap(BiMap<K, V> values, V searchItem) {
    return values.inverse().get(searchItem);
}

Это намного более кратко, и не нуждается в том же роде дженериков, что и предыдущий (этот должен быть только Numberне оба Number а также Comparable). Это также намного менее гибко, и из-за его природы, вы явно гарантируете однозначное соответствие между ключами и значениями.