Kotlin 中的 BiMap / 2-way hashmap

Question

kotlin 有双向 hashmap 吗？如果不是——在科特林中表达这一点的最佳方式是什么？包括番石榴以从那里获取 BiMap 感觉就像用一把非常大的枪在一个非常小的目标上射击 - 我可以想象目前没有任何解决方案感觉正确 - 我想到的最好的事情是为编写自定义 class它

Answer 1

嗯，你是对的 - 正如在 Java“Bi-directional Map in Java?”的类似问题中所述，Kotlin 没有开箱即用的 BiMap。

解决方法包括使用 Guava 和使用两个常用地图创建自定义 class：

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 相同时会发生什么。

Answer 2

我也需要一个简单的 BiMap 实现，所以决定创建一个名为 bimap 的小库。

BiMap 的实现非常简单，但它包含一个棘手的部分，即一组条目、键和值。我将尝试解释实施的一些细节，但您可以在 GitHub.

上找到完整的实施

首先，我们需要为不可变和可变 BiMap 定义接口。

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 returns 一个 Set 而不是 Collection。当 BiMap 已经包含给定值时，BiMap.put(K, V) 也会抛出异常。如果你想用 (K1, V2) 替换 (K1, V1) 和 (K2, V2) 对，你需要调用 forcePut(K, V)。最后你可能会得到一个逆 BiMap 来按值访问它的键。

BiMap使用两个正则映射实现：

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

只需交换 direct 和 reverse 映射即可创建反向 BiMap。我的实现提供了一个不变的 bimap.inverse.inverse === bimap 但这不是必需的。

如前所述，forcePut(K, V) 方法可以用 (K1, V2) 替换对 (K1, V1) 和 (K2, 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 包装器。

Answer 3

如果速度不是优先事项（O(n) 复杂度）您可以创建扩展函数：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 4

使用 Guava 的最干净的解决方案和创建一个扩展函数，将 Map 转换为 BiMap。这也遵循 Kotlin 的其他 Map 转换的语义。尽管 Guava 可能会有一些开销，但您可以灵活地在将来添加更多扩展函数包装器。您以后可以随时删除 Guava 并用其他实现替换扩展功能。

首先声明你的扩展函数。

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

然后像这样使用它：

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

Answer 5

FWIW，您可以使用扩展函数在 Kotlin 中获取地图的倒数：

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

map 运算符可用于迭代 Map 中键值对的 List，然后使用 .toMap() 转换回映射。

Kotlin 中的 BiMap / 2-way hashmap

BiMap / 2-way hashmap in Kotlin

bimap

kotlin