4. Zabaliť optimálne - hash funkcia

[jergus]

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

[USAmec]

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