Can a java Map return a size of -1?

Question

I have some code that creates a List, initialized with the size of a Map:

private Set<String> mKeys = new HashSet<String>(64);
....
List<String> keyList = new ArrayList<String>(mKeys.size());

I am seeing an exception: java.lang.IllegalArgumentException: Illegal Capacity: -1

Can a Map return a size of -1? I am looking at the source code for HashSet, which backed by a HashMap. The source code for HashMap shows the internals where elementCount is always decremented on a removeEntry() call. Also, the methods for HashMap.empty() reply on elementCount being == 0, which would return false if elementCount was -1.

Has anyone run into this before? I can code around it, but that feels like a hack, which makes me think I am doing something wrong with the current code.

EDIT: I was trying to simplify the problem originally. The Set I'm using is actually defined as

private static Set<String> mKeys = Collections.synchronizedSet(new HashSet<String>(64));

EDIT: The key here may be in the synchronizedSet. From the JavaDoc:

It is imperative that the user manually synchronize on the returned set when iterating over it:

Set s = Collections.synchronizedSet(new HashSet());
      ...
synchronized(s) {
    Iterator i = s.iterator(); // Must be in the synchronized block
    while (i.hasNext())
        foo(i.next());
}

Failure to follow this advice may result in non-deterministic behavior.

Non-deterministic behavior to me might include a size of -1. I need to go back and make sure I an synchronizing correctly when iterating over the set, but I suspect this is the problem.

Answer 1

According to the documentation, HashMap returns the number of element in the map, with no other conditions. A negative number of elements doesn't make any sense.

The only possible explanation I thought of was a Map of size Integer.MAX_VALUE + 1, which would result in a negative size. But AbstractMap#size() precise that if the Map size is greater than Integer.MAX_VALUE, Integer.MAX_VALUE is returned, so this case can't happen.

Also, I tried your code on my computer as follows:

Set<String> mKeys = new HashSet<String>(64);
System.out.println(mKeys.size());

I get the expected result: 0.

Maybe it is something related to the "...." part of your code?

Answer 2

HashSet size() method can return negative integer in multi threaded environment. Test 1 below will throw bunch of exceptions related to negative size. Test 2 is thread-safe approach, one of the solutions to avoid this.

Edit: Note: It seems to be an issue in Java 1.6 and older versions. When testing in Java 1.7, HashSet doesn't return negative size. Size doesn't change if object was not found and nothing was removed from a HashSet.

Test 1

package test;

import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

class TestHashSet1 {
    private static int NUMBER_OF_THREADS = 5;
    private static int COLLECTION_SIZE = 1000;

    public static void main(String[] arg) {
        final Set<Integer> toRemoveElement = new HashSet<Integer>();
        final Set<Integer> toStoreElements = new HashSet<Integer>();
        // populate collections for test
        for (int i = 0; i < COLLECTION_SIZE; i++) {
            Integer obj = new Integer(i);
            toRemoveElement.add(obj);
            toStoreElements.add(obj);
        }
        // two threads that will be using collection2 
        Runnable runnable = new Runnable() {
            @Override
            public void run() {
                for (Integer o : toStoreElements) {
                    removeObject(toRemoveElement, o);
                }
            }
        };
        Thread[] treads = new Thread[NUMBER_OF_THREADS];
        for (int i = 0; i < treads.length; i++) {
            treads[i] = new Thread(runnable);
        }
        for (Thread t : treads) {
            t.start();
        }
    }

    private static void removeObject(Set<Integer> toRemoveElement, Integer o) {
        toRemoveElement.remove(o);
        int size = toRemoveElement.size();
        if (size < 0) {
            System.out.println(size);
            try {
                toRemoveElement.toArray(new Integer[toRemoveElement.size()]);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
}

Test 2 - thread safe

package test;

import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

class TestHashSet2 {
    private static int NUMBER_OF_THREADS = 5;
    private static int COLLECTION_SIZE = 1000;

    public static void main(String[] arg) {
        final Set<Integer> toRemoveElement = Collections.synchronizedSet(new HashSet<Integer>()); // example of collection sync
        final Set<Integer> toStoreElements = new HashSet<Integer>();
        // populate collections for test
        for (int i = 0; i < COLLECTION_SIZE; i++) {
            Integer obj = new Integer(i);
            toRemoveElement.add(obj);
            toStoreElements.add(obj);
        }
        // two threads that will be using collection2 
        Runnable runnable = new Runnable() {
            @Override
            public void run() {
                for (Integer o : toStoreElements) {
                    removeObject(toRemoveElement, o);
                }
            }
        };
        Thread[] treads = new Thread[NUMBER_OF_THREADS];
        for (int i = 0; i < treads.length; i++) {
            treads[i] = new Thread(runnable);
        }
        for (Thread t : treads) {
            t.start();
        }
    }

    synchronized private static void removeObject(Set<Integer> toRemoveElement, Integer o) { // example of method sync
        toRemoveElement.remove(o);
        int size = toRemoveElement.size();
        if (size < 0) {
            System.out.println(size);
            try {
                toRemoveElement.toArray(new Integer[toRemoveElement.size()]);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
}