PHP Internals : Hashtables et tableaux PHP

Publié le 30 mars 2012 et mis à jour le 7 novembre 2012

Par Julien PauliSite personnelBlog

 

Les tables de hachage (hashtables) représentent une structure très utilisée dans le langage C pour stocker des paires clé/valeur de données en mémoire. Exactement ce que font les tableaux (array) PHP, qui en sont une implémentation.
Nous allons ici brièvement définir les tables de hachage, puis nous allons nous intéresser à la manière dont elles ont été implémentées dans PHP.
Nous détaillerons comment les manipuler, nous noterons quelques points remarquables et enfin nous ferons un petit le tour de leurs très nombreuses utilisations au sein du code source de PHP. Commentez Donner une note à l'article (0)

Viadeo Twitter Google Bookmarks ! Facebook Digg del.icio.us MySpace Yahoo MyWeb Blinklist Netvouz Reddit Simpy StumbleUpon Bookmarks Windows Live Favorites      



I. Pré-requis, rappels indispensables
II. Qu'est ce qu'une table de hachage ?
III. Implémentation des hashtables dans PHP
IV. API des hashtables
V. Manipulation des hashtables
VI. Cas d'utilisation des hashtables de PHP
VI-A. Liste des fonctions et classes disponibles
VI-B. Liste des variables du script
VI-C. Liste des directives INI
VII. Particularités remarquables et performances
VII-A. Consommation mémoire
VII-B. Gestion des clés numériques et littérales
VII-C. Agrandissement de la table et rehashing
VII-D. Collisions dans l'algorithme de hashage
VIII. Conclusions


I. Pré-requis, rappels indispensables

Pour suivre cet article, vous devez bien maitriser le langage C, avoir des notions sur les structures remarquables - comme les listes chainées - et être au courant du fonctionnement interne de PHP.

Vous pouvez pour cela vous aider des articles suivants :
fr PHP Internals : Fonctionnement global de PHP ;
fr Compilation détaillée de PHP sous Linux ;
fr Les listes chaînées en langage C ;
fr Les listes doublement chaînées en C.


II. Qu'est ce qu'une table de hachage ?

Je n'ai pas envie de revenir sur la théorie, surtout lorsque vous trouvez sur le Web - ou sur developpez.com directement - de très bons articles qui expliquent ces notions.
fr Les tables de hachage
en Theory of hashtables (extrait de en Mastering Algorithms with C)

Pour simplifier : en C, les tableaux doivent avoir une taille de clé fixe, de type size_t. Ecrire l'équivalent en PHP de $a[1] = 8; est possible en C, mais on ne peut pas écrire l'équivalent PHP de $a['foo'] = 8; car la clé ne peut être de type chaine.
Aussi, en C, les tableaux sont typés, c'est-à-dire que si on stocke des entiers à l'intérieur, on ne peut pas stocker de chaines en même temps (on ne peut mixer les types dans un même tableau).
Enfin, en C, les tableaux ont une taille fixe. On peut cependant changer leur taille si on utilise l'allocation dynamique de mémoire.
Nous sommes donc bien loin des tableaux PHP. Mais le C étant très bas niveau, on peut implémenter les tableaux PHP avec. L'idée est de transformer la clé en un entier de taille fixe, et de stocker dans le tableau C des pointeurs (taille fixe) vers des données de type différents.
J'ai beaucoup simplifié la problématique, mais ça donne un bon point de vue. Nous allons voir comment PHP a relevé ce challenge.


III. Implémentation des hashtables dans PHP

Les tables de hachage sont implémentées dans le ZendEngine. Elles se trouvent dans zend_hash.h/zend_hash.c. Elles se décomposent en deux structures, manipulables au moyen d'une poignée de fonctions et de macros. Ce n'est pas fondamentalement très compliqué, plutôt assez classique :
La table de hachage dans le ZendEngine

typedef struct _hashtable {
	uint nTableSize;            /* Taille de la table */
	uint nTableMask;            /* masque pour la fonction de hachage */
	uint nNumOfElements;        /* Nbre d'éléments dans la table */
	ulong nNextFreeElement;     /* hash du prochain élément */
	Bucket *pInternalPointer;   /* Elément couramment pointé */
	Bucket *pListHead;          /* Elément de tête */
	Bucket *pListTail;          /* Elément de queue */
	Bucket **arBuckets;         /* Ensemble des éléments */
	dtor_func_t pDestructor;    /* Fonction de destruction */
	zend_bool persistent;       /* Table persistente ou non*/
	unsigned char nApplyCount;  /* Utilisé pour traquer la récursivité */
	zend_bool bApplyProtection;
#if ZEND_DEBUG
	int inconsistent;
#endif
} HashTable;
buckets : éléments de la table de hachage ('cases' ou encore 'alvéoles') 

/* Un 'bucket' est une case unique de tableau, on parle parfois d'alvéole, ou d'élément */
typedef struct bucket {
	ulong h;                        /* Clé hachée par l'algo de hashage */
	uint nKeyLength;                /* Taille de la clé, 0 si indéxé numériquement */
	void *pData;                    /* Pointeur sur donnée utile */
	void *pDataPtr;                 /* Donnée utile (la plupart du temps) */
	struct bucket *pListNext;       /* Donnée suivante dans la table */
	struct bucket *pListLast;       /* Donnée précédente dans la table */
	struct bucket *pNext;           /* Donnée suivante dans la liste de cette case (colisions) */
	struct bucket *pLast;           /* Donnée précédente dans la liste  de cette case (colisions) */
	char *arKey;                    /* Clé (pour un tableau indéxé litéralement) */
} Bucket;
Comme vous avez lu la théorie des tables de hachage, on peut identifier des termes que vous devriez connaitre : les Hashtables du ZendEngine utilisent des listes chainées pour résoudre la problématique de la collision dans la fonction de hachage.
La fonction de hachage utilisée est "DJBX33A (Daniel J. Bernstein, Times 33 with Addition)", la voici pour info :
La fonction de hachage par défaut des HashTables du ZendEngine

/*
 * DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
 *
 * This is Daniel J. Bernstein's popular `times 33' hash function as
 * posted by him years ago on comp.lang.c. It basically uses a function
 * like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
 * known hash functions for strings. Because it is both computed very
 * fast and distributes very well.
 *
 * The magic of number 33, i.e. why it works better than many other
 * constants, prime or not, has never been adequately explained by
 * anyone. So I try an explanation: if one experimentally tests all
 * multipliers between 1 and 256 (as RSE did now) one detects that even
 * numbers are not useable at all. The remaining 128 odd numbers
 * (except for the number 1) work more or less all equally well. They
 * all distribute in an acceptable way and this way fill a hash table
 * with an average percent of approx. 86%. 
 *
 * If one compares the Chi^2 values of the variants, the number 33 not
 * even has the best value. But the number 33 and a few other equally
 * good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
 * advantage to the remaining numbers in the large set of possible
 * multipliers: their multiply operation can be replaced by a faster
 * operation based on just one shift plus either a single addition
 * or subtraction operation. And because a hash function has to both
 * distribute good _and_ has to be very fast to compute, those few
 * numbers should be preferred and seems to be the reason why Daniel J.
 * Bernstein also preferred it.
 *
 *
 *                  -- Ralf S. Engelschall <rse@engelschall.com>
 */

