Efficacité d'un algorithme de hachage de chaînes de caractères - Page 3

Un hash inferieur a 256 tout le temps :X
Tu veux hasher quoi au fait? Pke bjr les collisions...

Je me pose des contraintes

Ca me semble raisonnable en fait. D'ailleurs, le fichier megamix.txt fait 360 ko, et ma moulinette y trouve 26x256=6656 symboles. Je pense que le nombre maximal de symboles que mon programme sera amené à traiter sera inférieur à ça.
Le hachage permettra d'effectuer des recherches linéaires parmi 26 symboles en moyenne, au lieu de 6656. Ca me semble pas mal.

Je vais peut-être monter à une taille de 512, mais pas plus (soit une recherche linéaire sur 13 symboles au lieu de 6656).

Tu trouves que c'est trop ?

(en plus 256 doit etre un cas particulier, ça fait la meme taille qu'un char donc la fonction "simple" peut donner des resultats) essaye sur des tables plus grandes (dans les limite d'un long) et sur des tables plus petites, a mon avis tu risque d'avoir des changements (entre les "smart" et les "dumb" ones)

OK j'essaierai ça. Je vais modifier la source de la moulinette pour qu'on puisse changer facilement la taille des tables. On pourra faire des comparaisons plus poussées.

Thibaut (./60) :
Pollux : Puisque la boucle précédent le return donnera toujours un hach inférieur à 256, on peut faire return hash%256 non ?

surtout pas, la valeur modulo 257 et la valeur modulo 256 n'ont absolument rien à voir pour des nombres suffisamment grands en fait les propriétés mathématiques sont très différentes : par exemple, modulo 256, hash("il fait beau et chau") = hash("il fait chau et beau"), parce qu'on échange des lettres qui sont à 8 lettres d'écart, et que 33^8 = 1 mod 256 ; de même hash("hip hop") = hash("hop hip"), parce que i et o sont à 4 lettres d'écart, que 33^4 = 128+1 mod 256 et que i et o ont même parité... (et donc que i*128 mod 256 = o*128 mod 256)
modulo 257, on a pas tous ces problèmes parce que 257 est premier et que le plus petit nombre tel que 33^n = 1 mod 257, c'est n = 256 : autant dire que tu ne trouveras pas de contre-exemple de ce style pour une chaîne de moins de 256 caractères

(ne fais pas trop attention à la boucle while, c'est pas elle qui fait le gros du boulot : elle ne sert que dans un cas sur 257 ^^ c'est juste pour que même dans ce cas rare, les valeurs de hash restent bien distribuées )

La source, si vous souhaitez essayer plein de valeurs différentes : topics/103443-efficacite-dun-algorithme-de-hachage-de-chaines-de-caracteres#0
Il suffit de changer la constante HASH_TABLE_SIZE dans hashfunctions.h

Thibaut (./66) :
Voilà, j'ai testé avec une table de hachage longue de 1024 éléments, pour voir.
La fonction de Pollux, telle qu'il l'a donnée dans le ./55, est très mauvaise.

euh mais n'importe quoi, j'ai pas du tout écrit :

    for (s = str; *s; s++) {
        hash5+= hash + *s;
    }

(la fonction que j'ai donnée est en principe rigoureusement équivalente à hach_wkp, tant qu'il y a au plus 1024 valeurs de hash)

C'est pas pareil ?
Ah merde j'avais pas vu ton changement de variable ! dsl !

Corrigé Voilà le nouveau classement :

Pour un hash modulo 1024 :
1- Pollux (./55)
2- squalyl (./50)
3- fonction à la con (./41)

(Pollux et squalyl donnent la même efficacité à priori, mais comme Pollux est plus rapide, je la passe devant)

Pour un hash modulo 256 :
Même classement !


Source : topics/103443-efficacite-dun-algorithme-de-hachage-de-chaines-de-caracteres#0
Vous pouvez tester avec n'importe quel modulo, il suffit de changer la constante HASH_TABLE_SIZE dans hashfunctions.h

