Cili është ndryshimi midis një grupi dhe një tabele hash në një gjuhë programimi?


përgjigje 1:

Tabelat e hash përdorin vargje. Vargjet kanë një pronë të rëndësishme për hashing: Mund t'i qaseni secilit element në kohë të vazhdueshme nëse e dini indeksin e tij.

Ju mund të përdorni vargje për kova. Supozoni se doni të llogaritni sa shkronja janë në tekst, për shembull për të hartuar diçka si kodi Morse. Ju krijoni një grup me 26 shënime (për alfabetin e thjeshtë Romak pa theks). Kurdo që të shihni një letër, llogaritni indeksin dhe shkoni në atë hyrje në grup.

Tabelat e hashit e shtrijnë këtë për çelësat e çdo gjatësi. Ju llogaritni një hash të çelësit dhe shkoni në atë indeks. Problemi është kur shumë çelësa kanë të njëjtin hash. Ekzistojnë disa mënyra për t'u marrë me të, disa prej të cilave shfuqizojnë qëllimin e hash (por janë të lehtë për t’u zbatuar). Disa prej tyre nuk e mbajnë pronën me kohë konstante, të paktën mesatarisht.

Gjëja më e mirë që kam parë është rehashja e shtesave, në të cilën Gonnet dhe Munroe janë vërtetuar se kanë pasur një mesatare prej pak më shumë se 4 hite me një faktor ngarkese 50%, pavarësisht nga madhësia e tabelës së hashit. Sidoqoftë, kjo kërkon përdorimin e numrave kryesorë, dhe kjo e bën të vështirë implementimin. Duhet të gjesh numrat kryesorë disi. Për fat të mirë, tabelat e hash nuk bëhen aq të mëdha sa që bëhet qesharake.