static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength)
{
	register ulong hash = 5381;

	/* variant with the hash unrolled eight times */
	for (; nKeyLength >= 8; nKeyLength -= 8) {
		hash = ((hash << 5) + hash) + *arKey++;
		hash = ((hash << 5) + hash) + *arKey++;
		hash = ((hash << 5) + hash) + *arKey++;
		hash = ((hash << 5) + hash) + *arKey++;
		hash = ((hash << 5) + hash) + *arKey++;
		hash = ((hash << 5) + hash) + *arKey++;
		hash = ((hash << 5) + hash) + *arKey++;
		hash = ((hash << 5) + hash) + *arKey++;
	}
	switch (nKeyLength) {
		case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
		case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
		case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
		case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
		case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
		case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
		case 1: hash = ((hash << 5) + hash) + *arKey++; break;
		case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
	}
	return hash;
}
Finalement il s'agit là d'une implémentation assez "banale" d'un type de tables de hachage en C. Il est un peu plus complexe qu'une implémentation "bateau", car nous verrons que les HashTables sont très utilisées au sein de PHP, et donc leur performance est particulièrement importante. Des astuces concernant les performances ont donc été implémentées, pour éviter de traverser toute une liste chainée lorsque ce n'est pas nécessaire, ou encore le pré-calcul de certaines clés de hachage.
L'algorithme DJBX33A n'a là aussi pas été choisi au hasard : il offre une entropie pas mauvaise, mais surtout, il est très rapide.

Principe des tables de hachage de PHP

IV. API des hashtables

On va commencer par quelques rappels de faits, ou quelques règles :

Règles régissant les tables de hachage dans PHP (certaines détaillées en dernière partie)
  1. La table consomme de la mémoire dès l'insertion du premier élément, elle va réserver de l'espace pour tous les pointeurs des futurs éléments (des Buckets *) ;
  2. La table a une taille fixe, déterminée à sa création. Elle pourra certes grossir dans le futur (elle est doublée), mais ceci aura un coût en terme de performance ;
  3. La taille de la table est arrondie à la puissance de 2 immédiatement supérieure (alignement, facilité d'accès à la mémoire), une table prévue pour 23 éléments (par exemple) comportera 32 cases ;
  4. A la suppression d'un élément de la table, une fonction de "destruction" lui est éventuellement appliquée (changeable, c'est un pointeur sur fonction) ;
  5. Tous les éléments utilisent la même fonction de destruction, on a donc interêt à stocker dans la table des structures du même type ;
  6. Dans PHP, les valeurs stockées dans la table seront systématiquement des zval*, même si la table peut en réalité contenir ce que l'on veut.
Ensuite, on va lister quelques notions sur le fonctionnement interne et ce qu'il faut savoir pour comprendre et utiliser l'API :

Fonctionnement des tables (important)
  1. Les éléments stockés dans la table sont de type Bucket*, vous ne créez pas manuellement de Bucket*, la table s'en charge ;
  2. On stocke dans un Bucket* une donnée (que vous avez en votre posséssion), plus précisément un pointeur sur cette donnée (void*) ;
  3. Chaque élément Bucket* est stocké dans la table à un index, aussi appelé "hash", de type ulong, calculé par une fonction de hashage dans le cas de clés textuelles (de type chaine) ;
  4. Chaque élément peut posséder une clé textuelle, dans arKey, c'est le cas d'une clé de tableau PHP de type chaine ;
  5. Si arKey vaut NULL dans l'élément, c'est qu'on utilise une clé de tableau PHP numérique ;
  6. De type entier ou chaine, la clé réelle de la table en C est un hash, elle peut être précalculée et réutilisée, l'API vous proposera alors des fonctions dites 'quick' ;
info Vous trouverez des informations complémentaires sur ces points et pas mal de détails dans le chapitre traitant des particularités, en fin d'article.
Pour allouer une HashTable, on peut l'affecter directement ou encore utiliser la macro ALLOC_HASHTABLE(). Ensuite, il faut préparer la structure, zend_hash_init() s'en charge :
Allouons une HT manuellement

HashTable *myht = emalloc(sizeof(HashTable));
Allouons une HT via la macro dédiée

ALLOC_HASHTABLE(myht);
Préparons la structure

ALLOC_HASHTABLE(myht);

zend_hash_init(myht, 10, NULL, NULL, (zend_bool)0);

/* myht est prête à être utilisée, on indique vouloir stocker 10 éléments,
   elle comportera donc 16 cases, la puissance de 2 immédiatement supérieure */
La signature est la suivante :
zend_hash_init()

int zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent);
/*
ht : la structure Hashtable* allouée
nSize : le nombre d'éléments maximum qu'elle contiendra
pHashFunction : la fonction de hachage, inutile depuis ZendEngine2, passer un pointeur nul
pDestructor : la fonction qui sera appelée sur l'élément lorsque celui-ci sera supprimé de la table
persistent : Allocation persistente ou pas, voir "Zend Memory Manager"
*/
nSize renseigne sur le nombre d'éléments que la table contiendra. Si elle en contient moins, ce n'est pas très grave. Si elle doit en contenir plus, alors elle sera agrandie et ceci aura un coût en terme de performance, car toutes les clés devront être recalculées via la fonction de hachage (plus d'information dans le chapitre sur les particularités).
pDestructor est appelée sur chaque élément lorsque celui-ci est supprimé de la table. Ceci permet, entre autre, une gestion automatique de la mémoire. En fait, puisqu'il s'agira d'une zval* dans presque tous les cas, il suffira de passer un pointeur sur une fonction qui joue avec le refcount de cette zval, et cette fonction existe déjà : zval_ptr_dtor().
persistent : Renseigne si l'allocation doit être persistente ou pas (voir fr Zend Memory Manager).

Si on détruisait cette table ?
Détruit myht en appelant la fonction de destruction sur chaque élément contenu

zend_hash_destroy(myht);
efree(myht);
/* myht est libéré */
Voila. Pas très difficile pour le moment. Méfiez-vous des fuites mémoires, on va stocker des pointeurs dans la table, et si la fonction de destruction ne les libère pas (éventuellement) lorsqu'on supprime l'élément de la table : ça va fuire dans tous les sens.
On va se mettre dans un cas PHP, et on ne va stocker dans la table que des zval*, la structure des variables PHP.
Pour manipuler en lecture ou écriture les HashTables, des fonctions et des macros sont disponibles. Les macros ne sont pas toujours écrites en majuscules.

De manière générale, on passera toujours l'adresse de la donnée à stocker, cette donnée étant elle-même souvent un pointeur.
La table copie le contenu qu'on lui passe s'il n'a pas la taille d'un pointeur, il est donc recommandé de lui passer un pointeur sur pointeur. Vous trouverez plus d'informations sur ce point dans le chapitre traitant des particularités, en fin d'article.

Selon la fonction utilisée, 2 solutions s'offrent à vous : soit vous utilisez une clé numérique, auquel cas il n'est pas nécessaire de calculer la clé de hachage; soit vous utilisez une clé littérale et vous possédez la clé de hachage (h) associée, soit il faut la calculer à partir de la clé littérale (vous, ou la table elle-même le fera).
API pour ajouter ou mettre à jour des données d'une table (écriture)

zend_hash_add(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest)
zend_hash_quick_add(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void *pData, uint nDataSize, void **pDest)
zend_hash_next_index_insert(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest)

zend_hash_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest)
zend_hash_quick_update(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void *pData, uint nDataSize, void **pDest)
zend_hash_index_update(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest)
API de récupération de données (lecture)

