» »

C# HashSet<T>, HashTable kako deluje iskanje v ozadju? a lahko faila?

C# HashSet<T>, HashTable kako deluje iskanje v ozadju? a lahko faila?

Vapo1 ::

zanima me kaj se zgodi s searchanjem po HashTable oz HashSet ce pride pri racunanju hasha do collisiona .... torej da funkcija GetHashCode() za dva razlicna keya vrne isti hash.


Res da je majhna verjetnost da pride do tega da se izracuna isti hash .... ampak vseeno.
hash je 32 bit stevilka right? ...kar pomeni 4 miljarde moznih kombinacij

recimo da v hash tabelo meces stringe - imena fajlov na disku - (na disku imam jaz slik ki sem jih jaz poslikal ene 30 tisoc ... ce si profi fotograf jih imas lahko mimogrede v nekaj letih 1 miljon (profi fotoaparati podpirajo 7 slik na sekundo - in fotografi tako slikajo "da ena od 7 ziher uspe")...)

no uglavnem 1 miljon hashov proti 4 miljarde prostih mest ni vec tako ziher - na en hash pride 4000 mest - torej ko enkrat das noter miljon hashov se vsake 4000 naslednjih dodanih hashov zgodi kolizija......

da ne bo dileme glede moznosti kolizije si lahko zamislim da naredim svoj class in overridam GetHashCode() metodo v nek idiotizem - recimo "return DateTime.Now.Seconds;" HAHA
s tem bi dosegel da se vseh miljon stringov preslika v 60 prostih mest..... skratka kolizije same bi bile.....


........................

no zdaj pa na vprasanje glavno.....
a me lahko hash search oz addanje zaradi kolizije zafrkne...

HashSet-string- HS; nikoli ne vsebuje vec istih objektov ... torej ne mores dodati dveh enakih stringov not (drugega pac ne doda)...

torej ce... HS.Add(STR).. torej dodajam notri, in string STR je unikaten, ampak pride do kolizije pri racunanju hasha in je torej hash enak hashu enega ze prej dodanega(pa vendar drugacnega) stringa v HS .... kaj se zgodi ... ali ga doda? ali misli da ga je ze prej dodal in moj unikaten string STR pac izpuhti iz moje evidence....

Mavrik ::

Zgoščene tabele so v C#-u implementirane kot "zaprte" tabele. To pomeni da ko pride do kolizije, se poišče naslednja fraj lokacija za element.

To sicer podaljša čas dostopa (ker je po izračunu "hasha" potem potrebno poiskati še element če tisti na prvem zadetku ni pravi), pomeni pa tudi da ti ni treba nič skrbet okoli kolizij. Slaba "hash" funkcija ti bo samo spremenila čas dostopa s konstantnega v (v najslabšem primeru) v linearnega.
The truth is rarely pure and never simple.

Zgodovina sprememb…

  • spremenil: Mavrik ()

fiction ::

Pri implementaciji razpresene tabele (ki je vedno koncna in niti ne nujno 4 miljarde elementov velika) moras ze od zacetka upostevati moznost kolizije. Dejansko je pri .NET initial capacity precej manjsi.

Imas dva nacina resevanja takih problemov:

- Open hashing / closed addressing
pomeni, da imas kot element tabele nek povezan seznam v katerem je lahko poljubno elementov, ki imajo enak hash. Problem je v tem, da moras potem, ko najdes prostor v tabeli, se cez seznam, da najdes "pravi" element. Torej ce imajo vsi elementi enak hash je to v bistvu 1 linked list, kar pomeni, da iskanje
ni vec tako zelo hitro.

- Closed hashing / open addressing
pomeni da vedno pises podatke samo v elemente tabele, ampak ce je slucajno tisti prostor ze poln, naprej racunas da prides do praznega mesta. Pri cemer se ti malo zakomplicira brisanje (si moras pustiti oznacen "prvi pravi element"). Ko je cela tabela polna moras alocirati vecjo in vanjo "premakniti" stare
elemente itd.

Konkretno pri .NET:
- HashSet je mnozica. Ce das dvakrat Add() z istim elementom bo drugi Add() vrnil false. Ce sta pa slucajno dva elementa, ki nista Equals(), ampak dobita isto vrednost pri GetHashCode(), se bo to pomoje resilo. In sicer v stilu "Closed hashing" z dinamicnim povecevanjem tabele.

- Pri HashTable je podobno, le da Add() ne vraca bool, ampak pri istem kljucu vrze ArgumentException. S slabim hashcodom je pa pac vse skupaj pocasnejse.

Hude tezave dobis, ce ne upostevas dejstva, da mora za par elementov pri katerem Equals() vrne true tudi GetHashCode() vrniti isto. Tako se ti lahko dogajajo cudne stvari kot npr. da ne najdes vec elementa, ki si ga dal v hashtable.

