Hlavní navigace

GLib: Hash tabulky

Michal Burda

Hash tabulky, nebo chcete-li asociativní pole, představují výkonný programátorský nástroj. Jde o speciální typ, který realizuje spojení dat s jejich jednoznačným klíčem, takže pokud zadáte klíč, data mohou být v hash tabulce díky výkonným algoritmům velice rychle nalezena.

Hash tabulka je v knihovně GLib reprezentována strukturou GHashTable. Všechny položky této struktury jsou neveřejné a doporučuje se k nim přistupovat výhradně použitím následujících speciálních funkcí.

GHashTable 

Pozice ukládaných dat se totiž určitým způsobem vypočítává. Základem je určení tzv. hash hodnoty z předaného klíče: Například, je-li klíčem integerový typ nebo pointer, převede se jeho hodnota na nezápornou celočíselnou konstantu. Je-li klíčem řetězec, použije se nějaký algoritmus, který jej zakóduje tak, abychom dostali opět přirozené číslo. Takto získaná hodnota se pak použije jako index k přístupu do tabulky s daty: vypočítá se modulo hash hodnoty s velikostí tabulky (velikost je vždy prvočíslo) a tak se nalezne pozice, kam se mají data uložit. Je-li místo již obsazeno, uloží se prvek (spolu s klíčem, aby nedošlo k záměně) na nejbližší následující volnou pozici.

Výsledkem takového počínání je pak vysoká rychlost a efektivita v hledání požadovaných dat v paměti.

Vytvoření nové hash tabulky

guint(*GHashFunc)(gconstpointer key);
gint(*GCompareFunc)(gconstpointer a, gconstpointer b);

GHashTable* g_hash_table_new(GHashFunc hash_func,
                             GCompareFunc key_compare_func);

Novou GHashTable vytvoříte zavoláním funkce g_hash_table_new(). Funkce vrací pointer na nově alokovanou strukturu GHashTable a jako parametry si žádá dvě funkce. První musí odpovídat typu GHashFunc a druhá nám již známému GCompareFunc (používal se i v seznamech).

Od funkce hash_func se očekává realizace algoritmu kódování klíče na nezápornou celočíselnou hodnotu (hashovací funkce), ale nemusíte mít strach – funkce pro kódování nejčastějších typů klíčů jsou k dispozici:

guint g_direct_hash(gconstpointer v);
guint g_int_hash(gconstpointer v);
guint g_str_hash(gconstpointer v);
g_direct_hash() 
g_int_hash() 
g_str_hash() 

Pokud tedy budete jako klíče používat integerové hodnoty, použijte g_int_hash(), budou-li to řetězce, je správnou volbou g_str_hash(). V ostatních případech si většinou vystačíte s  g_direct_hash().

Nebudou-li vám tyto funkce stačit, nic vám nebrání v napsání vlastních. Jak jste asi vypozorovali, od funkcí typu GHashFunc se očekává, že převezmou pointer na klíč, ze kterého vyrobí tzv. hash hodnotu. Samozřejmě nemůžete dosáhnout toho, že pro všechny možné klíče se vždy vygeneruje unikátní hash hodnota. Je ale výhodnější, budou-li získávané hash hodnoty pokud možno rovnoměrně rozprostřeny po celém intervalu. Největší zřetel však berte na rychlost: hash funkce se v mechanizmu hash tabulek používá velmi často, takže pokud bude dělat nějaké náročné operace, veškerá výkonnost se ztratí.

Druhý argument funkce g_hash_table_new(), key_compare_func, je funkce typu GCompareFunc. Typ GCompareFunc je takový chameleón. Reprezentuje funkce, které mají za úkol vykonat porovnání. Podle kontextu se však vždy liší způsob, jakým výsledky dávají najevo. V případě GHashTable se od nich očekává, že vrátí TRUE, jsou-li její dva parametry stejné a FALSE v opačném případě.

Opět máme k dispozici trojici předpřipravených funkcí:

gint g_direct_equal(gconstpointer v, gconstpointer v2);
gint g_int_equal(gconstpointer v, gconstpointer v2);
gint g_str_equal(gconstpointer v, gconstpointer v2);

Funkce g_direct_equal() porovnává dva pointery a vrátí TRUE, jsou-li stejné. Hodí se k funkci g_direct_hash(). Bude-li parametr key_compare_func funkce g_hash_table_new() roven NULL, použije se k porovnávání implicitně právě tato funkce.

g_int_equal() 
g_str_equal() 

Uvolnění GHashTable z paměti

K uvolnění GHashTable z paměti slouží následující funkce. Škoda, že autoři knihovny GLib zde nedodrželi názvovou konvenci a místo slůvka destroy do názvu nedali raději klasické free jako v ostatních případech:

void g_hash_table_destroy(GHashTable *hash_table); 

…dealokuje paměť vyhrazenou pro hash tabulku hash_table. Pokud jste do tabulky ukládali dynamická data a klíče, musíte je dealokovat ještě předtím, než provedete tuto funkci.

Tak, už umíme hash tabulku vytvořit a odstranit, ale to asi moc neznamená. Potřebujeme hlavně umět přidávat nové záznamy, hledat v nich a vůbec dělat všelijaké jiné užitečnosti. Všechno to s knihovnou GLib lze, ale o tom až příště.

Našli jste v článku chybu?

14. 2. 2001 13:41

Tomas Horsky (neregistrovaný)

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





1. 8. 2000 21:23

Michal Burda (neregistrovaný)

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.

Vitalia.cz: Jmenuje se Janina a žije bez cukru

Jmenuje se Janina a žije bez cukru

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Vitalia.cz: 7 druhů hotových těst na vánoční cukroví

7 druhů hotových těst na vánoční cukroví

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Vitalia.cz: Taky věříte na pravidlo 5 sekund?

Taky věříte na pravidlo 5 sekund?

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

Vitalia.cz: Proč vás každý zubař posílá na dentální hygienu

Proč vás každý zubař posílá na dentální hygienu

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Vitalia.cz: Jedlé kaštany jsou trpké, je třeba je tepelně upravit

Jedlé kaštany jsou trpké, je třeba je tepelně upravit

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Vitalia.cz: 9 největších mýtů o mase

9 největších mýtů o mase

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

Vitalia.cz: Znáte „černý detox“? Ani to nezkoušejte

Znáte „černý detox“? Ani to nezkoušejte

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Podnikatel.cz: Zavře krám u #EET Malá pokladna a Teeta?

Zavře krám u #EET Malá pokladna a Teeta?