2. Fórumok
  3. Szoftverfejlesztés
  4. Java programozás
  5. (kiemelt téma)

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

  • #11598 Drizzt nagyúr bambano #11597
    Új Válasz #11598
    Ú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
    Privát üzenet küldése

    Drizzt

    nagyúr

    válasz bambano #11597 üzenetére

    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