Why does my Map claim to have no keys after adding keys?

Question

I have a map of Int->Queue, and I'm adding to the queues one entry at a time. At the end of the process I need to iterate over the keys and values (because I want to convert the Queues to Arrays), but scala says there are no keys/values in the map. Some simplified code below for illustration purposes. What is going on here? The result of m(4) below is also puzzling.

import scala.collection.mutable.Queue

val m = Map[Int, Queue[Int]]().withDefaultValue(Queue[Int]())

m(1) += 10
res25: scala.collection.mutable.Queue[Int] = Queue(10)

m(1) += 10
res26: scala.collection.mutable.Queue[Int] = Queue(10, 10)

m(1)
res35: scala.collection.mutable.Queue[Int] = Queue(10, 10)

m(4)
res37: scala.collection.mutable.Queue[Int] = Queue(10, 10)

m.keys
res28: Iterable[Int] = Set()

m
res36: scala.collection.immutable.Map[Int,scala.collection.mutable.Queue[Int]] = Map()

Using scala 2.10.3.

score 2 · Answer 1 · answered Jun 13 '17 at 23:07

2

You never add anything to the map. You are getting the mutable queue that you set as the default value and modifying that.

answered Jun 13 '17 at 23:07

puhlen

8,400
1
16
31

jwvh · Answer 2 · 2017-06-14T08:36:56.310

1

Yes, you do have to check if the Queue at a given index has been created or not, but the syntax need not be quite so "laborious."

import scala.collection.mutable.Queue
val mutablemap = scala.collection.mutable.Map[Int, Queue[Int]]()

mutablemap(9) = mutablemap.lift(9).fold(Queue(99))(_ += 99)
mutablemap(2) = mutablemap.lift(2).fold(Queue(22))(_ += 22)
mutablemap(9) = mutablemap.lift(9).fold(Queue(19))(_ += 19)
mutablemap(2) = mutablemap.lift(2).fold(Queue(12))(_ += 12)

mutablemap(9)  // res0: scala.collection.mutable.Queue[Int] = Queue(99, 19)
mutablemap(2)  // res1: scala.collection.mutable.Queue[Int] = Queue(22, 12)

update

On further reflection, your original design wasn't too far off the mark.

import scala.collection.mutable.Queue
val mutablemap = 
  scala.collection.mutable.Map[Int, Queue[Int]]().withDefault(_ => Queue[Int]())

mutablemap(3) = mutablemap(3) += 37
mutablemap(3) = mutablemap(3) += 45
mutablemap(6) = mutablemap(6) += 60
mutablemap(6) = mutablemap(6) += 62

mutablemap(3)  // res0: scala.collection.mutable.Queue[Int] = Queue(37, 45)
mutablemap(6)  // res1: scala.collection.mutable.Queue[Int] = Queue(60, 62)

edited Jun 14 '17 at 08:36

answered Jun 14 '17 at 07:02

jwvh

50,871
7
38
64

When you do mutablemap(6) = mutablemap(6) += 62 , is that O(1) or O(N) where N is the length of the queue? – foghorn Jun 14 '17 at 19:58
According to the [ScalaDocs page](http://www.scala-lang.org/api/current/scala/collection/mutable/Queue.html), the `+=` method "appends a single element to this buffer. This takes constant time." – jwvh Jun 14 '17 at 20:15
I was wondering about the `=` in `mutablemap(6) =`. Is this deleting the existing N length queue and replacing it with a new one, or is it O(1) due to smart internal handling of references? – foghorn Jun 14 '17 at 20:28
I'd be a bit surprised if the entire operation were O(N), but I don't really know. – jwvh Jun 14 '17 at 20:38
@foghorn Appending to Queue is O(1) as said. Accessing a HashMap element is effectively O(1), but this performance can degrade if you have a poor hashing algorithm. Also keep in mind the cost to calculate the hashcode of your key as well. Your keys are Ints so it's not a concern here. So you can say this operation as a whole should be O(1). – puhlen Jun 14 '17 at 21:18
Yes, the `+=` is definitely O(1). I'm not sure about the `=`. It's probably O(1), but might be O(N). Maybe I'll try to time it later. – foghorn Jun 14 '17 at 23:16
Confirmed it is also O(1) using https://stackoverflow.com/questions/9160001/how-to-profile-methods-in-scala – foghorn Jun 14 '17 at 23:30

foghorn · Answer 3 · 2017-06-14T20:11:22.730

Leveraging puhlen's answer:

First, I need to switch to a mutable map. Second, the use of withDefaultValue seems to be irrelevant to this problem (which is counterintuitive).

val mutablemap = scala.collection.mutable.Map[Int, Queue[Int]]()

When adding key-value pairs to the map, I have to laboriously check to see if the key exists first (because I don't want to destroy any pre-existing key-value pair, because I'm incrementally building up the queues):

if (mutablemap.contains(key)) {
    // mutate the existing Queue
    mutablemap(key) += new_value
} else {
    // key was not in map; start a new Queue
    mutablemap += key -> Queue[Int](first_value)
}

Why does my Map claim to have no keys after adding keys?

3 Answers3

Linked