Как реализовать поиск по значению в хэш-таблице

Что проверяют

Понимаете ли вы, что хэш-таблица ускоряет поиск по ключу, а по значению она ничем не лучше списка. Вопрос часто с подвохом: кандидат начинает рассказывать про get(key). Следом спрашивают, что делать, если искать по значению нужно часто.

Как отвечать

Сначала механика. HashMap раскладывает пары по бакетам по хэшу ключа, поэтому get и containsKey в среднем O(1). Значения тут не участвуют, и containsValue() обходит всю таблицу за O(n). Остаётся перебор:

• Kotlin: map.entries.firstOrNull { it.value == target }?.key для первого совпадения или map.filterValues { it == target }.keys для всех. Значения не уникальны, поэтому ответ в общем случае это множество ключей;
• Java: обход entrySet() или стрим с фильтром по Objects.equals(e.getValue(), target), чтобы не упасть на null;
• Android: у SparseArray есть indexOfValue(), но это тоже линейный поиск, и сравнивает он через ==, то есть по ссылке, а не через equals().

Если поиск по значению частый, заводится обратный индекс: второй HashMap<V, K> для уникальных значений или HashMap<V, MutableSet<K>> для повторяющихся. Обе структуры обновляются в одном методе, и при перезаписи ключа старое значение удаляется из обратного индекса. Для уникальных значений готовое решение есть в Guava: HashBiMap и его inverse().

Бывает и другой разворот: написать хэш-таблицу самому. Тогда проговорите хэш-функцию, разрешение коллизий цепочками или открытой адресацией, коэффициент загрузки 0.75 и рост массива. В HashMap начиная с Java 8 длинная цепочка в бакете превращается в красно-чёрное дерево.

Где спотыкаются

Отвечают про поиск по ключу и не замечают, что спросили про значение. Интервьюер слышит в этом непонимание, зачем вообще нужен хэш.

В самописной таблице считают индекс как key.hashCode() % capacity. Хэш бывает отрицательным, получается отрицательный индекс и ArrayIndexOutOfBoundsException. Нужен Math.floorMod или маска hash & (capacity - 1) при размере, равном степени двойки.

Заводят обратный индекс и забывают синхронизировать его при put и remove. Через пару обновлений структуры расходятся, и поиск по значению возвращает уже удалённый ключ.