Les taules hash , hash maps són una estructura de dades que, mitjançant una funció hash (o
funció resum) identifica uns valors, anomenats claus, amb uns valors associats.
L'avantatge de les taules hash sobre altres estructures de dades és la gran rapidesa d'accés a la informació i el cost constant d'aquest accés. Per això, les taules hash tenen un munt d'aplicacions.
En tot cas, les taules hash són una solució molt senzilla i eficient per a l'emmagatzematge i l'accés a la informació que es pugui modelar directament amb taules de parelles clau valor.
Amb C sobre Linux (en el meu cas Ubuntu 11.04) apareixen almenys tres opcions ràpides per a implementar taules hash:
Amb funcions de la llibreria estàndar
GlibC
Amb funcions de la llibreria GTK,
Glib
Amb "bases de dades" del tipus DBM, a Linux
Gdbm; o amb l'evolució amb capacitat concurrent de Gdbm desenvolupada per a
SAMBA:
TDB
Anem a repassar les opcions:
Amb Glibc (La llibreria estàndard de C)
Un exemple de taules hash amb les funcions de la llibreria estàndard Glibc (hcreate, hsearch i hdestroy)
/* aquest exemple està adaptat de la documentació del man */
#include <stdio.h>
#include <search.h>
#include <string.h>
struct info { /* aquesta estructura és la dels valors emmagatzemats a la taula */
int age, room;
};
#define NUM_EMPL 5000 /* # número d'elements. */
int main(void)
{
char string_space[NUM_EMPL*20]; /* espai d'emmagatzematge de la taula de valors de les claus. */
struct info info_space[NUM_EMPL]; /* espai per emmagatzemar la informació de claus. */
char *str_ptr = string_space; /* següent posició a l'espai de valors. */
struct info *info_ptr = info_space; /* següent posició a l'espai de claus. */
ENTRY item;
ENTRY *found_item; /* nom a buscar. */
char name_to_find[30];
int i = 0;
/* Create table; no error checking is performed. */
printf("Crea la taula\n");
(void) hcreate(NUM_EMPL);
printf("Introdueix clau age room a la taula. Per acabar d'entrar valors prem CTRL-D\n");
while (scanf("%s %d %d", str_ptr, &info_ptr->age,
&info_ptr->room) != EOF && i++ < NUM_EMPL) {
/* Put information in structure, and structure in item. */
printf("Afegeix %s %d %d a la taula\n", str_ptr, info_ptr->age, info_ptr->room);
item.key = str_ptr;
item.data = info_ptr;
str_ptr += strlen(str_ptr) + 1;
info_ptr++;
/* Put item into table. */
printf("Afegeix - hsearch(item, ENTER)\n");
(void) hsearch(item, ENTER);
}
/* Access table. */
printf("Busca valors a la taula. Per acabar CTRL-C\n");
item.key = name_to_find;
while (scanf("%s", item.key) != EOF) {
printf("Buscant %s amb hsearch(item, FIND)\n", item.key);
if ((found_item = hsearch(item, FIND)) != NULL) {
/* If item is in the table. */
(void)printf("trobat %s, age = %d, room = %d\n",
found_item->key,
((struct info *)found_item->data)->age,
((struct info *)found_item->data)->room);
} else
(void)printf("no trobat %s\n", name_to_find);
}
return 0;
}
Una excució podria ser, per exemple:
albert@atenea:~/wk-c/prova-hash-glibc$ ./prova_hash_glibc
Crea la taula
Introdueix clau age room a la taula. Per acabar d'entrar valors prem CTRL-D
clau1 1 2
Afegeix clau1 1 2 a la taula
Afegeix - hsearch(item, ENTER)
clau2 3 4
Afegeix clau2 3 4 a la taula
Afegeix - hsearch(item, ENTER)
clau3 5 6
Afegeix clau3 5 6 a la taula
Afegeix - hsearch(item, ENTER)
Busca valors a la taula. Per acabar CTRL-C
prova
Buscant prova amb hsearch(item, FIND)
no trobat prova
clau1
Buscant clau1 amb hsearch(item, FIND)
trobat clau1, age = 1, room = 2
clau3
Buscant clau3 amb hsearch(item, FIND)
trobat clau3, age = 5, room = 6
^C
albert@atenea:~/wk-c/prova-hash-glibc$
Amb GLib (la llibreria de GTK)
La referència per a taules hash amb Glib es troba a
http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html
En resum:
Per a crear una taula hash de Glib (una GHashTable), fem servir: g_hash_table_new().
Per afegir una clau i el seu valor associat a la GHashTable, fem servir: g_hash_table_insert().
Per a cercar el valor associat a una clar fem servir g_hash_table_lookup() i g_hash_table_lookup_extended().
Per a eliminar una aprella clau-valor, g_hash_table_remove().
Per a invocar una funció per a cada parella clau-valor, g_hash_table_foreach().
Per a esborrar del tot una GHashTable, g_hash_table_destroy().
Vet aquí l'exemple amb GLibC implementat amb les funcions de GLib. L'exemple ha estat desenvolupat fent servir Anjuta. He partit d'un projecte genèric mínim amb C. M'ha calgut afegir la llibreria glib2.0-0 i l'include a glib.h al fitxer Makefile.am (automake)
## Process this file with automake to produce Makefile.in
## Created by Anjuta
AM_CPPFLAGS = \
-DPACKAGE_DATA_DIR=\""$(datadir)"\"
AM_CFLAGS =\
-Wall\
-g\
-I/usr/include/glib-2.0\ -I/usr/lib/glib-2.0/include
bin_PROGRAMS = hashtables
hashtables_SOURCES = \
main.c
hashtables_LDFLAGS = -lglib-2.0
hashtables_LDADD =
El codi és el següent. Pràcticament només he tingut que canviar les funcions:
#include <stdio.h>
#include <string.h>
#include <glib.h>
struct value { /* aquesta estructura és la dels valors emmagatzemats a la taula */
gint age, room; /* gint és el tipus glib que encapsula a int*/
};
#define NUM_KEYS 5000 /* número d'elements. */
#define KEY_SIZE 20 /* tamanys de la clau*/
int main(void)
{
GHashTable *hashTable;
gchar keys[NUM_KEYS * KEY_SIZE]; /* espai d'emmagatzematge de la taula de valors de les claus. */
struct value values[NUM_KEYS]; /* espai per emmagatzemar la informació de claus. */
gchar *keyPtr = keys; /* següent posició a l'espai de valors. */
struct value *valuePtr = values; /* següent posició a l'espai de claus. */
gchar keyToFind[KEY_SIZE]; /* clau a buscar, màxim de KEY_SIZE caràcters */
int i=0;
/* Crea taula hash.
g_str_hash és una funció hash que es proporciona amb Glib
per a claus del tipus (gchar *)
g_str_equal és una funció que es proporciona amb Glib per verificar
l'igualtat de dues claus del tipus (gchar *)
*/
printf("Crea la taula\n");
hashTable = g_hash_table_new(g_str_hash, g_str_equal);
printf("Introdueix clau age room a la taula. Per acabar d'entrar valors prem CTRL-D\n");
while (scanf("%s %d %d",
keyPtr,
&valuePtr->age,
&valuePtr->room) != EOF && i++ < NUM_KEYS) {
/* traça */
printf("Afegeix %s %d %d a la taula\n", keyPtr, valuePtr->age, valuePtr->room);
/* els posa a la taula */
printf("Afegeix - g_hash_table_insert\n");
/* afegeix clau-valor a taula hash.
g_hash_table_insert rep tres paràmetres
punter a la taula hash
punter a la clau
punter al valor
*/
g_hash_table_insert(hashTable, keyPtr, valuePtr);
/* prepara els punters per a nova clau valor*/
keyPtr += strlen(keyPtr) + 1;
valuePtr++;
}
/* Ara busca per la taula. */
printf("Busca valors a la taula. Per acabar CTRL-C\n");
keyPtr = keyToFind;
while (scanf("%s", keyPtr) != EOF) {
printf("Buscant %s amb g_hash_table_lookup\n", keyPtr);
if ((valuePtr = g_hash_table_lookup(hashTable, keyPtr)) != NULL) {
/* si ha trobat diferent de nul, el mostra. */
/* nota: això pot ser un problema, perquè no es pot distingir
el "no trobat" del "trobat el valor nul".
En aquests casos, cal fer servir g_hash_table_lookup_extended
*/
printf("found %s, age = %d, room = %d\n",
keyPtr,
valuePtr->age,
valuePtr->room);
} else
printf("not found %s\n", keyPtr);
}
return 0;
}
L'execució del programa anterior segueix les mateixes indicacions que al primer exemple:
albert@atenea:~/wk-c/prova-hash-glib$ hashtables
Crea la taula
Introdueix clau age room a la taula. Per acabar d'entrar valors prem CTRL-D
albert 42 192
Afegeix albert 42 192 a la taula
Afegeix - g_hash_table_insert
montse 40 201
Afegeix montse 40 201 a la taula
Afegeix - g_hash_table_insert
^D
Busca valors a la taula. Per acabar CTRL-C
kok
Buscant kok amb g_hash_table_lookup
not found kok
albert
Buscant albert amb g_hash_table_lookup
found albert, age = 42, room = 192
montse
Buscant montse amb g_hash_table_lookup
found montse, age = 40, room = 201
^C
GDBM i TDB
En el desenvolupament de SAMBA es va veure que calia un sistema de base de dades senzill del tipus hash: una taula de claus i valors.
DBM (la BD de BSD) oferia la interfase adequada, però no permetia l'accés concurrent. Aleshores, es va reescriure DBM permetent aquest accés concurrent i el resultat va ser
TDB. TDB es pot utilitzar com un alternativa concurrent de DBM.
A Ubuntu es poden instal·lar des del Centre de Programari tant la versió GNU de DBM, la GDBM, com la TDB.
TDB i GDBM ocupen molt poc espai i poden ser una bona sol·lució per a implementar taules hash amb C allà on calguin, en comptes de fer servir les funcions que ofereixen la llibreria estàndard de C, GLibc, o les de la llibreria de GTK, GLib.
Una preacució a tenir en compte és que existeixen diferents formats de fitxer dbm.
La instal·ació de TDB inclou, a més dels llibreries i dels include, els executables següents:
tdbbackup: és una eina que es pot fer servir per fer el backup des fitxers .tdb de Samba i verificar-ne la integritat. Si troba un fitxer .tdb de Samba fet malbé i un fitxer de backup previ, aleshores restaura el fitxer anterior.
tdbdump: és una eina que fa el volcat, o dump, d'un fitxer .tdb en un format legible. A més també pot fer el volcat d'una clau específica.
tdbtool: permet manipular fitxers .tdb. Les opcions que ofereix aquest programa són:
albert@atenea:~$ tdbtool
tdb> help
database not open
tdbtool:
create dbname : create a database
open dbname : open an existing database
transaction_start : start a transaction
transaction_commit : commit a transaction
transaction_cancel : cancel a transaction
erase : erase the database
dump : dump the database as strings
keys : dump the database keys as strings
hexkeys : dump the database keys as hex values
info : print summary info about the database
insert key data : insert a record
move key file : move a record to a destination tdb
store key data : store a record (replace)
show key : show a record by key
delete key : delete a record by key
list : print the database hash table and freelist
free : print the database freelist
check : check the integrity of an opened database
speed : perform speed tests on the database
! command : execute system command
1 | first : print the first record
n | next : print the next record
q | quit : terminate
\n : repeat 'next' command
per exemple, puc fer
albert@atenea:~$ tdbtool
tdb> create prova.tdb
tdb> insert clau1 valor1
tdb> insert clau2 valor2
tdb> insert clau3 valor3
tdb> dump
key 5 bytes
clau1
data 6 bytes
[000] 76 61 6C 6F 72 31 valor1
key 5 bytes
clau2
data 6 bytes
[000] 76 61 6C 6F 72 32 valor2
key 5 bytes
clau3
data 6 bytes
[000] 76 61 6C 6F 72 33 valor3
tdb> quit
albert@atenea:~$ tdbdump prova.tdb
{
key(5) = "clau1"
data(6) = "valor1"
}
{
key(5) = "clau2"
data(6) = "valor2"
}
{
key(5) = "clau3"
data(6) = "valor3"
}
Amb TDB
Anem a repetir el mateix cas de prova de GLibC i GLib, però implementant-lo amb l'API C de TDB. Amb GDBM seria molt semblant.
El package de TDB em proporciona eines per a examinar fitxers de bases de dades TDB. Aquest pot ser un avantatge decisiu a l'hora de fer decantar-se per TDB per a implementar les taules hash d'una aplicació. No cal dir que l'API C de TDB permet volcar, i recuperar, taules hash a, i de, fitxers.
Com en els casos anteriors, he desenvolupat el programa amb Anjuta, amb un projecte C genèric mínim. M'ha calgut tocar el fitxer makefile.am (per a l'automake) per a afegir-li la referència a la
llibreria libtdb:
## Process this file with automake to produce Makefile.in
## Created by Anjuta
AM_CPPFLAGS = \
-DPACKAGE_DATA_DIR=\""$(datadir)"\"
AM_CFLAGS =\
-Wall\
-g
bin_PROGRAMS = hashtables_tdb
hashtables_tdb_SOURCES = \
main.c
hashtables_tdb_LDFLAGS = -ltdb
hashtables_tdb_LDADD =
Vet aquí el codi (consulteu
API TDB)
#include <stdio.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <sys/types.h> /* mode_t */
#include <tdb.h>
struct value { /* aquesta estructura és la dels valors */
int age, room; /* emmagatzemats a la taula */
};
#define NUM_KEYS 5000 /* número d'elements. */
#define KEY_SIZE 20 /* tamanys de la clau*/
int main() {
TDB_CONTEXT *tdbHashTable;
TDB_DATA tdbKey, tdbValue;
char keysData[NUM_KEYS * KEY_SIZE]; /* espai d'emmagatzematge de la taula de claus. */
struct value valuesData[NUM_KEYS]; /* espai d'emmagatzematge de la taula de valors. */
char *keyPtr = keysData; /* següent posició a l'espai de valors. */
struct value *valuePtr = valuesData; /* següent posició a l'espai de claus. */
char keyToFind[KEY_SIZE]; /* clau a buscar, màxim de KEY_SIZE caràcters */
int i=0; /* comptador de claus afegides*/
/* Crea taula hash.*/
printf("Crea la taula\n");
tdbHashTable = tdb_open("prova.tdb",
0,
TDB_CLEAR_IF_FIRST,
O_RDWR | O_CREAT | O_TRUNC,
0666);
printf("Introdueix clau age room a la taula. Per acabar d'entrar valors prem CTRL-D\n");
while (scanf("%s %d %d",
keyPtr,
&valuePtr->age,
&valuePtr->room) != EOF && i++ < NUM_KEYS) {
/* traça */
printf("Afegeix %s %d %d a la taula\n",
keyPtr,
valuePtr->age,
valuePtr->room);
/* els posa a la taula */
printf("Afegeix - tdb_store\n");
tdbKey.dptr = keyPtr;
tdbKey.dsize = strlen(keyPtr) + 1; /* caràcter 0 de final*/
tdbValue.dptr = valuePtr;
tdbValue.dsize = sizeof(struct value);
tdb_store(tdbHashTable, tdbKey, tdbValue, TDB_INSERT);
/* prepara els punters per a nova clau valor*/
keyPtr += strlen(keyPtr) + 1;
valuePtr++;
}
/* Ara busca per la taula. */
printf("Busca valors a la taula. Per acabar CTRL-C\n");
keyPtr = keyToFind;
while (scanf("%s", keyPtr) != EOF) {
printf("Buscant %s amb tdb_fetch\n", keyPtr);
/* prepara la clau per a la cerca*/
tdbKey.dptr = keyPtr;
tdbKey.dsize = strlen(keyPtr) + 1;
tdbValue = tdb_fetch(tdbHashTable, tdbKey);
if (tdbValue.dptr != NULL) {
/* si ha trobat diferent de nul, el mostra. */
/* obté el punter al valor a partir del TDB_DATA retornat*/
valuePtr = tdbValue.dptr;
printf("found %s, age = %d, room = %d\n",
keyPtr,
valuePtr->age,
valuePtr->room);
} else
printf("not found %s\n", keyPtr);
}
tdb_close(tdbHashTable);
return (0);
}
No hi han gaires diferències amb els casos anteriors. Si de cas remarcar l'ús de l'estructura TDB_DATA, per a passar, i recuperar, les claus i els valors a, i de, les funcions de l'API.
Amb la funció tdb_open es crea físicament un fitxer prova.tdb que podrem examinar (i modificar) amb tdbtool. Tanmateix, hauria pogut fer servir l'opció TDB_INTERNAL per a crear la taula hash només en memòria.
Una execució del programa anterior:
albert@atenea:~/wk-c/prova-hash-tdb$ hashtables_tdb
Crea la taula
Introdueix clau age room a la taula. Per acabar d'entrar valors prem CTRL-D
albert 42 125
Afegeix albert 42 125 a la taula
Afegeix - tdb_store
montse 40 125
Afegeix montse 40 125 a la taula
Afegeix - tdb_store
artiom 6 125
Afegeix artiom 6 125 a la taula
Afegeix - tdb_store
^D
Busca valors a la taula. Per acabar CTRL-C
prova
Buscant prova amb tdb_fetch
not found prova
albert
Buscant albert amb tdb_fetch
found albert, age = 42, room = 125
montse
Buscant montse amb tdb_fetch
found montse, age = 40, room = 125
artiom
Buscant artiom amb tdb_fetch
found artiom, age = 6, room = 125
^C
albert@atenea:~/wk-c/prova-hash-tdb$
I, a més, tenim un fitxer prova.tdb amb la taula generada. Aquest fitxer el podem examinar amb tdbtool:
albert@atenea:~/wk-c/prova-hash-tdb$ tdbtool prova.tdb
tdb> dump
key 7 bytes
artiom
data 8 bytes
[000] 06 00 00 00 7D 00 00 00 ....}..
key 7 bytes
montse
data 8 bytes
[000] 28 00 00 00 7D 00 00 00 (...}..
key 7 bytes
albert
data 8 bytes
[000] 2A 00 00 00 7D 00 00 00 *...}..
tdb> quit
albert@atenea:~/wk-c/prova-hash-tdb$
Dump fa un volcat de la taula en format de cadena. Què obtenim? pèr a cada registre de la taula obtenim: la clau i 8 bytes de dades en hexadecimal. No cal dir que 7D és 125; 06 hex. és 6 decimal; 28 hex. és 42 decimal i 2A hex, 40 decimal.
Conclusió
Evidentment, aquests petits escripts només són una aproximació a la implementació de taules hash amb GlibC, Glib i TDB.
Segurament, per a la majoria d'aplicacions n'hi ha prou i són més que suficients les funcions per a hashtables de la llibreria estàndard de C (GLibC); tanmateix, en aplicacions GTK, la GLib hi és present i aporta funcions més flexibles -per exemple, permetent definir la funció hash- i, a més, fan servir els tipus de dades de GTK, sent consistents amb la resta de l'aplicació.
Finalment, TDB pot ser una bona tria en el cas que ens interessi poder disposar de la taula hash en un fitxer i, a més, ens proporciona eines addicionals, la tdbtool, per a manipular aquests fitxers.
