HashMapheeft twee belangrijke eigenschappen: sizeen load factor. Ik heb de Java-documentatie doorgenomen en er staat dat 0.75fde initiële belastingsfactor is. Maar ik kan het daadwerkelijke gebruik ervan niet vinden.
Kan iemand beschrijven wat de verschillende scenario’s zijn waarin we de belastingsfactor moeten instellen en wat zijn enkele ideale voorbeeldwaarden voor verschillende gevallen?
Antwoord 1, autoriteit 100%
De documentatielegt het vrij goed uit :
Een instantie van HashMap heeft twee parameters die van invloed zijn op de prestaties: initiële capaciteit en belastingsfactor. De capaciteit is het aantal buckets in de hashtabel en de initiële capaciteit is gewoon de capaciteit op het moment dat de hashtabel wordt gemaakt. De belastingsfactor is een maatstaf voor hoe vol de hashtabel mag worden voordat de capaciteit automatisch wordt verhoogd. Wanneer het aantal items in de hashtabel het product van de belastingsfactor en de huidige capaciteit overschrijdt, wordt de hashtabel opnieuw gehasht (dat wil zeggen, interne gegevensstructuren worden opnieuw opgebouwd), zodat de hashtabel ongeveer tweemaal het aantal buckets heeft.
Over het algemeen biedt de standaardbelastingsfactor (.75) een goede afweging tussen tijd- en ruimtekosten. Hogere waarden verlagen de ruimteoverhead maar verhogen de opzoekkosten (weerspiegeld in de meeste bewerkingen van de HashMap-klasse, inclusief get en put). Bij het instellen van de initiële capaciteit moet rekening worden gehouden met het verwachte aantal vermeldingen op de kaart en de belastingsfactor ervan, om het aantal herhalingsoperaties te minimaliseren. Als de initiële capaciteit groter is dan het maximum aantal vermeldingen gedeeld door de bezettingsgraad, zullen er nooit herkauwbewerkingen plaatsvinden.
Zoals bij alle prestatie-optimalisaties, is het een goed idee om te voorkomen dat dingen voortijdig worden geoptimaliseerd (d.w.z. zonder harde gegevens over waar de knelpunten zich bevinden).
Antwoord 2, autoriteit 54%
Standaard initiële capaciteit van de HashMap-opnames is 16 en de belastingsfactor is 0,75f (d.w.z. 75% van de huidige kaartgrootte). De belastingsfactor geeft aan op welk niveau de capaciteit van de HashMapmoet worden verdubbeld.
Bijvoorbeeldproduct van capaciteit en belastingsfactor als 16 * 0.75 = 12. Dit geeft aan dat na het opslaan van het 12e sleutel-waardepaar in de HashMapde capaciteit 32 wordt.
Antwoord 3, autoriteit 15%
Uit mijn berekeningen blijkt dat de “perfecte” belastingsfactor dichter bij log 2 ligt (~ 0,7). Hoewel een belastingsfactor die lager is dan dit, betere prestaties zal opleveren. Ik denk dat .75 waarschijnlijk uit een hoed is getrokken.
Bewijs:
Chaining kan worden vermeden en vertakkingsvoorspelling kan worden misbruikt door te voorspellen of a
emmer is leeg of niet. Een emmer is waarschijnlijk leeg als de kans daarop
leeg zijn is groter dan 0,5.
Laten we de grootte en het aantal toegevoegde sleutels voorstellen. De binomiaal gebruiken
stelling, is de kans dat een emmer leeg is:
P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0)
Een emmer is dus waarschijnlijk leeg als er minder zijn dan
log(2)/log(s/(s - 1)) keys
Als s oneindig bereikt en als het aantal toegevoegde toetsen zodanig is dat
P(0) = .5, dan nadert n/s log (2) snel:
lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0.693...
Antwoord 4, autoriteit 11%
Wat is de belastingsfactor?
De hoeveelheid capaciteit die moet worden verbruikt voordat de HashMap zijn capaciteit kan vergroten?
Waarom belastingsfactor?
Belastingsfactor is standaard 0,75 van de initiële capaciteit (16), daarom zal 25% van de bakken vrij zijn voordat er een toename van de capaciteit is & hierdoor zijn er veel nieuwe buckets met nieuwe hashcodes die ernaar verwijzen net na de toename van het aantal buckets.
Waarom zou je nu veel gratis buckets & wat is de impact van het houden van gratis buckets op de prestaties?
Als je de laadfactor instelt op 1,0, dan kan er iets heel interessants gebeuren.
Stel dat u een object x toevoegt aan uw hashmap waarvan de hashCode 888 & in je hashmap is de bucket die de hashcode vertegenwoordigt vrij , dus het object xwordt toegevoegd aan de bucket, maar zeg nu nogmaals dat als je een ander object y toevoegt waarvan de hashcode ook 888 is, je object y zal krijgen zeker toegevoegd MAAR aan het einde van de bucket (omdat de buckets niets anders zijn dan linkedList-implementatie die sleutel, waarde en volgende opslaat) nu heeft dit een impact op de prestaties! Aangezien uw object yniet langer aanwezig is in de kop van de bucket als u een opzoeking uitvoert, zal de benodigde tijd niet O(1)zijn, deze keer hangt het af van hoeveel items zitten er in dezelfde emmer. Dit wordt trouwens een hash-botsing genoemd & dit gebeurt zelfs wanneer uw laadfactor lager is dan 1.
Correlatie tussen prestaties, hash-botsing & laadfactor ?
Lagere belastingsfactor= meer vrije bakken = minder kans op botsingen= hoge prestaties = veel benodigde ruimte.
Corrigeer me als ik ergens fout zit.
Antwoord 5, autoriteit 7%
Van de documentatie:
De belastingsfactor is een maatstaf voor hoe vol de hashtabel mag worden voordat de capaciteit automatisch wordt verhoogd
Het hangt echt af van uw specifieke vereisten, er is geen “vuistregel” voor het specificeren van een initiële belastingsfactor.
Antwoord 6, autoriteit 3%
Voor HashMap DEFAULT_INITIAL_CAPACITY = 16en DEFAULT_LOAD_FACTOR = 0.75f
het betekent dat MAX aantal ALLE vermeldingen in de HashMap = 16 * 0,75 = 12. Wanneer het dertiende element wordt toegevoegd, wordt de capaciteit (arraygrootte) van HashMap verdubbeld!
Perfecte illustratie beantwoordde deze vraag:
afbeelding is hier genomen:
https:// javabypatel.blogspot.com/2015/10/what-is-load-factor-and-rehashing-in-hashmap.html
Antwoord 7
Als de emmers te vol raken, moeten we doorkijken
een zeer lange gelinkte lijst.
En dat is een beetje het verslaan van het punt.
Dus hier is een voorbeeld waarbij ik vier emmers heb.
Ik heb tot nu toe olifant en das in mijn HashSet.
Dit is een redelijk goede situatie, toch?
Elk element heeft nul of één element.
Nu voegen we nog twee elementen toe aan onze HashSet.
buckets elements
------- -------
0 elephant
1 otter
2 badger
3 cat
Dit is ook niet erg.
Elke bucket heeft maar één element
.
Dus als ik het wil weten, bevat dit panda?
Ik kan heel snel naar emmer nummer 1 kijken en dat is het niet
daar en
Ik wist dat het niet in onze collectie zit.
Als ik wil weten of er een kat in zit, kijk ik naar de emmer
nummer 3,
Ik vind kat, ik weet heel snel of hij in onze
. zit
collectie.
Wat als ik koala toevoeg, nou dat is niet zo erg.
buckets elements
------- -------
0 elephant
1 otter -> koala
2 badger
3 cat
Misschien nu in plaats van in emmer nummer 1 alleen kijkend naar
één element,
Ik moet er twee bekijken.
Maar ik hoef in ieder geval niet naar olifant, das en
. te kijken
kat.
Als ik weer op zoek ben naar panda, kan het alleen in emmer zijn
nummer 1 en
Ik hoef naar niets anders te kijken dan naar otter en
koala.
Maar nu heb ik alligator in emmer nummer 1 gestopt en je kunt
kijk misschien waar dit heen gaat.
Dat als emmer nummer 1 steeds groter wordt
en
groter, dan moet ik eigenlijk alles doorzoeken
die elementen om te vinden
iets dat in emmer nummer 1 zou moeten staan.
buckets elements
------- -------
0 elephant
1 otter -> koala ->alligator
2 badger
3 cat
Als ik tekenreeksen aan andere buckets begin toe te voegen,
juist, het probleem wordt alleen maar groter en groter in elke
één emmer.
Hoe voorkomen we dat onze emmers te vol raken?
De oplossing hier is dat
"the HashSet can automatically
resize the number of buckets."
De HashSet realiseert zich dat de buckets aan het groeien zijn
te vol.
Het verliest dit voordeel van dit alles van één zoekopdracht voor
elementen.
En het zal gewoon meer buckets maken (meestal twee keer als voorheen) en
plaats vervolgens de elementen in de juiste emmer.
Dus hier is onze basis HashSet-implementatie met aparte
ketenen.
Nu ga ik een “self-resize HashSet” maken.
Deze HashSet gaat beseffen dat de buckets
. zijn
te vol raken en
het heeft meer emmers nodig.
loadFactor is een ander veld in onze HashSet-klasse.
loadFactor vertegenwoordigt het gemiddelde aantal elementen per
emmer,
waarboven we het formaat willen wijzigen.
loadFactor is een balans tussen ruimte en tijd.
Als de emmers te vol raken, passen we het formaat aan.
Dat kost natuurlijk tijd, maar
het kan ons onderweg tijd besparen als de emmers een
. zijn
beetje meer leeg.
Laten we een voorbeeld bekijken.
Hier is een HashSet, we hebben tot nu toe vier elementen toegevoegd.
Olifant, hond, kat en vis.
buckets elements
------- -------
0
1 elephant
2 cat ->dog
3 fish
4
5
Op dit moment heb ik besloten dat de loadFactor, de
drempel,
het gemiddelde aantal elementen per bucket dat ik oké vind
met, is 0,75.
Het aantal buckets is buckets.length, wat 6 is, en
op dit moment heeft onze HashSet vier elementen, dus de
huidige maat is 4.
We zullen de grootte van onze HashSet wijzigen, dat wil zeggen dat we meer buckets zullen toevoegen,
wanneer het gemiddelde aantal elementen per bucket groter is dan
de belastingfactor.
Dat is wanneer de huidige grootte gedeeld door buckets.length
. is
groter dan loadFactor.
Op dit moment is het gemiddelde aantal elementen per bucket
is 4 gedeeld door 6.
4 elementen, 6 emmers, dat is 0,67.
Dat is minder dan de drempel die ik heb ingesteld van 0,75, dus we zijn
oke.
We hoeven het formaat niet aan te passen.
Maar laten we zeggen dat we bosmarmot toevoegen.
buckets elements
------- -------
0
1 elephant
2 woodchuck-> cat ->dog
3 fish
4
5
Woodchuck zou eindigen in emmer nummer 3.
Op dit moment is de huidige grootte 5.
En nu het gemiddelde aantal elementen per bucket
is de huidige grootte gedeeld door buckets.length.
Dat zijn 5 elementen gedeeld door 6 buckets is 0,83.
En dit overschrijdt de loadFactor die 0,75 was.
Om dit probleem aan te pakken, om de
emmers misschien een beetje
meer leeg zodat bewerkingen zoals bepalen of een
emmer bevat
een element zal iets minder complex zijn, ik wil het formaat wijzigen
mijn HashSet.
Het formaat van de HashSet wijzigen duurt twee stappen.
Eerst verdubbel ik het aantal emmers, ik had 6 emmers,
nu heb ik 12 emmers.
Houd er rekening mee dat de loadFactor die ik op 0,75 heb ingesteld hetzelfde blijft.
Maar het aantal gewijzigde buckets is 12,
het aantal elementen is gelijk gebleven, is 5.
5 gedeeld door 12 is ongeveer 0,42, dat is ruim onder onze
loadFactor,
dus we zijn nu in orde.
Maar we zijn nog niet klaar, want sommige van deze elementen zijn in
nu de verkeerde emmer.
Bijvoorbeeld olifant.
Olifant zat in emmer nummer 2 omdat het aantal
karakters in olifant
was 8.
We hebben 6 emmers, 8 min 6 is 2.
Daarom is het op nummer 2 beland.
Maar nu we 12 emmers hebben, is 8 mod 12 8, dus
olifant hoort niet meer in emmer nummer 2.
Olifant hoort thuis in emmer nummer 8.
Hoe zit het met bosmarmot?
Woodchuck was degene die dit hele probleem begon.
Woodchuck eindigde in emmer nummer 3.
Omdat 9 mod 6 3 is.
Maar nu doen we 9 mod 12.
9 mod 12 is 9, bosmarmot gaat naar emmer nummer 9.
En je ziet het voordeel van dit alles.
Emmer nummer 3 heeft nu maar twee elementen, terwijl voorheen
het had 3.
Dus hier is onze code,
waar we onze HashSet hadden met aparte chaining die
het formaat niet aangepast.
Hier is een nieuwe implementatie waarbij we het formaat wijzigen.
De meeste van deze code is hetzelfde,
we gaan nog bepalen of het de
. bevat
waarde al.
Als dat niet het geval is, zoeken we uit in welke emmer het wel
moeten ingaan op en
voeg het dan toe aan die bucket, voeg het toe aan die LinkedList.
Maar nu verhogen we het veld currentSize.
currentSize was het veld dat het nummer bijhield
elementen in onze HashSet.
We gaan het verhogen en dan gaan we kijken
bij de gemiddelde belasting,
het gemiddelde aantal elementen per bucket.
We doen die verdeling hier beneden.
We moeten hier een beetje casten om er zeker van te zijn
dat we een dubbele krijgen.
En dan vergelijken we die gemiddelde belasting met het veld
die ik heb ingesteld als
0,75 toen ik deze HashSet maakte, bijvoorbeeld
de belastingfactor.
Als de gemiddelde belasting groter is dan de belastingfactor,
dat betekent dat er te veel elementen per bucket op
gemiddeld, en ik moet opnieuw invoeren.
Dus hier is onze implementatie van de methode om
. opnieuw in te voegen
alle elementen.
Eerst maak ik een lokale variabele met de naam oldBuckets.
Wat verwijst naar de emmers zoals ze er nu staan
voordat ik het formaat van alles ga wijzigen.
Opmerking: ik maak nog geen nieuwe reeks gekoppelde lijsten.
Ik hernoem buckets gewoon naar oldBuckets.
Onthoud dat emmers een veld was in onze klas, ik ga
om nu een nieuwe array te maken
van gelinkte lijsten, maar dit zal twee keer zoveel elementen bevatten
zoals de eerste keer.
Nu moet ik het opnieuw invoegen,
Ik ga alle oude buckets herhalen.
Elk element in oldBuckets is een LinkedList met strings
dat is een emmer.
Ik ga door die emmer en krijg elk element daarin
emmer.
En nu ga ik het opnieuw in de newBuckets plaatsen.
Ik krijg de hashCode.
Ik zal uitzoeken welke index het is.
En nu krijg ik de nieuwe bucket, de nieuwe LinkedList van
strings en
Ik voeg het toe aan die nieuwe bucket.
Dus om samen te vatten, HashSets zoals we hebben gezien zijn arrays van gekoppelde
Lijsten of buckets.
Een HashSet met zelfvergrotende grootte kan realiseren met behulp van een bepaalde verhouding of
Antwoord 8
Ik zou een tabelgrootte van n * 1,5 of n + (n >> 1) kiezen, dit zou een belastingsfactor van 0,66666~ geven zonder deling, wat traag is op de meeste systemen, vooral op draagbare systemen waar er is geen scheiding in de hardware.