Scala Programming Language
  1. Scala Programming Language
  2. SI-4954

LinkedHashMap.keys loses ordering when manipulated

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: Scala 2.9.0-1, Scala 2.9.1
    • Fix Version/s: Scala 2.10.0-M4
    • Component/s: Collections
    • Labels:
      None

      Description

      LinkedHashMap.keys returns the keys of the map in insertion order, but if that collection is manipulated in any way, it reverts to an unordered Set.

      This is somewhat surprising, particularly as keys is Iterable.

      Welcome to Scala version 2.9.0.1 (OpenJDK 64-Bit Server VM, Java 1.7.0-internal).
      Type in expressions to have them evaluated.
      Type :help for more information.
      
      scala> val m = scala.collection.mutable.LinkedHashMap("one" -> 1, "two" -> 2, "three" -> 3, "four" -> 4, "five" -> 5)
      m: scala.collection.mutable.LinkedHashMap[java.lang.String,Int] = Map(one -> 1, two -> 2, three -> 3, four -> 4, five -> 5)
      
      scala> m.keys
      res0: Iterable[java.lang.String] = Set(one, two, three, four, five)
      
      scala> m.keys.drop(0)
      res1: Iterable[java.lang.String] = Set(four, three, two, five, one)
      

        Activity

        Hide
        Paul Phillips added a comment -

        You are being fooled by a (fixed since 2.9.0-1) bug in the repl. If you compile and run this, they are in order.

        object Test {
          val m = scala.collection.mutable.LinkedHashMap("one" -> 1, "two" -> 2, "three" -> 3, "four" -> 4, "five" -> 5)
          
          def main(args: Array[String]): Unit = {
            m.keys foreach println
            m.keys drop 1 foreach println
          }
        }
        

        The repl has its own logic for printing traversables so Arrays don't get printed as mr. squiggly.

        Show
        Paul Phillips added a comment - You are being fooled by a (fixed since 2.9.0-1) bug in the repl. If you compile and run this, they are in order. object Test { val m = scala.collection.mutable.LinkedHashMap("one" -> 1, "two" -> 2, "three" -> 3, "four" -> 4, "five" -> 5) def main(args: Array[String]): Unit = { m.keys foreach println m.keys drop 1 foreach println } } The repl has its own logic for printing traversables so Arrays don't get printed as mr. squiggly.
        Hide
        Paul Phillips added a comment -

        I take it back. I got unlucky with "drop 1" there, drop 0 I see the same thing.

        Show
        Paul Phillips added a comment - I take it back. I got unlucky with "drop 1" there, drop 0 I see the same thing.
        Hide
        Michael Bayne added a comment -

        I did encounter this bug initially in real code, and just resorted to the repl to isolate it.

        I presume it has something to do with the REPR of LinkedHashMap keys as a Set instead of an OrderedSet (or whatever collection has both set and fixed ordering semantics, if such a beast exists).

        Show
        Michael Bayne added a comment - I did encounter this bug initially in real code, and just resorted to the repl to isolate it. I presume it has something to do with the REPR of LinkedHashMap keys as a Set instead of an OrderedSet (or whatever collection has both set and fixed ordering semantics, if such a beast exists).
        Hide
        Paul Phillips added a comment -

        I'm going with this:

        scala> scala.collection.mutable.LinkedHashMap().isInstanceOf[scala.collection.generic.Sorted[_, _]]
        res0: Boolean = false
        

        Without that, nothing is going to return the same type, i.e. "Sorted".

        Show
        Paul Phillips added a comment - I'm going with this: scala> scala.collection.mutable.LinkedHashMap().isInstanceOf[scala.collection.generic.Sorted[_, _]] res0: Boolean = false Without that, nothing is going to return the same type, i.e. "Sorted".
        Hide
        Michael Bayne added a comment -

        Is there an equivalent Ordered (rather than Sorted)? LinkedHashMap isn't sorted, just ordered based on insertion order.

        Show
        Michael Bayne added a comment - Is there an equivalent Ordered (rather than Sorted)? LinkedHashMap isn't sorted, just ordered based on insertion order.
        Hide
        Paul Phillips added a comment -

        Yeah, I was just realizing that, although I would say it is sorted: it's sorted and the custom ordering is the insertion order. But it looks to me like nothing beyond the trivial is going to keep happening in insertion order. keys returns DefaultKeySet, which will not be returning ordered sets on derivative operations.

        It looks like keysIterator preserves the order btw.

        Show
        Paul Phillips added a comment - Yeah, I was just realizing that, although I would say it is sorted: it's sorted and the custom ordering is the insertion order. But it looks to me like nothing beyond the trivial is going to keep happening in insertion order. keys returns DefaultKeySet, which will not be returning ordered sets on derivative operations. It looks like keysIterator preserves the order btw.
        Hide
        Paul Phillips added a comment -

        Here's another thing which seems less than ideal. I wish I could even find documentation as to what is expected here. If it's intentional that "keySet" stays sorted while "keys" throws it out the window, that should not be difficult information to come by.

        scala> scala.collection.immutable.SortedMap(1 to 100 zip (1 to 100) : _*).keys
        res0: Iterable[Int] = Set(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100)
        
        scala> res0.getClass
        res1: java.lang.Class[_ <: Iterable[Int]] = class scala.collection.immutable.SortedMap$DefaultKeySortedSet
        
        scala> scala.collection.immutable.SortedMap(1 to 100 zip (1 to 100) : _*).keys ++ Set()
        res2: Iterable[Int] = Set(69, 88, 5, 10, 56, 42, 24, 37, 25, 52, 14, 20, 46, 93, 57, 78, 29, 84, 61, 89, 1, 74, 6, 60, 85, 28, 38, 70, 21, 33, 92, 65, 97, 9, 53, 77, 96, 13, 41, 73, 2, 32, 34, 45, 64, 17, 22, 44, 59, 27, 71, 12, 54, 49, 86, 81, 76, 7, 39, 98, 91, 66, 3, 80, 35, 48, 63, 18, 95, 50, 67, 16, 31, 11, 72, 43, 99, 87, 40, 26, 55, 23, 8, 75, 58, 82, 36, 30, 51, 19, 4, 79, 94, 47, 15, 68, 62, 90, 83, 100)
        
        Show
        Paul Phillips added a comment - Here's another thing which seems less than ideal. I wish I could even find documentation as to what is expected here. If it's intentional that "keySet" stays sorted while "keys" throws it out the window, that should not be difficult information to come by. scala> scala.collection.immutable.SortedMap(1 to 100 zip (1 to 100) : _*).keys res0: Iterable[Int] = Set(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100) scala> res0.getClass res1: java.lang.Class[_ <: Iterable[Int]] = class scala.collection.immutable.SortedMap$DefaultKeySortedSet scala> scala.collection.immutable.SortedMap(1 to 100 zip (1 to 100) : _*).keys ++ Set() res2: Iterable[Int] = Set(69, 88, 5, 10, 56, 42, 24, 37, 25, 52, 14, 20, 46, 93, 57, 78, 29, 84, 61, 89, 1, 74, 6, 60, 85, 28, 38, 70, 21, 33, 92, 65, 97, 9, 53, 77, 96, 13, 41, 73, 2, 32, 34, 45, 64, 17, 22, 44, 59, 27, 71, 12, 54, 49, 86, 81, 76, 7, 39, 98, 91, 66, 3, 80, 35, 48, 63, 18, 95, 50, 67, 16, 31, 11, 72, 43, 99, 87, 40, 26, 55, 23, 8, 75, 58, 82, 36, 30, 51, 19, 4, 79, 94, 47, 15, 68, 62, 90, 83, 100)
        Hide
        Paul Phillips added a comment -

        Need input.

        Show
        Paul Phillips added a comment - Need input.
        Hide
        Paul Phillips added a comment -

        Going to pursue a minimal fix for linkedhashmap; we don't want to try to support orderedness in the type system, and linkedhashmap is performance sensitive so shoehorning things so it can use Sorted's machinery to retain ordering is a bust.

        Show
        Paul Phillips added a comment - Going to pursue a minimal fix for linkedhashmap; we don't want to try to support orderedness in the type system, and linkedhashmap is performance sensitive so shoehorning things so it can use Sorted's machinery to retain ordering is a bust.

          People

          • Assignee:
            Aleksandar Prokopec
            Reporter:
            Michael Bayne
          • Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development