Hash függvények: Egy empirikus összehasonlítás

Posted on

Hash táblák népszerű adatszerkezetek tárolására kulcs-érték párokat. Egy hash függvény segítségével térkép a legfontosabb érték (általában egy string) tömb index. A különböző funkciók a kriptográfiai hash függvények, mert sokkal gyorsabb, nem kell ellenálló preimage támadás. Hasító nagy adatbázisok is maradt, ebből a cikkből; a benchmark magában foglalja a közepes méretű hash táblák, például:

Két osztály, a használható funkciók a hash táblák:

Hash tábla referenciaértékek általában tartalmazzák az elméleti mutatók, mint például az ütközések száma, vagy engedély egységes (lásd például a hash függvény összehasonlítás a Vörös Sárkány könyv). Nyilvánvaló, hogy jobb elosztása a bonyolultabb funkciókhoz, így azok nyertesek ezek a benchmarkok.

A kérdés az, hogy segítségével az összetett funkciókat ad egy gyorsabb program. A komplex funkciókat igényel több művelet per egyik legfontosabb, így lassabb lehet. Az ár az ütközések elég magas ahhoz, hogy indokolja a további műveletek?

Multiplikatív hash függvények

Minden multiplikatív hash függvény egy speciális esete a következő algoritmus:

UINT HashMultiplicative(const CHAR *key, SIZE_T len) {
UINT hash = INITIAL_VALUE;
for(UINT i = 0; i < len; ++i)
hash = M * hash + key[i];
return hash % TABLE_SIZE;
}

(Néha XOR művelet helyett felül, de ez nem sokat számít.) A hash függvények különbözik csak értékei INITIAL_VALUE, szorzó (M). Például a népszerű Bernstein funkciót használja INITIAL_VALUE a 5381, M a 33; Kernighan, Ritchie funkciót használja INITIAL_VALUE a 0, M a 31.

A multiplikatív funkció hozzáadásával együtt a betűk súlyozott által hatáskörét a szorzó. Például, a hash a szó, TONE lesz:

INITIAL_VALUE * M^4 + ‘T’ * M^3 + ‘O’ * M^2 + ‘N’ * M + ‘E’

Nézzük meg, hogy több, hasonló húrokat nézni a kimeneti funkciók:

Bernstein Kernighan
(M=33) (M=31)
too b88af17 1c154
top b88af18 1c155
tor b88af1a 1c157
tpp b88af39 1c174
a000 7c9312d6 2cd22f
a001 7c9312d7 2cd230
a002 7c9312d8 2cd231
a003 7c9312d9 2cd232
a004 7c9312da 2cd233
a005 7c9312db 2cd234
a006 7c9312dc 2cd235
a007 7c9312dd 2cd236
a008 7c9312de 2cd237
a009 7c9312df 2cd238
a010 7c9312f7 2cd24e
a 2b606 61
aa 597727 c20
aaa b885c68 17841

Túl top különböző az utolsó levél. Betű P a következő után O, így az értékek a hash függvény vagy más által 1 (1c154, 1c155, b88af17, b88af18). Ugyanez a helyzet a000..a009.

Most hasonlítsuk össze a felső tpp. A hash-eket:

INITIAL_VALUE * M^3 + ‘T’ * M^2 + ‘O’ * M + ‘P’
INITIAL_VALUE * M^3 + ‘T’ * M^2 + ‘P’ * M + ‘P’

A hash-eket más lesz az M * (‘P’ – ‘O’) = M. Hasonlóképpen, amikor az első levelek különböző, a x, a hash-eket más lesz, az x * M^2.

Ha kevesebb, mint 33 lehetséges betűk, Bernstein funkció pakold bele egy számot (hasonló Radix40 csomagolási rendszer). Például, hash tábla mérete 333 nyújt tökéletes hasító (anélkül, hogy ütközések) mind a három betűs angol szavakat írva, kisebb betűkkel. A gyakorlatban, a szavak már hash táblák kisebb, így lesz egy kis ütközések (helyzetekben, amikor a különböző szálakat ugyanaz a hash érték).

