堆栈的 Scala 哈希只有一个堆栈用于所有键

Question

我有以下哈希图，其中每个元素都应该映射到堆栈：

var pos = new HashMap[Int, Stack[Int]] withDefaultValue Stack.empty[Int]           
 for(i <- a.length - 1 to 0 by -1) {
            pos(a(i)).push(i)
}

如果a将有元素{4, 6, 6, 4, 6, 6}，如果我在上面的代码之后添加以下行：

println("pos(0) is " + pos(0))
println("pos(4) is " + pos(4))

输出将是：

pos(0) is Stack(0, 1, 2, 3, 4, 5)
pos(4) is Stack(0, 1, 2, 3, 4, 5)

为什么会这样？我不想在pos(0)中添加元素，而只想添加pos(4)和pos(6)（a的命令）。

看起来只有一个堆栈映射到所有键。我想要每个键的堆栈。

Answer 1

查看文档：

http://www.scala-lang.org/api/current/index.html#scala.collection.mutable.HashMap

方法 withDefaultValue 将此值作为常规参数，不会重新计算，因此所有条目共享同一个可变堆栈。

def withDefaultValue(d: B): Map[A, B]

您应该改用withDefault方法。

val pos = new HashMap[Int, Stack[Int]] withDefault (_ => Stack.empty[Int])

编辑

上面的解决方案似乎不起作用，我得到空堆栈。检查源显示返回默认值，但从未放入映射中

override def apply(key: A): B = {
  val result = findEntry(key)
  if (result eq null) default(key)
  else result.value
}

我想一种解决方案可能是覆盖apply或default方法，以便在返回之前将条目添加到地图。default方法示例：

val pos = new mutable.HashMap[Int, mutable.Stack[Int]]() {
  override def default(key: Int) = {
    val newValue = mutable.Stack.empty[Int]
    this += key -> newValue
    newValue
  }
}

顺便说一句，这是对可变的惩罚，我鼓励您使用不可变的数据结构。

Answer 2

如果您正在寻找一个更惯用的 Scala、函数式解决方案，没有这些可变集合，请考虑以下因素：

scala> val a = List(4, 6, 6, 4, 6, 6)
a: List[Int] = List(4, 6, 6, 4, 6, 6)
scala> val pos = a.zipWithIndex groupBy {_._1} mapValues { _ map (_._2) }
pos: scala.collection.immutable.Map[Int,List[Int]] = Map(4 -> List(0, 3), 6 -> List(1, 2, 4, 5))

乍一看可能看起来很混乱，但如果你分解它，zipWithIndex会得到值对及其位置，groupBy从每个值到条目列表制作一个映射，然后mapValues用于将（值、位置）对的列表转换为位置列表。

scala> val pairs = a.zipWithIndex
pairs: List[(Int, Int)] = List((4,0), (6,1), (6,2), (4,3), (6,4), (6,5))
scala> val pairsByValue = pairs groupBy (_._1)
pairsByValue: scala.collection.immutable.Map[Int,List[(Int, Int)]] = Map(4 -> List((4,0), (4,3)), 6 -> List((6,1), (6,2), (6,4), (6,5)))
scala> val pos = pairsByValue mapValues (_ map (_._2))
pos: scala.collection.immutable.Map[Int,List[Int]] = Map(4 -> List(0, 3), 6 -> List(1, 2, 4, 5))