32 (708)

MlOMP jo i<X>'fKJdsVt

Eu

Metoda składania Ml:

W metodzie tej klucz dzieli się na kilka równych części i ewentualną resrię. które następnie składa się razerr i czasem przekształca. Istnieją csvre ,podmetody*. W obyawu pocł metod ach rozważać będziemy klu~ ‘123455789’.

Składanie z przesuwaniem. Klucz dzielimy na kilka częśd i łączymy jakąś operacją, np. dodawaniem. Przy skłaoaniu z przesileniem części te zapisujemy jedna pod drugą. Podzielmy nasz ki ucz na trzy częśd i dodajmy je do siebie:

123

455

+    789

1368, zatem naszym kluczem jest 1368 mod TSize. Można oczywiście przeprowadzić podział na pięć częśd: -(12+34+55+78+3) mcd TSize. Bitową (i tekstową) wersję składania z przesuwaniem otrzymujemy stosuje.: zamiast dodawania funkcję XOR_

Składanie brzegów. To samo co z przesuwaniem, ALE patrzymy na klucz tak, jakby byt zapisany na kartce papieru, który został zło zony wzdłuz brzegów między częściami klucza. Jeżeli nasz paprer z naszym kluczem, zagniemy mięczy 123 i 456 oraz między 456 i 789, to otrzymamy ciągi: 123, 654 i 789. No i oczywiście np. dodajemy i module: (123 ^ 654 + 789) mod TSae = 1566 mod TSize.

runkcia .środek kwadratu* f 11 f4];

Klucz podnoszony jest do kwadratu, 3 środkowa część wyniku wykorzystywana jest jako adres. Cały klucz bterze ucz^ał w tworzeniu khjczz, więc jact większe prawccgodobreńsiwo, że różne klucze będą dawać rózrć adresy. Np. {3121)² - 9740641, wyęc dla 1 OCO-elemerrtowej tablicy b(3l21) = 406. W praktyce operuje się na bitowych reprezentacjach liczb, a rozmiar tablicy jest potęcą 2. Jezeii zaozymy rozmiar naszej tabiicy 1024 = 2¹⁰, to (3121)_d = (100101001010000101100001). h(3121; = (oToi000010j2 = (322)*. ^r)

Uogornrenre/drICzecna na różne systemy iiczDowe: h(x) - [X² / cj mod 5 , a - poestawa systemu,

c - wiem o nim tyle, ze gdy k = zakres kluczy, to k² *■ a • c, dla pewnego c (hmm...)

VVvciranie (1l:

Do obliczania adresu bierzemy jedynie część lub części klucza. Np. ooy x = '12-3456-789' możemy uzyc uzietechi osiaundi cyfr h(x) = 6789 mod TSize lub pierwszych i osratnicn cwóch; h(x) = 1289 mod TSize. Uwaga na sens! Gdy np. adresujemy bazę legitymacji studenckich, odzie wszystkie zaczynają się od cyfr *122', to cyfry' ts możemy spokojnie wydać.

Zamiana podstawy f 11;

Klucz przekształcany jest do postad zapisanej w systemie o innej podstawie liczenia, np. dziewiankowym. No i oczywiśde mod TSize.

^v43. Omówić metody przezwyciężania kolizji w metodzie mieszą ni a zamkniętego. Jakk* są wady i zalety wyszukiwania i wstawiania mieszającego.

Liniowa metoda orzezwvciezania kolizji Ml. T2I [41:

Dla prawie wszystkich funkcji mieszających tej samej pozy di będzie przypisany więcej niż jeden klucz. h/x) = (ho(x) + 0 mod a , a = TSize

w tym przypadku tworzą się tzw. wiązki, czyli grupowania elementów razem - jeden za drugim. Wpływa to ujemnie na efektywność wykonywania operacji. Próba eliminacji grupowania to:

hj(x) = (ha(x) + krok ■ i) mod a •, krok względnie pierwszy za.