zend_hash_exists(const HashTable *ht, const char *arKey, uint nKeyLength)
zend_hash_quick_exists(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h)

zend_hash_index_exists(const HashTable *ht, ulong h)
zend_hash_get_current_key(const HashTable *ht, char **str_index, uint *str_length, ulong *num_index, zend_bool duplicate)
zend_hash_index_find(const HashTable *ht, ulong h, void **pData)

zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)
zend_hash_quick_find(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void **pData)
zend_hash_get_current_data(HashTable *ht, void **pData)
API de statistiques d'une table

zend_hash_num_elements(const HashTable *ht)
zend_hash_next_free_element(const HashTable *ht)
API d'itération d'une table

typedef Bucket* HashPosition;

typedef struct _HashPointer {
	HashPosition pos;
	ulong h;
} HashPointer;

zend_hash_get_pointer(const HashTable *ht, HashPointer *ptr)
zend_hash_set_pointer(HashTable *ht, const HashPointer *ptr)
zend_hash_internal_pointer_end(HashTable *ht)
zend_hash_internal_pointer_reset(HashTable *ht)
zend_hash_move_backwards(HashTable *ht)
zend_hash_move_forward(HashTable *ht)
API de suppression d'une table

zend_hash_del(HashTable *ht, const char *arKey, uint nKeyLength)
zend_hash_quick_del(HashTable *ht, const char *arKey, uint nKeyLength, ulong h)
zend_hash_index_del(HashTable *ht, ulong h)

zend_hash_clean(HashTable *ht)
zend_hash_destroy(HashTable *ht)
API de traitement des tables