Ha a zsinór túl hosszú, hogy fér bele a 32-bites szám, az első betű mindig befolyásolja az érték a hash függvény, mert a szorzás történik modulo 2^32 (32 bites regiszter), valamint a szorzó választotta, hogy nincs közös osztója, 2^32 (más szóval, furcsa lehet), így a bitek nem csak tolódott el.

Nincsenek pontos szabályok a választott a szorzó, csak egyes alkotóelemei:

Összetett hash függvények

Ezek a funkciók jó munkát keveri össze a részeket a forrás szó. A változás egy bemeneti kicsit változások fél a bitet a kimenethez (lásd Avalanche_effect), így a végeredmény teljesen véletlenszerű:

Paul Hsieh One At Time
too 3ad11d33 3a9fad1e
top 78b5a877 4c5dd09a
tor c09e2021 f2aa9d35
tpp 3058996d d5e9e480
a000 7552599f ed3859d8
a001 3cc1d896 fef7fd57
a002 c6ff5c9b 08a610b3
a003 dcab7b0c 1a88b478
a004 780c7202 3621ebaa
a005 7eb63e3a 47db8f1d
a006 6b0a7a17 b901717b
a007 cb5cb1ab caec1550
a008 5c2a15c0 e58d4a92
a009 33339829 f75aee2d
a010 eb1f336e bd097a6b
a 115ea782 ca2e9442
aa 008ad357 7081738e
aaa 7dfdc310 ae4f22ec

Ennek elérése érdekében a viselkedés, a hash függvények végrehajtásához sok műszakban, XORs, kiegészítések. De van szükségünk, hogy egy komplex függvény? Mi a gyorsabb: tolerálja az ütközések, illetve azok megoldására a láncolás, vagy elkerüli őket, hogy egy összetettebb funkciót?

Vizsgálati feltételek

A benchmark használ külön láncolás algoritmus ütközés állásfoglalás. Memória allokáció, valamint egyéb, a “nehéz” funkciók kizárták a összevetni kódot. RDTSC utasítás használták a benchmarking. A vizsgálatot végeztek a Pentium-M Core i5 processzorok.

A benchmark beszúr egy kulcsot az asztalra, akkor úgy néz ki őket ugyanabban a sorrendben, ahogy egészül ki. A vizsgálati adatok a következők:

Eredmények

Core i5 processzor