J'ai trouvé ça :
Fichier joint : GeneralHashFunctions_-_C.zip

dont les résultats sont :

mtrapier@prod500 ~/Desktop/test $ ./HashTest 
General Purpose Hash Function Algorithms Test
By Arash Partow - 2002         
Key:                         abcdefghijklmnopqrstuvwxyz1234567890
 1. RS-Hash Function Value:   4097835502
 2. JS-Hash Function Value:   1651003062
 3. PJW-Hash Function Value:  126631744
 4. ELF-Hash Function Value:  126631744
 5. BKDR-Hash Function Value: 3153586616
 6. SDBM-Hash Function Value: 3449571336
 7. DJB-Hash Function Value:  729241521
 8. DEK-Hash Function Value:  2923964919
 9. BP-Hash Function Value:   1726880944
10. FNV-Hash Function Value:  3243095106
11. AP-Hash Function Value:   3929913477
mtrapier@prod500 ~/Desktop/test $ ./GPHFATest 
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          7       1       35036   69693     1.50   66.55
 1      PJWHash         6       3       35017   69712     1.50   66.56
 2      ELFHash         6       3       35017   69712     1.50   66.56
 3      BKDRHash        6       9       35747   68982     1.52   65.87
 4      SDBMHash        7       1       37315   67414     1.55   64.37
 5      DJBHash         7       5       39062   65667     1.59   62.70
 6      DEKHash         8       1       40531   64198     1.63   61.30
 7      BPHash          110     476     103204  1525     68.66    1.46
 8      FNVHash         8       3       38609   66120     1.58   63.13
 9      APHash          7       10      38512   66217     1.58   63.23
mtrapier@prod500 ~/Desktop/test $ 

dont l'explication est trouvable la : http://www.partow.net/programming/hashfunctions/

Merci godzil.

parce que même si le code source est parfaitement portable, je vais pas installer un gcc et tout le bordel sur un ordi d'entreprise

Excuse-moi ne n'avoir pas pu servir ton impatience... Surtout que t'es sensé bosser sur autre chose que des tests de hash là non ?
Enfin bref

C'est dommage, ils n'ont pas testé l'algo de hash à la con.

j'ai refait les tests en ajoutant la version "stupide" (./41)

mtrapier@prod500 ~/Desktop/test $ ./HashTest 
General Purpose Hash Function Algorithms Test
By Arash Partow - 2002         
Key:                         abcdefghijklmnopqrstuvwxyz1234567890
 1. RS-Hash Function Value:   4097835502
 2. JS-Hash Function Value:   1651003062
 3. PJW-Hash Function Value:  126631744
 4. ELF-Hash Function Value:  126631744
 5. BKDR-Hash Function Value: 3153586616
 6. SDBM-Hash Function Value: 3449571336
 7. DJB-Hash Function Value:  729241521
 8. DEK-Hash Function Value:  2923964919
 9. BP-Hash Function Value:   1726880944
10. FNV-Hash Function Value:  3243095106
11. AP-Hash Function Value:   3929913477
12. StpdHash Function Value:  3372
mtrapier@prod500 ~/Desktop/test $ ./GPHFATest 
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          7       1       35036   69693     1.50   66.55
 1      PJWHash         6       3       35017   69712     1.50   66.56
 2      ELFHash         6       3       35017   69712     1.50   66.56
 3      BKDRHash        6       9       35747   68982     1.52   65.87
 4      SDBMHash        7       1       37315   67414     1.55   64.37
 5      DJBHash         7       5       39062   65667     1.59   62.70
 6      DEKHash         8       1       40531   64198     1.63   61.30
 7      BPHash          110     476     103204  1525     68.66    1.46
 8      FNVHash         8       3       38609   66120     1.58   63.13
 9      APHash          7       10      38512   66217     1.58   63.23
