Uploaded image for project: 'Scala Programming Language'
  1. Scala Programming Language
  2. SI-5879

scala.collection.immutable.HashMap.merge does not handle collisions correctly

    Details

    • Type: Bug
    • Status: CLOSED
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: Scala 2.9.2
    • Fix Version/s: Scala 2.10.0-M3
    • Component/s: None
    • Labels:
      None
    • Environment:

      Windows 7, 64bit

      Description

      The merge function of scala.collections.immutable.HashMap can result in an inconsistent HashMap when there is a hash code collision. The easiest way to get this behavior is to merge two maps and defining a collision function.

      But this also occasionally happens when no collision function is provided!

       
          import collection.immutable.HashMap
          val a = HashMap(1 -> "1")
          val b = HashMap(1 -> "2")
          def collision(a: (Int, String), b: (Int, String)) = {
            // shouldn't this be called with reversed order?
            println(a)
            a
          }
          val r = a.merge(b, collision)
          println(r)
          println(r(1))
      
      

      Output:

          (1,2)
          Map(1 -> 2)
          1
      

      Explanation:

      HashMap1 caches both the value and a key/value pair. As a result of the merge the value field is inconsistent to the kv field. When printing the map, the kv field is used, so the result is correct. When calling apply, the value field is used, and the result is wrong.

      Expected behavior:

      HashMap1.value and HashMap1.kv should never be able to become inconsistent. To fix this in HashMap1.updated0:

            if (hash == this.hash && key == this.key ) {
              val newKv = if (merger eq null) kv else merger(this.kv, kv)
              new HashMap1(key, hash, newKv ._2, newKv)
            } else {
              ...
      

      But there might be other places where this issue (inconsistency between kv and value) occurs.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                prokopec Aleksandar Prokopec
                Reporter:
                rklaehn Rüdiger Klaehn
              • Votes:
                0 Vote for this issue
                Watchers:
                4 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: