Scala中有双向映射吗

Question

我想链接两列唯一标识符，并能够通过第二列值获得第一列值，通过第一列值获得第二列的值。类似的东西

Map(1 <-> "one", 2 <-> "two", 3 <-> "three")

斯卡拉有这样的设施吗？

事实上，我需要更多：3列来选择一个三元组中的任何一个，然后选择另一个（在整个映射中，单个值永远不会满足一次以上）。但两列双向地图也有帮助。

Answer 1

Guava有一个可以与一起使用的bimap

import scala.collection.JavaConversions._

Answer 2

My BiMap方法：

object BiMap {
  private[BiMap] trait MethodDistinctor
  implicit object MethodDistinctor extends MethodDistinctor
}
case class BiMap[X, Y](map: Map[X, Y]) {
  def this(tuples: (X,Y)*) = this(tuples.toMap)
  private val reverseMap = map map (_.swap)
  require(map.size == reverseMap.size, "no 1 to 1 relation")
  def apply(x: X): Y = map(x)
  def apply(y: Y)(implicit d: BiMap.MethodDistinctor): X = reverseMap(y)
  val domain = map.keys
  val codomain = reverseMap.keys
}
val biMap = new BiMap(1 -> "A", 2 -> "B")
println(biMap(1)) // A
println(biMap("B")) // 2

当然，可以为<->而不是->添加语法。

Answer 3

下面是Guava的BiMap的快速Scala包装器。

import com.google.common.{collect => guava}
import scala.collection.JavaConversions._
import scala.collection.mutable
import scala.languageFeature.implicitConversions
class MutableBiMap[A, B] private (
    private val g: guava.BiMap[A, B] = new guava.HashBiMap[A, B]()) {
  def inverse: MutableBiMap[B, A] = new MutableBiMap[B, A](g.inverse)
}
object MutableBiMap {
  def empty[A, B]: MutableBiMap[A, B] = new MutableBiMap()
  implicit def toMap[A, B] (x: MutableBiMap[A, B]): mutable.Map[A,B] = x.g
}

Answer 4

我在Scala:中有一个非常简单的BiMap

  case class BiMap[A, B](elems: (A, B)*) {
    def groupBy[X, Y](pairs: Seq[(X, Y)]) = pairs groupBy {_._1} mapValues {_ map {_._2} toSet}
    val (left, right) = (groupBy(elems), groupBy(elems map {_.swap}))
    def apply(key: A) = left(key)
    def apply[C: ClassTag](key: B) = right(key)
  }

用法：

  val biMap = BiMap(1 -> "x", 2 -> "y", 3 -> "x", 1 -> "y")
  assert(biMap(1) == Set("x", "y"))
  assert(biMap("x") == Set(1, 3))

Answer 5

我不认为它是开箱即用的，因为一般行为不容易提取

如何在干净的api中处理与多个键匹配的值？

然而，对于特定的情况，这里有一个很好的练习，可能会有所帮助。它必须更新，因为没有使用哈希，并且获取密钥或值是O（n）。

但这个想法是让你写一些类似于你建议的东西，但使用Seq而不是Map。。。

在隐式和trait以及find的帮助下，您可以用一种干净的api（fromKey、fromValue）来模拟您需要的东西。

具体情况是，一个值不应该出现在几个地方。。。至少在这个实现中。

  trait BiMapEntry[K, V] {
    def key:K
    def value:V
  }
  trait Sem[K] {
    def k:K
    def <->[V](v:V):BiMapEntry[K, V] = new BiMapEntry[K,  V]() { val key = k; val value = v}
  }
  trait BiMap[K, V] {
    def fromKey(k:K):Option[V]
    def fromValue(v:V):Option[K]
  }

  object BiMap {
    implicit def fromInt(i:Int):Sem[Int] = new Sem[Int] {
      def k = i
    }
    implicit def fromSeq[K, V](s:Seq[BiMapEntry[K, V]]) = new BiMap[K, V] {
      def fromKey(k:K):Option[V] = s.find(_.key == k).map(_.value)
      def fromValue(v:V):Option[K] = s.find(_.value == v).map(_.key)
    }
  }


  object test extends App {
    import BiMap._

    val a = 1 <-> "a"
    val s = Seq(1 <-> "a", 2 <-> "b")
    println(s.fromKey(2))
    println(s.fromValue("a"))
  }

Answer 6

Scala是不可变的，值被分配为引用而不是副本，因此内存占用将仅用于引用/指针存储，最好将其用于两个映射，类型A是第一个映射的密钥，类型B是第二个映射的键，分别映射到B和A，而不是映射的时间交换。交换实现也有自己的内存占用，新交换的哈希映射也将存在于内存中，直到执行父回调和垃圾收集器调用。如果需要频繁地交换映射，那么实际上您使用的内存与最初的两个映射实现相同或更多。

您可以尝试使用单个映射的另一种方法是（仅适用于使用映射值获取密钥）：

def getKeyByValue[A,B](map: Map[A,B], value: B):Option[A] = hashMap.find((a:A,b:B) => b == value)

Scala实现按键查找的代码：

/** Find entry with given key in table, null if not found.
   */
  @deprecatedOverriding("No sensible way to override findEntry as private findEntry0 is used in multiple places internally.", "2.11.0")
  protected def findEntry(key: A): Entry =
    findEntry0(key, index(elemHashCode(key)))
  private[this] def findEntry0(key: A, h: Int): Entry = {
    var e = table(h).asInstanceOf[Entry]
    while (e != null && !elemEquals(e.key, key)) e = e.next
    e
  }