Pytanie w sprawie hashmap, java, bytearray – Używanie tablicy bajtów jako klucza Map

70

Czy widzisz jakiś problem z użyciem tablicy bajtów jako klucza Map? Mogę też to zrobićnew String(byte[]) i hash przezString ale jest prostszy w użyciubyte[].

Twoja odpowiedź

10   odpowiedzi
3

że odpowiedzi nie wskazują na najprostszą alternatywę.

Tak, nie jest możliwe użycie mapy HashMap, ale nikt nie uniemożliwia korzystania z SortedMap jako alternatywy. Jedyną rzeczą jest napisanie Komparatora, który musi porównać tablice. Nie jest tak skuteczny jak HashMap, ale jeśli chcesz prostej alternatywy, tutaj (możesz zastąpić SortedMap mapą, jeśli chcesz ukryć implementację):

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

Ta implementacja może być dostosowana dla innych tablic, jedyną rzeczą, o której musisz być świadomy, jest to, że równe tablice (= równa długość z równymi członami) muszą zwracać 0 i że masz porządek deterministyczny

Ładne rozwiązanie z ogromną korzyścią z nie tworzenia dodatkowych obiektów. Bardzo mały błąd, jeśli tablice nie są tej samej długości, ale najdłuższy ma tylko 0 po krótszej długości. Również zarządzanie kolejnością prawdopodobnie przyspiesza przejście drzewa. +1! jmspaggi
56

Problemem jestbyte[] używa tożsamości obiektu dlaequals ihashCode, więc to

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

nie pasuje do aHashMap. Widzę trzy opcje:

Zawijanie wString, ale musisz uważać na problemy z kodowaniem (musisz się upewnić, że bajt -> String -> bajt daje te same bajty).Posługiwać sięList<Byte> (może być kosztowna w pamięci).Zrób własną klasę pakowania, pisząchashCode iequals użyć zawartości tablicy bajtów.
Rozwiązałem problem owijania napisów za pomocą kodowania szesnastkowego. Możesz alternatywnie użyć kodowania base64. metadaddy
Opcja klasy owijania / obsługi jest prosta i powinna być bardzo czytelna. ZX9
1

hashCode() iequals(Object) intuicyjnie. Oznacza to, że dwie identyczne tablice bajtów niekoniecznie będą miały ten sam kod skrótu i ​​niekoniecznie będą twierdzić, że są równe. Bez tych dwóch cech twoja HashMap będzie zachowywać się niespodziewanie.

Dlatego polecamprzeciwko za pomocąbyte[] jako klucze w HashMapie.

s / niekoniecznie / nie / Michael Borgwardt
Przypuszczam, że moje sformułowanie było trochę nie tak. Uwzględniałem sytuację, w której tablica bajtów SAME jest używana zarówno do wstawiania do mapy mieszania, jak i do pobierania z mapy mieszania. W takim przypadku „obie” tablice bajtów są identyczne ORAZ dzielą ten sam kod skrótu. Adam Paynter
0

interfejs komparatora i metodę java java.util.Arrays.equals (bajt [], byte []);

UWAGA: Zamawianie na mapie nie ma znaczenia dla tej metody

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;
    }
}
0

ponieważ zamiast domyślnych implementacji tablicy należy użyć Arrays.equals i Array.hashCode

A jak byś je wykorzystał? Michael Borgwardt
zobacz odpowiedź Jona Skeeta (opakowanie tablicy bajtów) dfa
1

i równe metody, pamiętaj o umowie między nimi.

Zapewni to większą elastyczność, ponieważ można pominąć 0 pozycji, które są dołączane na końcu tablicy bajtów, szczególnie jeśli kopiujesz tylko część z innego bufora bajtów.

W ten sposób zdecydujesz, w jaki sposób oba obiekty POWINNY być równe.

39

owe [] z komparatorem)

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

wydrukuje

true
Należy zauważyć, że: „Ponieważ kody skrótu bufora są zależne od zawartości, nie zaleca się używania buforów jako kluczy w mapach mieszania lub podobnych strukturach danych, chyba że wiadomo, że ich zawartość nie ulegnie zmianie”.docs.oracle.com/javase/7/docs/api/java/nio/…) LMD
Byłoby to fajne rozwiązanie, ale jeśli chcesz serializować mapę (jak w moim przypadku), nie możesz użyć tego podejścia. 501 - not implemented
Działa to poprawnie z ByteBuffer.wrap (), ale bądź ostrożny, jeśli zawartość ByteBuffera została utworzona przy użyciu kilku wywołań put () w celu utworzenia złożonej tablicy bajtów klucza. W tym przypadku po ostatnim wywołaniu put () musi nastąpić wywołanie rewind () - w przeciwnym razie equals () zwraca wartość true, nawet jeśli podstawowe tablice bajtów zawierają różne dane. RenniePet
+1 dla najlżejszego opakowania tablicy bajtowej (myślę ...) Nicholas
72