10      StpdHash        5230    1       104643  86      1217.44   0.08
mtrapier@prod500 ~/Desktop/test $ 

(faut que je trouve la signification des colones par contre )

Merci
Mais j'ai pas compris : ils testent sur quoi ? Quels mots ?

Le premier test ne fait que donner la valeur de sortie du hash avec la clef donnée

le second n'est autre que les tests en lui meme et utilise une liste de 12.7Ko de mots (1 mot par ligne) mais je pense qu'on pourrais utilise une liste plus longue sans soucis

(et c'est dans l'archive)

sinon je vais ajouter le hash de thibaut en page 1)

D'accord. Je ne trouve pas la liste de mots dans l'archive.

La non-performance de l'algo à la con est un peu abusée quand même... 0,08% d'utilisation de la table ? Faut pas déconner

Ben c'est simple, l'algo a la con n'utilise pas toute la taille de la table, au max sur un mot de 5 lettres tu peut avoir 26*26*26*26*26 ce qui fait 11881376, ce qui est tres tres loin de remplir un int32 alors que les autres utilisent tout le temps 100% des bits de l'int32.

Alors avec l'algo de thib (./25)

mtrapier@prod500 ~/Desktop/test $ ./HashTest 
General Purpose Hash Function Algorithms Test
By Arash Partow - 2002         
Key:                         abcdefghijklmnopqrstuvwxyz1234567890
 1. RS-Hash Function Value:   4097835502
 2. JS-Hash Function Value:   1651003062
 3. PJW-Hash Function Value:  126631744
 4. ELF-Hash Function Value:  126631744
 5. BKDR-Hash Function Value: 3153586616
 6. SDBM-Hash Function Value: 3449571336
 7. DJB-Hash Function Value:  729241521
 8. DEK-Hash Function Value:  2923964919
 9. BP-Hash Function Value:   1726880944
10. FNV-Hash Function Value:  3243095106
11. AP-Hash Function Value:   3929913477
12. StpdHash Function Value:  3372
13. ThibHash Function Value:  178
mtrapier@prod500 ~/Desktop/test $ ./GPHFATest 
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          7       1       35036   69693     1.50   66.55
 1      PJWHash         6       3       35017   69712     1.50   66.56
 2      ELFHash         6       3       35017   69712     1.50   66.56
 3      BKDRHash        6       9       35747   68982     1.52   65.87
 4      SDBMHash        7       1       37315   67414     1.55   64.37
 5      DJBHash         7       5       39062   65667     1.59   62.70
 6      DEKHash         8       1       40531   64198     1.63   61.30
 7      BPHash          110     476     103204  1525     68.66    1.46
 8      FNVHash         8       3       38609   66120     1.58   63.13
 9      APHash          7       10      38512   66217     1.58   63.23
10      StpdHash        5230    1       104643  86      1217.44   0.08
11      ThibHash        1575    1       104529  200     523.50    0.19
mtrapier@prod500 ~/Desktop/test $ 

LCL = Longest Chain Len;
LCL_CNT = Longuest Chain Len Count;
NZL = Num Zero Len
NC = Num Chaining;
ACl = Average Chain Len;
UP = Usage Percentage;

OK c'est vrai.

Ce test compare des algos de hachage dans le cadre d'une utilisation différente de la mienne. Mon but n'est pas d'obtenir des clés de 32 bits les plus différentes possibles, mais de remplir une table de taille limitée (256, 512, au plus 1024).

Il faudrait faire un modulo compris entre 256 et 1024 sur toutes les valeurs renvoyées pour que le test rentre dans le contexte.
Merci pour ta trouvaille, tous ces détails sont intéressants

Le tableau a une taille de "104729"

