Etinyere m ya na Github .
Ọ bụ tebụl hash GPU dị mfe nwere ike ịhazi narị nde nde ntinye kwa nkeji. Na laptọọpụ NVIDIA GTX 1060 m, koodu ahụ na-etinye ụzọ abụọ igodo uru nde 64 na-enweghị usoro n'ihe dị ka 210 ms wee wepụ 32 nde ụzọ abụọ n'ihe dị ka 64 ms.
Ya bụ, ọsọ na laptọọpụ bụ ihe dị ka 300 nde ntinye / sk na 500 nde deletes / sk.
Edere tebụl na CUDA, ọ bụ ezie na otu usoro ahụ nwere ike itinye na HLSL ma ọ bụ GLSL. Mmejuputa a nwere ọtụtụ oke iji hụ na arụmọrụ dị elu na kaadị vidiyo:
- Naanị igodo 32-bit na otu ụkpụrụ ka a na-ahazi.
- Tebụl hash nwere nha a kapịrị ọnụ.
- Na nha a ga-abụ nha abụọ na ike.
Maka igodo na ụkpụrụ, ịkwesịrị idobe akara nchapụta dị mfe (na koodu dị n'elu nke a bụ 0xffffffff).
Tebụl hash na-enweghị mkpọchi
Tebụl hash na-eji adreesị mepere emepe na , ya bụ, ọ bụ naanị ụdị ụzọ abụọ igodo bara uru nke echekwara na ebe nchekwa ma nwee arụmọrụ cache dị elu. Enweghị ike ikwu otu ihe ahụ maka ịgbụ, nke gụnyere ịchọ ihe nrịbama na ndepụta ejikọtara. Tebụl hash bụ ihe dị mfe ịchekwa ihe KeyValue:
struct KeyValue
{
uint32_t key;
uint32_t value;
};
Ogo nke tebụl bụ ike nke abụọ, ọ bụghị ọnụ ọgụgụ dị elu, n'ihi na otu ntụziaka ngwa ngwa zuru ezu iji tinye ihe mkpuchi pow2 / AND, mana onye na-arụ ọrụ modulus na-eji nwayọọ nwayọọ. Nke a dị mkpa n'ihe gbasara nyocha nke linear, ebe ọ bụ na n'ime nyocha nke tebụl linear, a ga-ekechi ndepụta oghere na oghere ọ bụla. N'ihi ya, a na-agbakwunye ego nke ọrụ ahụ modulo na oghere ọ bụla.
Tebụlụ ahụ na-echekwa naanị igodo na uru maka mmewere ọ bụla, ọ bụghị hash nke igodo ahụ. Ebe ọ bụ na tebụl na-echekwa naanị igodo 32-bit, a na-agbakọ hash ngwa ngwa. Koodu dị n'elu na-eji Murmur3 hash, nke na-eme naanị mgbanwe ole na ole, XOR na mmụba.
Tebụl hash na-eji usoro nchebe mkpọchi na-adabereghị na usoro ebe nchekwa. Ọbụlagodi na ụfọdụ ọrụ ide na-akpaghasị usoro ọrụ ndị ọzọ dị otu a, tebụl hash ka ga-edobe ọnọdụ ziri ezi. Anyị ga-ekwu maka nke a n'okpuru. Usoro a na-arụ ọrụ nke ọma na kaadị vidiyo na-agba ọtụtụ puku eri n'otu oge.
A na-ebute igodo na ụkpụrụ dị na tebụl hash ka ọ tọgbọrọ chakoo.
Enwere ike ịmegharị koodu ahụ iji jikwaa igodo 64-bit na ụkpụrụ. Igodo chọrọ ịgụ, dee, na atụnyere-na-swap arụmọrụ. Na ụkpụrụ chọrọ ọrụ ịgụ na ide ihe atọm. Ọ dabara nke ọma, na CUDA, arụ ọrụ ịgụ-ede maka ụkpụrụ 32- na 64-bit bụ atọm ma ọ bụrụhaala na ha na-adakọ n'ụzọ nkịtị (lee n'okpuru). ), na kaadị vidiyo ọgbara ọhụrụ na-akwado ọrụ ntule na mgbanwe 64-bit atomic. N'ezie, mgbe ị na-akpụ akpụ na 64-bit, arụmọrụ ga-ebelata ntakịrị.
Hash okpokoro steeti
Otu ụzọ isi uru ọ bụla na tebụl hash nwere ike ịnwe otu n'ime steeti anọ:
- Igodo na uru abaghị uru. Na steeti a, a na-ebute tebụl hash.
- Edela igodo ahụ, mana edebeghị uru ya. Ọ bụrụ na eri ọzọ na-agụ data ugbu a, ọ ga-alaghachi efu. Nke a bụ ihe nkịtị, otu ihe ahụ gaara eme ma ọ bụrụ na eriri ogbugbu ọzọ na-arụ ọrụ ntakịrị oge, anyị na-ekwukwa banyere usoro data na-ejikọta ọnụ.
- A na-edekọ ma igodo na uru ya.
- Uru dị maka eriri mmezu ndị ọzọ, mana igodo ahụ erubeghị. Nke a nwere ike ime n'ihi na ụdị mmemme CUDA nwere ụdị ebe nchekwa enweghị iwu. Nke a bụ ihe nkịtị; n'ọnọdụ ọ bụla, igodo ahụ ka bụ ihe efu, ọbụlagodi na uru adịkwaghị.
Otu ihe dị mkpa bụ na ozugbo e dechara igodo ahụ na oghere, ọ naghị emegharị - ọ bụrụgodị na ehichapụ igodo ahụ, anyị ga-ekwu maka nke a n'okpuru.
Koodu tebụl hash na-arụ ọrụ na ụdị ebe nchekwa a na-enyeghị iwu nke na-amaghị usoro ebe nchekwa na-agụ na ide. Ka anyị na-ele anya ntinye, nyocha na ihichapụ na tebụl hash, cheta na ụzọ uru igodo ọ bụla dị n'otu steeti anọ akọwara n'elu.
Ịtinye n'ime tebụl hash
Ọrụ CUDA nke na-etinye ụzọ abụọ uru isi n'ime tebụl hash dị ka nke a:
void gpu_hashtable_insert(KeyValue* hashtable, uint32_t key, uint32_t value)
{
uint32_t slot = hash(key);
while (true)
{
uint32_t prev = atomicCAS(&hashtable[slot].key, kEmpty, key);
if (prev == kEmpty || prev == key)
{
hashtable[slot].value = value;
break;
}
slot = (slot + 1) & (kHashTableCapacity-1);
}
}
Iji fanye igodo, koodu ahụ na-agbanye n'usoro tebụl hash na-amalite site na hash nke igodo etinyere. Oghere ọ bụla dị n'usoro ahụ na-arụ ọrụ ntụnyere-na-swap atọm nke na-atụnyere igodo dị na oghere ahụ ka ọ tọgbọ chakoo. Ọ bụrụ na achọpụtara enweghị nkwekọrịta, a na-eji igodo etinyere emelite igodo dị na oghere ahụ, wee weghachi igodo oghere mbụ. Ọ bụrụ na igodo mbụ a tọgbọrọ chakoo ma ọ bụ dabara na igodo etinyere, mgbe ahụ koodu ahụ chọtara oghere dabara adaba maka ntinye wee tinye uru etinyere n'ime oghere ahụ.
Ọ bụrụ n'otu kernel oku gpu_hashtable_insert() enwere otutu ihe nwere otu igodo, mgbe ahụ, ụkpụrụ ha ọ bụla nwere ike dee ya na oghere igodo. A na-ewere nke a dị ka ihe nkịtị: otu n'ime isi-uru na-ede n'oge oku ga-aga nke ọma, ma ebe ọ bụ na ihe a niile na-eme n'otu n'otu n'ime ọtụtụ eri nke ogbugbu, anyị enweghị ike ịkọ nke ederede ederede ga-abụ nke ikpeazụ.
Nyocha tebụl hash
Koodu maka igodo ọchụchọ:
uint32_t gpu_hashtable_lookup(KeyValue* hashtable, uint32_t key)
{
uint32_t slot = hash(key);
while (true)
{
if (hashtable[slot].key == key)
{
return hashtable[slot].value;
}
if (hashtable[slot].key == kEmpty)
{
return kEmpty;
}
slot = (slot + 1) & (kHashTableCapacity - 1);
}
}
Iji chọta uru igodo echekwara na tebụl, anyị na-atụgharị n'usoro n'usoro malite na hash nke igodo anyị na-achọ. N'ime oghere ọ bụla, anyị na-elele ma igodo ahụ bụ nke anyị na-achọ, ma ọ bụrụ otú ahụ, anyị na-eweghachi uru ya. Anyị na-enyocha ma igodo ahụ ọ tọgbọrọ chakoo, ọ bụrụ otu a, anyị na-ewepụ ọchụchọ ahụ.
Ọ bụrụ na anyị enweghị ike ịchọta igodo ahụ, koodu ahụ na-eweghachi uru efu.
Enwere ike ịrụ ọrụ ọchụchọ ndị a n'otu oge site na ntinye na ihichapụ. Otu ụzọ abụọ dị na tebụl ga-enwe otu n'ime steeti anọ akọwara n'elu maka mgbaba.
Na-ehichapụ na tebụl hash
Koodu maka ihichapụ igodo:
void gpu_hashtable_delete(KeyValue* hashtable, uint32_t key, uint32_t value)
{
uint32_t slot = hash(key);
while (true)
{
if (hashtable[slot].key == key)
{
hashtable[slot].value = kEmpty;
return;
}
if (hashtable[slot].key == kEmpty)
{
return;
}
slot = (slot + 1) & (kHashTableCapacity - 1);
}
}
A na-eme ihichapụ igodo n'ụzọ na-adịghị ahụkebe: anyị na-ahapụ igodo ahụ na tebụl wee kaa uru ya (ọ bụghị igodo n'onwe ya) dị ka ihe efu. Koodu a yiri nke ukwuu lookup(), ma e wezụga na ọ bụrụ na ahụrụ egwuregwu na igodo, ọ na-eme ka uru ya tọgbọrọ chakoo.
Dịka ekwuru n'elu, ozugbo edere mkpịsị ugodi na oghere, a naghị ebugharị ya ọzọ. Ọbụlagodi mgbe a na-ehichapụ ihe mmewere na tebụl, igodo ahụ na-anọgide n'ọnọdụ ya, uru ya na-aghọ ihe efu. Nke a pụtara na anyị adịghị mkpa iji ihe atomic dee ọrụ maka oghere uru, n'ihi na ọ dịghị mkpa ma ugbu a uru ọ bụ efu ma ọ bụ na-ọ ka ga-aghọ efu.
Na-emegharị tebụl hash
Ị nwere ike ịgbanwe nha nke tebụl hash site na ịmepụta tebụl buru ibu ma tinye ihe ndị na-adịghị efu site na tebụl ochie n'ime ya. E mejuputaghị m ọrụ a n'ihi na achọrọ m idobe koodu nlele dị mfe. Ọzọkwa, na mmemme CUDA, a na-ekenye ebe nchekwa na koodu nnabata karịa na kernel CUDA.
Ke ibuotikọ na-akọwa otu esi agbanwe ụdị data echedoro mkpọchi.
Asọmpi
Na snippets koodu ọrụ dị n'elu gpu_hashtable_insert(), _lookup() и _delete() hazie otu igodo-uru ụzọ n'otu oge. Na ala gpu_hashtable_insert(), _lookup() и _delete() Hazie ọtụtụ ụzọ abụọ n'otu n'otu, ụzọ abụọ ọ bụla n'ime eriri mmezu GPU dị iche:
// CPU code to invoke the CUDA kernel on the GPU
uint32_t threadblocksize = 1024;
uint32_t gridsize = (numkvs + threadblocksize - 1) / threadblocksize;
gpu_hashtable_insert_kernel<<<gridsize, threadblocksize>>>(hashtable, kvs, numkvs);
// GPU code to process numkvs key/values in parallel
void gpu_hashtable_insert_kernel(KeyValue* hashtable, const KeyValue* kvs, unsigned int numkvs)
{
unsigned int threadid = blockIdx.x*blockDim.x + threadIdx.x;
if (threadid < numkvs)
{
gpu_hashtable_insert(hashtable, kvs[threadid].key, kvs[threadid].value);
}
}
Tebụl hash na-egbochi mkpọchi na-akwado ntinye, nleba anya na nhichapụ. N'ihi na ụzọ abụọ igodo-uru na-adị mgbe niile n'otu n'ime steeti anọ ma igodo anaghị agagharị, tebụl na-ekwe nkwa izi ezi ọbụlagodi na eji ụdị ọrụ dị iche iche n'otu oge.
Otú ọ dị, ọ bụrụ na anyị na-ahazi ogbe ntinye na nhichapụ n'otu aka ahụ, ma ọ bụrụ na ntinye nke ụzọ abụọ nwere igodo oyiri, mgbe ahụ anyị agaghị enwe ike ịkọ ụzọ abụọ ga-esi "merie" - a ga-ede ya na tebụl hash ikpeazụ. Ka anyị kwuo na anyị kpọrọ koodu ntinye ya na ntinye ntinye nke ụzọ abụọ A/0 B/1 A/2 C/3 A/4. Mgbe koodu gwụchara, abụọ B/1 и C/3 na-ekwe nkwa na ọ ga-adị na tebụl, ma n'otu oge ahụ ọ bụla n'ime ụzọ abụọ ga-apụta na ya A/0, A/2 ma ọ bụ A/4. Nke a nwere ike ma ọ bụ ọ gaghị abụ nsogbu - ihe niile dabere na ngwa ahụ. Ị nwere ike mara tupu oge eruo na enweghị igodo oyiri n'usoro ntinye, ma ọ bụ na ị chọghị ịma uru e dere ikpeazụ.
Ọ bụrụ na nke a bụ nsogbu gị, mgbe ahụ ịkwesịrị ikewapụ ụzọ abụọ oyiri n'ime oku usoro CUDA dị iche iche. Na CUDA, ọrụ ọ bụla nke na-akpọ kernel na-agwụcha mgbe niile tupu oku kernel na-esote (opekata mpe n'ime otu eri. Na eriri dị iche iche, a na-egbu kernel n'otu n'otu). N'ihe atụ dị n'elu, ọ bụrụ na ị na-akpọ otu kernel na A/0 B/1 A/2 C/3, na nke ọzọ nwere A/4, wee pịa igodo A ga-enweta uru 4.
Ugbu a, ka anyị kwuo banyere ma ọrụ kwesịrị lookup() и delete() jiri ntuba dị larịị ma ọ bụ nke na-agbanwe agbanwe gaa n'usoro ụzọ abụọ dị na tebụl hash. Na-ekwu na:
Onye nchịkọta nwere ike ịhọrọ ịkwalite ọgụgụ na ide na ebe nchekwa zuru ụwa ọnụ ma ọ bụ nkekọrịta... Enwere ike gbanyụọ njikarịcha ndị a site na iji isiokwu.
volatile: ... a na-achịkọta ntụaka ọ bụla maka mgbanwe a n'ime ezigbo ebe nchekwa gụọ ma ọ bụ dee ntụziaka.
Echiche ziri ezi anaghị achọ ngwa volatile. Ọ bụrụ na eri ogbugbu ahụ na-eji uru echekwara site na ọrụ agụburu mbụ, mgbe ahụ ọ ga-eji ozi emechiela anya. Mana ka, nke a bụ ozi sitere na ọnọdụ ziri ezi nke tebụl hash n'otu oge nke oku kernel. Ọ bụrụ na ịchọrọ iji ozi kachasị ọhụrụ, ịnwere ike iji ndeksi volatile, ma mgbe ahụ arụmọrụ ga-ebelata ntakịrị: dị ka ule m si dị, mgbe ị na-ehichapụ ihe nde 32, ọsọ ahụ belatara site na 500 nde nhichapụ / sec ruo 450 nde nhichapụ / sk.
Ubu oke
Na ule maka ntinye 64 nde ihe na ihichapụ 32 nde n'ime ha, asọmpi n'etiti std::unordered_map na ọ fọrọ nke nta ka ọ dịghị tebụl hash maka GPU:
std::unordered_map ejiri 70 ms tinye na iwepu ihe wee tọhapụ ha unordered_map (iwepụ ọtụtụ nde ihe na-ewe oge buru ibu, n'ihi na n'ime unordered_map A na-ekenye ọtụtụ ebe nchekwa). N'ikwu eziokwu, std:unordered_map kpamkpam dị iche iche mgbochi. Ọ bụ otu eri CPU nke mmezu, na-akwado isi-ụkpụrụ nke nha ọ bụla, na-arụ ọrụ nke ọma na ọnụego ojiji dị elu, ma gosipụta arụmọrụ kwụsiri ike mgbe ihichapụ ọtụtụ.
Ogologo oge tebụl hash maka GPU na nkwukọrịta mmemme bụ 984 ms. Nke a na-agụnye oge a na-etinye na tebụl na ebe nchekwa na ihichapụ ya (ịnye 1 GB nke ebe nchekwa otu oge, nke na-ewe oge na CUDA), itinye na ihichapụ ihe, na ịmegharị ha. A na-eburukwa n'uche na nnomi niile sitere na ebe nchekwa kaadị vidiyo.
Tebụl hash n'onwe ya were 271 ms iji wuchaa. Nke a na-agụnye oge nke kaadị vidiyo na-etinye na ihichapụ ihe, na anaghị eburu n'uche oge ejiri na-edegharị na ebe nchekwa ma na-atụgharị n'elu tebụl nke ga-esi na ya pụta. Ọ bụrụ na tebụl GPU dị ndụ ogologo oge, ma ọ bụ ọ bụrụ na tebụl hash dị kpamkpam na ebe nchekwa nke kaadị vidiyo (dịka ọmụmaatụ, ịmepụta tebụl hash nke koodu GPU ndị ọzọ ga-eji ma ọ bụghị nhazi etiti), mgbe ahụ. nsonaazụ ule dị mkpa.
Tebụl hash maka kaadị vidiyo na-egosiputa arụmọrụ dị elu n'ihi oke mmepụta na ntinye aka na-arụ ọrụ.
-adịghị emezi emezi
Ihe owuwu tebụl hash nwere nsogbu ole na ole ị kwesịrị ịma:
- A na-egbochi nyocha nke Linear site na nchịkọta, nke na-eme ka igodo ndị dị na tebụl tinye obere ka ọ dị mma.
- Anaghị ewepụ igodo site na iji ọrụ ahụ
deletena ka oge na-aga, ha na-akpakọba tebụl.
N'ihi ya, arụmọrụ nke tebụl hash nwere ike jiri nwayọọ nwayọọ na-eweda ya, karịsịa ma ọ bụrụ na ọ dị ogologo oge ma nwee ọtụtụ ntinye na ihichapụ. Otu ụzọ ị ga-esi belata ọghọm ndị a bụ ịghaghachi na tebụl ọhụrụ nwere ọnụego ojiji dị obere ma kpochaa igodo ndị ewepụrụ n'oge a na-emegharị ahụ.
Iji gosi okwu ndị a kọwara, m ga-eji koodu dị n'elu mepụta tebụl nwere ihe dị nde 128 na akaghị aka site na ihe nde 4 ruo mgbe m jupụta 124 nde oghere (ọnụego ojiji nke ihe dịka 0,96). Nke a bụ tebụl nsonaazụ, ahịrị ọ bụla bụ oku CUDA kernel iji tinye ihe ọhụrụ nde anọ n'ime otu tebụl hash:
Ọnụọgụ ojiji
Ogologo oge ntinye 4 ọcha
0,00
11,608448 ms (igodo nde 361,314798/sk.)
0,03
11,751424 ms (igodo nde 356,918799/sk.)
0,06
11,942592 ms (igodo nde 351,205515/sk.)
0,09
12,081120 ms (igodo nde 347,178429/sk.)
0,12
12,242560 ms (igodo nde 342,600233/sk.)
0,16
12,396448 ms (igodo nde 338,347235/sk.)
0,19
12,533024 ms (igodo nde 334,660176/sk.)
0,22
12,703328 ms (igodo nde 330,173626/sk.)
0,25
12,884512 ms (igodo nde 325,530693/sk.)
0,28
13,033472 ms (igodo nde 321,810182/sk.)
0,31
13,239296 ms (igodo nde 316,807174/sk.)
0,34
13,392448 ms (igodo nde 313,184256/sk.)
0,37
13,624000 ms (igodo nde 307,861434/sk.)
0,41
13,875520 ms (igodo nde 302,280855/sk.)
0,44
14,126528 ms (igodo nde 296,909756/sk.)
0,47
14,399328 ms (igodo nde 291,284699/sk.)
0,50
14,690304 ms (igodo nde 285,515123/sk.)
0,53
15,039136 ms (igodo nde 278,892623/sk.)
0,56
15,478656 ms (igodo nde 270,973402/sk.)
0,59
15,985664 ms (igodo nde 262,379092/sk.)
0,62
16,668673 ms (igodo nde 251,627968/sk.)
0,66
17,587200 ms (igodo nde 238,486174/sk.)
0,69
18,690048 ms (igodo nde 224,413765/sk.)
0,72
20,278816 ms (igodo nde 206,831789/sk.)
0,75
22,545408 ms (igodo nde 186,038058/sk.)
0,78
26,053312 ms (igodo nde 160,989275/sk.)
0,81
31,895008 ms (igodo nde 131,503463/sk.)
0,84
42,103294 ms (igodo nde 99,619378/sk.)
0,87
61,849056 ms (igodo nde 67,815164/sk.)
0,90
105,695999 ms (igodo nde 39,682713/sk.)
0,94
240,204636 ms (igodo nde 17,461378/sk.)
Ka ojiji na-abawanye, arụmọrụ na-ebelata. Nke a abụghị ihe a na-achọsi ike n'ọtụtụ ọnọdụ. Ọ bụrụ na ngwa na-etinye ihe n'ime tebụl wee tụfuo ha (dịka ọmụmaatụ, mgbe ị na-agụta okwu na akwụkwọ), nke a abụghị nsogbu. Ma ọ bụrụ na ngwa ahụ na-eji tebụl hash dị ogologo ndụ (dịka ọmụmaatụ, na onye na-ese foto na-echekwa akụkụ nke ihe oyiyi na-adịghị efu ebe onye ọrụ na-etinyekarị ma na-ehichapụ ozi), mgbe ahụ omume a nwere ike ịkpata nsogbu.
Ma tụọ omimi nke tebụl hash na-enyocha mgbe ntinye nde 64 (ihe eji eme ihe 0,5). Nkezi omimi bụ 0,4774, yabụ ọtụtụ igodo dị na oghere kacha mma enwere ike ma ọ bụ otu oghere dịpụrụ adịpụ na ọnọdụ kacha mma. Omimi ụda kacha elu bụ 60.
M wee tụọ omimi nyocha na tebụl nwere ntinye nde 124 (ihe eji eme ihe 0,97). Nkezi omimi bụ ugbua 10,1757, na kacha - 6474 (!!). Arụmọrụ nhụta Linear na-agbada nke ọma na ọnụego ojiji dị elu.
Ọ kacha mma idowe ọnụ ọgụgụ ojiji tebụl hash a dị ala. Mana anyị na-abawanye arụmọrụ na-efu nke oriri ebe nchekwa. Ọ dabara nke ọma, n'ihe gbasara igodo na ụkpụrụ 32-bit, nke a nwere ike ịzie ezi. Ọ bụrụ na ihe atụ dị n'elu, na tebụl nwere ihe dị nde 128, anyị na-edebe ihe eji eme ihe nke 0,25, mgbe ahụ, anyị nwere ike itinye ihe karịrị nde 32 n'ime ya, na oghere 96 nke fọdụrụ ga-efunahụ - 8 bytes maka ụzọ ọ bụla. , 768 MB nke ebe nchekwa furu efu.
Biko mara na anyị na-ekwu maka ọnwụ nke ebe nchekwa kaadị vidiyo, nke bụ ihe bara uru karịa ebe nchekwa usoro. Ọ bụ ezie na ọtụtụ kaadị eserese desktọpụ ọgbara ọhụrụ na-akwado CUDA nwere opekata mpe 4 GB nke ebe nchekwa (n'oge ederede, NVIDIA 2080 Ti nwere 11 GB), ọ ka ga-abụ mkpebi kacha amamihe iji tụfuo ụdị ahụ.
E mesịa, m ga-edekwu banyere ịmepụta tebụl hash maka kaadị vidiyo na-enweghị nsogbu na nyocha omimi, yana ụzọ isi jiri oghere ndị ehichapụrụ.
Nleta omimi na-ada ụda
Iji chọpụta omimi nyocha nke igodo, anyị nwere ike wepụ hash igodo ahụ (ntụgharị tebụl ya kacha mma) na ndeksi tebụl ya n'ezie:
// get_key_index() -> index of key in hash table
uint32_t probelength = (get_key_index(key) - hash(key)) & (hashtablecapacity-1);
N'ihi anwansi nke ọnụọgụ abụọ nke abụọ na-emeju ọnụọgụ ọnụọgụ abụọ na eziokwu ahụ bụ na ike nke tebụl hash bụ abụọ na ike nke abụọ, usoro a ga-arụ ọrụ ọbụna mgbe a na-ebugharị igodo igodo na mmalite nke tebụl. Ka anyị were igodo nke dabara na 1, mana etinyere ya na oghere 3. Mgbe ahụ maka tebụl nwere ikike 4 anyị ga-enweta. (3 — 1) & 3, nke ya na 2.
nkwubi
Ọ bụrụ na ị nwere ajụjụ ma ọ bụ kwuo, biko zitere m email ma ọ bụ mepee isiokwu ọhụrụ na.
Edere koodu a n'ike mmụọ nsọ site na akụkọ mara mma:
N'ọdịnihu, m ga-anọgide na-ede banyere hash table mmejuputa iwu kaadị vidiyo na nyochaa arụmọrụ ha. Atụmatụ m gụnyere ịke, Robin Hood hashing, na cuckoo hashing site na iji arụ ọrụ atọm na nhazi data bụ enyi na enyi GPU.
isi: www.habr.com