Java >> Java tutorial >  >> Tag >> byte

Brug af en byte-array som kortnøgle i Java

byte

1. Introduktion

I denne vejledning lærer vi, hvordan du bruger et byte-array som en nøgle i HashMap . På grund af hvordan HashMap fungerer, kan vi desværre ikke gøre det direkte. Vi vil undersøge hvorfor det er tilfældet og se på flere måder at løse det problem på.

2. Design af en god nøgle til HashMap

2.1. Hvordan HashMap Virker

HashMap bruger hashingmekanismen til at gemme og hente værdier fra sig selv. Når vi kalder put(nøgle, værdi) metode, HashMap beregner hashkoden baseret på nøglens hashCode() metode. Denne hash bruges til at identificere en bøtte, hvori værdien endelig gemmes:

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
 
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

Når vi henter en værdi ved hjælp af get(key) metode, er en lignende proces involveret. Nøglen bruges til at beregne hash-koden og derefter til at finde bøtten. Derefter kontrolleres hver post i bøtten for lighed ved hjælp af equals() metode. Til sidst returneres værdien af ​​den matchende post:

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

2.2. Kontrakt mellem lig med () og hashCode ()

Begge er lig med og hashCode metoder har kontrakter, der skal overholdes. I forbindelse med HashMaps , et aspekt er særligt vigtigt:objekter, der er ens med hinanden, skal returnere den samme hashCode . Men objekter, der returnerer den samme hashCode behøver ikke være lige hinanden. Derfor kan vi gemme flere værdier i en spand.

2.3. Uforanderlighed

hashkoden af nøglen i HashMap bør ikke ændre sig. Selvom det ikke er obligatorisk, anbefales det stærkt, at nøgler er uforanderlige. Hvis et objekt er uforanderligt, er dets hashCode vil ikke have mulighed for at ændre, uanset implementeringen af ​​hashkoden metode.

Som standard beregnes hashen baseret på alle objektets felter. Hvis vi gerne vil have en foranderlig nøgle, skal vi tilsidesætte hashkoden metode til at sikre, at foranderlige felter ikke bruges i dens beregning. For at opretholde kontrakten skal vi også ændre lig metode.

2.4. Meningsfuld Ligestilling

For at kunne hente værdier fra kortet, skal ligestilling være meningsfuld. I de fleste tilfælde skal vi være i stand til at oprette et nyt nøgleobjekt, der vil være lig med en eksisterende nøgle på kortet. Af den grund er objektidentitet ikke særlig nyttig i denne sammenhæng.

Dette er også hovedårsagen til, at brug af en primitiv byte-array ikke rigtig er en mulighed. Arrays i Java bruger objektidentitet til at bestemme lighed. Hvis vi opretter HashMap med byte array som nøglen, vil vi kun kunne hente en værdi ved at bruge nøjagtigt det samme array objekt.

Lad os skabe en naiv implementering med et byte-array som nøgle:

byte[] key1 = {1, 2, 3};
byte[] key2 = {1, 2, 3};
Map<byte[], String> map = new HashMap<>();
map.put(key1, "value1");
map.put(key2, "value2");

Ikke alene har vi to indgange med stort set den samme nøgle, men vi kan heller ikke hente noget ved hjælp af en nyoprettet matrix med de samme værdier:

String retrievedValue1 = map.get(key1);
String retrievedValue2 = map.get(key2);
String retrievedValue3 = map.get(new byte[]{1, 2, 3});

assertThat(retrievedValue1).isEqualTo("value1");
assertThat(retrievedValue2).isEqualTo("value2");
assertThat(retrievedValue3).isNull();

3. Brug af eksisterende containere

I stedet for byte-arrayet kan vi bruge eksisterende klasser, hvis lighedsimplementering er baseret på indhold, ikke objektidentitet.

3.1. streng

streng lighed er baseret på indholdet af karakterarrayet:

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = count;
        if (n == anotherString.count) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = offset;
            int j = anotherString.offset;
            while (n-- != 0) {
                if (v1[i++] != v2[j++])
                   return false;
            }
            return true;
        }
    }
    return false;
}

