Alors PolD = Pollux Déroulé
Pol7 = PolluxHash
Sqly = Java Hash (ou K&R hash)
J'en ai oublié un je refait...
edit: voila j'avais oublié le hash de java (celui de K&R en réalitée)
mtrapier@prod500 ~/Desktop/test $ ./GPHFATest
General Purpose Hash Function Algorithms Test
By Arash Partow - 2002
Moded by Manoel Trapier - 2007
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
14. PolDHash Function Value: 8285105
15. PolDHash Function Value: 8285105
16. SqlyHash Function Value: 2134697992
---------------------------------------------------------------------------------------------------
HASH QUALITY TEST
---------------------------------------------------------------------------------------------------
***************************************************************************************************
***************************************************************************************************
Definitions:
LCL: Longest chain length LCL_CNT: Count of buckets with longest chain length
NZL: Number of zero chaining buckets (aka empty bucket) NC: Number of chained buckets
ACL: Average chaining length UP: Usage percentange of hash-table
AVG: Ideal Average VAR: Variance
***************************************************************************************************
***************************************************************************************************
---------------------------------------------------------------------------------------------------
Table size : 42
Index Hash Name LCL LCL_CNT NZL NC COL ACL UP% AVG VAR
0 RSHash 196 1 0 42 42 095.24 100.00 95.24 6167.37
1 PJWHash 133 1 0 42 42 095.24 100.00 95.24 145.04
2 ELFHash 133 1 0 42 42 095.24 100.00 95.24 145.04
3 BKDRHash 208 1 0 42 42 095.24 100.00 95.24 6336.32
4 SDBMHash 181 1 0 42 42 095.24 100.00 95.24 6084.28
5 DJBHash 206 1 0 42 42 095.24 100.00 95.24 6413.99
6 DEKHash 108 1 0 42 42 095.24 100.00 95.24 40.37
7 BPHash 104 2 0 42 42 095.24 100.00 95.24 34.85
8 FNVHash 195 2 0 42 42 095.24 100.00 95.24 6176.51
9 APHash 119 1 0 42 42 095.24 100.00 95.24 106.80
10 StpdHash 1800 1 32 10 9 400.00 23.81 95.24 132625.94
11 ThibHash 250 1 7 35 35 114.29 83.33 95.24 5400.94
12 Pol7Hash 253 1 0 42 42 095.24 100.00 95.24 6905.51
13 PolDHash 253 1 0 42 42 095.24 100.00 95.24 6905.51
14 SqlyHash 191 1 0 42 42 095.24 100.00 95.24 6114.94
---------------------------------------------------------------------------------------------------
Table size : 50
Index Hash Name LCL LCL_CNT NZL NC COL ACL UP% AVG VAR
0 RSHash 168 1 0 50 50 080.00 100.00 80.00 4370.04
1 PJWHash 108 2 0 50 50 080.00 100.00 80.00 157.08
2 ELFHash 108 2 0 50 50 080.00 100.00 80.00 157.08
3 BKDRHash 164 2 0 50 50 080.00 100.00 80.00 4373.68
4 SDBMHash 153 1 0 50 50 080.00 100.00 80.00 4298.16
5 DJBHash 155 1 0 50 50 080.00 100.00 80.00 4298.64
6 DEKHash 97 1 0 50 50 080.00 100.00 80.00 52.84
7 BPHash 83 2 0 50 50 080.00 100.00 80.00 2.08
8 FNVHash 175 1 0 50 50 080.00 100.00 80.00 4391.80
9 APHash 104 1 0 50 50 080.00 100.00 80.00 72.16
10 StpdHash 1800 1 39 11 10 363.64 22.00 80.00 112611.88
11 ThibHash 375 2 18 32 32 125.00 64.00 80.00 9963.28
12 Pol7Hash 443 1 2 48 44 083.33 96.00 80.00 15631.60
13 PolDHash 443 1 2 48 44 083.33 96.00 80.00 15631.60
14 SqlyHash 159 1 0 50 50 080.00 100.00 80.00 4305.16
---------------------------------------------------------------------------------------------------
Table size : 100
Index Hash Name LCL LCL_CNT NZL NC COL ACL UP% AVG VAR
0 RSHash 147 2 0 100 100 040.00 100.00 40.00 2562.12
1 PJWHash 81 1 0 100 100 040.00 100.00 40.00 165.08
2 ELFHash 81 1 0 100 100 040.00 100.00 40.00 165.08
3 BKDRHash 147 1 10 90 88 044.44 90.00 40.00 2711.82
4 SDBMHash 137 2 1 99 87 040.40 99.00 40.00 2675.62
5 DJBHash 153 1 27 73 61 054.79 73.00 40.00 3644.44
6 DEKHash 61 1 0 100 100 040.00 100.00 40.00 93.20
7 BPHash 50 2 0 100 100 040.00 100.00 40.00 64.80
8 FNVHash 104 1 0 100 100 040.00 100.00 40.00 1149.90
9 APHash 58 1 0 100 100 040.00 100.00 40.00 35.36
10 StpdHash 1800 1 89 11 10 363.64 11.00 40.00 57905.94
11 ThibHash 250 2 57 43 43 093.02 43.00 40.00 3944.78
12 Pol7Hash 441 1 33 67 54 059.70 67.00 40.00 9302.04
13 PolDHash 441 1 33 67 54 059.70 67.00 40.00 9302.04
14 SqlyHash 139 1 7 93 88 043.01 93.00 40.00 2674.98
---------------------------------------------------------------------------------------------------
Table size : 256
Index Hash Name LCL LCL_CNT NZL NC COL ACL UP% AVG VAR
0 RSHash 130 1 30 226 168 017.70 88.28 15.62 976.59
1 PJWHash 41 1 120 136 130 029.41 53.12 15.62 305.64
2 ELFHash 41 1 120 136 130 029.41 53.12 15.62 305.64
3 BKDRHash 182 4 86 170 151 023.53 66.41 15.62 1780.05
4 SDBMHash 1921 1 157 99 77 040.40 38.67 15.62 17090.00
5 DJBHash 900 2 215 41 33 097.56 16.02 15.62 8468.13
6 DEKHash 80 1 85 171 140 023.39 66.80 15.62 369.36
7 BPHash 201 10 236 20 20 200.00 7.81 15.62 2880.94
8 FNVHash 49 1 5 251 228 015.94 98.05 15.62 188.38
9 APHash 27 1 0 256 256 015.62 100.00 15.62 15.41
10 StpdHash 1800 1 245 11 10 363.64 4.30 15.62 23000.37
11 ThibHash 180 1 198 58 57 068.97 22.66 15.62 1453.35
12 Pol7Hash 900 2 215 41 33 097.56 16.02 15.62 8468.13
13 PolDHash 900 2 215 41 33 097.56 16.02 15.62 8468.13
14 SqlyHash 961 2 88 168 120 023.81 65.62 15.62 8433.47
---------------------------------------------------------------------------------------------------
Table size : 257
Index Hash Name LCL LCL_CNT NZL NC COL ACL UP% AVG VAR
0 RSHash 32 1 0 257 257 015.56 100.00 15.56 22.28
1 PJWHash 337 1 38 219 208 018.26 85.21 15.56 932.92
2 ELFHash 337 1 38 219 208 018.26 85.21 15.56 932.92
3 BKDRHash 26 4 0 257 257 015.56 100.00 15.56 22.49
4 SDBMHash 29 2 0 257 257 015.56 100.00 15.56 30.99
5 DJBHash 21 2 0 257 257 015.56 100.00 15.56 4.79
6 DEKHash 36 1 0 257 257 015.56 100.00 15.56 44.89
7 BPHash 55 4 58 199 182 020.10 77.43 15.56 251.81
8 FNVHash 25 2 0 257 257 015.56 100.00 15.56 14.44
9 APHash 27 2 0 257 257 015.56 100.00 15.56 17.00
10 StpdHash 1800 1 246 11 10 363.64 4.28 15.56 22911.82
11 ThibHash 180 1 199 58 57 068.97 22.57 15.56 1448.64
12 Pol7Hash 152 1 91 166 125 024.10 64.59 15.56 955.27
13 PolDHash 152 1 91 166 125 024.10 64.59 15.56 955.27
14 SqlyHash 23 3 0 257 257 015.56 100.00 15.56 8.81
---------------------------------------------------------------------------------------------------
Table size : 1000
Index Hash Name LCL LCL_CNT NZL NC COL ACL UP% AVG VAR
0 RSHash 29 3 265 735 447 005.44 73.50 4.00 56.03
1 PJWHash 16 2 40 960 860 004.17 96.00 4.00 7.26
2 ELFHash 16 2 40 960 860 004.17 96.00 4.00 7.26
3 BKDRHash 65 2 392 608 374 006.58 60.80 4.00 119.47
4 SDBMHash 31 1 343 657 426 006.09 65.70 4.00 59.98
5 DJBHash 34 2 727 273 216 014.65 27.30 4.00 90.08
6 DEKHash 13 3 25 975 877 004.10 97.50 4.00 5.32
7 BPHash 16 2 266 734 686 005.45 73.40 4.00 13.09
8 FNVHash 17 2 252 748 583 005.35 74.80 4.00 15.06
9 APHash 11 3 22 978 897 004.09 97.80 4.00 3.80
10 StpdHash 1800 1 989 11 10 363.64 1.10 4.00 5934.59
11 ThibHash 180 1 942 58 57 068.97 5.80 4.00 418.56
12 Pol7Hash 148 1 827 173 126 023.12 17.30 4.00 304.43
13 PolDHash 148 1 827 173 126 023.12 17.30 4.00 304.43
14 SqlyHash 33 2 416 584 421 006.85 58.40 4.00 60.22
---------------------------------------------------------------------------------------------------
Table size : 1024
Index Hash Name LCL LCL_CNT NZL NC COL ACL UP% AVG VAR
0 RSHash 34 2 332 692 466 005.78 67.58 3.91 61.52
1 PJWHash 13 1 516 508 502 007.87 49.61 3.91 20.63
2 ELFHash 13 1 516 508 502 007.87 49.61 3.91 20.63
3 BKDRHash 54 1 471 553 393 007.23 54.00 3.91 112.75
4 SDBMHash 482 1 730 294 176 013.61 28.71 3.91 1068.23
5 DJBHash 227 2 903 121 96 033.06 11.82 3.91 547.63
6 DEKHash 40 1 721 303 236 013.20 29.59 3.91 81.78
7 BPHash 81 10 944 80 80 050.00 7.81 3.91 203.51
8 FNVHash 17 3 256 768 596 005.21 75.00 3.91 14.78
9 APHash 11 1 7 1017 962 003.93 99.32 3.91 2.95
10 StpdHash 1800 1 1013 11 10 363.64 1.07 3.91 5795.87
11 ThibHash 180 1 966 58 57 068.97 5.66 3.91 409.11
12 Pol7Hash 227 2 903 121 96 033.06 11.82 3.91 547.63
13 PolDHash 227 2 903 121 96 033.06 11.82 3.91 547.63
14 SqlyHash 245 1 604 420 268 009.52 41.02 3.91 527.63
---------------------------------------------------------------------------------------------------
Table size : 5178
Index Hash Name LCL LCL_CNT NZL NC COL ACL UP% AVG VAR
0 RSHash 5 8 2700 2478 1131 001.61 47.86 0.77 0.94
1 PJWHash 14 1 2469 2709 956 001.48 52.32 0.77 0.92
2 ELFHash 14 1 2469 2709 956 001.48 52.32 0.77 0.92
3 BKDRHash 6 1 2694 2484 1088 001.61 47.97 0.77 0.96
4 SDBMHash 6 1 2855 2323 1079 001.72 44.86 0.77 1.12
5 DJBHash 6 4 2851 2327 1121 001.72 44.94 0.77 1.10
6 DEKHash 6 1 2350 2828 941 001.41 54.62 0.77 0.73
7 BPHash 4 18 2154 3024 802 001.32 58.40 0.77 0.63
8 FNVHash 7 1 2876 2302 1080 001.74 44.46 0.77 1.17
9 APHash 5 3 2387 2791 936 001.43 53.90 0.77 0.77
10 StpdHash 1800 1 5167 11 10 363.64 0.21 0.77 1148.61
11 ThibHash 180 1 5120 58 57 068.97 1.12 0.77 83.33
12 Pol7Hash 183 1 4982 196 139 020.41 3.79 0.77 57.57
13 PolDHash 183 1 4982 196 139 020.41 3.79 0.77 57.57
14 SqlyHash 6 4 2938 2240 1143 001.79 43.26 0.77 1.17
---------------------------------------------------------------------------------------------------
Table size : 9728
Index Hash Name LCL LCL_CNT NZL NC COL ACL UP% AVG VAR
0 RSHash 8 1 7632 2096 883 001.91 21.55 0.41 1.01
1 PJWHash 9 9 7030 2698 993 001.48 27.73 0.41 0.62
2 ELFHash 9 9 7030 2698 993 001.48 27.73 0.41 0.62
3 BKDRHash 10 2 8195 1533 807 002.61 15.76 0.41 1.54
4 SDBMHash 64 2 8693 1035 237 003.86 10.64 0.41 12.32
5 DJBHash 30 2 9138 590 423 006.78 6.06 0.41 6.32
6 DEKHash 7 20 7644 2084 1098 001.92 21.42 0.41 0.89
7 BPHash 9 60 8968 760 760 005.26 7.81 0.41 2.31
8 FNVHash 5 10 6847 2881 876 001.39 29.62 0.41 0.53
9 APHash 5 2 6400 3328 591 001.20 34.21 0.41 0.40
10 StpdHash 1800 1 9717 11 10 363.64 0.11 0.41 611.53
11 ThibHash 180 1 9670 58 57 068.97 0.60 0.41 44.50
12 Pol7Hash 139 2 9511 217 149 018.43 2.23 0.41 28.33
13 PolDHash 139 2 9511 217 149 018.43 2.23 0.41 28.33
14 SqlyHash 28 4 8733 995 501 004.02 10.23 0.41 6.00
---------------------------------------------------------------------------------------------------
Table size : 54862
Index Hash Name LCL LCL_CNT NZL NC COL ACL UP% AVG VAR
0 RSHash 4 1 51164 3698 275 001.08 6.74 0.07 0.08
1 PJWHash 9 9 51088 3774 157 001.06 6.88 0.07 0.09
2 ELFHash 9 9 51088 3774 157 001.06 6.88 0.07 0.09
3 BKDRHash 2 118 50980 3882 118 001.03 7.08 0.07 0.07
4 SDBMHash 3 8 51091 3771 221 001.06 6.87 0.07 0.08
5 DJBHash 2 178 51040 3822 178 001.05 6.97 0.07 0.07
6 DEKHash 3 3 50964 3898 99 001.03 7.11 0.07 0.07
7 BPHash 1 4000 50862 4000 0 001.00 7.29 0.07 0.07
8 FNVHash 3 17 51096 3766 217 001.06 6.86 0.07 0.08
9 APHash 4 1 51041 3821 175 001.05 6.96 0.07 0.07
10 StpdHash 1800 1 54851 11 10 363.64 0.02 0.07 108.46
11 ThibHash 180 1 54804 58 57 068.97 0.11 0.07 7.92
12 Pol7Hash 139 2 54632 230 156 017.39 0.42 0.07 4.97
13 PolDHash 139 2 54632 230 156 017.39 0.42 0.07 4.97
14 SqlyHash 3 1 51050 3812 187 001.05 6.95 0.07 0.07
---------------------------------------------------------------------------------------------------
Table size : 98751
Index Hash Name LCL LCL_CNT NZL NC COL ACL UP% AVG VAR
0 RSHash 2 45 94796 3955 45 001.01 4.01 0.04 0.04
1 PJWHash 9 9 94867 3884 51 001.03 3.93 0.04 0.05
2 ELFHash 9 9 94867 3884 51 001.03 3.93 0.04 0.05
3 BKDRHash 2 43 94794 3957 43 001.01 4.01 0.04 0.04
4 SDBMHash 2 25 94776 3975 25 001.01 4.03 0.04 0.04
5 DJBHash 2 38 94789 3962 38 001.01 4.01 0.04 0.04
6 DEKHash 2 52 94803 3948 52 001.01 4.00 0.04 0.04
7 BPHash 1 4000 94751 4000 0 001.00 4.05 0.04 0.04
8 FNVHash 2 82 94833 3918 82 001.02 3.97 0.04 0.04
9 APHash 3 1 94836 3915 84 001.02 3.96 0.04 0.04
10 StpdHash 1800 1 98740 11 10 363.64 0.01 0.04 60.26
11 ThibHash 180 1 98693 58 57 068.97 0.06 0.04 4.40
12 Pol7Hash 139 2 98522 229 156 017.47 0.23 0.04 2.76
13 PolDHash 139 2 98522 229 156 017.47 0.23 0.04 2.76
14 SqlyHash 3 1 94814 3937 62 001.02 3.99 0.04 0.04
---------------------------------------------------------------------------------------------------
Table size : 104729
Index Hash Name LCL LCL_CNT NZL NC COL ACL UP% AVG VAR
0 RSHash 3 1 100797 3932 67 001.02 3.75 0.04 0.04
1 PJWHash 9 9 100905 3824 110 001.05 3.65 0.04 0.04
2 ELFHash 9 9 100905 3824 110 001.05 3.65 0.04 0.04
3 BKDRHash 2 40 100769 3960 40 001.01 3.78 0.04 0.04
4 SDBMHash 3 1 100854 3875 124 001.03 3.70 0.04 0.04
5 DJBHash 2 31 100760 3969 31 001.01 3.79 0.04 0.04
6 DEKHash 3 2 100877 3852 146 001.04 3.68 0.04 0.04
7 BPHash 1 4000 100729 4000 0 001.00 3.82 0.04 0.04
8 FNVHash 2 69 100798 3931 69 001.02 3.75 0.04 0.04
9 APHash 3 2 100802 3927 71 001.02 3.75 0.04 0.04
10 StpdHash 1800 1 104718 11 10 363.64 0.01 0.04 56.82
11 ThibHash 180 1 104671 58 57 068.97 0.06 0.04 4.15
12 Pol7Hash 139 2 104499 230 156 017.39 0.22 0.04 2.61
13 PolDHash 139 2 104499 230 156 017.39 0.22 0.04 2.61
14 SqlyHash 2 42 100771 3958 42 001.01 3.78 0.04 0.04
---------------------------------------------------------------------------------------------------
HASH SPEED TEST
---------------------------------------------------------------------------------------------------
***************************************************************************************************
***************************************************************************************************
Definitions:
STM: Start time in microsecond
ETM: End time in microsecond
EXT: Execution Time in second (lower is better)
HPS: Hash per second (higher is better)
***************************************************************************************************
***************************************************************************************************
---------------------------------------------------------------------------------------------------
Speed test with 10000000 loop
Key is: 'abcdefghijklmnopqrstuvwxyz1234567890'
Index Hash Name STM ETM EXT HPS
0 RSHash 1827510024 1830857010 3.35 2987762.72
1 PJWHash 1830857110 1835761855 4.90 2038841.98
2 ELFHash 1835761941 1841158523 5.40 1853024.75
3 BKDRHash 1841158561 1844364758 3.21 3118959.94
4 SDBMHash 1844364856 1847230719 2.87 3489350.33
5 DJBHash 1847230756 1849705349 2.47 4041068.57
6 DEKHash 1849705388 1852061153 2.36 4244905.58
7 BPHash 1852061191 1854463545 2.40 4162583.87
8 FNVHash 1854463650 1858149102 3.69 2713371.39
9 APHash 1858149205 1861730640 3.58 2792176.88
10 StpdHash 1861730676 1864166315 2.44 4105698.75
11 ThibHash 1864166397 1866202922 2.04 4910325.19
12 Pol7Hash 1866202994 1868951851 2.75 3637875.67
13 PolDHash 1868951935 1871123932 2.17 4604057.92
14 SqlyHash 1871124007 1873618514 2.49 4008808.15
PS: ma machine est un :
mtrapier@prod500 ~/Desktop/test $ cat /proc/cpuinfo
processor : 0
vendor_id : GenuineIntel
cpu family : 15
model : 4
model name : Intel(R) Pentium(R) D CPU 2.80GHz
stepping : 7
cpu MHz : 2793.356
cache size : 1024 KB
physical id : 0
siblings : 2
core id : 0
cpu cores : 2
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 5
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe lm constant_tsc pni monitor ds_cpl cid cx16 xtpr lahf_lm
bogomips : 5591.27
clflush size : 64
processor : 1
vendor_id : GenuineIntel
cpu family : 15
model : 4
model name : Intel(R) Pentium(R) D CPU 2.80GHz
stepping : 7
cpu MHz : 2793.356
cache size : 1024 KB
physical id : 0
siblings : 2
core id : 1
cpu cores : 2
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 5
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe lm constant_tsc pni monitor ds_cpl cid cx16 xtpr lahf_lm
bogomips : 5586.38
clflush size : 64
(pour situer les perfs en temps)