Words
Win32
Numbers
Prefix
Postfix
Variables
Sonnets
UTF-8
IPv4
Avg
iSCSI CRC
65
[105]
329
[415]
36
[112]
84
[106]
83
[92]
280
[368]
408
[584]
1964
[2388]
322
[838]
1.01
[1.78]
Meiyan
64
[102]
328
[409]
45
[125]
87
[106]
85
[112]
274
[350]
411
[588]
1972
[2377]
353
[768]
1.05
[1.87]
Murmur2
72
[103]
378
[415]
48
[104]
109
[106]
106
[111]
315
[383]
450
[566]
2183
[2399]
399
[834]
1.21
[1.74]
XXHfast32
78
[110]
372
[420]
57
[102]
88
[103]
88
[106]
315
[347]
473
[491]
2323
[2494]
463
[838]
1.23
[1.71]
SBox
70
[91]
389
[431]
46
[116]
124
[108]
123
[91]
304
[347]
430
[526]
2182
[2442]
377
[836]
1.23
[1.78]
Larson
72
[99]
401
[416]
34
[16]
143
[99]
141
[105]
312
[366]
451
[583]
2230
[2447]
349
[755]
1.25
[1.10]
XXHstrong32
79
[109]
385
[429]
58
[102]
93
[102]
92
[112]
321
[355]
474
[491]
2332
[2496]
464
[838]
1.25
[1.72]
Sedgewick
73
[107]
417
[414]
36
[48]
143
[103]
143
[103]
319
[348]
446
[570]
2246
[2437]
349
[782]
1.26
[1.33]
Novak unrolled
76
[113]
404
[399]
43
[90]
127
[118]
125
[113]
322
[342]
459
[581]
2284
[2430]
379
[969]
1.26
[1.68]
CRC-32
70
[101]
429
[426]
40
[64]
146
[107]
143
[94]
320
[338]
443
[563]
2231
[2400]
357
[725]
1.28
[1.41]
Murmur3
78
[101]
391
[380]
54
[104]
108
[103]
107
[105]
331
[334]
492
[555]
2360
[2376]
433
[783]
1.28
[1.69]
x65599
74
[111]
407
[382]
45
[203]
144
[107]
144
[122]
316
[379]
449
[560]
2221
[2373]
349
[846]
1.29
[2.45]
FNV-1a
74
[124]
408
[428]
47
[108]
144
[94]
144
[105]
309
[374]
440
[555]
2193
[2446]
376
[807]
1.30
[1.77]
Murmur2A
79
[114]
410
[433]
53
[102]
117
[112]
114
[109]
337
[365]
494
[544]
2377
[2369]
429
[772]
1.31
[1.73]
Fletcher
71
[131]
352
[406]
80
[460]
104
[127]
100
[108]
312
[507]
481
[1052]
2477
[4893]
388
[1359]
1.31
[4.62]
K&R
73
[106]
429
[437]
47
[288]
149
[94]
149
[106]
324
[360]
450
[561]
2266
[2365]
343
[831]
1.32
[3.00]
Paul Hsieh
80
[114]
410
[420]
54
[118]
123
[101]
121
[100]
336
[341]
496
[600]
2351
[2380]
433
[847]
1.33
[1.83]
Bernstein
75
[114]
428
[412]
49
[288]
150
[100]
150
[102]
324
[353]
460
[572]
2312
[2380]
351
[703]
1.34
[2.99]
x17 unrolled
78
[109]
446
[415]
43
[24]
156
[113]
153
[102]
344
[368]
472
[589]
2361
[2392]
373
[829]
1.37
[1.19]
lookup3
83
[101]
459
[412]
55
[97]
140
[101]
137
[95]
359
[361]
526
[550]
2480
[2392]
427
[834]
1.42
[1.65]
MaPrime2c
79
[103]
459
[426]
50
[106]
155
[91]
155
[106]
349
[349]
486
[550]
2493
[2406]
406
[865]
1.42
[1.73]
Ramakrishna
80
[108]
513
[409]
44
[91]
189
[125]
186
[103]
370
[360]
483
[528]
2565
[2383]
380
[840]
1.51
[1.66]
One At Time
85
[105]
562
[421]
58
[110]
221
[97]
220
[103]
392
[364]
511
[545]
2659
[2346]
459
[795]
1.72
[1.75]
Arash Partow
83
[101]
560
[435]
71
[420]
215
[98]
212
[85]
392
[355]
507
[570]
2638
[2372]
407
[779]
1.72
[3.88]
Weinberger
87
[104]
590
[422]
37
[100]
254
[111]
273
[117]
398
[364]
541
[712]
2734
[2547]
419
[744]
1.78
[1.75]
Hanson
73
[118]
417
[649]
45
[112]
123
[118]
1207
[499]
318
[435]
448
[592]
2324
[2890]
370
[833]
2.70
[2.46]

Pentium-M processzor

