Scala hash of stacks has only one stack for all th

问题:

I have the following hashmap, where each element should be mapped to a stack:

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)
}

If a will have elements {4, 6, 6, 4, 6, 6}, and if I add the following lines after the code above:

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

The output will be:

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

Why is this happening? I don't want to add elements to pos(0), but only to pos(4) and pos(6) (the lements of a).

It looks like there is only one stack mapped to all the keys. I want a stack for each key.

回答1:

Check the docs:

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

method withDefaultValue takes this value as a regular parameter, it won't be recalculated so all your entries share the same mutable stack.

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

You should use withDefault method instead.

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

Edit

Above solution doesn't seem to work, I get empty stacks. Checking with sources shows that the default value is returned but never put into map

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

I guess one solution might be to override apply or default method to add the entry to map before returning it. Example for default method:

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

Btw. that is punishment for being mutable, I encourage you to use immutable data structures.

回答2:

If you are looking for a more idiomatic Scala, functional-style solution without those mutable collections, consider this:

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))

It may look confusing at first, but if you break it down, zipWithIndex gets pairs of values and their positions, groupBy makes a map from each value to a list of entries, and mapValues is then used to turn the lists of (value, position) pairs into just lists of positions.

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))