
raikhik jaanch

raikhik jaanch computer prograaming mein haish table mein takraav koo hull karane key liye ack yojana haye, detta sanrachanaaen kunji-moolya jode key sangrah koo banaae rakhane aur dee gaee kunji seey judey moolya koo dekhane key liye. iska aavishkaar 1954 mein jeane amdahal, elen aim dwara kiya gayaa thaa. mcgra aur arther saimuel aur pahali baar 1963 mein donald naath dwara vishleshan kiya gayaa.
dwighaat jaanch aur dohri hashing key saath, raikhik jaanch khule sambodhan kaa ack roop haye. inn yojanaon mein, haish table kaa pratyek kaksh ack ekal kunji-moolya jodee koo sangraheet kartaa haye. jaba haish function haish table key ack cell key liye ack naee kunji kaa maanchitran karke ack takkar kaa kaaran banata haye joe pahale seey hii ack anya kunji dwara kabja curr liya gayaa haye, tou raikhik jaanch talika koo nikatatam nimn mukt sthaan key liye khojati haye aur vahaan naee kunji daalati haye. haish function dwara dee gaee sthiti seey kramik roop seey shuru karke, jaba taka kii ack milan kunji yaa ack khaali cell key saath ack cell naheen mill jaataa, taba taka khoj usee tarah seey kii jaati haye.
jaisa kii likhein, "haish table sabse adhik upayog kii jaane vaali gair-tuchchh detta sanrachanaaen hain, aur maanak hardware parr sabse lokpriya karyanvayan raikhik jaanch kaa upayog kartaa haye, joe tez aur saral donon haye."
raikhik jaanch apane sandarbh key achche sthaan key kaaran uchch pradarshan pradaan curr sakati haye, lekin kuchh anya takkar samadhan yojanaon kii tulanaa mein isake haish kaary kii gunavatta key prati adhik samvedansheel haye. yaadrichhik haish function, 5-swatantra haish function, yaa tabulation hashing kaa upayog karke lagu kiye jaane parr prati khoj, sammilan, yaa vilopan mein nirantar apekshit samay lagata haye. achche parinam anya haish karyon jaise kii marmurash key saath bhee praapt kiye jaa sakate hain.
sanchaalan.
raikhik jaanch shabdakosh samasya koo hull karane key liye haish table kaa upayog karane key liye khuli sambodhit yojanaon kaa ack ghatak haye. shabdakosh samasya mein, ack detta sanrachana koo kunji-moolya jode key sangrah koo banaae rakhna chaahiye joe una karyon key adheen haye joe sangrah seey jode daalate hain yaa hataa dete hain yaa joe kissy dee gaee kunji seey judey moolya key liye khoj karate hain.
iss samasya key khule samadhan mein, detta sanrachana ack sarani (haish table) haye jisaki koshikaaen (jaba khaali naheen hoti hain) pratyek ack ekal kunji-moolya jodee koo sangraheet karati hain. haish function kaa upayog pratyek kunji koo usa kaksh mein maanchitrit karane key liye kiya jaataa haye jahan usa kunji koo sangraheet kiya jaanaa chaahiye, aam taur parr chabiyon koo scrambling karna taaki samaan moolyon vaali chabiyon koo talika mein ack dusare key paas naa rakhaa jaae. haish takkar taba hoti haye jaba haish function ack koshika mein ack kunji kaa maanchitra banaata haye joe pahale seey hii ack alag kunji dwara kabja curr liya gayaa haye. raikhik jaanch takraav koo hull karane key liye ack ranneeti haye, naee kunji koo nikatatam khaali kaksh mein rakhkar.
khojo.
ack dee gaee kunji kii khoj key liye, koshikaon kii jaanch kii jaati haye, soochkaank parr koshika seey shuru hoti haye (jahaan haish kaary haye) aur aasann koshikaon taka jaari rahati haye...jaba taka kii ack khaali kaksh yaa ack kaksh naa mill jaae jisaki sangraheet kunji haye.
yadi kunji yukt ack cell paaya jaataa haye, tou khoj usa cell seey moolya lautaati haye. anyatha, yadi ack khaali kaksh paaya jaataa haye, tou kunji talika mein naheen hoe sakati haye, kyonki ise usa kaksh mein kissy bhee baad key kaksh kii vareeyata mein rakhaa gayaa hoga jise abhee taka naheen khoja gayaa haye. iss mamle mein, khoj apane parinam key roop mein lautati haye kii kunji shabdakosh mein maujood naheen haye.
sammilit karein.
talika mein ack kunji-moolya jodee daalane key liye (sambhavatah kissy bhee maujooda jodee koo usee kunji key saath pratisthaapit karane key liye), sammilan algorithm koshikaon key usee anukram kaa anusaran kartaa haye jiska anusaran khoj key liye kiya jaayega, jaba taka kii ack khaali koshika yaa ack koshika kaa pataa naa chaley jiska sangrahit kunji haye.
phir naee kunji-moolya jodee koo usa kaksh mein rakhaa jaataa haye.
yadi sammilit karane seey talika kaa bhaar kaarak (adhiniveshit koshikaon kaa iska ansh) kuchh poorv nirdhaarit seema seey oopar badh jaataa haye, tou poori talika koo ack naee talika dwara pratisthaapit kiya jaa sakata haye, joe ack sthir kaarak dwara badee hoe sakati haye, ack nae haish function key saath, ack gatishil sarani mein. iss seema koo shoonya key karib sthaapit karna aur talika key aakar key liye uchch vikas darr kaa upayog karane seey haish table sanchaalan teji seey hotaa haye, lekin ack aur cumm vikas darr key karib seema moolyon kii tulanaa mein adhik smriti upayog hotaa haye. ack aam vikalp table key aakar koo doguna karna hoga jaba bhaar kaarak 1/2 seey adhik hoe jaayega, jisase bhaar kaarak 1/4 aur 1/2 key beach rahega.
hataa dein.
shabdakosh seey ack kunji-moolya jodee koo hataana bhee sambhav haye. haalaanki, kewal apani koshika koo khaali karke aisaa karna paryaapt naheen haye. yeh anya kunjiyon kii khoj koo prabhaavit karega jinka haish moolya khaali kiye gaye kaksh seey pahale hotaa haye, lekin joe khaali kiye gaye kaksh kii tulanaa mein baad mein ack sthiti mein sangraheet hotey hain. khaali cell una khojon koo galat tareeke seey report karane kaa kaaran banega kii kunji maujood naheen haye.
isake bajaay, jaba ack koshika khaali hoe jaati haye, tou table key nimnalikhit kakshon key madhyam seey aage kii khoj karna aavashyak haye jaba taka kii yaa tou ack aur khaali koshika yaa ack kunji naheen mill jaati haye jise koshika mein sthanantarit kiya jaa sakata haye (yaani, ack kunji jiska haish moolya barabar yaa usase pahale haye). jaba ack khaali kaksh paaya jaataa haye, tou kaksh koo khaali karna surakshit hotaa haye aur hataane kii prakriya samaapt hoe jaati haye. lekin, jaba khoj koo ack kunji milati haye jise cell mein sthanantarit kiya jaa sakata haye, tou yeh iss chaal koo nishpaadit kartaa haye. iska prabhaav baad mein sthanantarit kunji kii khoj mein teji laane kaa haye, lekin yeh ack anya koshika koo bhee khaali curr detaa haye, baad mein usee block mein joe adhiniveshit koshikaon mein hoti haye. ack chala kunji kii khoj usee tarah seey naee khaali koshika key liye jaari rahati haye, jaba taka kii yeh pahale seey hii khaali koshika taka pahunch curr samaapt naheen hoe jaati haye. pahale kii koshikaon mein kunjiyon koo sthanantarit karane kii iss prakriya mein, pratyek kunji kii kewal ack baar jaanch kii jaati haye. isaliye, poori prakriya koo puuraa karane kaa samay hataae gaye kunji vaale adhiniveshit koshikaon key khand kii lambai key samanupati haye, joe anya haish table sanchaalan key chalane key samay seey mell khaata haye.
vaikalpik roop seey, ack aalsi hataane kii ranneeti kaa upayog karna sambhav haye jisamen ack pramukh-moolya jodee koo ack vishesh dhwaj moolya dwara moolya koo pratisthaapit karke hataa diyaa jaataa haye joe ack hataae gaye kunji kaa sanket detaa haye. haalaanki, yeye dhwaj moolya haish table key bhaar kaarak mein yogdan denge. iss ranneeti key saath, sarani seey dhwaj moolyon koo saaf karna aavashyak hoe sakata haye aur sabhi shesh kunji-moolya jode koo phir seey dohrana aavashyak hoe sakata haye jaba sarani kaa ack badaa ansh hataa dee gaee kunjiyon dwara kabja curr liya jaataa haye.
guna.
raikhik jaanch sandarbh kaa achchha sthaan pradaan karati haye, jisake kaaran ise prati operation kuchh uncash memori axes kii aavashyakta hoti haye. isake kaaran, cumm seey madhyam bhaar karakon key liye, yeh bahut uchch pradarshan pradaan curr sakata haye. haalaanki, kuchh anya khuli sambodhit ranneetiyon kii tulanaa mein, iska pradarshan praathamik clustering key kaaran uchch bhaar karakon parr adhik teji seey cumm hoe jaataa haye, ack takkar key liye adhik aas-paas kii takkar kaa kaaran banane kii pravritti. isake alawa, iss vidhi key saath achchha pradarshan praapt karane key liye kuchh anya takraav samadhan yojanaon kii tulanaa mein uchch gunavatta vaale haish kaary kii aavashyakta hoti haye. jaba nimn-gunavatta vaale haish karyon key saath upayog kiya jaataa haye joe input vitaran mein gair-ekroopataon koo samaapt karane mein whiffle rahate hain, tou raikhik jaanch anya khule-patey kii ranneetiyon kii tulanaa mein dheemi hoe sakati haye jaise kii double hashing, joe koshikaon key ack anukram kii jaanch karati haye jiska prithakkaran dusare haish kaary dwara nirdhaarit kiya jaataa haye, yaa dwighaat jaanch, jahaan pratyek charan kaa aakar jaanch anukram key bheetar apani sthiti key aadhar parr bhinn hotaa haye.
vishleshan.
raikhik jaanch kaa upayog karke, shabdakosh sanchaalan koo nirantar apekshit samay mein lagu kiya jaa sakata haye. dusare shabdon mein, sammilit karein, hataaen aur khoj sanchaalan koo oh (1) mein lagu kiya jaa sakata haye, jaba taka kii haish table kaa bhaar kaarak ack seey cumm sthir rahata haye.
adhik vistaar seey, kissy vishesh operation (ack khoj, sammilan, yaa vilopan) kaa samay kabje vaali koshikaon key sannihit block kii lambai key samanupati haye jiss parr operation shuru hotaa haye. yadi sabhi praarambhik koshikaon kii koshikaon key saath ack haish table mein samaan sambhavana haye, tou adhiniveshit koshikaon key ack adhikatam khand mein khoj key praarambhik sthaan koo rakhane kii sambhavana hogi, aur jaba bhee yeh praarambhik sthaan hoga tou samay lagega. isaliye, ack operation key liye apekshit samay kii ganana inn dou shabdon key utpaad key roop mein kii jaa sakati haye, joe talika mein sannihit koshikaon key sabhi adhikatam khandon parr yogit haye. varg khand lambai kaa ack samaan yog ack yaadrichhik haish function key liye apekshit samay seema detaa haye (haish table kii ack vishisht sthiti mein ack yaadrichhik praarambhik sthaan key bajaay), una sabhi blocks koo jodkar joe maujood hoe sakate hain (bajaay una blocks key joe vaastav mein table kii dee gaee sthiti mein maujood hain), aur pratyek sambhaavit block key liye shabd koo iss sambhavana seey gunaa karke kii block vaastav mein kabja curr liya gayaa haye. vaha haye,
iss ghatana koo paribhaashit karate hue kii soochkaank seey shuru honey vaali lambai kii adhiniveshit koshikaon kaa ack adhikatam sannihit khand haye, prati operation apekshit samay haye
iss sootra koo ack saral aavashyak sthiti dwara pratisthaapit karke saral banaaya jaa sakata haye, ghatana joe
cumm seey cumm tatvon mein haish maan hotey hain joe lambai kii koshikaon key ack khand key bheetar hotey hain. iss pratisthaapan key baad, raashi key bheetar moolya abb iss parr nirbhar naheen kartaa haye, aur kaarak baahari yog kii sharton koo radd curr detaa haye. inn saralikaranon seey seema taya hoti haye
lekin chernoff bound key gunak roop seey, jaba bhaar kaarak ack seey door hotaa haye, tou sambhavana haye kii lambai key ack khand mein cumm seey cumm haish moolya hotey hain, joe ack kaary key roop mein teji seey chhota hotaa haye,
iss raashi koo ack sthir swatantra seey bandha huaa haye. ack block mein thheek seey haish kiye gaye moolyon kii sambhavana kaa anuman lagaane key liye chernoff key bajaay halchal key sanniktan kaa upayog karke ack hii vishleshan karna bhee sambhav haye.
load kaarak key sandarbh mein, ack yaadrichhik kunji parr safal khoj karane key liye apekshit samay haye, aur ack asafal khoj (yaa ack naee kunji kaa sammilan) karane key liye apekshit samay haye.
nirantar bhaar karakon key liye, uchch sambhavana key saath, sabse lambe jaanch anukram (talika mein sangraheet sabhi kunjiyon key liye jaanch anukramon mein seey) mein laghuganak kii lambai hoti haye.
haish function kaa chayan.
kyonki raikhik jaanch asman roop seey vitarit haish moolyon key prati vishesh roop seey samvedansheel haye, isaliye ise uchch gunavatta vaale haish function key saath jodana mahatvapurna haye joe aisee aniyamitataon kaa utpaadan naheen kartaa haye.
uparokt vishleshan yeh maanata haye kii pratyek kunji kaa haish ack yaadrichhik sankhya haye joe anya sabhi kunjiyon key haish seey swatantra haye. hashing key adhikansh anuprayogon key liye yeh dhaarana avaastavik haye.
haalaanki, yaadrichhik yaa chhadm haish moolyon kaa upayog taba kiya jaa sakata haye jaba vastuon koo unaki pehchaan key bajaay unake moolya key anusaar haish kiya jaataa haye. udaaharan key liye, yeh jaava sangrah dhaanche key identity hashmap varg dwara raikhik jaanch kaa upayog karke kiya jaataa haye.
haish moolya joe yeh varg pratyek vastu key saath jodata haye, iska pehchaan hashcode, kissy vastu key jivankal key liye nishchit rahane kii guaranti haye lekin anyatha manmana haye. kyonki identity hashcode kaa nirmaan prati vastu kewal ack baar kiya jaataa haye, aur ise vastu key patey yaa moolya seey sambandhit honey kii aavashyakta naheen haye, isake nirmaan mein yaadrichhik yaa chhadm sankhya generator koo coll karane jaisi dheemi ganana shamil hoe sakati haye. udaaharan key liye, jaava 8 inn moolyon key nirmaan key liye ack zorshift sudorandum sankhya generator kaa upayog kartaa haye.
hashing key adhikansh anuprayogon key liye, pratyek moolya key liye haish function kii ganana karna aavashyak haye jaba bhee ise haish kiya jaataa haye, bajaay ack baar jaba isaki vastu banaai jaati haye. aise anuprayogon mein, yaadrichhik yaa chhadm sankhya kaa upayog haish moolyon key roop mein naheen kiya jaa sakata haye, kyonki taba ack hii moolya vaali vibhinn vastuon mein alag-alag haish honge. aur gupt lipi haish kaary (joe vaastav mein yaadrichhik karyon seey computational roop seey aprabhedya honey key liye design kiye gaye hain) aamtaur parr haish table mein upayog karane key liye bahut dheeme hotey hain. isake bajaay, haish karyon key nirmaan key liye anya tareeke taiyar kiye gaye hain. yeye vidhiyaan haish function kii jaldi seey ganana karati hain, aur raikhik jaanch key saath achchi tarah seey kaam karane key liye saabit hoe sakati hain. vishesh roop seey, raikhik jaanch kaa vishleshan-swatantra hashing key dhaanche seey kiya gayaa haye, haish karyon kaa ack varg joe ack chhote yaadrichhik beej seey aarambh kiya jaataa haye aur joe kissy bhee-tupple kii vishisht kunji koo kissy bhee-tupple key soochkaank key liye maanchitrit karane kii samaan roop seey sambhavana rakhate hain. iss mapdand koo haish function kii gunavatta key maap key roop mein socha jaa sakata haih jitna badaa hoga, haish function kii ganana karane mein utanaa hii adhik samay lagega lekin yeh poori tarah seey yaadrichhik karyon key samaan hii vyavhaar karega.
raikhik jaanch key liye, 5-swatantrata prati sanchaalan nirantar apekshit samay kii guaranti dene key liye paryaapt haye,
jabaki kuchh 4-swatantra haish kaary buri tarah seey pradarshan karate hain, prati operation laghuganak samay taka lete hain.
uchch gunavatta aur vyaavhaarik gati donon key saath haish karyon key nirmaan kii ack anya vidhi haye tabulation hashing. iss vidhi mein, ack kunji key liye haish moolya kii ganana yaadrichhik sankhyaon kii talika mein (pratyek bite sthiti key liye ack alag talika key saath) ack soochkaank key roop mein kunji key pratyek bite kaa upayog karke kii jaati haye. una talika koshikaon seey sankhyaaen phir ack bitwise exclusive yaa operation dwara sanyukt kii jaati hain. iss tarah seey nirmit haish kaary kewal 3-swatantra hain. phir bhee, inn haish karyon kaa upayog karke raikhik jaanch prati operation nirantar apekshit samay letee haye. 5-swatantra haish kaary utpann karane key liye saaraneekaran hashing aur maanak vidhiyaan donon una kunjiyon taka seemit hain jinamen bits kii ack nishchit sankhya hoti haye. string yaa anya prakaar kii charr-lambai kii kunjiyon koo sambhaalane key liye, ack saral saarvbhaumik hashing takneek kii rachana karna sambhav haye joe madhyavarti moolyon kii kunjiyon koo mapp karati haye aur ack uchch gunavatta (5-swatantra yaa saaraneekaran) haish function joe madhyavarti moolyon koo haish table soochkaankon key liye mapp karati haye.
ack prayogaatmak tulanaa mein, richar aitt all. paaya gayaa kii haish karyon kaa bahu-sthanantaran parivaar (sootra _ 3 key roop mein paribhaashit) "sabhi hashing yojanaon key saath ekikrit honey parr sabse tez haish kaary thaa, i.ee., uchchatam thruput kaa utpaadan kartaa haye aur achchi gunavatta kaa bhee utpaadan kartaa haye jabaki tabulation hashing ney "sabse cumm thruput" kaa utpaadan kiya.
way bataate hain kii pratyek table look-upp key liye kaee chakron kii aavashyakta hoti haye, joe saral ankganitiya sanchaalan kii tulanaa mein adhik mahange hotey hain. unhone yeh bhee paaya kii bamuresha koo saaraneekaran hashing seey behtar paaya gayaah "multy aur bamure dwara pradaan kiye gaye parinamon kaa adhyayan karke, humm sochate hain kii saaraneekaran dwara (...) vyavhaar mein cumm aakarshak haye.
itihas.
ack sahayogi sarani kaa vichaar joe detta koo usake patey key bajaay usake moolya seey praapt karane kii anumati detaa haye, 1940 key dashak key madhya mein konrad zoos aur vanever busch key kaam mein, lekin haish table kaa varnan 1953 taka naheen kiya gayaa thaa, ack aaee. bee. aim. gyaapan mein hains peater luhn dwara. luhn ney raikhik jaanch key bajaay ack alag takraav samadhan vidhi, chain kaa upayog kiya.
 raikhik jaanch key praarambhik itihas koo sankshep mein prastut kartaa haye. yeh pahali khuli sambodhan vidhi thee, aur mool roop seey khuli sambodhan kaa paryaay thee. noth key anusaar, iska upayog pahali baar jeane amdahal, elen aim dwara kiya gayaa thaa. 1954 mein aaee. bee. aim. 701 computer key liye ack assembler prograam mein mcgra (nee boheme) aur arther saimuel. raikhik jaanch kaa pahala prakaashit vivaran haye, joe saimuel, amdal aur bohem koo bhee shreya detaa haye, lekin yeh kahata haye kii "pranali itani swabhavik haye, kii isaki kalpana usa samay seey pahale yaa baad mein dusaron dwara swatantra roop seey kii gaee hogi. iss vidhi kaa ack aur praarambhik prakaashan 1958 mein soviyat shodhkarta aur ray ershov dwara kiya gayaa thaa.
raikhik jaanch kaa pahala saiddhaantik vishleshan, joe darshaata haye kii yeh yaadrichhik haish karyon key saath prati operation nirantar apekshit samay letaa haye, noth dwara diyaa gayaa thaa. sejwick ney noth key kaam koo "algorithm key vishleshan mein ack meal kaa patthar" kahaa haye. baad key mahatvapurna vikaason mein chalane key samay key sambhaavyata vitaran kaa adhik vistrit vishleshan shamil haye, aur yeh pramaan kii raikhik jaanch pahale key vishleshan dwara griheet aadarsh yaadrichhik karyon key bajaay vyaavhaarik roop seey upayog karane yogya haish karyon key saath prati operation nirantar samay mein chalati haye.