zend_hash_func(const char *arKey, uint nKeyLength)
zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size)
zend_hash_apply(HashTable *ht, apply_func_t apply_func)
zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered)
zend_hash_merge(HashTable *ht, int key_type, const char *str_index, uint str_length, ulong num_index)
zend_hash_sort(HashTable *ht, sort_func_t sort_func, compare_func_t compar, int renumber
info Les listings ci-dessus détaillent l'API de manière non exhaustive. On repère cependant qu'il est possible d'effectuer à peu près toutes les actions possibles et imaginables sur une (ou des) table.
Une partie de l'API (non présentée ci-dessus) est de la forme _zend_hash_*(), elle est en théorie privée et réservée aux manipulations avancées.
Les fonctions parlent d'elles-mêmes, elles ne sont donc pas détaillées; consultez la source si nécessaire, ou voyez les exemples qui suivent.
L'API retourne très souvent SUCCESS ou FAILURE.
L'API "quick" concerne les clés textuelles et suppose que vous ayez à la fois la clé textuelle (char *) et son hash (h).
Comme dans une énorme majorité des cas, les Hashtables contiendront des zval*, il existe une API spécifique, basée sur l'API HashTable vue ci-dessus, mais qui s'occupe pour nous de créer et d'affecter les zval pour la plupart des opérations courantes.
API jouant avec les Hashtables et des zval

/* 'index' signifie clé numérique, 'assoc' signifie clé littérale */

/* la même API existe avec 'next_index' : à la place suivante */
add_index_bool(zval *arg, ulong index, int b)
add_index_long(zval *arg, ulong index, long n)
add_index_null(zval *arg, ulong index)
add_index_resource(zval *arg, ulong index, int r)
add_index_double(zval *arg, ulong index, double d)
add_index_string(zval *arg, ulong index, const char *str, int duplicate)
add_index_stringl(zval *arg, ulong index, const char *str, uint length, int duplicate)

add_assoc_bool_ex(zval *arg, const char *key, uint key_len, int b)
add_assoc_long_ex(zval *arg, const char *key, uint key_len, long n)
add_assoc_null_ex(zval *arg, const char *key, uint key_len)
add_assoc_resource_ex(zval *arg, const char *key, int r)
add_assoc_double_ex(zval *arg, const char *key, uint key_len, double d)
add_assoc_string_ex(zval *arg, const char *key, uint key_len, char *str, int duplicate)
add_assoc_stringl_ex(zval *arg, const char *key, uint key_len, char *str, uint length, int duplicate)
Voyons maintenant comment utiliser tout cela, il n'y a rien de vraiment compliqué, ça reste du C : de la rigueur, de la compréhension, et c'est gagné.


V. Manipulation des hashtables

Nous voila partis dans du concrêt. Nous allons créer quelques fonctions qui jouent avec les tables de hachage. (Nous réécrirons en fait une fonction hash_test() à chaque fois, pour les exemples).

info Nous supposons que vous connaissez l'API de PHP pour créer des fonctions PHP.
Nous supposons aussi que vous êtes à l'aise avec le concept de variables PHP "zval" et leurs macros associées.
Si ce n'est pas le cas, faites un tour sur PHP Internals : Les bases de la création d'extensions PHP.
Exemple simple HashTables stockant des zval

PHP_FUNCTION(hash_test)
{
    array_init(return_value);

    add_assoc_double(return_value, "foo", 1.1);
    add_assoc_string(return_value, "bar", "barvalue", 1);
    add_assoc_long(return_value, "foo", 2);
    add_next_index_bool(return_value, 1);

    zval **result = NULL;
    if(zend_hash_find(Z_ARRVAL_P(return_value), "foo", sizeof("foo"), (void **)&result) == SUCCESS) {
        php_printf("Found key 'foo', value was %ld \n", Z_LVAL_PP(result));
    }
    php_printf("The array's got %d elements \n", zend_hash_num_elements(Z_ARRVAL_P(return_value)));

    ulong somehash;
    somehash = zend_hash_func("bar", sizeof("bar"));
    if(zend_hash_quick_exists(Z_ARRVAL_P(return_value), "bar", sizeof("bar"), somehash)) {
        printf("The key 'bar' hash a hash of %ld and there is a value stored there", somehash);
    }
}
Petit exemple simple, qui pourrait se traduire en PHP par ceci :
Traduction PHP

<?php
function hash_test()
{
    $return_value = array()
    $return_value['foo'] = 1.1;
    $return_value['bar'] = 'barvalue';
    $return_value['foo'] = 2;
    if(array_key_exists('foo', $return_value)) {
        echo "Found key foo, value was {$return_value['foo']}";
    }
    printf("The array's got %d elements", count($return_value));
    if(array_key_exists('bar', $return_value)) {
        /* impossible de récupérer une clé hashée depuis PHP */
    }
    return $return_value;
}
Les fonctions add_*() créent une zval, leur affecte la bonne la valeur, et la stockent dans la table. Si vous utilisez plusieurs fois la même clé littérale, pour effectuer des recherches par exemple, n'oubliez pas de précalculer son hash, grâce à zend_hash_func(), et d'utiliser cette clé hashée plus tard avec les fonctions "quick", ça évite un recalcul à chaque fois.

warning Toutes les fonctions add_*() ajoutent dans la table l'adresse du pointeur sur la zval qu'elles créent, un zval** donc. Vous devrez ainsi récupérer en lecture le contenu sur une variable de type zval** et non zval*.
Les fonctions add_*() prennent en paramètre une zval de type IS_ARRAY, et non pas la HashTable directement.
Les fonctions add_*() utilisent ZEND_HANDLE_NUMERIC_KEY pour gérer les clés littérales de type numérique, comme "16", qui sera traduit en une clé numérique 16, voyez le chapitre sur les particularités en fin d'article pour plus d'informations.
Ainsi, si vous n'utilisez pas les fonctions add_*(), vous devez éventuellement gérer ces cas-là à la main (si nécessaire).

Voyons un exemple un peu plus "manuel" :
Exemple HashTables stockant des zval

PHP_FUNCTION(hash_test)
{
    HashTable *ht1 = NULL, *ht2 = NULL;

    ALLOC_HASHTABLE(ht1);
    ALLOC_HASHTABLE(ht2);
    /* ZVAL_PTR_DTOR : les hashtables vont contenir des zval */
    zend_hash_init(ht1, 2, NULL, ZVAL_PTR_DTOR, 0);
    zend_hash_init(ht2, 2, NULL, ZVAL_PTR_DTOR, 0);

    zval *myval = NULL;
    MAKE_STD_ZVAL(myval);
    ZVAL_STRING(myval, "hello world", 1);

    ulong key;
    /* Prochaine clé numérique libre, ici, c'est 0 bien sûr */
    key = zend_hash_next_free_element(ht1);
    /* Il n'est pas possible de récupérer la clé après l'ajout, nous l'avons récupérée avant (en la précalculant)*/
    if (zend_hash_next_index_insert(ht1, (void *)&myval, sizeof(zval *), NULL) == SUCCESS) {
        php_printf("Added zval to ht1 at index %ld \n", key);
    }

    if (zend_hash_add(ht2, "str", sizeof("str"), (void *)&myval, sizeof(zval *), NULL) == SUCCESS) {
        /* la zval va être partagée dans un 2ème tableau, incrémenter son refcount ! */
        Z_ADDREF_P(myval);
        php_printf("Added zval to ht2 at index 'str' \n");
    }
    /* La fonction PHP (hash_test() ici) retournera un tableau */
    array_init(return_value);

    /* Création de deux tableaux PHP array1 et array2 et liaison avec ht1 et ht2 */
    zval *array1 = NULL, *array2 = NULL;
    MAKE_STD_ZVAL(array1); MAKE_STD_ZVAL(array2);
    array1->value.ht = ht1; array2->value.ht = ht2;
    Z_TYPE_P(array1) = IS_ARRAY; Z_TYPE_P(array2) = IS_ARRAY;

    /* Ajout de array1 et array2 dans le tableau retourné par la fonction PHP */
    zend_hash_next_index_insert(Z_ARRVAL_P(return_value), (void *)&array1, sizeof(zval *), NULL);
    zend_hash_next_index_insert(Z_ARRVAL_P(return_value), (void *)&array2, sizeof(zval *), NULL);
Essai visuel de la fonction hash_test() créee ci-dessus

<?php
var_dump(hash_test());
/*
Added zval to ht1 at index 0 
Added zval to ht2 at index 'str' 
array(2) {
  [0]=>
  array(1) {
    [0]=>
    string(11) "hello world"
  }
  [1]=>
  array(1) {
    ["str"]=>
    string(11) "hello world"
  }
}
*/
Le but de l'article n'étant pas de publier des exemples pour 100% de l'API, nous allons parler d'un dernier point important : l'itération.
Il est possible d'itérer sur les tables de hachage de 2 manières différentes :

Manières d'itérer sur une table de hachage
  1. Manuellement, en se balandant dans la table d'élément en élément ;
  2. Automatiquement, en appliquant une fonction sur chaque élément de la table (traversée alors en interne).
Voyons un premier exemple, qui itère sur une table en utilisant une fonction de rappel sur chaque élément, et élimine d'une table tout élément stocké à une clé non numérique :
Supprimons tous les éléments qui ont une clé littérale

/* Rappel :
typedef struct _zend_hash_key {
	const char *arKey;
	uint nKeyLength;
	ulong h;
} zend_hash_key;
*/

static int my_sort(void *pDest, int num_args, va_list args, zend_hash_key *hash_key)
{
	if (hash_key->nKeyLength == 0) {
        /* key is numeric */
        return ZEND_HASH_APPLY_KEEP;
    }
    return ZEND_HASH_APPLY_REMOVE;
}

PHP_FUNCTION(hash_test)
{
    array_init_size(return_value, 8);

    add_assoc_bool(return_value, "bool", 1);
    add_index_double(return_value, 1, 1.1);
    add_next_index_string(return_value, "hello world", 1);
    add_assoc_long(return_value, "the answer", 42);

    zend_hash_apply_with_arguments(Z_ARRVAL_P(return_value), my_sort, 0);
}
Je vous laisse lire la source pour la forme de la fonction de rappel, ce n'est pas très complexe et assez puissant. A partir de là, on peut imaginer n'importe quoi, par exemple "Transforme toute les clés littérales en clés numériques", "Compte moi les clés numériques et les clés littérales" etc... On va vite tomber sur des fonctions PHP existantes, et je vous conseille de lire leur source pour débrouissailler votre esprit si nécessaire (en ext/standard/array.c).

Voyons ensuite comment traverser une table manuellement. Tout va se jouer avec le pointeur de position interne, pInternalPointer, que l'on va pouvoir copier éventuellement (recommandé) dans un HashPosition.

info pInternalPointer est de type Bucket*. HashPosition est un typedef vers Bucket*.
C'est assez simple au final : il s'agit de traverser une liste chainée, concept relativement connu dans la manipulation de données en langage C.
Parcourt de la table itérativement pour afficher les couples clé/valeur

static void copy_and_convert_to_string(const zval *orig, zval **dest)
{
    MAKE_STD_ZVAL(*dest);
    INIT_PZVAL_COPY(*dest, orig);
    zval_copy_ctor(*dest);
    convert_to_string(*dest);
}

PHP_FUNCTION(hash_test)
{
    HashTable *myht = NULL;
    ALLOC_HASHTABLE(myht);
    zend_hash_init(myht, 8, NULL, ZVAL_PTR_DTOR, 0);
    zval *array = NULL;
    ALLOC_ZVAL(array);
    array->type = IS_ARRAY;
    array->value.ht = myht;

    add_assoc_bool(array, "bool", 1);
    add_index_double(array, 1, 1.1);
    add_next_index_string(array, "hello world", 1);
    add_assoc_long(array, "the answer", 42);

    HashPosition mypos;
    zval **data = NULL;
    ulong longkey;
    char *strkey = NULL;
    zend_hash_internal_pointer_reset_ex(myht, &mypos);
	
    while(zend_hash_has_more_elements_ex(myht, &mypos) == SUCCESS) {
        zend_hash_get_current_data_ex(myht, (void **)&data, &mypos);
        php_printf("At key ");
        switch (zend_hash_get_current_key_type_ex(myht, &mypos)) {
            case HASH_KEY_IS_LONG:
                zend_hash_get_current_key_ex(myht, &strkey, NULL, &longkey, 0, &mypos);
                php_printf("%ld", longkey);
            break;
            case HASH_KEY_IS_STRING:
                zend_hash_get_current_key_ex(myht, &strkey, NULL, &longkey, 0, &mypos);
                php_printf("'%s'", strkey);
            break;
        }
        zval *datacopy = NULL;
        copy_and_convert_to_string(*data, &datacopy);
        php_printf(", we have '%s' \n", Z_STRVAL_P(datacopy));
        zval_ptr_dtor(&datacopy);

        zend_hash_move_forward_ex(myht, &mypos);
    }
    zval_ptr_dtor(&array);
}

/* Affiche :
At key 'bool', we have '1' 
At key 1, we have '1.1' 
At key 2, we have 'hello world' 
At key 'the answer', we have '42'
*/
info Les fonctions manipulant le "pointeur de position" ont des parallèles en PHP que vous devriez connaitre : les fonctions end(), current(), reset() etc...
Préférez l'utilisation d'un HashPosition, vous pouvez itérer sans mais vous aller toucher directement à la position interne pInternalPointer ce qui peut créer des problèmes et perturber la table si elle est utilisée ailleurs. En utilisant un HashPosition, vous gardez le contrôle du "pointeur d'itération" à tout moment et ne vous reposez jamais sur celui interne.

VI. Cas d'utilisation des hashtables de PHP

Les tables de hachages sont une structure tellement utiles, performantes et pratiques, qu'elles sont utilisées à plein d'endroits dans PHP.
Il existe cependant d'autres structures qui peuvent s'avérer plus pratiques pour certains cas précis, n'oublions pas les tableaux/pointeurs C, bien sûr, sinon PHP et le ZendEngine disposent encore de listes chainées génériques ou d'un tas (heap), par exemple.
Voyons tout de suite quelques exemples d'utilisation de HashTable en interne, les plus pertinents :

info Nous listons les organes de PHP dans l'article fr PHP Internals : Fonctionnement global de PHP. Il est vivement conseillé de le lire.

VI-A. Liste des fonctions et classes disponibles

Dans Compiler Globals (CG) et Executor Globals (EG), Zend initialise, stocke et détruit la liste des fonctions, des classes et des constantes connues dans des HashTables :
zend_startup(), démarre le ZendEngine

GLOBAL_FUNCTION_TABLE = (HashTable *) malloc(sizeof(HashTable));
GLOBAL_CLASS_TABLE = (HashTable *) malloc(sizeof(HashTable));
GLOBAL_AUTO_GLOBALS_TABLE = (HashTable *) malloc(sizeof(HashTable));
GLOBAL_CONSTANTS_TABLE = (HashTable *) malloc(sizeof(HashTable));

zend_hash_init_ex(GLOBAL_FUNCTION_TABLE, 100, NULL, ZEND_FUNCTION_DTOR, 1, 0);
zend_hash_init_ex(GLOBAL_CLASS_TABLE, 10, NULL, ZEND_CLASS_DTOR, 1, 0);
zend_hash_init_ex(GLOBAL_AUTO_GLOBALS_TABLE, 8, NULL, NULL, 1, 0);
zend_hash_init_ex(GLOBAL_CONSTANTS_TABLE, 20, NULL, ZEND_CONSTANT_DTOR, 1, 0);
Ensuite, lorsque par exemple, on appelle une classe depuis PHP, le code de la machine virtuelle mènera vers quelque chose comme ça :
zend_lookup_class_ex() recherche d'une classe

if (zend_hash_quick_find(EG(class_table), lc_name, lc_length, hash, (void **) ce) == SUCCESS) {
    if (!key) {
        free_alloca(lc_free, use_heap);
    }
    return SUCCESS;
}
C'est un "quick find" sur la HashTable représentant la liste des classes. La clé de hachage est en effet calculée une fois puis cachée par la suite, pour des raisons de performances.


VI-B. Liste des variables du script

Aussi appelée la "table des symboles", la liste des variables PHP disponibles pour l'espace de nommage courant est elle aussi stockée dans une HashTable de Executor Globals :
La table des symboles actifs

zend_hash_init(&EG(symbol_table), 50, NULL, ZVAL_PTR_DTOR, 0);
Idem, dans un code PHP, lorsqu'on tente d'accéder à une variable, la machine virtuelle cherchera dans cette table :
zend_fetch_var_address_helper() , accès à une variable PHP

if (zend_hash_quick_find(target_symbol_table, Z_STRVAL_P(varname), Z_STRLEN_P(varname)+1, hash_value, (void **) &retval) == FAILURE) {
    switch (type) {
        case BP_VAR_R:
        case BP_VAR_UNSET:
            zend_error(E_NOTICE,"Undefined variable: %s", Z_STRVAL_P(varname));
            /* break missing intentionally */
        case BP_VAR_IS:
            retval = &EG(uninitialized_zval_ptr);
            break;
/* ... */

VI-C. Liste des directives INI

Toutes les directives INI sont stockées elles aussi dans une table HashTable. Là encore, quelques coups d'oeil à la source... :
zend_ini_startup()

ZEND_API int zend_ini_startup(TSRMLS_D)
{
    registered_zend_ini_directives = (HashTable *) malloc(sizeof(HashTable));

    EG(ini_directives) = registered_zend_ini_directives;
    EG(modified_ini_directives) = NULL;
    EG(error_reporting_ini_entry) = NULL;
    if (zend_hash_init_ex(registered_zend_ini_directives, 100, NULL, NULL, 1, 0) == FAILURE) {
        return FAILURE;
    }
    return SUCCESS;
}
zend_ini_deactivate()

ZEND_API int zend_ini_deactivate(TSRMLS_D)
{
    if (EG(modified_ini_directives)) {
        zend_hash_apply(EG(modified_ini_directives), (apply_func_t) zend_restore_ini_entry_wrapper TSRMLS_CC);
        zend_hash_destroy(EG(modified_ini_directives));
        FREE_HASHTABLE(EG(modified_ini_directives));
        EG(modified_ini_directives) = NULL;
    }
    return SUCCESS;
}
Rien de fondamentalement complexe.


VII. Particularités remarquables et performances


VII-A. Consommation mémoire

Dès l'insertion du premier élément dans la table, toutes les alvéoles sont allouées dans ht.arBuckets. Un tableau de 2048 cases (2048 alvéoles) dont une seule est occupée, consomme tout de même 2048 fois la taille d'un pointeur sur Bucket, et en 64bits, un pointeur pèse 64bits, soit 8 octets tout de même (le fameux "problème" du 64bits).
Ainsi, une table peu pleine en éléments comporte tout de même X places disponibles allouées en mémoire pour X futures alvéoles à y loger :
Attention à la taille mémoire de la table

Hashtable *myht = emalloc(sizeof(HashTable)); /* Allocation */

/* Ici, aucune allocation n'est faite, juste de l'affectation */
zend_hash_init(myht, 32, NULL, NULL, (zend_bool)0);

char mystring[] = "foo";

/* Enregistrement d'un élément, la macro CHECK_INIT(ht); est exécutée dans cette fonction */
zend_hash_next_index_insert(myht, &mystring, sizeof(mystring), NULL);


/* Voici CHECK_INIT(ht); :
#define CHECK_INIT(ht) do {												
	if (UNEXPECTED((ht)->nTableMask == 0)) {								
		(ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent);
		(ht)->nTableMask = (ht)->nTableSize - 1;
	}
} while (0)

On constate que le premier remplissage (nTableMask vaut 0 lorsque la table est initialisée) va
allouer nTableSize pointeurs sur Bucket*, dans notre cas, 32*8=256 octets vont être alloués, alors
que nous n'allons insérer qu'une chaine "foo" de 4 octets.
En fait, le tableau arBuckets[] doit être préparé pour qu'il puisse être sondé pour vérifier
dans le futur le contenu des cases
*/

/*
L'alvéole elle-même, n'est allouée qu'après, à l'insertion effective, et la valeur qu'on y stocke
n'est qu'un pointeur universel void*

p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent);

Notez que la donnée insérée est copiée (dupliquée) dans la table. Souvent, on passera une donnée de type pointeur et on se retrouvera avec un double niveau d'indirection (void **).
Si la donnée n'a pas la taille d'un pointeur, la duplication peut peser loud

/* INIT_DATA() insère une nouvelle donnée dans la table */

/*
p est de type Bucket*
pData est un pointeur sur la donnée passée, de type void*
nDataSize est la taille de la donnée passée */
#define INIT_DATA(ht, p, pData, nDataSize);								
	if (nDataSize == sizeof(void*)) {									
		memcpy(&(p)->pDataPtr, pData, sizeof(void *));					
		(p)->pData = &(p)->pDataPtr;									
	} else {															
		(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
		if (!(p)->pData) {												
			pefree_rel(p, (ht)->persistent);						
			return FAILURE;												
		}																
		memcpy((p)->pData, pData, nDataSize);							
		(p)->pDataPtr=NULL;												
	}
Un exemple concrêt avec une chaine de caractères :
Insérer une chaine dans la table va mener à sa duplication

// ...
#define MYSTR "hello world!"

char *mystring = emalloc(sizeof(MYSTR));
strcpy(mystring, MYSTR);

/* Insertion de la chaine en table, elle va être dupliquée entièrement */
zend_hash_next_index_insert(myht, (void *)mystring, sizeof(MYSTR), NULL);

/* On libère le buffer alloué à la chaine */
efree(mystring);

void *data;

/* On récupère bien la donnée (la chaine) malgré la libération */
zend_hash_get_current_data(myht, &data);

/* La preuve : on l'affiche sur la sortie standard PHP */
PHPWRITE((char *)data, sizeof(MYSTR)); /* hello world! */

zend_hash_destroy(myht); /* La donnée dupliquée va ici être libérée en interne */
efree(myht);
Pour éviter de dupliquer trop d'octets (dans l'exemple précédent, on duplique sizeof("hello world") soit 12 octets), on passera souvent un pointeur sur sa donnée pour insérer dans la table. Ce pointeur va se retrouver logé dans le champ pDataPtr de l'alvéole, analysez INIT_DATA() pour comprendre.
On passe généralement un pointeur sur notre donnée, il va être stocké dans la table dans pDataPtr et son adresse sera stockée dans pData

// ...
#define MYSTR "hello world!"

char *mystring   = emalloc(sizeof(MYSTR));
strcpy(mystring, MYSTR);

/* Insertion de l'adresse du char* (char **) en table */
zend_hash_next_index_insert(myht, (void *)&mystring, sizeof(mystring), NULL);

/* On ne libère plus le buffer alloué, on va être embêté sinon */

void *data;

/* On récupère bien la donnée */
zend_hash_get_current_data(myht, &data);

/* Que l'on affiche sur la sortie standard PHP */
PHPWRITE(*(char **)data, sizeof(MYSTR)); /* hello world! */

/* On peut libérer */
efree(mystring);

zend_hash_destroy(myht);
efree(myht);
Attention à la fonction de libération (pDestructor). Elle sert à détruire éventuellement la donnée pointée par le pointeur présent dans l'alvéole, lorsque celle-ci est détruite (ou lorsque toute la table est détruite).
Dans le cas du stockage de zvals dans la table, ZVAL_PTR_DTOR peut être utilisé, sinon vous devez créer votre propre fonction dont le type doit être dtor_func_t.
Exemple de fonction de destruction personnalisée, qui s'occupe de libérer des structures perso

/* Soit une structure fictive que nous stockerons dans la stable */
struct mystruct {
	char *str;
	void *data;
};

/* Son destructeur */
void destroy_mystruct(struct mystruct* ptr)
{
	efree(ptr->str);
	efree(ptr->data);
}

/* Son destructeur spécifique pour une HashTable */
void destroy_mystruct_hash(void** ptr)
{
	destroy_mystruct(*(struct mystruct**)ptr);
}

/* Son constructeur */
struct mystruct* new_mystruct(size_t internalsize)
{
	struct mystruct* my_struct = (struct mystruct *)emalloc(sizeof(struct mystruct));
	my_struct->data = emalloc(internalsize);
	my_struct->str = emalloc(internalsize);

	return my_struct;
}

PHP_FUNCTION(hashtable_exemple)
{
    HashTable *myht = NULL;
    ALLOC_HASHTABLE(myht);
    void *data = NULL;
#define MYSTR "foo bar and baz"

    /* On créer et on remplit mystruct */
    struct mystruct* somestruct = new_mystruct(100);
    strncpy(somestruct->str, MYSTR, sizeof(MYSTR));

    /* On passe le destructeur à l'initialisation de la table */
    zend_hash_init(myht, 8, NULL, (dtor_func_t)destroy_mystruct_hash, (zend_bool)0);

    /* On ajoute l'adresse de somestruct dans la table */
    zend_hash_next_index_insert(myht, &somestruct, sizeof(struct mystruct*), NULL);

    /* Récupérons la donnée */
    zend_hash_get_current_data(myht, &data);
	
    /* Affichons le texte, par exemple */
    PHPWRITE((*(struct mystruct **)data)->str, sizeof(MYSTR));
	
    /* A la destruction de la table, la fonction de destruction est appliquée
       sur tous les éléments s'y trouvant */
    zend_hash_destroy(myht);
    efree(somestruct);
    efree(myht);
}

VII-B. Gestion des clés numériques et littérales

Quelle différence entre les tableaux PHP indéxés numériquement et littéralement ?
Les alvéoles de la table (les cases) sont repérées et indéxées grâce au hash de la clé. Que le tableau PHP soit numérique, littéral ou mixte, en C, seul le hash (h) compte.
Lorsque la clé est numérique, arKey et nKeyLength vallent NULL. On en n'a pas besoin, seul le hash de la clé servira à trouver l'alvéole lors d'une recherche.

info C'est bien le principe des tables de hachage : la clé de hashage est l'identifiant. A cause des collisions dans l'algo de hachage, il n'est malheureusement pas unique (presque), si plusieurs enregistrements ont la même clé de hachage, PHP les stocke alors dans une liste chainée.
Clé littérale

/* clé littérale, la valeur de la chaine est consérvée dans l'alvéole */

// ...
p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent);
if (!p) {
	return FAILURE;
}
p->arKey = (const char*)(p + 1);
memcpy((char*)p->arKey, arKey, nKeyLength);

p->nKeyLength = nKeyLength;
INIT_DATA(ht, p, pData, nDataSize);
p->h = h;
// ...
Clé numérique

// ...
p = (Bucket *) pemalloc_rel(sizeof(Bucket), ht->persistent);
if (!p) {
	return FAILURE;
}
p->arKey = NULL;
p->nKeyLength = 0; /* Numeric indices are marked by making the nKeyLength == 0 */
p->h = h;
INIT_DATA(ht, p, pData, nDataSize);
// ...
On a sinon carrément accès à zend_hash_get_current_key(), les choses sont claires : 

/* Notez qu'il existe une macro zend_hash_get_current_key() */

ZEND_API int zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos)
{
    Bucket *p;
    p = pos ? (*pos) : ht->pInternalPointer;

    IS_CONSISTENT(ht);

    if (p) {
        if (p->nKeyLength) {
            return HASH_KEY_IS_STRING;
        } else {
            return HASH_KEY_IS_LONG;
        }
    }
    return HASH_KEY_NON_EXISTANT;
}
Ainsi, si on a une chaine pour la clé, on la passe dans l'algo de hachage et on a une clé de hachage (Rappel : la clé de hachage est un ulong), si on a un entier, on le convertit en ulong et on l'utilise directement comme clé de hachage avec la table.
Notez que la table mémorise "l'index de la prochaine case vide", c'est à dire la clé de hachage "suivante" dans nNextFreeElement. A chaque ajout d'un index numérique dans la table, nNextFreeElement est incrémenté de une unité, et n'est jamais décrémenté. On retrouve là encore, le comportement des tableaux PHP.

Concernant les "chaines numériques", c'est-à-dire des chaines qui représentent très exactement des nombres, comme par exemple "452", vous les gérez comme vous voulez.
Soit vous les conservez sous forme de chaine, et vous tombez donc dans le cas banal d'une clé de type chaine, qui doit donc être hachée, soit vous considérez que cette clé doit être convertie en entier.
C'est ce que fait la machine virtuelle PHP avec les tableaux PHP, et c'est ce que vous permettent certaines fonctions de l'API zend_hash. La macro qui sert à ça est ZEND_HANDLE_NUMERIC_EX(), quant aux fonctions de l'API, en général, il faut regarder du coté de zend_symtable_*(), qui font la même chose que les traditionnelles zend_hash_*() , mais passent les clés dans ZEND_HANDLE_NUMERIC_EX() et transforment donc les clés de type "chaines numériques" en clés de type entier.
Ajout d'un élément à une clé numérique

HashTable *myht = NULL;
ALLOC_HASHTABLE(myht);
zend_hash_init(myht, 8, NULL, NULL, (zend_bool)0);

char foo[] = "foo";
ulong key = 123UL;

/* Si un élément existe à cette clé, il sera écrasé */
zend_hash_index_update(myht, key, &foo, sizeof(foo), NULL);
Ajout d'un élément à une clé littérale

HashTable *myht = NULL;
ALLOC_HASHTABLE(myht);
zend_hash_init(myht, 8, NULL, NULL, (zend_bool)0);

char data[] = "foo";
char key[] = "this-is-the-key";

/* La clé va passer dans l'algo de hachage */
zend_hash_add(myht, key, sizeof(key), &data, sizeof(data), NULL);
Ajout d'un élément à une clé littérale numérique que l'on convertit en entier comme le fait la VM

HashTable *myht = NULL;
ALLOC_HASHTABLE(myht);
zend_hash_init(myht, 8, NULL, NULL, (zend_bool)0);

char data[] = "foo";
char key[] = "123";
ulong h = 0UL;

/* Repère les chaines numériques et les convertit en ulong */
ZEND_HANDLE_NUMERIC_EX(key, sizeof(key), h, NULL);

zend_hash_index_update(myht, h, &data, sizeof(data), NULL);

/* Nous aurions pu utiliser directement
zend_symtable_update(myht, key, sizeof(key), &data, sizeof(data), NULL); */

VII-C. Agrandissement de la table et rehashing

Les index du tableau C arBuckets sont calculés en fonction du résultat de la fonction de hachage (bien entendu), et aussi d'un masque :
Calcul de l'index du tableau menant à la donnée

//...
ulong h;
uint nIndex;
Bucket *p;

h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask; /* masquage */
p = ht->arBuckets[nIndex];

//...
Si on ne masquait pas la clé, comme l'algo de hachage retourne un entier non signé (ulong), il faudrait posséder dans la table 2^64 cases : impossible, on explose la mémoire.
La clé de hachage est donc masquée avec nTableMask.
Mais nTableMask dépend directement de la taille de la table :
Macro CHECK_INIT(), le masque dépend directement du nombre d'éléments dans la table

(ht)->nTableMask = (ht)->nTableSize - 1;
On en déduit donc que si on venait à dépasser le nombre d'éléments précédemment prévu, il faut agrandir nTableSize (la taille sera doublée), et donc nécessairement recalculer toutes les clés de hachage de toutes les alvéoles déja présentes dans la table.
L'algorithme a beau être rapide, sur des centaines/milliers d'éléments, ceci a un coût en terme de cycles CPU.
zend_hash_do_resize() double la taille de la table, et appelle zend_hash_rehash() qui recalcule toutes les clés

static int zend_hash_do_resize(HashTable *ht)
{
    Bucket **t;
    IS_CONSISTENT(ht);
    if ((ht->nTableSize << 1) > 0) {	/* Let's double the table size */
        t = (Bucket **) perealloc_recoverable(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent);
        if (t) {
            HANDLE_BLOCK_INTERRUPTIONS();
            ht->arBuckets = t;
            ht->nTableSize = (ht->nTableSize << 1);
            ht->nTableMask = ht->nTableSize - 1;
            zend_hash_rehash(ht);
            HANDLE_UNBLOCK_INTERRUPTIONS();
            return SUCCESS;
        }
        return FAILURE;
    }
    return SUCCESS;
}

ZEND_API int zend_hash_rehash(HashTable *ht)
{
    Bucket *p;
    uint nIndex;

    IS_CONSISTENT(ht);
    if (UNEXPECTED(ht->nNumOfElements == 0)) {
        return SUCCESS;
    }

    memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
    p = ht->pListHead;
    while (p != NULL) {
        nIndex = p->h & ht->nTableMask;
        CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
        ht->arBuckets[nIndex] = p;
        p = p->pListNext;
    }
    return SUCCESS;
}

VII-D. Collisions dans l'algorithme de hashage

Petit résumé rapide et simple de la situation :

Récapitulatif
  • Chaque table comporte des cases, vides au début, mais allouées (reservées) pour de futurs éléments (alvéoles) ;
  • Dès insertion d'une donnée, l'alvéole est créee et logée dans la case dont l'index vaut la clé de hachage ;
  • La clé de hachage est soit calculée, soit pré-fournie ;
  • Lors du calcul, l'algo de hachage possède des collisions, il n'est pas parfait, et n clés d'entrées peuvent mener vers la même clé de hachage en sortie ;
  • Si il y a collision, 2 éléments se retrouvent donc affectés dans la même case, en théorie, ils devraient donc s'écraser mutuellement ;
  • Les Hashtables de PHP n'écrasent pas : si 2 éléments on la même clé de hachage, ils sont alors stockés dans une liste chainée, elle-même stockée dans la case.
Or, la recherche dans une liste chainée s'effectue en O(n), donc plus il va y avoir de collisions, plus la recherche sera lente.
Comme une recherche est lancée à chaque insertion dans la table (pour savoir si l'élément existe déja, et être éventuellement mis à jour le cas échéant), il est possible de manger toute la puissance CPU avec des index de tableau (PHP) spécialement conçus pour ça.

C'est exactement ce genre de faille qui a été découvert en Novembre 2011 (très très tard donc, les hashtables dans PHP datent de 2000 environ). Les informations techniques en se trouvent sur cette page avec des exemples d'exploits.
Comme PHP utilise très massivement les tables de hachages, y compris avec des données provenant de l'extérieur ($_GET, $_POST... ), il est facile de monter une attaque vers un serveur en injectant des données de l'extérieur qui vont mener à des collisions dans l'algo de hachage, et donc à une consommation CPU massive dûe à la traversée d'une seule et même liste chainée.
Exemple de code PHP menant à des collisions systématiques, donc extrêmement lent à s'exécuter

<?php
/* 2^15, par exemple, toute puissance de 2 fonctionne */
$taille = 32768;
$startTime = microtime(1);

$array     = array();
$maxInsert = $taille * $taille;

for ($key = 0; $key <= $maxInsert; $key += $taille) {
    $array[$key] = 0;
}

printf("%d insertions en %.2f secondes", $maxInsert, microtime(1)-$startTime);
J'obtiens sur ma machine 32768 insertions en 12.28 secondes, c'est énorme. Faites varier $taille, comme on est dans une boucle à incrémentation, on tombe en compléxité quadratique (O(n²)), et ça devient rapidement invivable.
Histoire de se convaincre, utilisez une $taille qui n'est pas une puissance de 2, par exemple 32767 (2^15 -1), le temps fond : moins d'une seconde nécessaire !

Le pourquoi du comment se trouve, comme toujours, dans le code source.
On sait que si on utilise un indice de tableau entier (PHP), la fonction de hachage n'intervient pas. Le hash de la clé dans le tableau C est simplement la clé PHP utilisée masquée par le masque de la HashTable :
Rappel du calcul de l'indice du tableau C dans lequel stocker la donnée

//...
ulong h;
uint nIndex;
Bucket *p;

/* Dans le cas d'un entier PHP comme $a[18], celui-ci est directement
   utilisé comme 'h', la fonction de hachage n'intervient pas */
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask; /* masquage */
p = ht->arBuckets[nIndex];

//...
Le masque est égal à la taille du tableau - 1. Si un tableau pèse 32768 éléments, le masque appliqué est 32767.
Représenté en binaire, il s'agit de 0111.1111.1111.1111. Ainsi, toute puissance de 2 supérieure à 32767 mènera à la même clé de hachage : 0
Collision dans la clé de hachage

for ($key = 0; $key <= $maxInsert; $key += $taille) {
    $array[$key] = 0;
}

masque: 0000.0111.1111.1111.1111
                 &
32768   0000.1000.0000.0000.0000
98304   0001.1000.0000.0000.0000
229376  0011.1000.0000.0000.0000
491520  0111.1000.0000.0000.0000
1015808 1111.1000.0000.0000.0000
...
             = 0 !
Plutôt que chaque élément soit distribué dans une case du tableau C sous-jascent différente, et donc mener à une insertion/recherche en O(1), toutes les clés du tableau PHP ont été spécialement conçues pour que, une fois le masque appliqué, elles mènent toutes vers la clé du tableau C '0'.
PHP se retrouve donc avec un tableau comportant plein de cases vides et une une seule (la case à l'index 0) pleine avec une liste chainée qui grossit à vue d'oeil, qu'il doit traverser de part en part à chaque nouvelle itération, celle-ci grossisant à chaque fois d'une unité. On est en compléxité O(n²) : le processeur de la machine mouline pendant un temps qui tend rapidement vers l'infini.

Une bonne distribution de la clé hashée
Une mauvaise distribution de la clé hashée
info La solution ultime consiste à changer l'algo de hachage (y compris le masquage) pour rajouter un facteur aléatoire dedans. Mais dans le cas de PHP, ce n'est pas si simple, car les performances des HashTables doivent rester très avantageuses, au risque de voir tout le langage prendre une claque. Aussi, le problème de l'aléatoire est qu'il n'est pas possible de stocker temporairement une table de hachage, et la ressortir à la requête suivante, ce que font par exemple les caches d'OPCode comme APC.

VIII. Conclusions

Les tables de hachage sont une structure remarquable en C, qui trouve de très nombreuses implémentations ça-et-là (ouvrez le code source de projets opensources pour en témoigner), PHP ayant la sienne, qui répond à ses problématiques.
Du point de vue du développeur PHP, il utilise directement ces tables au travers des tableaux PHP (array). Le développeur C, qui par exemple développe des extensions pour PHP, utilisera l'API zend_hash_* très souvent, car au sein de PHP les tables de hachage sont beaucoup utilisées.

Voyez aussi : fr PHP Internals : Les bases de la création d'extensions PHP
en A Closer Look Into PHP Arrays: What You Don't See



               Version PDF   Version hors-ligne   Version ePub   Version Azw   Version Mobi

Valid XHTML 1.0 TransitionalValid CSS!

Copyright © 2011 Julien Pauli. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts. Cette page est déposée.

 
 
Developpez.com

Nous contacter

Participez

Informations légales

 
Services

Forum PHP

Blogs

Hébergement

 
Partenaires

Hébergement Web