HashTable = tableau associatif

8 avril 2007
c

Fonctions de Hash

Je ne me souviens plus bien quelle était la fonction de Hash utilisée dans ma HashTable mais je devrais bouquiner l'article suivant :

Hash Functions for Hash Table Lookup (Jenkins, 1997)

Un petit bout de code pour tester une fonction de hash qui minimise les collisions pour des adresses mémoires stockées dans une hash table. Avec cet exemple j'ai un taux d'occupation de ~1.4 pour 60000 pointeurs stockés, ce qui est très appréciable.

function    hash($n)
{
    $a = (($n >> 24) & 0xF) << 7;
    $b = (($n >> 16) & 0x3F) << 6;
    $c = (($n >> 8) & 0xFF) << 1;
    $d = $n & 0xFF;
    $d *= $d;
    return ($a+$b+$c+$d) & 0xFFFF;
}

$Counts = array();
$p = 0x81000000;        //Adresse mémoire de départ pour l'affectation des new...
for($i=0; $i<60000; $i++)       {
    $Hash = hash($p + $i*32 + rand(0, 24));
    if (!isset($Counts[$Hash]))     $Counts[$Hash] = 0;
    $Counts[$Hash]++;
}

$Total = 0;
foreach($Counts as $Index=>$Count)      $Total += $Count;
echo "Moyenne d'occupation (".count($Counts)." cellules occupées) : ".($Total / count($Counts))."<br/>\n\";

La fonction de hash adaptative

Si je veux stocker des pointeurs mémoires dans une hashtable (en table de correspondance ID<-->Pointeurs) j'aurais intérêt à analyser les pointeurs successivement renvoyés par new et à rendre la fonction de hash adaptative : elle se modifierait en fonction des adresses fournies par new. Une analyse des bits les plus fréquemment changeant ou fixes et hop !

Accueil