BiMap / 2-way hashmap in Kotlin

Question

is there a bi-directional hashmap for kotlin? If not, what is the best way to express this in Kotlin? Turning on the guava to get the BiMap from there is like shooting with a very large weapon on a very small target - no solution I can imagine right now feels right - the best I have in mind is to write my own class for it

Answer 1

I need a simple BiMap implementation, so I decided to create a small library called BiMap .

The implementation of BiMap quite simple, but it contains a complex part, which is a set of records, keys and values. I will try to explain some implementation details, but you can find the full implementation on GitHub .

First we need to define interfaces for immutable and mutable BiMap s.

 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? } 

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

BiMap is implemented using two regular maps:

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

Reverse BiMap can be created by simply replacing direct and reverse cards. My implementation provides the bimap.inverse.inverse === bimap , but this is optional.

As mentioned earlier, the forcePut(K, V) method can replace the pairs (K1, V1) and (K2, V2) with (K1, V2) . First, he checks what the current value is for K1 , and removes it from the reverse map. He then finds the key for the V2 value and removes it from the direct card. And then the method inserts this pair on both cards. This is 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 } 

The implementations of the Map and MutableMap fairly simple, so I won’t provide details here. They just perform an operation on both cards.

The hardest part is entries , keys and values . In my implementation, I create a Set that delegates all method calls to direct.entries and processes record changes. Each modification occurs in a try / catch , so that BiMap remains in a consistent state when an exception is thrown. Moreover, iterators and mutable records are wrapped in similar classes. Unfortunately, it makes iterating over the records much less efficient, because at each step of the iteration an additional wrapper MutableMap.MutableEntry .

Answer 2

If speed is not a priority, you can use the extension function: map.findKeyByValue (value)

 fun <Key,Value> Map<Key,Value>.findKeyByValue(searchValue: Value): Key? { for ((key, value) in this) { if (value == searchValue) return key } return null } 

Answer 3

Well, you're right - as he stated in a similar question for Java, “ Bidirectional Map in Java? ”, Kotlin does not have BiMap out of the box.

Workarounds include using Guava and creating a custom class using two regular 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 have more memory than a more complex one. Although I'm not sure what will happen when K is the same as V

Answer 4

The cleanest solution to use Guava and creates an extension function that turns the map into BiMap. This follows the semantics of other transformations of the Kotlin map. Although Guava may have a bit of overhead, you get the flexibility to add additional shells for extension functions in the future. You can always remove Guava in the future and replace the extension function with another implementation.

Declare your extension function first.

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

Then use it as follows:

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