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

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.

... 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.

hashset v cpp == dictionary v pythonu?

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).

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).

CAR