Edit: V C# se uporablja "open hashing"? Kolikor sem Googlal ne, ampak no ja, to je itak implementacijski detajl. V praksi ti je lahko vseeno kako resujejo problem, samo da ga.

Zgodovina sprememb…

  • spremenil: fiction ()

Vapo1 ::

... Ok.. Super. Hvala za odgovore.

Torej ce dam public static override gethashcode()... Return 1;
Se bojo vsi elementi nametali v prvi bucket pod en hash
in bo search performance isti kot z obicnim list

Btw... A vaju lahko se vprasam kje sta to znanje dobila - ker jaz sem popolni samouk programiranja - na faksu (fmf) smo imeli malo obicni c (ciste osnove) - pa bi rad nekako dobil pregled kaksno znanje imajo ljudje tukaj na slotechu in kje ga dobijo - kaksna je kvaliteta slovenskega fri faksa in kaj se ljudje tam naucijo ali ste se to vsi v vasih sluzbah naucili al kje... Torejnekako bi rad vsaj priblizno zaobjel kaksne so dimenzije programerskega sveta - kaj standardno vsi vejo in kaj je v domeni nekih super specializiranih posameznikov

Recimo kaksno leto nazaj sem nekaj gledal neke videote o programiranju in bral malo o zgodovini abuseanja goto statementov in sem naletel, na prej meni skrito, bolj teoreticno plat programiranja. Odkril sem koncepte kot so deklerativno vs imperativno programiranje. Objektno vs funkcionalno.. Databinding. Da je eden od namenov objektov ravno skrivanje podatkov - wrapanj. In vsi ti koncepti so mi bili zalo zanimivi in sem zacel veliko razmisljati o tem kako pisem kodo - in sem nekako prisel do zaljucka da v c# 99% kode pisem zase in ne za procesno enoto - torej da je meni preprosta za vizualizirat napisat modificirat in maintainat ne pa da "hitro dela na procesorju". Tisti 1% kodi ki predstavlja bottleneck se lahko potem ze optimizira (z uporabo hashsetov namesto navadnikh listov - haha). Torej ugotovil sem da sem pri programiranju ubistvu omejen s kompleksnostjo programa in ne s hitrostjo izvajanja - torej z mojo sposobnostjo vizualizacije in dejanske implementacije idej iz glave v kodo. In tukaj je zelo poemmbna sposobnost poenostavitve problema na najbolj enostavni level kar se da ko pises kodo. Recimo veliko kompleksnih nalog si lahko zamislim v glavi ki se jih z racunalnikom da narediti in kjer ni bottleneck hitrost - ampak je problem vse to skupaj spraviti v kodo ker zelo hitro zadeva rata velikin kompleksen program. Recimo ze ce si hocem zamislit samo malo bolj bogat in bolj intuitiven in intiligenten umesnik za aplikacijo - torejmalo vec gumbov in textboxov in checkboxov s katerimi lahko programi malo bolj detaljno in kompleksno poves kaj hoces da naredi - se v ozadju zelo hitro zakomplicirajo zadeve ce si nisi dovolj pametne in robustne implementacije zamislil - pa ceprav na povrsini programa se zdi ideja zelo preprosta glede tega kaj hoces da naredi

Mogoce to malo off topic... Bilahko novo temo odprl glede tega. Mogoceje ze kaksna odprta kje. Mogoce mi lahko predlagate kaksne dobre knjige kjer so kaksni dobri koncepti s katerimi bi izboljsal svojo sposobnost poenostavljanja pristopa k programiranju programa.

Zgodovina sprememb…

  • polepsal: Mavrik ()

Vapo1 ::

aja in a te na FRI ucijo o tem teoreticnem pristopu k programiranju ... ali te zasuvajo z lov level kodo in te silijo z optimiziranjem posameznih for loopov oz kombinacij if else stavkov in podobno

ker recimo na faksu fizike te vecinoma samo zasufajo z nalogami in matematiko in formulami... bolj malo te pa ucijo razmisljat o fiziki in jo razumeti

Zgodovina sprememb…

  • spremenilo: Vapo1 ()

Isotropic ::

hashset v cpp == dictionary v pythonu?

Vapo1 ::

v c# imas Dictionary tudi.... imas potem se nek HybridDictionary ... nisem ju se sprobal... ampak se zadaj skriva ubistvu ista fora kot HashTable in HashSet.. zadaj je ista tehnologija... samo namenjeno malo drugacni uporabi


takoda mozno da v pythonu je dictionary nekaj podobnega kot hashset

Zgodovina sprememb…

  • spremenilo: Vapo1 ()

fiction ::

HashSet, HashTable in Dictionary kolikor razumem vsi uporabljajo v ozadju enako podatkovno strukturo. Fora je samo v tem, kaj hoces (oz. lahko z njo pocnes):

