Scala 2.8 mutable.Set 空处理

Question

使用 scala，2.8:

import scala.collection.mutable
import mutable.MultiMap
val m = new mutable.HashMap[String, mutable.Set[String]] with MultiMap[String, String]
m.addBinding("key", null)
m exists { _._2 contains null }

打印错误

m exists { _._2 isEmpty }

打印错误

m("key").size

打印 1

如何找到通过值为 null 的 addBinding 调用添加的第一个(或任何)键？

Answer 1

在 Scala 2.7.7 中，添加 null 时会立即得到一个 NullPointer:

scala> val s = new scala.collection.mutable.HashSet[String]
s: scala.collection.mutable.HashSet[String] = Set()

scala> s += null
java.lang.NullPointerException
    at scala.collection.mutable.FlatHashTable$class.elemHashCode(FlatHashTable.scala:144)
    at scala.collection.mutable.HashSet.elemHashCode(HashSet.scala:31)
    at scala.collection.mutable.FlatHashTable$class.addEntry(FlatHashTable.scala:66)
    at scala.collection.mutable.HashSet.addEntry(HashSet.scala:31)
    at scala.collection.mutable.HashSet.$plus$eq(HashSet.s...

使用 Scala 2.8.0.RC7，情况不再如此。然而，作为Randall has observed ，行为也不完全一致:

scala> import scala.collection.mutable.HashSet
import scala.collection.mutable.HashSet

scala> val s = new HashSet[String]
s: scala.collection.mutable.HashSet[String] = Set()

scala> s += null
res0: s.type = Set()

scala> s += null
res1: s.type = Set()

scala> s.size
res2: Int = 2

scala> s.head
java.util.NoSuchElementException: next on empty iterator
    at scala.collection.Iterator$$anon$3.next(Iterator.scala:29)
    at scala.collection.Iterator$$anon$3.next(Iterator.scala:27)
    at scala.collection.mutable.FlatHashTable$$anon$1.next(FlatHashTable.scala:176)
    at scala.collection.IterableLike$class.head(IterableLike.scala:102)
    at scala.collection.mutable.HashSet.head(HashSet.scala:38)
    at .(:8)



<p>Most of the work when adding an entry is done in
<a href="https://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/src/library/scala/collection/mutable/FlatHashTable.scala" rel="noreferrer noopener nofollow">FlatHashTable</a>
When you add an entery, <code>addEntry</code> is invoked, which looks like this:</p>

<pre><code>
/** The actual hash table.
*/
@transient protected var table: Array[AnyRef] = new Array(initialCapacity)

def addEntry(elem: A) : Boolean = {
var h = index(elemHashCode(elem))
var entry = table(h)
while (null != entry) {
if (entry == elem) return false
h = (h + 1) % table.length
entry = table(h)
}
table(h) = elem.asInstanceOf[AnyRef]
tableSize = tableSize + 1
if (tableSize >= threshold) growTable()
true
}
</code></pre>

<p><code>null.asInstanceOf[AnyRef]</code> just gives you back <code>null</code>, and the <code>elemHashCode(elem)<code> returns zero if the elem is <code>null</code>. So in this case, the element with index zero is 'initialized' with <code>null</code> (which is the value it already had), but the tableSize is increased. This explains the results that are seen in the REPL.</code></code></p><code><code>

<p>If you call <code>head</code> on the Set, ultimately the iterator in <code>FlatHashTable</code> is called, as can be seen from the stacktrace. This is implemented as follows:</p>

<pre><code>
iterator = new Iterator[A] {
private var i = 0
def hasNext: Boolean = {
while (i < table.length && (null == table(i))) i += 1
i < table.length
}
def next(): A =
if (hasNext) { i += 1; table(i - 1).asInstanceOf[A] }
else Iterator.empty.next
}
</code></pre>

</code></code><p><code><code><code>hasNext</code> will return false, since the element that we stored in the Array is null, therefore, the call to <code>next</code> will call Iterator.empty.next</code>, which throws an exception.
Since adding null</code> to a HashSet is not handled consistently in Scala 2.8, this indeed looks like a bug. Also, as already has been remarked, it provides another good reason to stay away from using null where possible.</p>

<p><strong>Edit</strong> Since I couldn't find a ticket for this, I <a href="https://lampsvn.epfl.ch/trac/scala/ticket/3630" rel="noreferrer noopener nofollow">added it</a>.</p>