Verwenden eines Byte-Arrays als Map-Schlüssel

76

Sehen Sie ein Problem bei der Verwendung eines Byte-Arrays als Map-Schlüssel? Ich könnte es auch tun new String(byte[])und Stringdurchgehen, aber es ist einfacher zu bedienen byte[].

Shikhar
quelle

Antworten:

65

Das Problem ist, dass byte[]die Objektidentität für equalsund verwendet wird hashCode, so dass

byte[] b1 = {1, 2, 3}
byte[] b2 = {1, 2, 3}

wird in a nicht übereinstimmen HashMap. Ich sehe drei Möglichkeiten:

  1. Umschließen in a String, aber dann müssen Sie vorsichtig mit Codierungsproblemen sein (Sie müssen sicherstellen, dass das Byte -> String -> Byte die gleichen Bytes enthält).
  2. Verwendung List<Byte>(kann im Speicher teuer sein).
  3. Machen Sie Ihre eigene Wrapping-Klasse, schreiben Sie hashCodeund equalsverwenden Sie den Inhalt des Byte-Arrays.
Kathy Van Stone
quelle
3
Ich habe das String-Wrapping-Problem durch Hex-Codierung gelöst. Alternativ können Sie die Base64-Codierung verwenden.
Metadaddy
1
Die Option für die Wrapping / Handling-Klasse ist unkompliziert und sollte gut lesbar sein.
ZX9
79

Es ist in Ordnung, solange Sie nur Referenzgleichheit für Ihren Schlüssel wünschen - Arrays implementieren "Wertgleichheit" nicht so, wie Sie es wahrscheinlich möchten. Zum Beispiel:

byte[] array1 = new byte[1];
byte[] array2 = new byte[1];

System.out.println(array1.equals(array2));
System.out.println(array1.hashCode());
System.out.println(array2.hashCode());

druckt so etwas wie:

false
1671711
11394033

(Die tatsächlichen Zahlen sind irrelevant; die Tatsache, dass sie unterschiedlich sind, ist wichtig.)

Angenommen, Sie möchten tatsächlich Gleichheit, dann schlage ich vor, dass Sie Ihren eigenen Wrapper erstellen, der a enthält byte[]und Gleichheit und Hash-Code-Generierung entsprechend implementiert:

public final class ByteArrayWrapper
{
    private final byte[] data;

    public ByteArrayWrapper(byte[] data)
    {
        if (data == null)
        {
            throw new NullPointerException();
        }
        this.data = data;
    }

    @Override
    public boolean equals(Object other)
    {
        if (!(other instanceof ByteArrayWrapper))
        {
            return false;
        }
        return Arrays.equals(data, ((ByteArrayWrapper)other).data);
    }

    @Override
    public int hashCode()
    {
        return Arrays.hashCode(data);
    }
}

Beachten Sie, dass Sie Probleme haben, den Schlüssel erneut zu suchen , wenn Sie die Werte innerhalb des Byte-Arrays nach Verwendung von ByteArrayWrapper, als Schlüssel in einem HashMap(usw.) ändern. Sie können eine Kopie der Daten im ByteArrayWrapperKonstruktor erstellen, wenn Sie möchten Aber das ist natürlich eine Verschwendung von Leistung, wenn Sie wissen, dass Sie den Inhalt des Byte-Arrays nicht ändern werden.

