GLib: Hash tabulky

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