KSP.sk

Korešpondenčný seminár z programovania


Odpovedať 
 
Hodnotenie témy:
  • 0 Hlasov - 0 Priemer
  • 1
  • 2
  • 3
  • 4
  • 5
4. Zabaliť optimálne - hash funkcia
03.02.2012, 18:39:21
Príspevok: #1
4. Zabaliť optimálne - hash funkcia
Potreboval som kodit hash a tak som si spomenul na tuto ulohu...
Zamyslel som sa nad hashovaciou funkciou v pascalovskom zdrojaku... je dost lahke vytvorit vstup pre ktory sa tato funkcia cykli.
napr. vstup
Kód:
2
23 3
po modulovani tsize to dava rovnaky vysledok a teda sa ta funkcia spusta dovtedy kym i nepretecie.
Staci v takomto pripade navrhnut domyselnejsi vzorec pre hash(x,i)? lebo velakrat sa da vymyslet hnusny vstup...
Alebo je lepsie implementovat hashovanie cez spajane zoznamy. Ako vlastne funguje unordered_map?
dakujem
Vyhľadať všetky príspevky tohoto používateľa
Citovať príspevok v odpovedi
03.02.2012, 23:24:40
Príspevok: #2
RE: 4. Zabaliť optimálne - hash funkcia
Sypem si popol na hlavu...

Ano staci urobit lepsi vzorec pre tu funkciu (v principe by mal zarucit, ze h(x,0), h(x,1), ..., su rozne), nie je tazke ho vymysliet.

Toto ta posunie na zaruceny cas O(n) na vkladanie a ocakavanych O(1) (za predpokladu, ze tabulka je aspon radovo tak velka ako pocet itemov).

Hasovanie zretazenim (na kazdom mieste si robim spajany zoznam) funguje rovnako dobre. Stale existuje vstup, kde mas v najhorsom pripade O(n) cas na vlozenie (ked sa vsetko zahasuje na to iste) a v ocakavanom pripade mas O(1) cas na vlozenie.
Vyhodou je potreba jednoduchsej hasovacej funkcie.

Unordered_map pouziva hasovanie zretazenim + navyse raz za cas zvacsi hasovaciu tabulku (podobne ako sa zvacsuje vektor a vsetko prehasuje).
Vyhľadať všetky príspevky tohoto používateľa
Citovať príspevok v odpovedi
Odpovedať 







Účet

Ako sa prihlásim?
 
loading

Redirecting