jeśli tylko chcesz mieć równość dla klucza - tablice nie implementują „równości wartości” w sposób, który prawdopodobnie chcesz. Na przykład:

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

drukuje coś w stylu:

false
1671711
11394033

(Rzeczywiste liczby są nieistotne; fakt, że są różne, jest ważny.)

Zakładając ciętak właściwie chcę równości, proponuję stworzyć własny wrapper zawierającybyte[] i odpowiednio implementuje generowanie kodu równości i kodu skrótu:

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

Zauważ, że jeśli zmienisz wartości w tablicy bajtów po użyciuByteArrayWrapper, jako klucz w aHashMap (itp.) będziesz miał problemy z ponownym wyszukiwaniem klucza ... możesz zrobić kopię danych wByteArrayWrapper konstruktor, jeśli chcesz, ale oczywiście będzie to strata wydajności, jeśli Cię znaszprzyzwyczajenie zmieniać zawartość tablicy bajtów.

EDYCJA: Jak wspomniano w komentarzach, możesz również użyćByteBuffer do tego (w szczególności jegoByteBuffer#wrap(byte[]) metoda). Nie wiem, czy to naprawdę właściwa rzecz, biorąc pod uwagę wszystkie dodatkowe umiejętnościByteBuffers, których nie potrzebujesz, ale jest to opcja.

@Adamski: Wspominam o możliwości kopiowania na końcu odpowiedzi. W niektórych przypadkach jest to właściwe, ale nie w innych. Prawdopodobnie chciałbym, aby była to opcja (prawdopodobnie metody statyczne zamiast konstruktorów - copyOf i wrapperAround). Zauważ, żebez kopiowanie, możesz zmienić podstawową tablicę, dopóki nie weźmiesz skrótu i ​​nie zaznaczysz równości, co może być przydatne w niektórych sytuacjach. Jon Skeet
@dfa: Test „instanceof” obsługuje przypadek zerowy. Jon Skeet
Kilka innych rzeczy, które możesz dodać do implementacji wrappera: 1. Wykonaj kopię bajtu [] na konstrukcji, gwarantując tym samym, że obiekt jest niezmienny, co oznacza, że ​​nie ma niebezpieczeństwa, że ​​kod skrótu klucza zmieni się w czasie. 2. Wstępnie oblicz i zapisz kod skrótu (zakładając, że prędkość jest ważniejsza niż narzut pamięci). Adamski
Chciałem tylko zwrócić uwagę, że klasa java.nio.ByteBuffer zasadniczo robi wszystko, co robi twój wrapper, chociaż z tym samym zastrzeżeniem, że powinieneś go używać tylko wtedy, gdy zawartość tablicy bajtów nie będzie się zmieniać. Możesz zmienić swoją odpowiedź, aby wspomnieć o tym. Ed Anuff
Ups - Przepraszam Jon; Brakowało mi tej części twojej odpowiedzi. Adamski
0

se32 lub Base64, na przykład:

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

oczywiście istnieje wiele wariantów powyższego, takich jak:

String key = org.apache.commons.codec.binary.Base64.encodeBase64(keyValue);
12

java.math.BigInteger. To maBigInteger(byte[] val) konstruktor. Jest to typ odniesienia, więc może być użyty jako klucz do hashtable. I.equals() i.hashCode() są zdefiniowane jako odpowiednie liczby całkowite, co oznacza, że ​​BigInteger ma spójną semantykę równości jako tablicę bajtów [].

dzięki, niesamowite rozwiązanie! Vsevolod Dyomkin
Dobry punkt @leonbloy. Możliwe jest obejście tego problemu: dodanie do niego stałej stałej bajtów nieprowadzących do wartości NULL, ale będzie to wymagało napisania opakowania wokół konstruktora BigInteger i zwrócenia nas z powrotem do odpowiedzi Jona. Artem Oboturov
Odpowiedź @ vinchan byłaby bardziej odpowiednia, ponieważ nie istniałby problem bajtowy z zerową przewagą. Artem Oboturov
Brzmi atrakcyjnie, ale jest w błędzie, jako dwie tablice, które różnią się tylko prowadzeniem zerowych elementów (powiedzmy,{0,100} i{100}) da ten sam BigInteger leonbloy

Powiązane pytania