BEARBEITEN: Wie in den Kommentaren erwähnt, können Sie dies auch verwenden ByteBuffer(insbesondere die ByteBuffer#wrap(byte[])Methode). Ich weiß nicht, ob es wirklich das Richtige ist, angesichts all der zusätzlichen Fähigkeiten, ByteBufferdie Sie nicht benötigen, aber es ist eine Option.

Jon Skeet
quelle
@dfa: Der "instanceof" -Test behandelt den Nullfall.
Jon Skeet
4
Ein paar andere Dinge, die Sie zur Wrapper-Implementierung hinzufügen könnten: 1. Erstellen Sie eine Kopie des Bytes [] bei der Erstellung, um sicherzustellen, dass das Objekt unveränderlich ist. Dies bedeutet, dass keine Gefahr besteht, dass sich der Hash-Code Ihres Schlüssels im Laufe der Zeit ändert. 2. Berechnen und speichern Sie den Hash-Code einmal vorab (vorausgesetzt, die Geschwindigkeit ist wichtiger als der Speicheraufwand).
Adamski
2
@Adamski: Ich erwähne die Möglichkeit des Kopierens am Ende der Antwort. In einigen Fällen ist es das Richtige, in anderen nicht. Ich möchte es wahrscheinlich zu einer Option machen (möglicherweise statische Methoden anstelle von Konstruktoren - copyOf und wrapperAround). Beachten Sie, dass Sie das zugrunde liegende Array ohne Kopieren ändern können, bis Sie zuerst den Hash nehmen und auf Gleichheit prüfen, was in einigen Situationen hilfreich sein kann.
Jon Skeet
Ups - Entschuldigung Jon; Ich habe diesen Teil Ihrer Antwort verpasst.
Adamski
3
Ich wollte nur darauf hinweisen, dass die Klasse java.nio.ByteBuffer im Wesentlichen alles tut, was Ihr Wrapper tut, obwohl Sie sie nur verwenden sollten, wenn sich der Inhalt des Byte-Arrays nicht ändert. Möglicherweise möchten Sie Ihre Antwort ändern, um sie zu erwähnen.
Ed Anuff
46

Wir können dafür ByteBuffer verwenden (Dies ist im Grunde der Byte [] -Wrapper mit einem Komparator).

HashMap<ByteBuffer, byte[]> kvs = new HashMap<ByteBuffer, byte[]>();
byte[] k1 = new byte[]{1,2 ,3};
byte[] k2 = new byte[]{1,2 ,3};
byte[] val = new byte[]{12,23,43,4};

kvs.put(ByteBuffer.wrap(k1), val);
System.out.println(kvs.containsKey(ByteBuffer.wrap(k2)));

wird gedruckt

true
byte_array
quelle
2
+1 für den leichtesten Byte-Array-Wrapper (glaube ich ...)
Nicholas
7
Dies funktioniert mit ByteBuffer.wrap () einwandfrei. Seien Sie jedoch vorsichtig, wenn der Inhalt des ByteBuffers mithilfe einiger put () -Aufrufe erstellt wurde, um ein zusammengesetztes Schlüsselbyte-Array zu erstellen. In diesem Fall muss auf den letzten Aufruf von put () ein Aufruf von rewind () folgen. Andernfalls gibt equals () true zurück, auch wenn die zugrunde liegenden Bytearrays unterschiedliche Daten enthalten.
RenniePet
Dies wäre eine gute Lösung, aber wenn Sie die Karte serialisieren möchten (wie in meinem Fall), können Sie diesen Ansatz nicht verwenden.
501 - nicht implementiert
Beachten Sie Folgendes: "Da Puffer-Hash-Codes inhaltsabhängig sind, ist es nicht ratsam, Puffer als Schlüssel in Hash-Maps oder ähnlichen Datenstrukturen zu verwenden, es sei denn, es ist bekannt, dass sich deren Inhalt nicht ändert." ( Docs.oracle.com/javase/7 / docs / api / java / nio /… )
LMD
Sie sollten ByteBuffer.wrap(k1.clone())eine defensive Kopie des Arrays erstellen. Wenn nicht, wenn jemand das Array ändert, werden schlimme Dinge passieren. In einem Debugger hat ein ByteBuffer im Vergleich zu einem String einen hohen internen Status. Es sieht also so aus, als wäre dies keine wirklich einfache Lösung in Bezug auf den Speicheraufwand.
Simbo1905
12

Sie könnten verwenden java.math.BigInteger. Es hat einen BigInteger(byte[] val)Konstruktor. Es ist ein Referenztyp und kann daher als Schlüssel für Hashtabellen verwendet werden. Und .equals()und .hashCode()sind wie für die jeweiligen Ganzzahlen definiert, was bedeutet, dass BigInteger eine konsistente Semantik gleich als Byte [] -Array hat.

Artem Oboturov
quelle
16
Klingt attraktiv, ist aber falsch, da zwei Arrays, die sich nur in führenden Nullelementen (z. B. {0,100}und {100}) unterscheiden, dieselbe BigInteger
leonbloy
Guter Punkt @leonbloy. Es könnte eine Problemumgehung geben: Durch Hinzufügen einer festen Nicht-Null-Leitbyte-Konstante, die erforderlich ist, muss jedoch ein Wrapper um den BigInteger-Konstruktor geschrieben werden, und wir kehren zu Jons Antwort zurück.
Artem Oboturov
Die Antwort von @ vinchan wäre angemessener, da es kein Problem mit null führenden Bytes geben würde.
Artem Oboturov
5

Ich bin sehr überrascht, dass die Antworten nicht auf die einfachste Alternative hinweisen.

Ja, es ist nicht möglich, eine HashMap zu verwenden, aber niemand hindert Sie daran, eine SortedMap als Alternative zu verwenden. Das einzige, was ist, einen Komparator zu schreiben, der die Arrays vergleichen muss. Es ist nicht so performant wie eine HashMap, aber wenn Sie eine einfache Alternative suchen, können Sie loslegen (Sie können SortedMap durch Map ersetzen, wenn Sie die Implementierung ausblenden möchten):

 private SortedMap<int[], String>  testMap = new TreeMap<>(new ArrayComparator());

 private class ArrayComparator implements Comparator<int[]> {
    @Override
    public int compare(int[] o1, int[] o2) {
      int result = 0;
      int maxLength = Math.max(o1.length, o2.length);
      for (int index = 0; index < maxLength; index++) {
        int o1Value = index < o1.length ? o1[index] : 0;
        int o2Value = index < o2.length ? o2[index] : 0;
        int cmp     = Integer.compare(o1Value, o2Value);
        if (cmp != 0) {
          result = cmp;
          break;
        }
      }
      return result;
    }
  }

Diese Implementierung kann für andere Arrays angepasst werden. Das einzige, was Sie beachten müssen, ist, dass gleiche Arrays (= gleiche Länge mit gleichen Elementen) 0 zurückgeben müssen und dass Sie eine deterministische Reihenfolge haben

Thorsten S.
quelle
Schöne Lösung mit dem großen Vorteil, keine zusätzlichen Objekte zu erstellen. Sehr kleiner Fehler, wenn Arrays nicht dieselbe Länge haben, aber das längste nur 0 nach einer kürzeren Länge hat. Außerdem hilft die Verwaltung der Bestellung wahrscheinlich dabei, die Baumdurchquerung zu beschleunigen. +1!
jmspaggi
1

Ich glaube, dass Arrays in Java die Methoden hashCode()und nicht unbedingt equals(Object)intuitiv implementieren . Das heißt, zwei identische Byte-Arrays teilen nicht notwendigerweise denselben Hash-Code und sie behaupten nicht notwendigerweise, gleich zu sein. Ohne diese beiden Merkmale verhält sich Ihre HashMap unerwartet.

Daher empfehle ich gegen Verwendung byte[]als Schlüssel in einer HashMap.

Adam Paynter
quelle
Ich nehme an, mein Wortlaut war etwas falsch. Ich habe die Situation berücksichtigt, in der das gleiche Byte-Array sowohl zum Einfügen in die Hash-Map als auch zum Abrufen von der Hash-Map verwendet wird. In diesem Fall sind "beide" Byte-Arrays identisch UND teilen denselben Hash-Code.
Adam Paynter
1

Sie sollten eine Klasse wie ByteArrKey erstellen und Hashcode und gleiche Methoden überladen. Denken Sie an den Vertrag zwischen ihnen.

Dies gibt Ihnen mehr Flexibilität, da Sie 0 Einträge überspringen können, die am Ende des Byte-Arrays angehängt werden, insbesondere wenn Sie nur einen Teil aus dem anderen Byte-Puffer kopieren.

Auf diese Weise entscheiden Sie, wie beide Objekte gleich sein sollen.

Milind Patil
quelle
0

Ich sehe Probleme, da Sie Arrays.equals und Array.hashCode anstelle von Standard-Array-Implementierungen verwenden sollten

dfa
quelle
Und wie würden Sie die HashMap dazu bringen, diese zu verwenden?
Michael Borgwardt
siehe Jon Skeets Antwort (ein Byte-Array-Wrapper)
dfa
0

Arrays.toString (Bytes)

df.
quelle
1
Könnte verwendet werden, ist aber nicht sehr effizient. Wenn Sie diesen Weg gehen möchten, können Sie stattdessen die Base64-Codierung verwenden.
Maarten Bodewes
0

Sie können das Byte [] auch mit Base32 oder Base64 in eine 'sichere' Zeichenfolge konvertieren, zum Beispiel:

byte[] keyValue = new byte[] {…};
String key = javax.xml.bind.DatatypeConverter.printBase64Binary(keyValue);

Natürlich gibt es viele Varianten der oben genannten, wie:

String key = org.apache.commons.codec.binary.Base64.encodeBase64(keyValue);
Christof R.
quelle
0

Hier ist eine Lösung mit TreeMap, Comparator-Schnittstelle und Java-Methode java.util.Arrays.equals (Byte [], Byte []);

HINWEIS: Die Reihenfolge in der Karte ist bei dieser Methode nicht relevant

SortedMap<byte[], String> testMap = new TreeMap<>(new ArrayComparator());

static class ArrayComparator implements Comparator<byte[]> {
    @Override
    public int compare(byte[] byteArray1, byte[] byteArray2) {

        int result = 0;

        boolean areEquals = Arrays.equals(byteArray1, byteArray2);

        if (!areEquals) {
            result = -1;
        }

        return result;
    }
}
matdev
quelle
0

Außerdem können wir wie folgt eine eigene benutzerdefinierte ByteHashMap erstellen.

ByteHashMap byteMap = new ByteHashMap();
byteMap.put(keybyteArray,valueByteArray);

Hier ist die komplette Implementierung

public class ByteHashMap implements Map<byte[], byte[]>, Cloneable,
        Serializable {

    private Map<ByteArrayWrapper, byte[]> internalMap = new HashMap<ByteArrayWrapper, byte[]>();

    public void clear() {
        internalMap.clear();
    }

    public boolean containsKey(Object key) {
        if (key instanceof byte[])
            return internalMap.containsKey(new ByteArrayWrapper((byte[]) key));
        return internalMap.containsKey(key);
    }

    public boolean containsValue(Object value) {
        return internalMap.containsValue(value);
    }

    public Set<java.util.Map.Entry<byte[], byte[]>> entrySet() {
        Iterator<java.util.Map.Entry<ByteArrayWrapper, byte[]>> iterator = internalMap
                .entrySet().iterator();
        HashSet<Entry<byte[], byte[]>> hashSet = new HashSet<java.util.Map.Entry<byte[], byte[]>>();
        while (iterator.hasNext()) {
            Entry<ByteArrayWrapper, byte[]> entry = iterator.next();
            hashSet.add(new ByteEntry(entry.getKey().data, entry
                    .getValue()));
        }
        return hashSet;
    }

    public byte[] get(Object key) {
        if (key instanceof byte[])
            return internalMap.get(new ByteArrayWrapper((byte[]) key));
        return internalMap.get(key);
    }

    public boolean isEmpty() {
        return internalMap.isEmpty();
    }

    public Set<byte[]> keySet() {
        Set<byte[]> keySet = new HashSet<byte[]>();
        Iterator<ByteArrayWrapper> iterator = internalMap.keySet().iterator();
        while (iterator.hasNext()) {
            keySet.add(iterator.next().data);
        }
        return keySet;
    }

    public byte[] put(byte[] key, byte[] value) {
        return internalMap.put(new ByteArrayWrapper(key), value);
    }

    @SuppressWarnings("unchecked")
    public void putAll(Map<? extends byte[], ? extends byte[]> m) {
        Iterator<?> iterator = m.entrySet().iterator();
        while (iterator.hasNext()) {
            Entry<? extends byte[], ? extends byte[]> next = (Entry<? extends byte[], ? extends byte[]>) iterator
                    .next();
            internalMap.put(new ByteArrayWrapper(next.getKey()), next
                    .getValue());
        }
    }

    public byte[] remove(Object key) {
        if (key instanceof byte[])
            return internalMap.remove(new ByteArrayWrapper((byte[]) key));
        return internalMap.remove(key);
    }

    public int size() {
        return internalMap.size();
    }

    public Collection<byte[]> values() {
        return internalMap.values();
    }

    private final class ByteArrayWrapper {
        private final byte[] data;

        public ByteArrayWrapper(byte[] data) {
            if (data == null) {
                throw new NullPointerException();
            }
            this.data = data;
        }

        public boolean equals(Object other) {
            if (!(other instanceof ByteArrayWrapper)) {
                return false;
            }
            return Arrays.equals(data, ((ByteArrayWrapper) other).data);
        }

        public int hashCode() {
            return Arrays.hashCode(data);
        }
    }

    private final class ByteEntry implements Entry<byte[], byte[]> {
        private byte[] value;
        private byte[] key;

        public ByteEntry(byte[] key, byte[] value) {
            this.key = key;
            this.value = value;
        }

        public byte[] getKey() {
            return this.key;
        }

        public byte[] getValue() {
            return this.value;
        }

        public byte[] setValue(byte[] value) {
            this.value = value;
            return value;
        }

    }
}
Rakesh Chaudhari
quelle
0

Andere Antworten haben nicht darauf hingewiesen, dass nicht alle byte[]in einzigartig verdeckt sind String. Ich bin in diese Falle geraten und habe new String(byteArray)als Schlüssel für eine Map nur festgestellt, dass viele negative Bytes derselben Zeichenfolge zugeordnet sind. Hier ist ein Test, der dieses Problem demonstriert:

    @Test
    public void testByteAsStringMap() throws Exception {
        HashMap<String, byte[]> kvs = new HashMap<>();
        IntStream.range(Byte.MIN_VALUE, Byte.MAX_VALUE).forEach(b->{
            byte[] key = {(byte)b};
            byte[] value = {(byte)b};
            kvs.put(new String(key), value);
        });
        Assert.assertEquals(255, kvs.size());
    }

Es wird werfen:

java.lang.AssertionError: Erwartet: 255 Ist: 128

Dies geschieht, weil a Stringeine Folge von Zeichencodepunkten ist und jede Konvertierung von a byte[]auf einer Bytecodierung basiert. Im obigen Fall ordnet die Plattform-Standardcodierung viele negative Bytes demselben Zeichen zu. Eine andere Tatsache Stringist, dass es immer eine Kopie seines internen Zustands nimmt und gibt. Wenn die ursprünglichen Bytes von einer StringKopie stammen, Stringwird eine zweite Kopie benötigt, um sie als Schlüssel für eine Karte zu verwenden. Das kann viel Müll erzeugen, der vermeidbar sein könnte.

Hier gibt es eine gute Antwort, die die Verwendung java.nio.ByteBuffermit vorschlägt ByteBuffer.wrap(b). Das Problem dabei ist, dass byte[]es veränderlich ist und keine Kopie benötigt. Sie müssen also darauf achten, eine defensive Kopie aller Arrays zu erstellen, die an Sie übergeben wurden, da ByteBuffer.wrap(b.clone())sonst die Schlüssel Ihrer Karte beschädigt werden. Wenn Sie sich das Ergebnis einer Karte mit ByteBufferSchlüsseln in einem Debugger ansehen, werden Sie feststellen, dass die Puffer viele interne Referenzen enthalten, mit denen das Lesen und Schreiben aus jedem Puffer verfolgt werden kann. Die Objekte sind also viel schwerer als das Einwickeln in eine einfache String. Schließlich enthält sogar eine Zeichenfolge mehr Status als erforderlich. Wenn ich es in meinem Debugger betrachte, speichert es Zeichen als Zwei-Byte-UTF16-Array und speichert auch einen Vier-Byte-Hashcode.

Mein bevorzugter Ansatz ist es, Lombok zur Kompilierungszeit das Boilerplate generieren zu lassen, um einen leichten Byte-Array-Wrapper zu erstellen, der keinen zusätzlichen Status speichert:

import lombok.Data;
import lombok.EqualsAndHashCode;
import lombok.ToString;

@ToString
@EqualsAndHashCode
@Data(staticConstructor="of")
class ByteSequence {
    final byte[] bytes;
}

Dies besteht dann den Test, der überprüft, ob alle möglichen Bytes einer eindeutigen Zeichenfolge zugeordnet sind:

    byte[] bytes(int b){
        return new byte[]{(byte)b};
    }

    @Test
    public void testByteSequenceAsMapKey() {
        HashMap<ByteSequence, byte[]> kvs = new HashMap<>();
        IntStream.range(Byte.MIN_VALUE, Byte.MAX_VALUE).forEach(b->{
            byte[] key = {(byte)b};
            byte[] value = {(byte)b};
            kvs.put(ByteSequence.of(key), value);
        });
        Assert.assertEquals(255, kvs.size());
        byte[] empty = {};
        kvs.put(ByteSequence.of(empty), bytes(1));
        Assert.assertArrayEquals(bytes(1), kvs.get(ByteSequence.of(empty)));
    }

Sie müssen sich dann keine Sorgen mehr machen, ob die Gleichheits- und Hashcode-Logik korrekt ist, da sie von Lombok bereitgestellt wird, wo dies Arrays.deepEqualsunter https://projectlombok.org/features/EqualsAndHashCode dokumentiert ist. Beachten Sie, dass Lombok nicht nur eine Laufzeitabhängigkeit ist Wenn Sie eine Abhängigkeit zur Kompilierungszeit haben, können Sie ein OpenSource-Plugin in Ihre IDE installieren, sodass Ihre IDE alle generierten Boilerplate-Methoden "sieht".

Bei dieser Implementierung müssen Sie sich immer noch Gedanken über die Veränderlichkeit des Bytes machen. Wenn Ihnen jemand eine byte[]möglicherweise mutierte Karte übergibt , sollten Sie eine defensive Kopie erstellen, indem Sie clone():

kvs.put(ByteSequence.of(key.clone()), value);
simbo1905
quelle