HASH
Section : Manuel du programmeur Linux (
3)
Mise à jour de la version anglaise : 18 août 1994
Index
Menu principal
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(3)
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(3)
est définie dans
<db.h>
ainsi :
typedef struct {
unsigned int bsize;
unsigned int ffactor;
unsigned int nelem;
unsigned int cachesize;
uint32_t (*hash)(const void *, size_t);
int lorder;
} HASHINFO;
Les éléments de cette structure sont les suivants :
- bsize
-
défini la taille des cases de la table (bucket size),
et vaut, par défaut, 256 octets.
Il est préférable d'augmenter la taille de page pour les tables situées
sur disque ayant des éléments avec beaucoup de données.
- 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'agrandir ou se rétrécir.
La valeur par défaut est 8.
- 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'agrandira 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
-
est la 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
-
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
-
est 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à, la valeur indiquée est ignorée et
on utilise l'ordre des octets indiqués lors de sa création.
Si le fichier existe déjà, (et que l'attribut
O_TRUNC
n'est pas spécifié), les valeurs indiquées pour les paramètres
bsize,
ffactor,
lorder
et
nelem
sont ignorés et on utilise l'ordre des octets indiqués
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ées,
et échouera si ce n'est pas le cas.
Des interfaces pour les routines décrites dans
dbm(3),
et
ndbm(3)
sont fournies pour compatibilité ascendante,
toutefois ces interfaces ne sont pas compatibles
avec les anciens formats de fichier.
ERREURS
Les routines des méthodes d'accès aux
tables de hachage
peuvent échouer et remplir
errno
avec n'importe quelle erreur indiquée par la routine
dbopen(3).
BOGUES
Seuls les ordres d'octets gros boutiste (big-endian)
et petit boutiste (little-endian) fonctionnent.
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 Proceedings, Winter 1991.
TRADUCTION
Ce document est une traduction réalisée par Christophe Blaess
<http://www.blaess.fr/christophe/> le 11 mai 1999
et révisée le 17 juillet 2008.
L'équipe de traduction a fait le maximum pour réaliser une adaptation
française de qualité. La version anglaise la plus à jour de ce document est
toujours consultable via la commande : « LANG=C man 3 hash ».
N'hésitez pas à signaler à l'auteur ou au traducteur, selon le cas, toute
erreur dans cette page de manuel.
Index
- NOM
-
- SYNOPSIS
-
- DESCRIPTION
-
- ERREURS
-
- BOGUES
-
- VOIR AUSSI
-
- TRADUCTION
-
Dernière mise à jour : 17 juillet 2008