Kāda ir atšķirība starp masīvu un hash tabulu programmēšanas valodā?


Atbilde 1:

Hash tabulās tiek izmantoti masīvi. Masīviem ir svarīga hashinga īpašība: jūs varat piekļūt jebkuram elementam nemainīgā laikā, ja zināt tā indeksu.

Kausiem varat izmantot masīvus. Pieņemsim, ka jūs gribējāt, lai jūs saskaitītu, cik daudz no katra teksta burtiem, piemēram, ir, lai izstrādātu kaut ko līdzīgu Morzes kodam. Jūs izveidojat masīvu ar 26 ierakstiem (vienkāršam bezakcentam romiešu alfabētam). Ikreiz, kad redzat burtu, jūs aprēķināt indeksu un doties uz šo masīva ierakstu.

Sajaukšanās tabulas to pagarina patvaļīgi gariem taustiņiem. Jūs aprēķināt atslēgas maiņu un pāriet uz šo indeksu. Problēma ir tad, ja vairākiem taustiņiem ir viena un tā pati hash. Ir dažādi veidi, kā to risināt, un daži no tiem sabojā hash mērķi (bet ir viegli īstenojami). Daži no viņiem vismaz vidēji uztur nemainīgu laika īpašību.

Labākais, ko esmu redzējis, ir atkārtotās pievienošanas funkcija, kurai, ja atmiņa kalpo pirms gadu desmitiem, Gonnet un Munroe pierādīja, ka vidēji ir nedaudz vairāk nekā 4 piekļuves ar 50% slodzes koeficientu, neatkarīgi no tā lieluma. hash tabula. Tomēr tam ir nepieciešams izmantot sākotnējos skaitļus, un tas padara to par sarežģītu ieviešanu. Kaut kā ir jāatrod primārie skaitļi. Par laimi, hash tabulas nav tik lielas, ka tās kļūst smieklīgas.