Words
Win32
Numbers
Prefix
Postfix
Variables
Sonnets
UTF-8
IPv4
Avg
Meiyan
80
[102]
426
[409]
56
[125]
123
[106]
121
[112]
354
[350]
525
[588]
2443
[2377]
445
[768]
1.02
[1.87]
Novak unrolled
90
[113]
517
[399]
56
[90]
169
[118]
164
[113]
398
[342]
575
[581]
2716
[2430]
482
[969]
1.18
[1.68]
Fletcher
84
[131]
444
[406]
102
[460]
140
[127]
133
[108]
374
[507]
592
[1052]
2891
[4893]
513
[1359]
1.21
[4.62]
SBox
88
[91]
552
[431]
57
[116]
181
[108]
178
[91]
414
[347]
560
[526]
2814
[2442]
472
[836]
1.22
[1.78]
Murmur2
97
[103]
532
[415]
65
[104]
165
[106]
162
[111]
434
[383]
622
[566]
2948
[2399]
537
[834]
1.25
[1.74]
CRC-32
90
[101]
565
[426]
55
[64]
198
[107]
192
[94]
427
[338]
590
[563]
2842
[2400]
469
[725]
1.26
[1.41]
x17 unrolled
93
[109]
593
[415]
52
[24]
214
[113]
208
[102]
434
[368]
593
[589]
2867
[2392]
486
[829]
1.30
[1.19]
lookup3
94
[101]
565
[412]
70
[97]
189
[101]
182
[95]
432
[361]
631
[550]
2943
[2392]
572
[834]
1.32
[1.65]
K&R
93
[106]
619
[437]
58
[288]
221
[94]
218
[106]
442
[360]
587
[561]
2961
[2365]
447
[831]
1.33
[3.00]
Larson
95
[99]
631
[416]
49
[16]
231
[99]
228
[105]
455
[366]
599
[583]
3027
[2447]
469
[755]
1.35
[1.10]
XXHfast32
108
[110]
546
[420]
86
[102]
139
[103]
136
[106]
459
[347]
681
[491]
3259
[2494]
717
[838]
1.35
[1.71]
Murmur3
108
[101]
561
[380]
74
[104]
167
[103]
165
[105]
468
[334]
700
[555]
3259
[2376]
604
[783]
1.36
[1.69]
Bernstein
97
[114]
622
[412]
61
[288]
225
[100]
222
[102]
448
[353]
609
[572]
3053
[2380]
469
[703]
1.37
[2.99]
XXHstrong32
108
[109]
558
[429]
86
[102]
150
[102]
147
[112]
460
[355]
682
[491]
3262
[2496]
714
[838]
1.38
[1.72]
x65599
99
[111]
628
[382]
61
[203]
234
[107]
232
[122]
459
[379]
630
[560]
3097
[2373]
471
[846]
1.40
[2.45]
Paul Hsieh
106
[114]
576
[420]
82
[118]
183
[101]
178
[100]
456
[341]
678
[600]
3154
[2380]
670
[847]
1.41
[1.83]
Sedgewick
101
[107]
667
[414]
52
[48]
245
[103]
242
[103]
478
[348]
630
[570]
3204
[2437]
475
[782]
1.42
[1.33]
Murmur2A
113
[114]
598
[433]
78
[102]
183
[112]
178
[109]
488
[365]
719
[544]
3380
[2369]
651
[772]
1.44
[1.73]
FNV-1a
102
[124]
660
[428]
62
[108]
239
[94]
237
[105]
473
[374]
627
[555]
3140
[2446]
516
[807]
1.44
[1.77]
MaPrime2c
108
[103]
705
[426]
65
[106]
255
[91]
254
[106]
508
[349]
674
[550]
3413
[2406]
542
[865]
1.54
[1.73]
Ramakrishna
108
[108]
728
[409]
61
[91]
278
[125]
272
[103]
511
[360]
660
[528]
3378
[2383]
517
[840]
1.56
[1.66]
Arash Partow
106
[101]
739
[435]
93
[420]
280
[98]
275
[85]
514
[355]
671
[570]
3332
[2372]
543
[779]
1.65
[3.88]
One At Time
118
[105]
830
[421]
81
[110]
321
[97]
319
[103]
578
[364]
741
[545]
3809
[2346]
657
[795]
1.82
[1.75]
Weinberger
119
[104]
956
[422]
54
[100]
375
[111]
379
[117]
614
[364]
745
[712]
3973
[2547]
560
[744]
1.89
[1.75]
Hanson
86
[118]
531
[649]
55
[112]
168
[118]
1722
[499]
393
[435]
549
[592]
2742
[2890]
463
[833]
2.60
[2.46]

