[ABD] Le hachage sous SQLite

SQLite est un petit SGBD. Il est largement utilisé pour ses performances pour les petites bases des données (sur Smartphone, navigateurs web, applications de gestion de petite taille, etc.). SQLite est Open Source et il est écrit en C, c'est pourquoi il représente un excellent choix pour analyser le code d'un SGBD et voir du plus près les algorithmes et les techniques utilisés en bas niveau d'un SGBD (les module les plus proches du fichier physique - voir schéma).

Dans cet article, nous allons voir une fonction très intéressante de SQLite : c'est la fonction de hachage.
Le hachage est une structure très efficace pour les fichiers. Elle permet de réduire considérablement le nombre d'accès disque lors d'une recherche d'un enregistrement et sans utiliser des structures secondaires (index, arbre-B+, etc.).
L'idée est de choisir la position d'insertion des nouveaux éléments en appliquant une fonction, dite fonction du hachage, sur un champ (clé du hachage) de l'enregistrement à insérer.
Cette approche est largement décrite par différents auteurs. Pour plus de détails, je vous recommande le cours de Pr. D.E. Zegour :
Structures des données avancées
Restons sur notre SGBD d'aujourd'hui : SQLite. Comme nous avons mentionné, le code source de SQLite est disponible.L' analyse de ce code en cherchant les fonctions liées au hachage ne peut être plus simple puisque le code est bien organisé; nous pouvons constater directement  les deux fichiers :

1. hash.h
2. hash.c

Le fichier entête déclare les focntions nécessaires et le fichier en C les implémente (pour ne pas entrer en détail.
La fonction qui nous interesse c'est la fonction strHash suivante :

/*
** The hashing function.
*/
static unsigned int strHash(const char *z){
  unsigned int h = 0;
  unsigned char c;
  while( (c = (unsigned char)*z++)!=0 ){
    h = (h<<3) ^ h ^ sqlite3UpperToLower[c];
  }
  return h;
}

Cette fonction prend comme paramètre une chaine de caractère et nous retourne un entier (non signé) qui représente le numéro de bloc où indérer l'enregistrement.
Les trois opérateurs principaux sont :

• << : décalage à gauche par un certain nombre de bits,
• ^ : le OU bit-à-bit exclusif,
• sqlite3UpperToLower : convertir les majuscule en miniscule.

Prenons un exemple et calculons la valeur de hachage pour la chaîne de caractère "Abc"
Notons que nous aurons besoin des codes binaires des caractères suivants :

• a (en miniscule) : 01100001
• b : 01100010
• c : 01100011

le "h" à calculer est initialisé à 0 et les trois carcatères de notre chaîne sont traités l'un après l'autre grâce à la condition de la boucle while :

 while( (c = (unsigned char)*z++)!=0 ){
    ...
  }

• Pour le A :

h << 3 : 0000000000000000000000000000 ^
h      : 0000000000000000000000000000 ^
a      : 0000000000000000000001100001
=      : 0000000000000000000001100001

• Pour le b : 

h << 3 : 0000000000000000001100001000 ^
h      : 0000000000000000000001100001 ^
b      : 0000000000000000000001100010
=      : 0000000000000000001100001011

• Pour le c : 

h << 3 : 0000000000000001100001011000 ^
h      : 0000000000000000001100001011 ^
c      : 0000000000000000000001100011
=      : 0000000000000001101100100000

Ainsi, la valeur de hachage pour la chaîne de caractères "Abc" est :6944 .