trove hashmap fail when size approaching half int max value

[Rob Eden]

Originally reported by Guo Jiacheng

Hi all,

When a hashmap fulled, the hash map try to double its capacity and find next prime number. However, this behavior is problematic when the size is approaching the half of int max value. It results int overflow, while actually data can be filled in the int max value and Int.MaxValue is actually a prime number needed by the algorithm.

The offending code is in gnu.trove.impl.hash.THash line 387 in

protected final void [More ...] postInsertHook( boolean usedFreeSlot ) {
int newCapacity = _size > _maxSize ? PrimeFinder.nextPrime( capacity() << 1 ) : capacity();

here the new capacity is not checked against Int overflow. and do not even ensure newCapacity is larger than original.

Thanks,

Jiacheng Guo

Original SF bug

[Rob Eden]

Not sure there's much we're going to be able to do with this given the current design of a single array list. We could check for overflow in this location, but the backing array can't be bigger than 2^31 elements. Best solution would currently be to use multiple maps. You can also tweak your load factor to leave less free space in the array, but this would have performance ramifications.

Theoretically we could develop and implementation that uses multiple backing arrays or Unsafe, though there's nothing like this currently in the works.