Ман онро дар Github нашр кардам .
Ин як ҷадвали оддии GPU аст, ки қодир аст дар як сония садҳо миллион замимаҳоро коркард кунад. Дар ноутбуки NVIDIA GTX 1060-и ман, код 64 миллион ҷуфтҳои тасодуфӣ тавлидшудаи калиди-арзишро дар тақрибан 210 мс дохил мекунад ва 32 миллион ҷуфтро дар тақрибан 64 мс нест мекунад.
Яъне, суръат дар ноутбук тақрибан 300 миллион ворид / сония ва 500 миллион несткунӣ / сония аст.
Ҷадвал дар CUDA навишта шудааст, гарчанде ки ҳамон техникаро ба HLSL ё GLSL татбиқ кардан мумкин аст. Татбиқи якчанд маҳдудиятҳо барои таъмини иҷрои баланд дар корти видео дорад:
- Танҳо калидҳои 32-бит ва ҳамон арзишҳо коркард мешаванд.
- Ҷадвали ҳаш андозаи муайян дорад.
- Ва ин андоза бояд ба ду ба қудрат баробар бошад.
Барои калидҳо ва арзишҳо, шумо бояд аломати ҷудокунандаи оддиро захира кунед (дар коди боло ин 0xffffffff аст).
Ҷадвали хэш бе қуфлҳо
Ҷадвали ҳаш суроғаи кушодро бо истифода мебарад , яъне он танҳо як массиви ҷуфтҳои калид-арзиш аст, ки дар хотира нигоҳ дошта мешавад ва иҷрои аълои кэш дорад. Дар бораи занҷирбандӣ, ки ҷустуҷӯи нишондиҳанда дар рӯйхати алоқамандро дар бар мегирад, ҳаминро гуфтан мумкин нест. Ҷадвали ҳаш як массиви оддии нигоҳдории унсурҳо мебошад KeyValue:
struct KeyValue
{
uint32_t key;
uint32_t value;
};
Андозаи ҷадвал қувваи ду аст, на рақами аслӣ, зеро як дастури зуд барои татбиқи ниқоби pow2/AND кифоя аст, аммо оператори модул хеле сусттар аст. Ин дар мавриди санҷиши хатӣ муҳим аст, зеро дар ҷустуҷӯи ҷадвали хатӣ индекси слот бояд дар ҳар як слот печонида шавад. Ва дар натиҷа, арзиши амалиёт дар ҳар як слот модул илова карда мешавад.
Ҷадвал танҳо калид ва арзишро барои ҳар як элемент нигоҳ медорад, на хэши калид. Азбаски ҷадвал танҳо калидҳои 32-битро нигоҳ медорад, хэш хеле зуд ҳисоб карда мешавад. Рамзи дар боло овардашуда хэши Murmur3-ро истифода мебарад, ки танҳо чанд баст, XOR ва зарбҳоро иҷро мекунад.
Ҷадвали ҳаш усулҳои муҳофизати қулфро истифода мебарад, ки аз тартиби хотира новобастаанд. Ҳатто агар баъзе амалиётҳои навиштан тартиби дигар чунин амалиётҳоро вайрон кунанд ҳам, ҷадвали hash ҳолати дурустро нигоҳ медорад. Мо дар ин бора дар поён гап мезанем. Техника бо кортҳои видеоӣ, ки ҳамзамон ҳазорҳо риштаҳоро иҷро мекунанд, хуб кор мекунад.
Калидҳо ва арзишҳо дар ҷадвали ҳаш ба холӣ оғоз карда мешаванд.
Рамзро барои коркарди калидҳо ва арзишҳои 64-бит низ тағир додан мумкин аст. Калидҳо амалиёти атомии хондан, навиштан ва муқоиса ва ивазкуниро талаб мекунанд. Ва арзишҳо амалиёти хондан ва навиштани атомиро талаб мекунанд. Хушбахтона, дар CUDA, амалиёти хондан-навиштан барои арзишҳои 32 ва 64-бит атомӣ мебошанд, то даме ки онҳо табиатан мувофиқанд (ба поён нигаред). ) ва кортҳои видеоии муосир амалиёти муқоиса ва мубодилаи атомии 64-битро дастгирӣ мекунанд. Албатта, ҳангоми гузаштан ба 64 бит, иҷроиш каме коҳиш меёбад.
Ҳолати ҷадвали хэш
Ҳар як ҷуфти калид-арзиш дар ҷадвали ҳаш метавонад яке аз чаҳор ҳолат дошта бошад:
- Калид ва арзиш холӣ мебошанд. Дар ин ҳолат, ҷадвали hash оғоз карда мешавад.
- Калид навишта шудааст, аммо арзиши он ҳанӯз навишта нашудааст. Агар риштаи дигар ҳоло маълумотро мехонад, он холӣ бармегардад. Ин муқаррарӣ аст, агар риштаи дигари иҷроиш каме пештар кор мекард, ҳамин чиз рӯй медод ва мо дар бораи сохтори ҳамзамон маълумот сухан меронем.
- Ҳам калид ва ҳам арзиш сабт карда мешаванд.
- Арзиш барои дигар риштаҳои иҷро дастрас аст, аммо калид ҳанӯз нест. Ин метавонад рӯй диҳад, зеро модели барномасозии CUDA дорои модели хотираи ба таври озод фармоишшуда мебошад. Ин муқаррарӣ аст; дар ҳар сурат, калид холӣ аст, ҳатто агар арзиш дигар набошад.
Як нозуки муҳим он аст, ки вақте ки калид ба слот навишта шудааст, он дигар ҳаракат намекунад - ҳатто агар калид нест карда шавад, мо дар ин бора дар зер сӯҳбат хоҳем кард.
Рамзи ҷадвали хэш ҳатто бо моделҳои хотираи суст фармоишшуда кор мекунад, ки дар онҳо тартиби хондан ва навиштани хотира номаълум аст. Вақте ки мо ба воридкунӣ, ҷустуҷӯ ва несткунӣ дар ҷадвали ҳаш назар мекунем, дар хотир доред, ки ҳар як ҷуфти калид-арзиш дар яке аз чаҳор ҳолати дар боло тавсифшуда ҷойгир аст.
Ворид кардан ба ҷадвали ҳаш
Функсияи CUDA, ки ҷуфтҳои калид-арзишро ба ҷадвали хэш дохил мекунад, чунин менамояд:
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);
}
}
Барои ворид кардани калид, код аз массиви ҷадвали ҳаш аз хэши калиди воридшуда сар карда такрор мешавад. Ҳар як слот дар массив амалиёти атомии муқоиса ва ивазкуниро иҷро мекунад, ки калиди он слотро ба холӣ муқоиса мекунад. Агар номувофиқатӣ ошкор карда шавад, калиди слот бо калиди воридшуда нав карда мешавад ва он гоҳ калиди аслии ковокии баргардонида мешавад. Агар ин калиди аслӣ холӣ бошад ё ба калиди воридшуда мувофиқат кунад, он гоҳ код барои воридкунӣ слоти мувофиқро ёфт ва арзиши воридшударо ба слот ворид кард.
Агар дар як ядро занг занад gpu_hashtable_insert() унсурҳои сершумор бо як калид вуҷуд доранд, пас ҳар кадоме аз арзишҳои онҳоро метавон ба ковокии калид навишт. Ин муқаррарӣ ҳисобида мешавад: яке аз навиштаҷоти калидӣ ҳангоми занг бомуваффақият хоҳад буд, аммо азбаски ҳамаи ин дар як чанд риштаи иҷро мувозӣ сурат мегирад, мо пешгӯӣ карда наметавонем, ки кадом навиштани хотира охирин навишта мешавад.
Ҷустуҷӯи ҷадвали хэш
Рамзи ҷустуҷӯи калидҳо:
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);
}
}
Барои дарёфти арзиши калиде, ки дар ҷадвал нигоҳ дошта мешавад, мо аз хэши калиди ҷустуҷӯкардаи мо дар массив сар карда такрор мекунем. Дар ҳар як слот мо месанҷем, ки калид ҳамон калидест, ки мо меҷӯем ва агар ин тавр бошад, мо арзиши онро бармегардонем. Мо инчунин тафтиш мекунем, ки калид холӣ аст ва агар ин тавр бошад, мо ҷустуҷӯро қатъ мекунем.
Агар мо калидро ёфта натавонем, код арзиши холӣ медиҳад.
Ҳамаи ин амалиёти ҷустуҷӯиро метавон ҳамзамон тавассути дохилкунӣ ва ҳазф анҷом дод. Ҳар як ҷуфт дар ҷадвал яке аз чаҳор ҳолати дар боло тавсифшуда барои ҷараёнро дорад.
Нест кардан дар ҷадвали hash
Рамз барои нест кардани калидҳо:
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);
}
}
Тозакунии калид ба таври ғайриоддӣ сурат мегирад: мо калидро дар ҷадвал мегузорем ва арзиши онро (на худи калид) холӣ қайд мекунем. Ин код хеле монанд аст lookup(), ба истиснои он ки вақте ки мувофиқат дар калид пайдо мешавад, арзиши онро холӣ мекунад.
Тавре ки дар боло зикр гардид, вақте ки калид ба слот навишта мешавад, он дигар интиқол дода намешавад. Ҳатто вақте ки элемент аз ҷадвал нест карда мешавад, калид дар ҷои худ мемонад, арзиши он танҳо холӣ мешавад. Ин маънои онро дорад, ки ба мо лозим нест, ки амалиёти навиштани атомиро барои арзиши слот истифода барем, зеро муҳим нест, ки арзиши ҷорӣ холӣ аст ё не - он ҳоло ҳам холӣ хоҳад шуд.
Андозаи ҷадвали ҳашро тағир диҳед
Шумо метавонед андозаи ҷадвали ҳашро тавассути сохтани ҷадвали калонтар ва ворид кардани унсурҳои холӣ аз ҷадвали кӯҳна ба он тағир диҳед. Ман ин функсияро иҷро накардам, зеро ман мехостам рамзи намунаро оддӣ нигоҳ дорам. Ғайр аз он, дар барномаҳои CUDA, тақсимоти хотира аксар вақт дар коди мизбон анҷом дода мешавад, на дар ядрои CUDA.
Дар мақола тасвир мекунад, ки чӣ гуна тағир додани чунин сохтори додаҳои аз қулф муҳофизатшаванда.
Рақобатпазирӣ
Дар пораҳои рамзи функсияи боло gpu_hashtable_insert(), _lookup() и _delete() коркарди як ҷуфти калид-арзиш дар як вақт. Ва пасттар gpu_hashtable_insert(), _lookup() и _delete() массиви ҷуфтҳоро дар баробари коркард, ҳар як ҷуфт дар риштаи иҷрои GPU алоҳида:
// 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);
}
}
Ҷадвали хэш ба қулф тобовар воридкуниҳо, ҷустуҷӯҳо ва ҳазфкуниро дастгирӣ мекунад. Азбаски ҷуфтҳои калид-арзиш ҳамеша дар яке аз чаҳор ҳолат қарор доранд ва калидҳо ҳаракат намекунанд, ҷадвал ҳатто ҳангоми ҳамзамон намудҳои гуногуни амалиёт истифода шудан дурустиро кафолат медиҳад.
Аммо, агар мо як партияи дохилкунӣ ва несткуниро дар баробари коркард кунем ва агар массиви вуруди ҷуфтҳо калидҳои такрорӣ дошта бошад, пас мо пешгӯӣ карда наметавонем, ки кадом ҷуфтҳо "ғолиб мешаванд" - ба ҷадвали хэш охирин навишта мешаванд. Фарз мекунем, ки мо рамзи воридкуниро бо массиви вуруди ҷуфтҳо даъват кардем A/0 B/1 A/2 C/3 A/4. Вақте ки рамз ба итмом мерасад, ҷуфт мешавад B/1 и C/3 кафолат дода мешавад, ки дар ҷадвал ҳузур дошта бошанд, аммо дар айни замон ягон ҷуфт дар он пайдо мешавад A/0, A/2 ё A/4. Ин метавонад мушкилот бошад ё не - ҳамааш аз барнома вобаста аст. Шумо шояд пешакӣ донед, ки дар массиви вуруд калидҳои такрорӣ вуҷуд надоранд ё шояд ба шумо аҳамият надиҳед, ки кадом арзиш дар охир навишта шудааст.
Агар ин барои шумо мушкил бошад, пас шумо бояд ҷуфтҳои такрориро ба зангҳои гуногуни системаи CUDA ҷудо кунед. Дар CUDA ҳама амалиёте, ки ядроро даъват мекунад, ҳамеша пеш аз занги навбатии ядро анҷом дода мешавад (ҳадди ақал дар дохили як ришта. Дар риштаҳои гуногун ядроҳо параллел иҷро карда мешаванд). Дар мисоли боло, агар шумо як ядроро бо A/0 B/1 A/2 C/3, ва дигаре бо A/4, пас калид A арзиш пайдо мекунад 4.
Акнун биёед дар бораи он сӯҳбат кунем, ки оё функсияҳо бояд бошанд lookup() и delete() Нишондиҳандаи оддӣ ё ноустуворро ба массиви ҷуфтҳо дар ҷадвали ҳаш истифода баред. Изҳорот мекунад, ки:
Компилятор метавонад оптимизатсияи хондан ва навиштанро ба хотираи глобалӣ ё муштарак интихоб кунад... Ин оптимизатсияҳоро бо истифода аз калимаи калидӣ ғайрифаъол кардан мумкин аст.
volatile: ... ҳама гуна истинод ба ин тағирёбанда ба дастури хондан ё навиштани хотираи воқеӣ тартиб дода мешавад.
Мулоҳизаҳои дурустӣ дархостро талаб намекунанд volatile. Агар риштаи иҷро арзиши кэшро аз амалиёти хондани қаблӣ истифода барад, он гоҳ маълумоти каме кӯҳнашударо истифода мебарад. Аммо ба ҳар ҳол, ин маълумот аз ҳолати дурусти ҷадвали ҳаш дар лаҳзаи муайяни занги ядро ист. Агар шумо бояд маълумоти охиринро истифода баред, шумо метавонед индексро истифода баред volatile, аммо он гоҳ кор каме коҳиш хоҳад ёфт: мувофиқи санҷишҳои ман, ҳангоми нест кардани 32 миллион элемент, суръат аз 500 миллион ҳазф / сония то 450 миллион ҳазф / сония коҳиш ёфт.
Маҳсулнокӣ
Дар санҷиш барои ворид кардани 64 миллион элемент ва нест кардани 32 миллиони онҳо, рақобат байни std::unordered_map ва барои GPU аслан ҷадвали ҳаш вуҷуд надорад:
std::unordered_map 70 мс-ро барои дохил кардан ва нест кардани элементхо ва баъд озод кардани онхо сарф кард unordered_map (аз миллионҳо элемент халос шудан вақти зиёдро талаб мекунад, зеро дар дохили он unordered_map тақсимоти хотираи сершумор анҷом дода мешавад). Рости гап, std:unordered_map маҳдудиятҳои комилан гуногун. Он як риштаи ягонаи CPU-и иҷрошаванда аст, арзишҳои калидҳои ҳама гуна андозаҳоро дастгирӣ мекунад, бо суръати баланди истифодаи хуб кор мекунад ва пас аз несткунии сершумор кори устуворро нишон медиҳад.
Давомнокии ҷадвали хэш барои GPU ва иртиботи байни барномаҳо 984 мс буд. Ин вақти дар хотира ҷойгир кардани ҷадвал ва нест кардани он (тақсим кардани 1 ГБ хотира як маротиба, ки дар CUDA каме вақтро мегирад), ворид кардан ва нест кардани элементҳо ва такрор кардани онҳо дар бар мегирад. Ҳама нусхаҳо ба хотираи корти видеоӣ ва аз он низ ба инобат гирифта мешаванд.
Худи ҷадвали ҳаш барои ба итмом расонидани 271 мс вақт лозим буд. Ин вақти сарфи корти видеоиро барои ворид кардан ва нест кардани элементҳо дар бар мегирад ва вақти нусхабардорӣ ба хотира ва такрори ҷадвали натиҷавиро ба назар намегирад. Агар ҷадвали GPU муддати тӯлонӣ зиндагӣ кунад ё ҷадвали hash пурра дар хотираи корти видео мавҷуд бошад (масалан, барои сохтани ҷадвали hash, ки онро дигар коди GPU истифода хоҳад кард, на протсессори марказӣ), он гоҳ натиҷаи санҷиш мувофиқ аст.
Ҷадвали шудаи барои корти видеоӣ аз ҳисоби қобилияти баланд ва параллелизатсияи фаъол иҷрои баландро нишон медиҳад.
Нобудӣ
Меъмории ҷадвали hash дорои якчанд масъалаҳое мебошад, ки бояд аз онҳо огоҳ бошанд:
- Санҷиши хаттӣ бо кластеркунӣ монеъ мешавад, ки ин боиси он мегардад, ки калидҳо дар ҷадвал камтар аз комил ҷойгир карда шаванд.
- Калидҳо бо истифода аз функсия хориҷ карда намешаванд
deleteва бо мурури замон дастархонро парешон мекунанд.
Дар натиҷа, иҷрои ҷадвали ҳаш метавонад тадриҷан паст шавад, хусусан агар он муддати тӯлонӣ вуҷуд дошта бошад ва дорои дохилкуниҳо ва несткунии сершумор бошад. Яке аз роҳҳои коҳиш додани ин норасоиҳо ин дубора ворид шудан ба ҷадвали нав бо суръати хеле пасти истифода ва филтр кардани калидҳои хориҷшуда ҳангоми бозсозӣ мебошад.
Барои нишон додани масъалаҳои тавсифшуда, ман коди дар боло зикршударо барои сохтани ҷадвал бо 128 миллион элемент истифода мебарам ва то 4 миллион слотро пур кунам (меъёри истифода тақрибан 124). Ин аст ҷадвали натиҷаҳо, ҳар як сатр занги ядрои CUDA барои ворид кардани 0,96 миллион элементи нав ба як ҷадвали хэш мебошад:
Меъёри истифода
Давомнокии воридкунӣ 4 элемент
0,00
11,608448 мс (361,314798 миллион калид/сония)
0,03
11,751424 мс (356,918799 миллион калид/сония)
0,06
11,942592 мс (351,205515 миллион калид/сония)
0,09
12,081120 мс (347,178429 миллион калид/сония)
0,12
12,242560 мс (342,600233 миллион калид/сония)
0,16
12,396448 мс (338,347235 миллион калид/сония)
0,19
12,533024 мс (334,660176 миллион калид/сония)
0,22
12,703328 мс (330,173626 миллион калид/сония)
0,25
12,884512 мс (325,530693 миллион калид/сония)
0,28
13,033472 мс (321,810182 миллион калид/сония)
0,31
13,239296 мс (316,807174 миллион калид/сония)
0,34
13,392448 мс (313,184256 миллион калид/сония)
0,37
13,624000 мс (307,861434 миллион калид/сония)
0,41
13,875520 мс (302,280855 миллион калид/сония)
0,44
14,126528 мс (296,909756 миллион калид/сония)
0,47
14,399328 мс (291,284699 миллион калид/сония)
0,50
14,690304 мс (285,515123 миллион калид/сония)
0,53
15,039136 мс (278,892623 миллион калид/сония)
0,56
15,478656 мс (270,973402 миллион калид/сония)
0,59
15,985664 мс (262,379092 миллион калид/сония)
0,62
16,668673 мс (251,627968 миллион калид/сония)
0,66
17,587200 мс (238,486174 миллион калид/сония)
0,69
18,690048 мс (224,413765 миллион калид/сония)
0,72
20,278816 мс (206,831789 миллион калид/сония)
0,75
22,545408 мс (186,038058 миллион калид/сония)
0,78
26,053312 мс (160,989275 миллион калид/сония)
0,81
31,895008 мс (131,503463 миллион калид/сония)
0,84
42,103294 мс (99,619378 миллион калид/сония)
0,87
61,849056 мс (67,815164 миллион калид/сония)
0,90
105,695999 мс (39,682713 миллион калид/сония)
0,94
240,204636 мс (17,461378 миллион калид/сония)
Баробари зиёд шудани истифодабарй, кор кам мешавад. Ин дар аксари мавридҳо матлуб нест. Агар барнома элементҳоро ба ҷадвал ворид кунад ва сипас онҳоро партояд (масалан, ҳангоми ҳисоб кардани калимаҳо дар китоб), пас ин мушкилот нест. Аммо агар барнома ҷадвали хэш-и дарозмуддатро истифода барад (масалан, дар муҳаррири графикӣ барои нигоҳ доштани қисмҳои холии тасвирҳо, ки корбар зуд-зуд маълумотро ворид ва нест мекунад), пас ин рафтор метавонад мушкил бошад.
Ва чуқурии санҷиши ҷадвали хэшро пас аз 64 миллион ворид чен кард (омили истифода 0,5). Ба ҳисоби миёна умқи 0,4774 буд, бинобар ин аксари калидҳо ё дар ҷои беҳтарини имконпазир ё як слот дуртар аз мавқеи беҳтарин буданд. Чуқурии максималии садодиҳӣ 60 буд.
Пас аз он ман умқи санҷишро дар ҷадвал бо 124 миллион дохил чен кардам (омили истифода 0,97). Дар чуқурии миёна аллакай 10,1757 буд, ва ҳадди - 6474 (!!). Фаъолияти ҳассосии хатӣ дар сатҳи баланди истифода ба таври назаррас коҳиш меёбад.
Беҳтар аст, ки сатҳи истифодаи ин ҷадвали ҳашро паст нигоҳ доред. Аммо он гоҳ мо иҷрои корҳоро аз ҳисоби истеъмоли хотира зиёд мекунем. Хушбахтона, дар мавриди калидҳо ва арзишҳои 32-бит, ин метавонад асоснок карда шавад. Агар дар мисоли дар боло овардашуда, дар ҷадвали дорои 128 миллион элемент, мо коэффитсиенти истифодаи 0,25-ро нигоҳ дорем, мо метавонем дар он на бештар аз 32 миллион элементро ҷойгир кунем ва 96 миллион слотҳои боқимонда гум мешаванд - барои ҳар як ҷуфт 8 байт , 768 МБ хотираи гумшуда.
Лутфан таваҷҷӯҳ намоед, ки сухан дар бораи аз даст додани хотираи корти видео меравад, ки захираи арзишмандтар аз хотираи система аст. Гарчанде ки аксари кортҳои графикии муосири мизи корӣ, ки CUDA-ро дастгирӣ мекунанд, ҳадди аққал 4 ГБ хотира доранд (дар вақти навиштан, NVIDIA 2080 Ti 11 ГБ дорад), ин ҳанӯз ҳам оқилонатарин қарори аз даст додани чунин маблағҳо нест.
Баъдтар ман дар бораи сохтани мизҳои ҳаш барои кортҳои видеоие, ки бо умқи санҷиш мушкилот надоранд ва инчунин роҳҳои истифодаи дубораи слотҳои ҳазфшуда бештар менависам.
Андозаи чуқурии садо
Барои муайян кардани умқи санҷиши калид, мо метавонем хэши калидро (индекси беҳтарини ҷадвали он) аз индекси ҷадвали воқеии он хориҷ кунем:
// get_key_index() -> index of key in hash table
uint32_t probelength = (get_key_index(key) - hash(key)) & (hashtablecapacity-1);
Аз сабаби ҷодугарии рақамҳои дуии дуи комилкунандаи ду ва он, ки иқтидори ҷадвали ҳаш ду ба дараҷаи ду баробар аст, ин равиш ҳатто вақте ки шохиси калидӣ ба аввали ҷадвал интиқол дода мешавад, кор хоҳад кард. Биёед калидеро гирем, ки ба 1 ҳашед, вале ба ковокии 3 гузошта шудааст. Сипас барои ҷадвали дорои иқтидори 4 мо мегирем (3 — 1) & 3, ки ба 2 баробар аст.
хулоса
Агар шумо савол ё шарҳ дошта бошед, лутфан ба ман бо почтаи электронӣ муроҷиат кунед ё мавзӯи нав кушоед.
Ин код зери илҳом аз мақолаҳои олӣ навишта шудааст:
Дар оянда, ман навиштанро дар бораи татбиқи ҷадвали hash барои кортҳои видео идома медиҳам ва иҷрои онҳоро таҳлил мекунам. Нақшаҳои ман занҷирбандӣ, ҳашинг Робин Гуд ва ҳашингҳои кокуро бо истифодаи амалиёти атомӣ дар сохторҳои додаҳо, ки ба GPU мувофиқанд, дар бар мегиранд.
Манбаъ: will.com