Vlákno názorů k článku GLib: Hash tabulky od Michal Illich - Hash tabulky jsou velmi silny nastroj. Ale tahle implementace...

Hash tabulky jsou velmi silny nastroj.

Ale tahle implementace mi neprijde dobra. Pokud vstupni integer pouze prevede na unsigned integer a pozici vypocita pomoci modulo, bude vykon takoveho 'hashovani' dost otresny - u vetsiny prirozenych data nastane neskutecne mnozstvi kolizi.

Hashove klice by mely hlavne splnovat podminku pseudonahodnosti - tedy by mely byt rovnomerne rozlozene po cele delce intervalu.

Navic 32 bitu na hash byva vetsinou malo.
Autor hned v druhe vete pise, ze jde o 'jednoznacny' klic. To samozrejme neni pravda. Klic muze byt stejny pro ruzna data.

K tomu 'jednoznacnemu' klici. Omlouvam se, asi jsem se vyjadril nepresne: tim 'jednoznacnym klicem' jsem myslel trochu neco jineho:

Klic je skutecne v jistem smyslu jednoznacny, protoze pointer na nej je ulozen spolu s daty. Kazda datova polozka ma tedy svuj 'jednoznacny' klic...

V dalsim vykladu jsem v popisu prubehu hashovani doufam vse vysvetlil poradne.

Jeste jednou se omlouvam.

Mimochodom, nevie mi niekto poradit skutocne dobre pseudonahodne hash funkcie pre unsigned int a pre retazce? Zatial pouzivam v programoch tiez iba modulo a nezda sa mi to najlepsie (aj ked ja som si HT implementoval tak, ze v pripade kolizie ide o jednosmerny zoznam prvkov na jednom indexe, co je lepsie ako najst najblizsiu volnu poziciu).

Ak niekto viete , prosim poradte, staci aj odkaz na nejaku stranku kde sa tato problematika rozobera.

Dakujem