Minden sejt tartalmazza a végrehajtási idő, akkor az ütközések száma, szögletes zárójelben. Végrehajtási idő van kifejezve több ezer óra ciklus (egy kisebb számot jobb). Avg oszlop tartalmazza a normalizált átlagos végrehajtási idő (az ütközések száma).

A funkció által Kernighan, majd Ritchie-től a híres könyv “C programozási Nyelv”, 3rd edition; Weinberger hash a hash a szorzó 65599 a Vörös Sárkány könyv. Ez utóbbi funkció használható a gawk, sdbm, más Linux programok. x17 a funkció által Peter Kankowski (szorzó = 17; 32 vonni minden betű kód).

Mint látható a táblázatból, akkor a függvény a legalacsonyabb számú ütközések nem mindig a leggyorsabb.

Eredmények nagy adathalmaz (listáját szavak Angol Wikipédia, 12,5 millió szavak, a benchmark által Georgi ‘Sanmayce’):

Core i5 processzor

Wikipedia
Avg
iSCSI CRC
5725944
[2077725]
1.00
[1.00]
Meiyan
5829105
[2111271]
1.02
[1.02]
Murmur2
6313466
[2081476]
1.10
[1.00]
Larson
6403975
[2080111]
1.12
[1.00]
Murmur3
6492620
[2082084]
1.13
[1.00]
x65599
6479417
[2102893]
1.13
[1.01]
FNV-1a
6599423
[2081195]
1.15
[1.00]
SBox
6964673
[2084018]
1.22
[1.00]
Hanson
7007689
[2129832]
1.22
[1.03]
CRC-32
7016147
[2075088]
1.23
[1.00]
Sedgewick
7060691
[2080640]
1.23
[1.00]
XXHfast32
7078804
[2084164]
1.24
[1.00]
K&R
7109841
[2083145]
1.24
[1.00]
XXHstrong32
7168788
[2084514]
1.25
[1.00]
Bernstein
7247096
[2074237]
1.27
[1.00]
lookup3
7342986
[2084889]
1.28
[1.01]
Murmur2A
7376650
[2081370]
1.29
[1.00]
Paul Hsieh
7387317
[2180206]
1.29
[1.05]
x17 unrolled
7410443
[2410605]
1.29
[1.16]
Ramakrishna
8172670
[2093253]
1.43
[1.01]
One At Time
8338799
[2087861]
1.46
[1.01]
MaPrime2c
8428492
[2084467]
1.47
[1.00]
Arash Partow
8503299
[2084572]
1.49
[1.00]
Weinberger
9416340
[3541181]
1.64
[1.71]
Novak unrolled
21289919
[6318611]
3.72
[3.05]
Fletcher
22235133
[9063797]
3.88
[4.37]

Pentium-M processzor

