user3295962 user3295962 - 3 months ago 29
Scala Question

Scala: why mutable Map and immutable Map have different result on same custom class instance as key?

My Scala version is

2.11.8
and Java version is
1.8.0_77
.

I had a custom class
V
extends
Ordered[V]
. I defined custom
compare
and
equals
. I want
V
instances have
>
,
<
,
>=
,
<=
operators and can be thought equal when some specific attribute of them are equal.

Here is the simplified code extracted from my project:

class V(val value: Int, val score: Int = 0) extends Ordered[V] {
def compare(that: V): Int = this.score compare that.score

override def equals(that: Any): Boolean = that match {
case that: V => this.value == that.value
case _ => false
}
}

val a = new V(1, 2)
val b = new V(1, 3)

// return true because a.value == b.value
a == b


And strangely:

import collection.mutable.ArrayBuffer

val mm = collection.mutable.Map(a -> ArrayBuffer(0, 1), b -> ArrayBuffer(2, 3, 4))
val im = collection.immutable.Map(a -> ArrayBuffer(0, 1), b -> ArrayBuffer(2, 3, 4))

// return scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer()
mm.getOrElse(new V(1, 0), ArrayBuffer())

// return scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(2, 3, 4)
im.getOrElse(new V(1, 0), ArrayBuffer())


Why the result of
immutable.Map
and
mutable.Map
are different?

But when I define
hashCode
for
V
:

class V(val value: Int, val score: Int = 0) extends Ordered[V] {
def compare(that: V): Int = this.score compare that.score

override def hashCode: Int = value // new method here!

override def equals(that: Any): Boolean = that match {
case that: V => this.value == that.value
case _ => false
}
}

val a = new V(1, 2)
val b = new V(1, 3)

a == b // true


And this time, the result are the same:

val mm = collection.mutable.Map(a -> ArrayBuffer(0, 1), b -> ArrayBuffer(2, 3, 4))
val im = collection.immutable.Map(a -> ArrayBuffer(0, 1), b -> ArrayBuffer(2, 3, 4))

// both return scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(2, 3, 4)
mm.getOrElse(new V(1, 0), ArrayBuffer())
im.getOrElse(new V(1, 0), ArrayBuffer())


Why does
hashCode
definition affect the result of mutable Map on custom class instance as key?

Answer

Why does hashCode definition affect the result of mutable Map on custom class instance as key

immutable.Map has a custom implementation up to 4 key value pairs (Map1, ...., Map4). The get operation for those customized implementations doesn't use an internal bucket array for hashcodes which maps to an object arrays where the values are actually stored, it simply stores key-value pairs as fields.

For example, here is Map1.get which is invoked by getOrElse:

class Map1[A, +B](key1: A, value1: B) extends AbstractMap[A, B] 
                                      with Map[A, B] with Serializable {
    def get(key: A): Option[B] =
      if (key == key1) Some(value1) else None

On the contrary, mutable.Map is a backed by a mutable.HashMap which uses a bucket to find the objects hashcode, which in turn point to the values in the object array. The objects inside those buckets are stored by their hashcode. Since your object doesn't implement a custom hashcode method, it derives it's hashcode from Any (Object). Thus, the mutable map isn't able to find the value inside those buckets, as equal values in your custom implementation don't have equal hashcodes.

Once you implement a custom hashcode method, and it obeys the rule that all equal instances should yield the same hashcode, HashMap is able to find the right bucket where your object is stored and invoke equals on the two objects, to see they're equal.