Kotlin中的BiMap /双向哈希图

4 回答

• 0

  我也需要一个简单的 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 返回 Set 而不是 Collection . 当 BiMap 已包含给定值时， BiMap.put(K, V) 也会抛出异常 . 如果要用 (K1, V2) 替换对 (K1, V1) 和 (K2, V2) ，则需要调用 forcePut(K, V) . 最后，您可能会得到一个反向 BiMap 来按值访问其键 .

  BiMap 使用两个常规 Map 实现：

  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 方法的实现非常简单，因此我不在这里提供它们的详细信息 . 他们只是在两个 Map 上执行操作 .

  最复杂的部分是 entries ， keys 和 values . 在我的实现中，我创建了一个 Set ，它将所有方法调用委托给 direct.entries 并处理条目的修改 . 每次修改都发生在 try / catch 块中，以便在抛出异常时 BiMap 保持一致状态 . 此外，迭代器和可变条目包含在类似的类中 . 不幸的是，它使条目上的迭代效率低得多，因为在每个迭代步骤中都会创建一个额外的 MutableMap.MutableEntry 包装器 .

  回复于 2024-05-08T14:17:33+08:00
• 9

  如果speed不是优先级，您可以创建扩展功能： 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
  

  回复于 2024-05-08T14:17:33+08:00
• 2

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

  解决方法包括使用 Guava 并使用两个常用 Map 创建自定义类：

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

  回复于 2024-05-08T14:17:33+08:00
• 0

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

  首先声明你的扩展功能 .

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

  然后像这样使用它：

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

  回复于 2024-05-08T14:17:33+08:00