BiMap / 2-way hashmap in Kotlin

Question

is there a bidirectional hashmap for kotlin? If not - what is the best way to express this in kotlin? Including guava to get the BiMap from there feels like shooting with a very big gun on a very little target - no solution that I can imagine currently feels right - the best thing I have in mind is to write a custom class for it

Answer 1

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.

Answer 2

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

Answer 3

FWIW, you can get the inverse of the map in Kotlin using an extension function:

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

The map operator can be used to iterate over the List of key-value pairs in the Map, then convert back to a map using .toMap().

Answer 4

Well, you are right - as it stated in a similar question for Java "Bi-directional Map in Java?", Kotlin does not have BiMap out of the box.

The workarounds include using Guava and creating a custom class using two usual maps:

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

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

    ...
}

This solution should not be slower or take more memory than a more sophisticated one. Although I am not sure what happens when K is the same as V.

Answer 5

The cleanest solution to to use Guava and create an extension function that turns a Map into a BiMap. This follows the semantics of Kotlin's other Map conversions as well. Although Guava might have a bit of overhead, you gain the flexibility to add more extension functions wrappers in the future. You can always remove Guava in the future and replace the extension function with another implementation.

First declare your extension function.

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

Then use it like this:

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