BiMap / 2-way hashmap in Kotlin

I need a simple BiMap implementation too so decided to create a little library called bimap.

The implementation of BiMap is quite straightforward but it contains a tricky part, which is a set of entries, keys and values. I'll try to explain some details of the implementation but you can find the full implementation on GitHub.

First, we need to define interfaces for an immutable and a mutable 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?
}

Please, notice that BiMap.values returns a Set instead of a Collection. Also BiMap.put(K, V) throws an exception when the BiMap already contains a given value. If you want to replace pairs (K1, V1) and (K2, V2) with (K1, V2) you need to call forcePut(K, V). And finally you may get an inverse BiMap to access its keys by values.

The BiMap is implemented using two regular maps:

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

The inverse BiMap can be created by just swapping the direct and the reverse maps. My implementation provides an invariant bimap.inverse.inverse === bimap but that's not necessary.

As mentioned earlier the forcePut(K, V) method can replace pairs (K1, V1) and (K2, V2) with (K1, V2). First it checks what the current value for K1 is and removes it from the reverse map. Then it finds a key for value V2 and removes it from the direct map. And then the method inserts the given pair to both maps. Here's how it looks in code.

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
}

Implementations of Map and MutableMap methods are quite simple so I will not provide details for them here. They just perform an operation on both maps.

The most complicated part is entries, keys and values. In my implementation I create a Set that delegates all method invocations to direct.entries and handle modification of entries. Every modification happens in a try/catch block so that the BiMap remains in consistent state when an exception is thrown. Moreover, iterators and mutable entries are wrapped in similar classes. Unfortunately, it makes iteration over entries much less efficient because an additional MutableMap.MutableEntry wrapper is created on every iteration step.

If speed is not a priority ( O(n) complexity ) you can create an extension function: 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