- HashSet je v bistvu implementacije mnozice v kateri noces podvojenih elementov. Hash je nacin kako hitro ugotovis, ce mnozica ze vsebuje dolocen element (se pravi najprej po hashu, potem pa pogleda se Equals() za kandidate).

- Dictionary je pa mapping key -> value kot ga poznajo tudi drugi programski jeziki. IDictionary naceloma lahko implementiras tudi kot seznam vseh parov ali kaj takega, samo da je potem iskanje precej pocasno. Dictionary je pa realiziran tako, da se uporabi hash kljuca kot mesto v tabeli. Zelo zanimiv je se omenjen HybridDictionary, kjer gre najprej za seznam, ce je elementov vec pa uporabi hash table. Ampak po pravici povedano se nikjer nisem zasledil, da bi ga kdo uporabljal.

HashTable je nekaj podobnega kot Dictionary samo da ne uporablja generikov. Nekje sem zasledil tudi to, da naj bi drugace resevala collisione, torej da gre pri prvem za zaprto razprseno tabelo pri drugem pa za odprto, ceprav o tem nisem preprican. Tisto, kar sem nasel na Googlu mi ni izgledalo prevec kredibilno. Mogoce ve kdo drug kaj vec o tem?

Kar se tice FRI-ja: Programiranje je precej teoreticno, prakse se itak naucis skozi (studentsko) delo. Ceprav na zalost se vedno vecina folka misli, da bi moral biti faks kot nekakasna poklicna sola, kjer bi te naucili do potankosti posameznih programskih jezikov (in po moznosti cim manj matematike in ostalega).

Zgodovina sprememb…

  • spremenil: fiction ()

fiction ::

Izgleda kot da je tisto glede razlike o collision resolutionu res:
http://msdn.microsoft.com/en-us/library...
In the next section, we'll look at a third collision resolution technique called rehasing, which is the technique used by the .NET Framework's Hashtable class. In the final section, we'll look at the Dictionary class, which uses a collision resolution technique knows as chaining.

Mavrik ::


HashTable je nekaj podobnega kot Dictionary samo da ne uporablja generikov. Nekje sem zasledil tudi to, da naj bi drugace resevala collisione, torej da gre pri prvem za zaprto razprseno tabelo pri drugem pa za odprto, ceprav o tem nisem preprican. Tisto, kar sem nasel na Googlu mi ni izgledalo prevec kredibilno. Mogoce ve kdo drug kaj vec o tem?


Ni čist tako. V Comp. Sci. je Slovar ime za družino podatkovnih struktur, ki so predvsem namenjene iskanju elementov po ključu. V to družino spadajo potem zgoščene tabele (HashTables), vsa drevesa in še kaj.

Zdaj, te podatkovne strukture jeziki poimenujejo različno. C# recimo pravi "Dictionary" zaprti zgoščeni (oz. razpršeni, odvisno od prevoda :) ) tabeli, odprti pa "HashTable", Java ima samo odprte (HashMap, HashTable plus vse ostale Hash-nekaj- strukture uporabljajo odprto zg. tabelo odzadaj), Python pravi odprti zg. tabeli "Dictionary", v PHPju so to kar asociativni arrayi... itd.

aja in a te na FRI ucijo o tem teoreticnem pristopu k programiranju ... ali te zasuvajo z lov level kodo in te silijo z optimiziranjem posameznih for loopov oz kombinacij if else stavkov in podobno


Ne, na FRIju se učiš lih to kar tule sprašuješ. Konkretno, o teh osnovnih podatkovnih strukturah in njihovih prednostih in slabostih ter implementaciji se moraš naučiti pri predmetu Algoritmi in podatkovne strukture 1 oz. Programiranje in Algoritmi po novem programu (ki je precej snovi izgubil nekje po poti zgleda).
The truth is rarely pure and never simple.

Zgodovina sprememb…

  • spremenil: Mavrik ()

detroit ::

hehe prejšn tedn sm ga opravu da se pohvalim tko neumestno:)
Skero

darkolord ::

CAR

detroit ::

ti se sm zajebavej, tokrat je bil prouzaprou nemogoče narest vseh 5 nalog in jih itak noben ni sm slišu da je en 4naredu to je pa to..
Skero


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

SQL inner join

Oddelek: Programiranje
393349 (2604) smacker
»

[Java - DN] Naključna števila

Oddelek: Šola
121364 (893) nyler
»

java problem

Oddelek: Programiranje
7744 (624) Sergio
»

[Java] Frekvenca besed

Oddelek: Programiranje
71341 (1195) zila90
»

[Java] Preverjanje polja za iste stringe

Oddelek: Programiranje
81142 (1020) infiniteLoop

Več podobnih tem