streng s er også uforanderlige og skaber en streng baseret på et byte-array er ret ligetil. Vi kan nemt indkode og afkode en streng ved hjælp af Base64 skema:

String key1 = Base64.getEncoder().encodeToString(new byte[]{1, 2, 3});
String key2 = Base64.getEncoder().encodeToString(new byte[]{1, 2, 3});

Nu kan vi oprette et HashMap med streng som nøgler i stedet for byte-arrays. Vi indsætter værdier i kortet på samme måde som i det foregående eksempel:

Map<String, String> map = new HashMap<>();
map.put(key1, "value1");
map.put(key2, "value2");

Så kan vi hente en værdi fra kortet. For begge nøgler får vi den samme anden værdi. Vi kan også kontrollere, at tasterne virkelig er ens med hinanden:

String retrievedValue1 = map.get(key1);
String retrievedValue2 = map.get(key2);

assertThat(key1).isEqualTo(key2);
assertThat(retrievedValue1).isEqualTo("value2");
assertThat(retrievedValue2).isEqualTo("value2");

3.2. Lister

På samme måde som String , List#equals metoden vil kontrollere for lighed af hvert af dets elementer. Hvis disse elementer har en fornuftig equals() metode og er uforanderlige, List vil fungere korrekt som HashMap nøgle. Vi behøver kun at sikre, at vi bruger en uforanderlig Liste implementering :

List<Byte> key1 = ImmutableList.of((byte)1, (byte)2, (byte)3);
List<Byte> key2 = ImmutableList.of((byte)1, (byte)2, (byte)3);
Map<List<Byte>, String> map = new HashMap<>();
map.put(key1, "value1");
map.put(key2, "value2");

assertThat(map.get(key1)).isEqualTo(map.get(key2));

Husk at Listen af Byten objekt vil tage meget mere hukommelse end arrayet med byte primitiver. Så selv om den løsning er praktisk, er den ikke levedygtig i de fleste scenarier.

4. Implementering af tilpasset container

Vi kan også implementere vores egen wrapper for at tage fuld kontrol over hashkodeberegning og lighed. På den måde kan vi sikre, at løsningen er hurtig og ikke har et stort hukommelsesfodaftryk.

Lad os lave en klasse med en sidste, privat byte array felt. Den har ingen setter, og dens getter vil lave en defensiv kopi for at sikre fuld uforanderlighed:

public final class BytesKey {
    private final byte[] array;

    public BytesKey(byte[] array) {
        this.array = array;
    }

    public byte[] getArray() {
        return array.clone();
    }
}

Vi skal også implementere vores egne lige og hashCode metoder. Heldigvis kan vi bruge Arrays hjælpeklasse for begge disse opgaver:

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    BytesKey bytesKey = (BytesKey) o;
    return Arrays.equals(array, bytesKey.array);
}

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

Endelig kan vi bruge vores indpakning som en nøgle i et HashMap :

BytesKey key1 = new BytesKey(new byte[]{1, 2, 3});
BytesKey key2 = new BytesKey(new byte[]{1, 2, 3});
Map<BytesKey, String> map = new HashMap<>();
map.put(key1, "value1");
map.put(key2, "value2");

Derefter kan vi hente den anden værdi ved at bruge en af ​​de erklærede nøgler, eller vi kan bruge en, der er oprettet på et øjeblik:

String retrievedValue1 = map.get(key1);
String retrievedValue2 = map.get(key2);
String retrievedValue3 = map.get(new BytesKey(new byte[]{1, 2, 3}));

assertThat(retrievedValue1).isEqualTo("value2");
assertThat(retrievedValue2).isEqualTo("value2");
assertThat(retrievedValue3).isEqualTo("value2");

5. Konklusion

I denne øvelse så vi på forskellige problemer og løsninger til brug af en byte array som en nøgle i HashMap . Først undersøgte vi, hvorfor vi ikke kan bruge arrays som nøgler. Så brugte vi nogle indbyggede beholdere til at afhjælpe det problem og implementerede til sidst vores egen indpakning.

Som sædvanlig kan kildekoden til dette selvstudie findes på GitHub.


Java tag