BiMap / двусторонняя хеш-карта в Котлине

Мне тоже нужна простая реализация BiMap, поэтому я решил создать небольшую библиотеку под названием bimap.

Реализация BiMap довольно проста, но содержит сложную часть, которая представляет собой набор записей, ключей и значений. Я попытаюсь объяснить некоторые детали реализации, но вы можете найти полную реализацию на GitHub.

Во-первых, нам нужно определить интерфейсы для неизменяемых и изменяемых BiMaps.

interface BiMap<K : Any, V : Any> : Map<K, V> {
  override val values: Set<V>
  val inverse: BiMap<V, K>
}

interface MutableBiMap<K : Any, V : Any> : BiMap<K, V>, MutableMap<K, V> {
  override val values: MutableSet<V>
  override val inverse: MutableBiMap<V, K>

  fun forcePut(key: K, value: V): V?
}

Обратите внимание, что BiMap.values возвращает Set вместо Collection. Также BiMap.put(K, V) выдает исключение, когда BiMap уже содержит заданное значение. Если вы хотите заменить пары (K1, V1) и (K2, V2) на (K1, V2), вам нужно позвонить forcePut(K, V). И, наконец, вы можете получить обратный BiMap для доступа к своим ключам по значениям.

BiMap реализовано с использованием двух обычных карт:

val direct: MutableMap<K, V>
val reverse: MutableMap<V, K>

Инверсию BiMap можно создать, просто поменяв местами карты direct и reverse. Моя реализация предоставляет инвариант bimap.inverse.inverse === bimap, но это не обязательно.

Как упоминалось ранее, метод forcePut(K, V) может заменить пары (K1, V1) и (K2, V2) на (K1, V2). Сначала он проверяет текущее значение K1 и удаляет его с карты reverse. Затем он находит ключ для значения V2 и удаляет его с карты direct. Затем метод вставляет заданную пару в обе карты. Вот как это выглядит в коде.

override fun forcePut(key: K, value: V): V? {
  val oldValue = direct.put(key, value)
  oldValue?.let { reverse.remove(it) }
  val oldKey = reverse.put(value, key)
  oldKey?.let { direct.remove(it) }
  return oldValue
}

Реализации методов Map и MutableMap довольно просты, поэтому я не буду подробно описывать их здесь. Они просто выполняют операцию на обеих картах.

Самая сложная часть это entries, keys и values. В моей реализации я создаю Set, который делегирует все вызовы методов direct.entries и обрабатывает изменение записей. Каждое изменение происходит в блоке try/catch, так что BiMap остается в согласованном состоянии при возникновении исключения. Более того, итераторы и изменяемые записи заключены в аналогичные классы. К сожалению, это делает итерацию по записям гораздо менее эффективной, потому что на каждом шаге итерации создается дополнительная оболочка MutableMap.MutableEntry.

Если скорость не является приоритетом, вы можете создать функцию расширения: map.getKey(value)

/**
 * Returns the first key corresponding to the given [value], or `null`
 * if such a value is not present in the map.
 */
fun <K, V> Map<K, V>.getKey(value: V) =
    entries.firstOrNull { it.value == value }?.key

FWIW, вы можете получить обратную карту в Kotlin, используя функцию расширения:

fun <K, V> Map<K, V>.inverseMap() = map { Pair(it.value, it.key) }.toMap()

Оператор map можно использовать для перебора List пар ключ-значение в Map, а затем преобразовать обратно в карту с помощью .toMap().

Ну, вы правы - как указано в аналогичном вопросе для Java "Двунаправленная карта в Java ?», в Kotlin нет BiMap из коробки.

Обходные пути включают использование Guava и создание пользовательского класса с использованием двух обычных карт:

class BiMap<K, V>() {
    private keyValues = mutableMapOf<K, V>()
    private valueKeys = mutableMapOf<V, K>()

    operator fun get(key: K) = ...
    operator fun get(value: V) = ...

    ...
}

Это решение не должно быть медленнее или занимать больше памяти, чем более сложное. Хотя я не уверен, что происходит, когда K совпадает с V.

Самое чистое решение для использования Guava и создать функцию расширения, которая превращает карту в BiMap. Это также следует семантике других преобразований карты Kotlin. Хотя у Guava могут быть некоторые накладные расходы, вы получаете возможность добавлять больше оболочек расширенных функций в будущем. Вы всегда можете удалить Guava в будущем и заменить функцию расширения другой реализацией.

Сначала объявите свою функцию расширения.

fun <K, V> Map<K, V>.toBiMap() = HashBiMap.create(this)

Затем используйте его следующим образом:

mutableMapOf("foo" to "bar", "me" to "you").toBiMap()