Wikipedia
Avg
x17 unrolled
11321744
[2410605]
1.00
[1.16]
K&R
11666050
[2083145]
1.03
[1.00]
Bernstein
11833902
[2074237]
1.05
[1.00]
Larson
11888751
[2080111]
1.05
[1.00]
Sedgewick
12111839
[2080640]
1.07
[1.00]
x65599
12144777
[2102893]
1.07
[1.01]
Arash Partow
12235396
[2084572]
1.08
[1.00]
Ramakrishna
12185834
[2093253]
1.08
[1.01]
Meiyan
12269691
[2111271]
1.08
[1.02]
CRC-32
12604152
[2075088]
1.11
[1.00]
Murmur2
12713455
[2081476]
1.12
[1.00]
SBox
12716574
[2084018]
1.12
[1.00]
Hanson
12627597
[2129832]
1.12
[1.03]
lookup3
12791917
[2084889]
1.13
[1.01]
FNV-1a
12868991
[2081195]
1.14
[1.00]
Murmur3
12916960
[2082084]
1.14
[1.00]
XXHfast32
12936106
[2084164]
1.14
[1.00]
XXHstrong32
12950650
[2084514]
1.14
[1.00]
Murmur2A
13068746
[2081370]
1.15
[1.00]
Paul Hsieh
12992315
[2180206]
1.15
[1.05]
MaPrime2c
13348580
[2084467]
1.18
[1.00]
One At Time
13662010
[2087861]
1.21
[1.01]
Weinberger
14592843
[3541181]
1.29
[1.71]
Fletcher
37410790
[9063797]
3.30
[4.37]
Novak unrolled
37769882
[6318611]
3.34
[3.05]

Bizonyos funkciók kizárták a viszonyítási alap, mert nagyon rossz teljesítmény:

Az ütközések száma attól függően, hogy a hash tábla méret (ugyanazon adatok, köszönöm, hogy Ace az ötlet):

Vörös Sárkány Könyv javasolja a következő képlet értékelésére hash függvény minőség:

az összeg j=0 to m-1: b_j(b_j+1)/2 / [(n/2m)(n+2m-1)]

ahol bj a tételek száma a j-edik helyére, m a rések száma, n pedig a tételek száma összesen. Az összeg bj(bj + 1) / 2 becslése szerint a rések száma a program kellene látogatnia, hogy megtalálja a szükséges értéket. A nevező (n / 2)(n + 2m − 1) a száma látogatott slots egy ideális funkció teszi, hogy minden egyes elem egy véletlenszerű nyílásba. Szóval, ha a funkció ideális, a formula kell adni 1. A valóság az, hogy egy jó funkció valahol között 0.95 es 1.05. Ha ez több, van egy nagy számú ütközések (lassan!). Ha kisebb, akkor a függvény ad a kisebb ütközések, mint a véletlenszerűen elosztó funkció, ami nem rossz.

Itt vannak az eredmények az egyes funkciók:

Következtetés

Összetett függvények által Paul Hsieh Bob Jenkins vannak hangolva a hosszú kulcsokat, mint azok a postfix, előtag vizsgálatok. Vegye figyelembe, hogy ezek nem biztosítják a legjobb száma ütközések esetében ezeket a vizsgálatokat, de van a legjobb idő, ami azt jelenti, hogy a funkciók gyorsabb, mint a többiek, mert a hurok kibontása. Ugyanakkor, ezek optimális rövid gombok (szavak, szonett vizsgálatok).

Egy szót sem számolja a program, egy fordító, vagy egy másik alkalmazás, amely jellemzően kezeli rövid kulcsok, gyakran előnyös használni egy egyszerű multiplikatív függvény például x17 vagy Larson hash. Azonban ezek a funkciók teljesítettek rosszul a hosszú kulcsokat.

Novak mutatott rossz eredmények-a nagy adathalmaz. Jesteress nagyszámú ütközések a számok teszt.

Murmur2, meiyan-t, SBox, CRC32 nyújt jó teljesítményt, minden típusú kulcs. Ők is ajánlott, mint általános célú hasító függvények x86.

Hardver-gyorsított CRC (jelölt iSCSI CRC a táblázat) a leggyorsabb hash függvény a mostani Core i5/i7 processzorok. Azonban a CRC32 utasítás nem támogatja az AMD korábbi Intel processzorok.

Töltse le a forráskód (152 KB, MSVC++)

Variációk

XORing magas, illetve alacsony rész

A tábla mérete kevesebb, mint 2^16, minőségének javítása hash függvény által XORing magas, illetve alacsony a szavakat, hogy több levelet lesz figyelembe venni:

return hash ^ (hash >> 16);

Levonva az állandó

