MateClar
← Capitol

Manual · pagina 93

Exercițiul 12 · O funcție de dispersie

În securitatea informatică, o funcție de dispersie („hash”) simplificată, h:{0,1,…,P−1}→h : \{0, 1, \dots, P - 1\} \to{} {0,1,…,M−1}\{0, 1, \dots, M - 1\}, distribuie chei de date în „containere” de memorie („buckets”). Pentru a evita irosirea memoriei, un inginer dorește ca funcția hh să fie surjectivă, astfel încât fiecare container să poată fi utilizat. Considerând funcția h:{0,1,…,11}→{0,1,2,3}h : \{0, 1, \dots, 11\} \to \{0, 1, 2, 3\}, h(x)=(3x+2) (mod 4)h(x) = (3x + 2) \,(\mathrm{mod}\ 4), justifică dacă funcția hh este surjectivă. În caz afirmativ, determină câte suprapuneri (chei diferite care merg în același container) există pentru fiecare element din codomeniu.

O funcție de dispersie („hash”) distribuie chei de date în „containere” de memorie; inginerul dorește ca ea să fie surjectivă, ca fiecare container să poată fi utilizat. Considerând funcția h:{0,1,…,11}→{0,1,2,3}h : \{0, 1, \dots, 11\} \to \{0, 1, 2, 3\}, h(x)=(3x+2) (mod 4)h(x) = (3x + 2) \,(\mathrm{mod}\ 4), justifică dacă funcția hh este surjectivă. În caz afirmativ, determină câte suprapuneri (chei diferite care merg în același container) există pentru fiecare element din codomeniu.

Calculează h(0)h(0), h(1)h(1), h(2)h(2), h(3)h(3). Apoi compară h(x+4)h(x + 4) cu h(x)h(x).

  1. 1. Ce face funcția

    Cheile sunt numerele 0,1,…,110, 1, \dots, 11, iar containerele sunt 0,1,2,30, 1, 2, 3. Cheia xx merge în containerul h(x)h(x), restul împărțirii lui 3x+23x + 2 la 44 (ca la mod 3\mathrm{mod}\ 3 din manual, p. 92).

    De exemplu, h(0)h(0) este restul lui 22 la 44, adică 22; h(1)h(1) este restul lui 5=1⋅4+15 = 1 \cdot 4 + 1, adică 11.

    Verifică-te

    Cât este h(2)h(2)?

  2. 2. Este hh surjectivă?

    Mai calculăm h(3)h(3): 3⋅3+2=11=2⋅4+33 \cdot 3 + 2 = 11 = 2 \cdot 4 + 3, deci h(3)=3h(3) = 3. Așadar cheile 0,1,2,30, 1, 2, 3 merg în containerele 2,1,0,32, 1, 0, 3.

    Verifică-te

    Ce poți spune despre surjectivitatea lui hh?

  3. 3. Câte chei în fiecare container

    Comparăm cheile xx și x+4x + 4: 3(x+4)+2=(3x+2)+123(x + 4) + 2 = (3x + 2) + 12, iar 1212 se împarte exact la 44. Deci au același rest: h(x+4)=h(x)h(x + 4) = h(x). Valorile se repetă din 44 în 44.
    cheile
    containerele
    hh
    00
    11
    22
    33
    44
    55
    66
    77
    00
    11
    22
    33

    Cheile 00–77: cheile 44–77 repetă drumurile cheilor 00–33. Cheile 88–1111 le repetă încă o dată.

    Verifică-te

    Câte chei ajung în containerul 00?
    containercheile
    002, 6, 102,\ 6,\ 10
    111, 5, 91,\ 5,\ 9
    220, 4, 80,\ 4,\ 8
    333, 7, 113,\ 7,\ 11
    Cheile se distribuie egal: 12:4=312 : 4 = 3 chei în fiecare container. Cele trei chei dintr-un container se suprapun: în containerul 00, de exemplu, se suprapun 22, 66 și 1010 (perechile {2,6}\{2, 6\}, {2,10}\{2, 10\}, {6,10}\{6, 10\}, tot 33).
Răspuns

hh este surjectivă: h(2)=0h(2) = 0, h(1)=1h(1) = 1, h(0)=2h(0) = 2, h(3)=3h(3) = 3.

Cum h(x+4)=h(x)h(x + 4) = h(x), fiecare container primește exact 33 chei, care se suprapun: {2,6,10}\{2, 6, 10\}, {1,5,9}\{1, 5, 9\}, {0,4,8}\{0, 4, 8\}, {3,7,11}\{3, 7, 11\} pentru containerele 0,1,2,30, 1, 2, 3.