12

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

4

5 回答 5

13

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

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

首先，我们需要为不可变和可变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?
}

请注意，它BiMap.values返回 aSet而不是 a Collection。当已经包含给定值时也会BiMap.put(K, V)引发异常。BiMap如果你想替换对和(K1, V1)你需要调用. 最后你可能会得到一个逆来按值访问它的键。(K2, V2)(K1, V2)forcePut(K, V)BiMap

这BiMap是使用两个常规映射实现的：

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

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

如前所述，该forcePut(K, V)方法可以替换 pair(K1, V1)和(K2, V2)with (K1, 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和。在我的实现中，我创建了一个将所有方法调用委托给并处理条目修改的方法。每个修改都发生在/块中，以便在抛出异常时保持一致状态。此外，迭代器和可变条目被包装在类似的类中。不幸的是，它使条目的迭代效率大大降低，因为在每个迭代步骤上都会创建一个额外的包装器。keysvaluesSetdirect.entriestrycatchBiMapMutableMap.MutableEntry

于 2016-04-02T18:52:42.940 回答
11

如果速度不是优先级（ 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
于 2017-06-30T10:57:01.063 回答
4

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

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

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

于 2020-03-14T10:18:58.877 回答
1

好吧，你是对的 - 正如 Java 的类似问题“Java中的双向映射？ ”中所述，Kotlin 没有开箱即用的 BiMap。

解决方法包括使用Guava和使用两个常用映射创建自定义类：

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。

于 2016-04-02T14:33:51.340 回答
0

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

于 2017-09-17T12:32:55.777 回答