Java >> Java tutorial >  >> Tag >> class

Brug af en brugerdefineret klasse som en nøgle i et Java HashMap

class

1. Oversigt

I denne artikel lærer vi hvordan HashMap administrerer internt nøgleværdi-par og hvordan man skriver tilpassede nøgleimplementeringer.

2. Nøglestyring

2.1. Intern struktur

Kort bruges til at gemme værdier, der er tildelt nøgler. Nøglen bruges til at identificere værdien i kortet og for at detektere dubletter.

Mens TreeMap bruger Comparable#compareTo(Object) metode til at sortere nøgler (og også til at identificere lighed), HashMap bruger en hash-baseret struktur, der lettere kan forklares ved hjælp af en hurtig skitse:

Et kort tillader ikke duplikerede nøgler, så nøglerne sammenlignes med hinanden ved hjælp af Object#equals(Object) metode. Fordi denne metode har dårlig ydeevne, bør påkald undgås så meget som muligt. Dette opnås gennem Object#hashCode() metode. Denne metode gør det muligt at sortere objekter efter deres hash-værdier og derefter Object#equals metode skal kun aktiveres, når objekter deler den samme hashværdi.

Denne form for nøglestyring anvendes også på HashSet klasse, hvis implementering bruger et HashMap internt.

2.2. Indsættelse og søgning af et nøgle-værdi-par

Lad os oprette et HashMap eksempel på en simpel butik, der administrerer antallet af lagervarer (heltal ) af et artikel-id (String ). Der indsætter vi en eksempelværdi:

Map<String, Integer> items = new HashMap<>();
// insert
items.put("158-865-A", 56);
// find
Integer count = items.get("158-865-A");

Algoritmen til at indsætte nøgleværdi-parret:

  1. kalder “158-865-A”.hashCode() for at få hashværdien
  2. søger efter listen over eksisterende nøgler, der deler den samme hashværdi
  3. sammenligner enhver nøgle på listen med "158-865-A".equals(key)
    1. Den første lighed identificeres som allerede eksisterende, og den nye erstatter den tildelte værdi.
    2. Hvis der ikke opstår lighed, indsættes nøgleværdi-parret som en ny post.

For at finde en værdi er algoritmen den samme, bortset fra at ingen værdi erstattes eller indsættes.

3. Brugerdefinerede nøgleklasser

Vi kan konkludere, at for at bruge en brugerdefineret klasse til en nøgle, er det nødvendigt at hashCode() og lig med() er implementeret korrekt . For at sige det enkelt skal vi sikre, at hashCode() metode returnerer:

  • den samme værdi for objektet, så længe tilstanden ikke ændres (intern konsistens )
  • den samme værdi for objekter, der er ens (Svar med konsistens )
  • så mange forskellige værdier som muligt for objekter, der ikke er ens.

Vi kan almindeligvis sige, at hashCode() og lig med() bør overveje de samme felter i deres beregning, og vi skal tilsidesætte begge eller ingen af ​​dem. Vi kan nemt opnå dette ved at bruge Lombok eller vores IDE's generator.

Et andet vigtigt punkt er:Ændr ikke et objekts hash-kode, mens objektet bruges som en nøgle. En simpel løsning er at designe nøgleklassen til at være uforanderlig, men dette er ikke nødvendigt, så længe vi kan sikre, at manipulation ikke kan finde sted ved nøglen.

Uforanderlighed har en fordel her:Hashværdien kan beregnes én gang ved objektforekomst, hvilket kan øge ydeevnen, især for komplekse objekter.

3.1. Godt eksempel

Som et eksempel vil vi designe en Koordinat klasse, der består af et x og y værdi, og brug den som en nøgle i et HashMap :

Map<Coordinate, Color> pixels = new HashMap<>();
Coordinate coord = new Coordinate(1, 2);
pixels.put(coord, Color.CYAN);
// read the color
Color color = pixels.get(new Coordinate(1, 2));

Lad os implementere vores Koordinering klasse:

public class Coordinate {
    private final int x;
    private final int y;
    private int hashCode;

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
        this.hashCode = Objects.hash(x, y);
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (o == null || getClass() != o.getClass())
            return false;
        Coordinate that = (Coordinate) o;
        return x == that.x && y == that.y;
    }

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

Som et alternativ kunne vi gøre vores klasse endnu kortere ved at bruge Lombok:

@RequiredArgsConstructor
@Getter
// no calculation in the constructor, but
// since Lombok 1.18.16, we can cache the hash code
@EqualsAndHashCode(cacheStrategy = CacheStrategy.LAZY)
public class Coordinate {
    private final int x;
    private final int y;
}

Den optimale interne struktur ville være:

3.2. Dårligt eksempel:Statisk Hash-værdi

Hvis vi implementerer Coordinate klasse ved at bruge en statisk hashværdi for alle forekomster, HashMap vil fungere korrekt, men ydeevnen vil falde betydeligt:

public class Coordinate {

    ...

    @Override
    public int hashCode() {
        return 1; // return same hash value for all instances
    }
}

Hash-strukturen ser så således ud:

Det negerer fordelen ved hashværdier fuldstændigt.

3.3. Dårligt eksempel:Modificerbar Hash-værdi

Hvis vi gør nøgleklassen mutable, bør vi sikre, at instansens tilstand aldrig ændres, mens den bruges som en nøgle:

Map<Coordinate, Color> pixels = new HashMap<>();
Coordinate coord = new Coordinate(1, 2); // x=1, y=2
pixels.put(coord, Color.CYAN);
coord.setX(3); // x=3, y=2

Fordi Coordinate er gemt under den gamle hash-værdi, kan den ikke findes under den nye. Så linjen nedenfor ville føre til en nul værdi:

Color color = pixels.get(coord);

Og den følgende linje ville resultere i, at objektet gemmes to gange i kortet :

pixels.put(coord, Color.CYAN);

4. Konklusion

I denne artikel har vi præciseret, at implementering af en tilpasset nøgleklasse for et HashMap er et spørgsmål om at implementere equals() og hashCode() korrekt. Vi har set, hvordan hashværdien bruges internt, og hvordan dette ville blive påvirket på både gode og dårlige måder.

Som altid er eksempelkoden tilgængelig på GitHub.


Java tag