Kann eine Java Map eine Größe von -1 zurückgeben?

Question

Ich habe einige Code, der eine Liste erstellt, initialisiert mit der Größe einer Karte:

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

Ich erhalte eine Ausnahme: java.lang.IllegalArgumentException: Unzulässige Kapazität: -1

Kann eine Map eine Größe von -1 zurückgeben? Ich schaue mir den Quellcode für HashSet an, das von einer HashMap unterstützt wird. Der Quellcode für HashMap zeigt die Interna, wo elementCount bei einem removeEntry()-Aufruf immer dekrementiert wird. Außerdem setzen die Methoden für HashMap.empty() voraus, dass elementCount == 0 ist, was false zurückgeben würde, wenn elementCount -1 wäre.

Ist das schon mal jemandem aufgefallen? Ich kann Code um es, aber das fühlt sich wie ein Hack, die mich denken, ich bin etwas falsch mit dem aktuellen Code zu tun macht.

EDIT: Ich habe versucht, das Problem ursprünglich zu vereinfachen. Die Menge, die ich verwende, ist tatsächlich definiert als

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

EDIT: Der Schlüssel liegt hier möglicherweise im synchronizedSet. Aus der JavaDoc:

Es ist unbedingt erforderlich, dass der Benutzer die zurückgegebene Menge manuell synchronisiert, wenn er darüber iteriert:

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

Die Nichtbeachtung dieses Hinweises kann zu nicht-deterministischem Verhalten führen.

Nicht-deterministisches Verhalten zu mir könnte eine Größe von -1 umfassen. Ich muss zurück gehen und sicherstellen, dass ich eine Synchronisierung richtig, wenn über die Menge iteriert, aber ich vermute, dass dies das Problem ist.

Answer 1

Die Methode HashSet size() kann in einer Umgebung mit mehreren Threads eine negative ganze Zahl zurückgeben. Test 1 unten wird eine Reihe von Ausnahmen im Zusammenhang mit negativer Größe auslösen. Test 2 ist ein thread-sicherer Ansatz, eine der Lösungen, um dies zu vermeiden.

Bearbeiten: Anmerkung: Es scheint ein Problem in Java 1.6 und älteren Versionen zu sein. Beim Testen in Java 1.7 gibt HashSet keine negative Größe zurück. Die Größe ändert sich nicht, wenn kein Objekt gefunden wurde und nichts aus einem HashSet entfernt wurde.

Prüfung 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();
            }
        }
    }
}

Prüfung 2 - fadensicher

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();
            }
        }
    }
}

Answer 2

Der Dokumentation zufolge gibt HashMap die Anzahl der Elemente in der Map zurück, ohne weitere Bedingungen. Eine negative Anzahl von Elementen macht keinen Sinn.

Die einzige mögliche Erklärung, die mir einfiel, war eine Map der Größe Integer.MAX_VALUE + 1, was zu einer negativen Größe führen würde. Aber AbstractMap#size() präzisiert, dass, wenn die Größe der Map größer als Integer.MAX_VALUE ist, Integer.MAX_VALUE zurückgegeben wird, so dass dieser Fall nicht eintreten kann.

Außerdem habe ich Ihren Code auf meinem Computer wie folgt ausprobiert:

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

Ich erhalte das erwartete Ergebnis: 0.

Vielleicht hängt es mit dem Teil "...." Ihres Codes zusammen?

Answer 3

Bei HashMap sollte size() nicht -1 zurückgeben. size() gibt jedoch size zurück, ein privates Feld von HashMap, das unabhängig verwaltet wird, anstatt bei jedem Aufruf die Anzahl der Mitglieder zu berechnen (da die Tabelle der Einträge als verknüpfte Liste (NB, nicht LinkedList) gespeichert ist). Theoretisch könnte also ein Fehler aufgetreten sein, der dazu geführt hat, dass die Größe nicht mit der tatsächlichen Anzahl der Einträge in der Tabelle übereinstimmt (z. B. durch Überschreiten der Integer.MAX_VALUES-Einträge). Es erscheint jedoch unwahrscheinlich, dass dies nicht bereits bekannt ist.