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

Pillow

Why do you say that using Guava "feels like shooting with a very big gun"? Lots of libraries use Guava. I don't see any reason to reimplement what is already readily available. If you are worried about JAR size then you can use ProGuard or copy the necessary classes. – Malpractice

Yea but even if I remove with proguard I have the penalty of a big library at build-time – Pillow

If you find your build with and without Guava I suspect you'll find the difference marginal. – Malpractice

not in an android context – Pillow

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.

Coupe

Thanks so much for the detailed answer and the lib – Pillow

You're welcome! It's in the process of linkage with jcenter, which may take a day or so. Tomorrow it should become available on jcenter. – Coupe

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

Smug

You end up with a get method which has a O(1) complexity and a getKey method with O(n) complexity, I don't think it's a good idea. A more consistent solution would be to create a Bimap which use two maps like the other answer suggest. – Deleterious

He wrote "If speed is not a priority" ... – Slaw

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().

Ennoble

This isn't a bi-map like OP asked for, i.e. the inverse map will not be in sync with the original map. But if you just need a quick, throwaway inverse map this is a very elegant solution! – Legitimatize

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.

Shepley

Unfortunately creating a BiMap is not that simple. Consider entries, keys and values. – Coupe

@Coupe that's what the ... are for – Shepley

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()

Pamplona