HASH(3) Manuel du programmeur Linux HASH(3)
NOM
hash - Méthodes d'accès aux bases de données avec tables
de hachage.
SYNOPSIS
#include <sys/types.h>
#include <db.h>
DESCRIPTION
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 per
formances puisse être observée. La valeur par
Linux 11 Mai 1999 1
HASH(3) Manuel du programmeur Linux HASH(3)
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 partic
ulièrement mauvaise sur un jeu particulier de
données. La fonction de hachage fournie par l'util
isateur doit prendre deux arguments (un pointeur
sur une chaîne d'octets et une longueur) et ren
voyer 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 essay
era 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.
ERREURS
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).
VOIR AUSSI
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 Pro
ceedings, Winter 1991.
Linux 11 Mai 1999 2
HASH(3) Manuel du programmeur Linux HASH(3)
BUGS
Seuls les ordres d'octets big-endian et little-endian
fonctionnent.
TRADUCTION
Christophe Blaess, 1999
Linux 11 Mai 1999 3