hash - Méthodes d'accès aux bases de données avec tables de hachage.

#include <sys/types.h>
#include <db.h>

La routine dbopen est l'interface de bibliothèque pour les fichiers de base de données. L'un des formats de fichier supportés est la table de hachage. La description générale des méthodes d'accès à une base de données est fournie dans la page de manuel dbopen(3). La page présente ne décrit que les informations spécifiques aux tables de hachage.

Les structures de hachage représentent un schéma de base de données dynamique et extensible.

La structure de données spécifique aux tables de hachage que l'on transmet à dbopen est définie dans <db.h> ainsi : typedef struct { u_int bsize;

u_int ffactor;

u_int nelem;

u_int cachesize;

u_int32_t (*hash)(const void *, size_t);

int lorder; } HASHINFO;

Les éléments de cette structure sont les suivants :

bsize

Bsize (bucket size) défini la taille des cases de la table, et vaut, par défaut, 256 octets. Il est préférable d'augmenter la taille de page pour les table situées sur disque ayant des éléments avec beaucoup de données.

ffactor

Ffactor indique une densité désirée au sein de la table. Il s'agit d'une approximation du nombre de clés pouvant s'accumuler dans une seule case, ce qui détermine le moment où la table doit s'aggrandir ou se rétrécir. La valeur par défaut est 8.

nelem

Nelem est une estimation de la taille finale de la table de hachage. S'il n'est pas configuré, ou s'il est configuré trop bas, la table s'aggrandira quand même correctement au fur et à mesure de l'entrée des clés, bien qu'une légère dégradation des performances puisse être observée. La valeur par défaut est 1.

cachesize

Une taille maximale suggérée de mémoire cache, en octets. Ceci n'a qu'une valeur indicative, et les méthodes d'accès alloueront plus de mémoire plutôt que d'échouer.

hash

Hash est une fonction définie par l'utilisateur. Comme aucune fonction de hachage ne se comporte parfaitement bien sur tout type de données, il peut arriver que la fonction interne soit particulièrement mauvaise sur un jeu particulier de données. La fonction de hachage fournie par l'utilisateur doit prendre deux arguments (un pointeur sur une chaîne d'octets et une longueur) et renvoyer une valeur sur 32 bits utilisable comme valeur de hachage.

lorder

L'ordre des octets pour les entiers stockés dans la base de données. Ce nombre doit représenter l'ordre sous forme d'entier. Par exemple l'ordre poids faible-poids fort (big endian) est représenté par le nombre 4321. Si lorder vaut 0 (pas d'ordre indiqué), on utilise l'ordre des octets du système hôte.

Si le fichier existe déjà, on utilise l'ordre des octets indiqués lors de sa création.

SI une fonction de hachage est indiquée, hash_open essayera de déterminer s'il s'agit de la même fonction que celle indiquée lors de la création de la base de donnée, et échouera si ce n'est pas le cas.

Des interfaces pour les routines décrites dans dbm(3), et ndbm(3) sont fournies, toutefois ces interfaces ne sont pas compatibles avec les anciens formats de fichiers.

Les routines des méthodes d'accès au tables de hachage peuvent échouer et remplir errno avec n'importe quelle erreur indiquée par la routine dbopen(3).

Seuls les ordres d'octets big-endian et little-endian fonctionnent.

btree(3), dbopen(3), mpool(3), recno(3) Dynamic Hash Tables, Per-Ake Larson, Communications of the ACM, April 1988. A New Hash Package for UNIX, Margo Seltzer, USENIX Proceedings, Winter 1991.

Christophe Blaess, 1999-2003.