Tu as moyen de réduire à 512 pour voir ? (je le ferais bien mais j'ai pas trop le temps de me plonger dans la source)

Rho mais hein

LCL     = Longest Chain Len;
LCL_CNT = Longuest Chain Len Count;
NZL     = Num Zero Len
NC      = Num Chaining;
ACL     = Average Chain Len;
UP      = Usage Percentage; [/ore]

[pre]mtrapier@prod500 ~/Desktop/test $ ./GPHFATest 
--------------------------------------------------------------------------------
Table size : 42
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          2533    1       0       42      2492.86 100.00
 1      PJWHash         2666    1       0       42      2492.86 100.00
 2      ELFHash         2666    1       0       42      2492.86 100.00
 3      BKDRHash        2544    1       0       42      2492.86 100.00
 4      SDBMHash        2544    1       0       42      2492.86 100.00
 5      DJBHash         2532    1       0       42      2492.86 100.00
 6      DEKHash         2552    1       0       42      2492.86 100.00
 7      BPHash          2990    2       0       42      2492.86 100.00
 8      FNVHash         2620    1       0       42      2492.86 100.00
 9      APHash          2579    1       0       42      2492.86 100.00
10      StpdHash        5268    1       0       42      2492.86 100.00
11      ThibHash        3825    1       0       42      2492.86 100.00
--------------------------------------------------------------------------------
Table size : 50
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          2140    1       0       50      2094.00 100.00
 1      PJWHash         2130    1       0       50      2094.00 100.00
 2      ELFHash         2130    1       0       50      2094.00 100.00
 3      BKDRHash        2193    1       0       50      2094.00 100.00
 4      SDBMHash        2163    1       0       50      2094.00 100.00
 5      DJBHash         2133    1       0       50      2094.00 100.00
 6      DEKHash         2149    1       0       50      2094.00 100.00
 7      BPHash          2340    2       0       50      2094.00 100.00
 8      FNVHash         2219    1       0       50      2094.00 100.00
 9      APHash          2202    1       0       50      2094.00 100.00
10      StpdHash        5248    1       0       50      2094.00 100.00
11      ThibHash        3648    1       0       50      2094.00 100.00
--------------------------------------------------------------------------------
Table size : 100
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          1089    2       0       100     1047.00 100.00
 1      PJWHash         1293    1       0       100     1047.00 100.00
 2      ELFHash         1293    1       0       100     1047.00 100.00
 3      BKDRHash        1105    1       0       100     1047.00 100.00
 4      SDBMHash        1089    1       0       100     1047.00 100.00
 5      DJBHash         1101    1       0       100     1047.00 100.00
 6      DEKHash         1138    1       0       100     1047.00 100.00
 7      BPHash          1440    2       0       100     1047.00 100.00
 8      FNVHash         1139    1       0       100     1047.00 100.00
 9      APHash          1140    1       0       100     1047.00 100.00
10      StpdHash        5230    1       14      86      1217.44  86.00
11      ThibHash        2373    1       0       100     1047.00 100.00
--------------------------------------------------------------------------------
Table size : 256
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          452     1       0       256     408.98  100.00
 1      PJWHash         1073    7       96      160     654.38   62.50
 2      ELFHash         1073    7       96      160     654.38   62.50
 3      BKDRHash        457     1       0       256     408.98  100.00
 4      SDBMHash        1432    1       0       256     408.98  100.00
 5      DJBHash         756     1       0       256     408.98  100.00
 6      DEKHash         747     1       0       256     408.98  100.00
 7      BPHash          5420    6       235     21      4985.71   8.20
 8      FNVHash         459     1       0       256     408.98  100.00
 9      APHash          457     1       0       256     408.98  100.00
10      StpdHash        5230    1       170     86      1217.44  33.59
11      ThibHash        1575    1       56      200     523.50   78.12
--------------------------------------------------------------------------------
Table size : 257
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          444     1       0       257     407.39  100.00
 1      PJWHash         658     1       0       257     407.39  100.00
 2      ELFHash         658     1       0       257     407.39  100.00
 3      BKDRHash        513     1       0       257     407.39  100.00
 4      SDBMHash        459     1       0       257     407.39  100.00
 5      DJBHash         433     1       0       257     407.39  100.00
 6      DEKHash         434     1       0       257     407.39  100.00
 7      BPHash          2550    2       133     124     844.35   48.25
 8      FNVHash         486     1       0       257     407.39  100.00
 9      APHash          456     1       0       257     407.39  100.00
10      StpdHash        5230    1       171     86      1217.44  33.46
11      ThibHash        1575    1       57      200     523.50   77.82
--------------------------------------------------------------------------------
Table size : 1000
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          125     1       0       1000    104.70  100.00
 1      PJWHash         183     1       0       1000    104.70  100.00
 2      ELFHash         183     1       0       1000    104.70  100.00
 3      BKDRHash        133     1       0       1000    104.70  100.00
 4      SDBMHash        157     1       0       1000    104.70  100.00
 5      DJBHash         179     1       0       1000    104.70  100.00
 6      DEKHash         145     1       0       1000    104.70  100.00
 7      BPHash          460     2       409     591     177.16   59.10
 8      FNVHash         137     1       0       1000    104.70  100.00
 9      APHash          157     1       0       1000    104.70  100.00
10      StpdHash        5230    1       914     86      1217.44   8.60
11      ThibHash        1575    1       800     200     523.50   20.00
--------------------------------------------------------------------------------
Table size : 1024
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          119     1       0       1024    102.25  100.00
 1      PJWHash         288     2       384     640     163.59   62.50
 2      ELFHash         288     2       384     640     163.59   62.50
 3      BKDRHash        147     1       0       1024    102.25  100.00
 4      SDBMHash        370     2       0       1024    102.25  100.00
 5      DJBHash         260     2       0       1024    102.25  100.00
 6      DEKHash         296     1       60      964     108.61   94.14
 7      BPHash          2120    19      943     81      1292.59   7.91
 8      FNVHash         131     2       0       1024    102.25  100.00
 9      APHash          143     1       0       1024    102.25  100.00
10      StpdHash        5230    1       938     86      1217.44   8.40
11      ThibHash        1575    1       824     200     523.50   19.53
--------------------------------------------------------------------------------
Table size : 5178
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          30      4       0       5178     20.22  100.00
 1      PJWHash         35      1       0       5178     20.22  100.00
 2      ELFHash         35      1       0       5178     20.22  100.00
 3      BKDRHash        32      1       0       5178     20.22  100.00
 4      SDBMHash        34      1       0       5178     20.22  100.00
 5      DJBHash         36      9       0       5178     20.22  100.00
 6      DEKHash         41      1       0       5178     20.22  100.00
 7      BPHash          220     36      4153    1025    102.15   19.80
 8      FNVHash         39      1       0       5178     20.22  100.00
 9      APHash          39      1       0       5178     20.22  100.00
10      StpdHash        5230    1       5092    86      1217.44   1.66
11      ThibHash        1575    1       4978    200     523.50    3.86
--------------------------------------------------------------------------------
Table size : 9728
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          20      4       0       9728     10.76  100.00
 1      PJWHash         37      1       3648    6080     17.22   62.50
 2      ELFHash         37      1       3648    6080     17.22   62.50
 3      BKDRHash        23      1       0       9728     10.76  100.00
 4      SDBMHash        49      2       980     8748     11.97   89.93
 5      DJBHash         31      1       0       9728     10.76  100.00
 6      DEKHash         41      1       681     9047     11.57   93.00
 7      BPHash          520     10      8987    741     141.30    7.62
 8      FNVHash         25      1       1       9727     10.76   99.99
 9      APHash          25      1       0       9728     10.76  100.00
10      StpdHash        5230    1       9642    86      1217.44   0.88
11      ThibHash        1575    1       9528    200     523.50    2.06
--------------------------------------------------------------------------------
Table size : 54862
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          9       1       6317    48545     2.16   88.49
 1      PJWHash         9       3       6563    48299     2.17   88.04
 2      ELFHash         9       3       6563    48299     2.17   88.04
 3      BKDRHash        8       1       5962    48900     2.14   89.13
 4      SDBMHash        8       1       5323    49539     2.11   90.30
 5      DJBHash         8       2       7068    47794     2.19   87.12
 6      DEKHash         9       5       7476    47386     2.21   86.37
 7      BPHash          110     476     53337   1525     68.66    2.78
 8      FNVHash         9       5       8179    46683     2.24   85.09
 9      APHash          10      1       8099    46763     2.24   85.24
10      StpdHash        5230    1       54776   86      1217.44   0.16
11      ThibHash        1575    1       54662   200     523.50    0.36
--------------------------------------------------------------------------------
Table size : 98751
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          7       1       33110   65641     1.60   66.47
 1      PJWHash         7       1       32981   65770     1.59   66.60
 2      ELFHash         7       1       32981   65770     1.59   66.60
 3      BKDRHash        6       18      33377   65374     1.60   66.20
 4      SDBMHash        7       1       31652   67099     1.56   67.95
 5      DJBHash         7       5       34897   63854     1.64   64.66
 6      DEKHash         7       5       33787   64964     1.61   65.79
 7      BPHash          110     476     97226   1525     68.66    1.54
 8      FNVHash         9       1       34266   64485     1.62   65.30
 9      APHash          9       1       34027   64724     1.62   65.54
10      StpdHash        5230    1       98665   86      1217.44   0.09
11      ThibHash        1575    1       98551   200     523.50    0.20
--------------------------------------------------------------------------------
Table size : 104729
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP%
 0      RSHash          7       1       35036   69693     1.50   66.55
 1      PJWHash         6       3       35017   69712     1.50   66.56
 2      ELFHash         6       3       35017   69712     1.50   66.56
 3      BKDRHash        6       9       35747   68982     1.52   65.87
 4      SDBMHash        7       1       37315   67414     1.55   64.37
 5      DJBHash         7       5       39062   65667     1.59   62.70
 6      DEKHash         8       1       40531   64198     1.63   61.30
 7      BPHash          110     476     103204  1525     68.66    1.46
 8      FNVHash         8       3       38609   66120     1.58   63.13
 9      APHash          7       10      38512   66217     1.58   63.23
10      StpdHash        5230    1       104643  86      1217.44   0.08
11      ThibHash        1575    1       104529  200     523.50    0.19

(on s'apercois apr exemple que le hash PJW/ELF est moins bon sur des tailles en puissance de 2) (et bien sur ce n'est trié que par l'ordre d'execution par la qualitée ^^)

Et bien sur plus UP% est grand est LCL petit, et mieux c'est ^^

et ACL est le nombre moyen de colisions et NZL le nombre de cases vides (donc plus pour chaque c'est grand moins bien c'est)
(d'ailleurs c'est marrant, les resultat de stupid hash ne change pas apres une liste de 100, et thibhash a partir de 256...)

(mais je suis en train de me demander si thibhash est pas borné a 256....)

euh ton bench n'est pas du tout adapté à ce que cherche Thibaut, le but c'est d'avoir à peu près autant de clés pour chaque valeur ; une bonne fonction qui renvoie 255 valeurs est nettement meilleure qu'une mauvaise fonction qui renvoie 256 valeurs, alors qu'elle sera moins bien notée dans ton bench ^^

Ben les tests sur 256/257 sont la pour sa :

-------------------------------------------------------------------------------- 
Table size : 256 
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP% 
 0      RSHash          452     1       0       256     408.98  100.00 
 1      PJWHash         1073    7       96      160     654.38   62.50 
 2      ELFHash         1073    7       96      160     654.38   62.50 
 3      BKDRHash        457     1       0       256     408.98  100.00 
 4      SDBMHash        1432    1       0       256     408.98  100.00 
 5      DJBHash         756     1       0       256     408.98  100.00 
 6      DEKHash         747     1       0       256     408.98  100.00 
 7      BPHash          5420    6       235     21      4985.71   8.20 
 8      FNVHash         459     1       0       256     408.98  100.00 
 9      APHash          457     1       0       256     408.98  100.00 
10      StpdHash        5230    1       170     86      1217.44  33.59 
11      ThibHash        1575    1       56      200     523.50   78.12 
-------------------------------------------------------------------------------- 
Table size : 257 
Index   Hash Name       LCL     LCL_CNT NZL     NC        ACL    UP% 
 0      RSHash          444     1       0       257     407.39  100.00 
 1      PJWHash         658     1       0       257     407.39  100.00 
 2      ELFHash         658     1       0       257     407.39  100.00 
 3      BKDRHash        513     1       0       257     407.39  100.00 
 4      SDBMHash        459     1       0       257     407.39  100.00 
 5      DJBHash         433     1       0       257     407.39  100.00 
 6      DEKHash         434     1       0       257     407.39  100.00 
 7      BPHash          2550    2       133     124     844.35   48.25 
 8      FNVHash         486     1       0       257     407.39  100.00 
 9      APHash          456     1       0       257     407.39  100.00 
10      StpdHash        5230    1       171     86      1217.44  33.46 
11      ThibHash        1575    1       57      200     523.50   77.82 

On peut tres bien comparer sur le nombre de collision moyenne & co (ACL) et on remarque que l'utilisation de la table est pas complete pour stpdhash et thibhash

Cool, mon algo est pourrit mais pas tant que ça

Bon, je vais utiliser le hash de wikipedia optimisé par Pollux. Il correspond au DJBHash de ton test, qui lui octroie une efficacité très correcte. Je pense que c'est le meilleur compromis vitesse / (randomization des valeurs).

Ton test confirme ce que disait le mien d'ailleurs, mais il est plus intéressant car plus détaillé

Ben en fait ton algo ne devrais deja pas supposer qu'il a affaire a un bloc multiple de 8 octet....

./84:

DJB Hash Function
An algorithm produced by Professor Daniel J. Bernstein and shown first to the world on the usenet newsgroup comp.lang.c. It is one of the most efficient hash functions ever published

Godzil : il ne le suppose pas. Tu as bien utilisé la version du post ./25 ?

ha oui non c'est moi ai mal lu le code, c'est du bit-a-bot

Godzil (./83) :
On peut tres bien comparer sur le nombre de collision moyenne & co (ACL) et on remarque que l'utilisation de la table est pas complete pour stpdhash et thibhash

ça permet d'éliminer les fonctions particulièrement inefficaces comme StpdHash et BPHash, mais c'est tout : avec tes données impossible de savoir si RSHash est plus ou moins efficace que BKDRHash, par exemple (et puis même une fonction avec un UP de 80% peut être plus efficace en pratique qu'une avec un UP de 100%, même si pour ThibHash a priori ça n'est pas le cas)

et puis ACL n'est pas le nombre de collisions moyennes, c'est juste n_entrées/NC, autant dire que ça n'apporte strictement aucune information

Thibaut (./84) :
Ton test confirme ce que disait le mien d'ailleurs, mais il est plus intéressant car plus détaillé

non, le tien est bcp plus pertinent que celui de Godzil (c'est pas parce qu'il y a des tonnes de colonnes qu'elles sont bien choisies)

Thibaut 71 > oui, mais disons que ça m'intéresse quand même

Pollux (./88) :
ALC = n_entrées/NC

Non, le nombre de colision de chaque case (ou il y a collision) / nombre de chaines

(chaine = case ou il y a eu 1 ou plus de colision)

sinon on aurait la meme valeur pour chaques

Normalement les meme valeurs que thibeau sont présente dans le tableau si ce n'est la variance (je vais l'ajouter)