x17 hash függvény kivonása a tér minden egyes levelet, hogy vágja le a vezérlő karakter a tartomány 0x00..0x1F. Ha a hash kulcs, hosszú, amelyek csak a Latin betűket, a számokat, a betűket lesz ritkábban tolódott ki, de a teljes ütközések száma alacsonyabb lesz. Akkor is vonjuk ki “A”, ha tudod, hogy a kulcsok csak angol szavakat.

Segítségével nagyobb szorzók egy fordító

Paul Hsieh megjegyezte, hogy nagy szorzók rendelkezhetnek jobb eredményeket a hash tábla a fordító, mert egy tipikus forráskódot tartalmaz egy csomó egy levelet, hogy egy változó neve (i, j, s, stb.), meg fognak ütközni, ha a szorzó száma kevesebb, mint a betű az abc-ben.

A vizsgálat megerősíti ezt a feltételezést: a funkció által Kernighan & Ritchie (M = 33) alacsonyabb száma ütközések, mint x17 (M = 17), de az utóbbi még mindig gyorsabb (lásd a Változók oszlop a fenti táblázatot).

Beállítás hash tábla méret prímszám

Egy vizsgálat azt mutatta, hogy az ütközések száma általában kisebb, ha egy miniszterelnök, de a számítások modulo miniszterelnök több időt, mint a számítások teljesítmény 2, így ez a módszer nem célravezető. Még cseréje osztás szorzás által kölcsönös értékek nem segít itt:

Words
Win32
Numbers
Prefix
Postfix
Variables
Shakespeare
Bernstein % 2K
145
[261]
880
[889]
426
[8030]
326
[214]
316
[226]
649
[697]
874
[1131]
Bernstein % prime
186
[221]
1049
[995]
445
[5621]
364
[194]
357
[217]
805
[800]
1123
[1051]
Bernstein optimized mod
160
[221]
960
[995]
416
[5621]
341
[194]
334
[217]
722
[800]
969
[1051]
x17 % 2K
137
[193]
847
[1002]
81
[340]
314
[244]
300
[228]
641
[863]
832
[1012]
x17 % prime
173
[256]
1010
[1026]
104
[324]
356
[246]
339
[216]
760
[760]
1046
[1064]
x17 optimized mod
155
[256]
915
[1026]
96
[324]
330
[246]
315
[216]
691
[760]
930
[1064]

Végrehajtási nyílt címzés vs. külön láncolás

Nyílt címzés, a legtöbb hash függvények show kínos csoportosítási viselkedés, a “Számok” teszt:

Bernst.
K&R
x17 unroll
x65599
FNV
Univ
Weinb.
Hsieh
One-at
Lookup3
Partow
CRC
OA
426
81
84
207
88
91
273
110
103
92
1042
79
[8030]
[20810]
[340]
[3158]
[207]
[480]
[4360]
[342]
[267]
[205]
[20860]
[96]
32-bit
179
69
74
114
86
80
125
105
99
92
347
82
[8030]
[20810]
[340]
[3158]
[207]
[480]
[4360]
[342]
[267]
[205]
[20860]
[96]
chain
92
68
73
82
88
84
73
107
99
95
149
84
[500]
[500]
[24]
[258]
[124]
[48]
[100]
[138]
[131]
[108]
[1530]
[64]

Lehet elkerülni a legrosszabb esetben segítségével láncolás az ütközés állásfoglalás. Azonban láncolás több memóriát igényelnek a következő elemre mutató, így a teljesítmény javítása nem jön ingyen. Egyéni memória kiutaló kell általában írásbeli, mert hív a malloc(), nagyszámú kis szerkezetek az optimális.

Egyes implementációk (pl. hash tábla a Python értelmező) tárolja egy teljes 32 bites hash a tétel, hogy gyorsítsák fel a karakterlánc-összehasonlítás, de ez kevésbé hatékony, mint a láncolás.

Eredetileg a https://www.strchr.com/hash_functions. Készítette http://hunsci.com