Új hozzászólás Aktív témák

• Drizzt nagyúr

  #11598

  #11597 bambano

  2021-07-07 16:46:49

  Új Válasz

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  

  Drizzt

  nagyúr

  #11597 bambano

  #11597 bambano

  nem ismerem, hogy a jáva ezt hogy csinálja, de a rendes eredeti hash tárolási struktúra egyáltalán nem keres hash értéket. ettől gyors.
  és úgy tartják fenn az elemek növekedése ellenére a gyorsaságot, hogy módosítják a hash függvényt.

  Pedig tok egyszeru a dolog.
  Van kiindulaskor valamennyi(n) darab bucket. A bucketek gyakorlatilag tombok. Tehat van egy n elemu tombod. Minden bucketben van egy linkelt lista, vagy valamilyen annak megfelelo struktura.
  A hash fuggvenyen nem modositanak semmit, mivel azt Javaban a user-nek szokas megadnia(oke, altalaban a Lombok irja meg helyette, meg lehet hasznalni a default implementaciot is, de az lehet lassu bizonyos esetekben).

  Kereses kulcs alapjan:
  - Meghivod a kulcsra a .hashCode metodust. Igy kapod az x erteket.
  - Kiszamolod , hogy x mod n = z alapjan mi a z.
  - A z. bucketet kikeresed(ez egy lepesben megvan).
  - A z. bucket osszes elemen vegigiteralsz, s megnezed, hogy a kulcs equals-e az eppen iteralas alatt levo elemmel. Ha igen, akkor az ott szinten eltarolt erteket visszaadod.

  Mikor lesz ez az egesz lassu?
  - Ha a hashCode ugy van megirva, hogy minden kulcs ugyanabba a bucketbe keruljon, vagy legalabbis a bucketek egy kis reszebe. Ilyenkor abban a bucketben egy hosszu lista lesz, ami miatt nem o(1) lesz a lookup, hanem kozeliti az o(n)-et.
  Ugyanez akkor is igaz lenne, ha a map-ben levo elemek szama joval nagyobb lenne, mint n. Mit csinal ez ellen a Java? Figyel egy toltottsegi szintet. Ha a toltottsegi szinte egy hataron tul van, akkor fogja, s csinal 2*n uj bucketet, s a meglevo elemeket belerakja, a regi n bucketet meg eldobja.

  Ebbe a pogramozo is bele tud szolni, van olyan konstruktor, amiben meg tudod adni a kezdeti n-t, s a toltottsegi tenyezot. Szoval ha tudod, hogy rohadt sok elemet fogsz belepakolni, akkor rogton csinalhatsz egy HashMap-et jo nagy n ertekkel, s akkor meguszol par rehash-t. Alapbol 16 bucket lesz, amit akkor ujrahashel, ha legalabb 13-ra no a size. Ekkor 32 bucket lesz, majd ha size legalabb 25 lesz, akkor ujrahashel 64 bucketbe, stb.

  A LinkedHashMap az egy specibb valtozat, ahol az egesz HashMap-en tul egy LinkedList is fenn van tartva, ami az osszes elemet tartalmazza a hozzaadas sorrendjeben. Akkor kell hasznalni, ha fontos a hozzaadas sorrendjet tudni.

Új hozzászólás Aktív témák