Scala HashSet java.lang.NegativeArraySizeException

Question

Following code throws exception after inserting 483180000 values. Is this expected. Is there any way to add more than a billion values into a mutable HashSet in Scala. Tried this code with Scala versions 2.11 and 2.12. Both versions throw same exception.

import scala.collection.mutable.HashSet

object TestApp extends App {
    val hs = HashSet[Int]()
    for (i <- 1 to Int.MaxValue) {
        hs += i
    }
}

java.lang.NegativeArraySizeException
        at scala.collection.mutable.FlatHashTable.growTable(FlatHashTable.scala:218)
        at scala.collection.mutable.FlatHashTable.addEntry(FlatHashTable.scala:160)
        at scala.collection.mutable.FlatHashTable.addEntry$(FlatHashTable.scala:148)
        at scala.collection.mutable.HashSet.addEntry(HashSet.scala:39)
        at scala.collection.mutable.FlatHashTable.addElem(FlatHashTable.scala:140)
        at scala.collection.mutable.FlatHashTable.addElem$(FlatHashTable.scala:139)
        at scala.collection.mutable.HashSet.addElem(HashSet.scala:39)
        at scala.collection.mutable.HashSet.$plus$eq(HashSet.scala:58)
        at alice.grid.collection.TestApp$.$anonfun$new$2(TestApp.scala:12)
        at scala.collection.immutable.Range.foreach$mVc$sp(Range.scala:155)
        at alice.grid.collection.TestApp$.delayedEndpoint$alice$grid$collection$TestApp$1(TestApp.scala:11)
        at alice.grid.collection.TestApp$delayedInit$body.apply(TestApp.scala:5)
        at scala.Function0.apply$mcV$sp(Function0.scala:34)
        at scala.Function0.apply$mcV$sp$(Function0.scala:34)
        at scala.runtime.AbstractFunction0.apply$mcV$sp(AbstractFunction0.scala:12)
        at scala.App.$anonfun$main$1$adapted(App.scala:76)
        at scala.collection.immutable.List.foreach(List.scala:388)
        at scala.App.main(App.scala:76)
        at scala.App.main$(App.scala:74)
        at alice.grid.collection.TestApp$.main(TestApp.scala:5)
        at alice.grid.collection.TestApp.main(TestApp.scala)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
        at java.lang.reflect.Method.invoke(Method.java:498)

I stumbled on a pure Java8 application about that a java.util.HashSet had a negative size. Totally impossible! You cannot empty an empty Set and have less items in there than before. So I guess it is a Java problem. Though the exception was exactly the same. Probably it is due a multithreaded environment where values have been twisted by several threads. — Dirk Schumacher, May 14 '19 at 10:27

ygor · Answer 1 · 2018-11-16T21:15:03.067

3

No, there is no way, how to add that many items. If you check the source code at (FlatHashTable.scala:218), you will find:

table = new Array[AnyRef](table.length * 2)

lenth is an integer. At certain point, multiplying it by two will cause an overflow and the result is a negative number. Java does not allow to create an array with size specified by negative number.

This is simply a limitation imposed by implementation of the HashSet.

edited Nov 16 '18 at 21:15

answered Nov 16 '18 at 21:10

ygor

1,726
1
11
23

Additionally, the max size of Java arrays is also limited roughly to max value of `Integer`, more precisely: https://stackoverflow.com/questions/3038392/do-java-arrays-have-a-maximum-size – ygor Nov 16 '18 at 21:14

Scala HashSet java.lang.NegativeArraySizeException

1 Answers1