Java >> Java tutorial >  >> Tag >> HashMap

Optimering af HashMaps ydeevne

HashMap

1. Introduktion

HashMap er en kraftfuld datastruktur, der har en bred anvendelse, især når hurtig opslagstid er nødvendig. Men hvis vi ikke er opmærksomme på detaljer, kan det blive suboptimalt.

I denne vejledning tager vi et kig på, hvordan man laver HashMap så hurtigt som muligt.

2. HashMap ’s flaskehals

HashMap 's optimistiske konstante tidspunkt for elementhentning (O(1) ) kommer fra kraften ved hashing. For hvert element, HashMap beregner hashkoden og placerer elementet i den bøtte, der er knyttet til denne hashkode. Fordi ikke-lige objekter kan have de samme hash-koder (et fænomen kaldet hash-kodekollision), kan buckets vokse i størrelse.

Spanden er faktisk en simpel linket liste. Det er ikke særlig hurtigt at finde elementer i den linkede liste (O(n) ), men det er ikke et problem, hvis listen er meget lille. Problemer starter, når vi har mange hash-kodekollisioner, så i stedet for et stort antal små buckets, har vi et lille antal store buckets.

I det værste tilfælde, hvor vi putter alt i én spand, er vores HashMap er nedgraderet til en linket liste. Derfor i stedet for O(1) opslagstid, får vi et meget utilfredsstillende O(n) .

3. Træ i stedet for LinkedList

Fra Java 8 er én optimering indbygget i HashMap : Når spande bliver for store, omdannes de til træer i stedet for linkede lister. Det bringer den pessimistiske tid af O(n) til O(log(n)) , hvilket er meget bedre. For at det skal virke, skal du bruge nøglerne til HashMap skal implementere Sammenlignelige grænseflade.

Det er en fin og automatisk løsning, men den er ikke perfekt. O(log(n))  er stadig værre end ønsket konstant tid, og transformation og lagring af træer kræver ekstra kraft og hukommelse.

4. Bedste hashCode Implementering

Der er to faktorer, vi skal tage i betragtning, når vi vælger en hashfunktion:kvaliteten af ​​de producerede hashkoder og hastigheden.

4.1. Måler hashCode Kvalitet

Hash-koder er gemt i int variabler, så antallet af mulige hashes er begrænset til kapaciteten af ​​int type. Det må være tilfældet, fordi hashes bruges til at beregne indekser for et array med buckets. Det betyder, at der også er et begrænset antal nøgler, som vi kan gemme i et HashMap uden hashkollision.

For at undgå kollisioner så længe vi kan, ønsker vi at sprede hash så jævnt som muligt. Vi ønsker med andre ord at opnå ensartet fordeling. Det betyder, at hver hashkodeværdi har samme chance for at forekomme som enhver anden.

Tilsvarende en dårlig hashCode metoden ville have en meget ubalanceret fordeling. I det værste tilfælde ville det altid returnere det samme nummer.

4.2. Standard Objekt 's hashCode

Generelt bør vi ikke bruge standard Objektets hashCode metode, fordi vi ikke ønsker at bruge objektidentitet i equals metode. Men i det meget usandsynlige scenario, hvor vi virkelig ønsker at bruge objektidentitet til nøgler i et HashMap , standard hashCode funktion vil fungere fint. Ellers vil vi have en tilpasset implementering.

4.3. Brugerdefineret hashCode

Normalt ønsker vi at tilsidesætte lig med metode, og så skal vi også tilsidesætte hashCode . Nogle gange kan vi drage fordel af klassens specifikke identitet og nemt lave en meget hurtig hashCode metode.

Lad os sige, at vores objekts identitet udelukkende er baseret på dets heltal id . Så kan vi bare bruge dette id som en hash-funktion:

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    MemberWithId that = (MemberWithId) o;

    return id.equals(that.id);
}

@Override
public int hashCode() {
    return id;
}

Det vil være ekstremt hurtigt og vil ikke producere nogen kollisioner. Vores HashMap vil opføre sig som om den har en heltalsnøgle i stedet for et komplekst objekt.

Situationen bliver mere kompliceret, hvis vi har flere områder, som vi skal tage højde for. Lad os sige, at vi ønsker at basere lighed på begge id og navn :

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    MemberWithIdAndName that = (MemberWithIdAndName) o;

    if (!id.equals(that.id)) return false;
    return name != null ? name.equals(that.name) : that.name == null;
}

Nu skal vi på en eller anden måde kombinere hashes af id og navn .

Først får vi id 's hash den samme som før. Derefter multiplicerer vi det med et nøje udvalgt tal og tilføjer navnet 's hash:

@Override
public int hashCode() {
    int result = id.hashCode();
    result = PRIME * result + (name != null ? name.hashCode() : 0);
    return result;
}

Hvordan man vælger det nummer er ikke et let spørgsmål at besvare tilstrækkeligt. Historisk set var det mest populære nummer 31. Det er prime, det resulterer i en god fordeling, det er lille, og multiplicering med det kan optimeres ved hjælp af en bit-shift-operation:

31 * i == (i << 5) - i

Men nu, hvor vi ikke behøver at kæmpe for hver CPU-cyklus, kan nogle større primtal bruges. For eksempel 524287  kan også optimeres:

524287 * i == i << 19 - i

Og det kan give en hash af bedre kvalitet, hvilket resulterer i en mindre chance for kollision. Husk på, at disse bit-shift-optimeringer udføres automatisk af JVM , så vi behøver ikke at sløre vores kode med dem.

4.4. Objekter Hjælpeklasse

Algoritmen, vi lige har implementeret, er veletableret, og vi behøver normalt ikke at genskabe den i hånden hver gang. I stedet kan vi bruge hjælpemetoden fra Objekter klasse:

@Override
public int hashCode() {
    return Objects.hash(id, name);
}

Under hætten bruger den nøjagtig den algoritme, der er beskrevet tidligere med tallet 31 som en multiplikator.

4.5. Andre hash-funktioner

Der er mange hash-funktioner, der giver en mindre kollisions chance end den, der er beskrevet tidligere. Problemet er, at de er beregningsmæssigt tungere og dermed ikke giver den hastighedsforøgelse, vi søger.

Hvis vi af en eller anden grund virkelig har brug for kvalitet og er ligeglade med hastighed, kan vi tage et kig på Hashing klasse fra Guava-biblioteket:

@Override
public int hashCode() {
    HashFunction hashFunction = Hashing.murmur3_32();
    return hashFunction.newHasher()
      .putInt(id)
      .putString(name, Charsets.UTF_8)
      .hash().hashCode();
}

Det er vigtigt at vælge en 32-bit funktion, fordi vi alligevel ikke kan gemme længere hashes.

5. Konklusion

Moderne Javas HashMap  er en kraftfuld og veloptimeret datastruktur. Dens ydeevne kan dog blive forværret af en dårligt designet hashCode metode. I dette selvstudie har vi set på mulige måder at gøre hashing hurtig og effektiv.

Som altid er kodeeksemplerne til denne artikel tilgængelige på GitHub.


Java tag