33 (709)

. Mieszanie podwójne fH. f2L [4]:

P“>.rUOV

Tutaj yrystępują dwie funkcje mieszające: h₀(x) i h'(x). h'(x) - oznaczane przez dr Czecha jako krok(x), to funkq'a, która winna spełniać nasi warunki:

U j~ (v

1.    h‘(x) > 0    -

2.    h'(x) względnie pierwsza z a = TS/ze    l

3.    rtistotnie różna od h(x).

Jeżeli a to Ib. pierwsza, to dowolna liczba z zakresu 1..a - 1 może być wybrana jako krok, gdyż zawsze a i. ‘(x) są wzgIędnie pierwsze.

Jeżeli a = 2^m, to h'(x) - Ib. nieparzysta z zakresu    1.

Metocs kwadratowa f 11 [4]:

fi/*; = (/ioW + c/ + cy) mod a , stałe c odpowiednio dobrać = {h₀(x) ±F).

Tu mamy do czynienia z grupowaniem wtórnym, czyli z tym, że klucze, którym przydzielone zostały te same adresy i tak mają ten sam ciąg <pozyq\ do sprawdzenia, aie efekt ten jest mniej szkodliwy niż grupowanie w wiązki'

Generator liczb pseudo losowych [11;

h/x) = (ho(x) + o) mod a j r, - Ib. losowa z przędz. t..a - 1

Należy tu zwrócić uwagę, by podczas szukania i wstawiania inicjować generator Tą samą włością - aąę liczb' pseudolosowych musi się powtórzyć! Więc piszemy swój 'Masny generator lub inicjujemy generator z góry ustalona, wartością. Potrafi to np. funkqa srand(inł) w języku C.

A

Podsumowanie wyszukiwania i wstawiania zamkniętego ^l:

zalety: ziozoność rzędu 1 z zastosowaniem nadmiaru; E^dła wstaw, wyszukaj funkcją c, a nie n [c = wsp. zapełnienia tabłicy = /c / (a * 1), k - Ib. kluczy w tablicy); nie za tezy od rąerfren; rt ab i I cy? *?{

wady: nadmiar, by uniknąć zl. liniowej (gdy tabi. wypełniona > 80%, złożoność zbliża się do liniowej); rozmiar tablicy trzeba znać przed rozpoczęciem kompilaqt; w tablicy mieszającej usuwanie kluczy nie przyspiesza wyszukiwania.

Mieszania zamkniętego nie stosuje się. gdy liczba kluczy jest zmienna w szerokich granicach.

44. Określić złożOwCsini CrtmCZ-arrk>Vy*ą mieszania zamkniętego. Jak należy dobrać objętość tablicy mieszającej?

W

\

\ , x c K pojawia się z jednakowym prawdopodobieństwem (K - zb. wszystkich wartości kluczy)

2.    dana tablica, w środku już k kluczy

3.    funkcje mieszające sa_v idealne (patrz pyt. 42), p(h(x) = /) = 1 / a .    /? dowolne, a - rozmiar tablicy

liniowe funkcje mieszaja.ee nie sa. idealne !!

Średnia liczba orób potrzebnych do wprowadzenia k +1 klucza do tablicy Minimalna Ib. prób = 1. max Ib. prób = k + 1 3 _ y

p, -- za I - szym razem trafiamy w wolne miejsce

k a - k ^ a a-1

P.

k k-1 a a-t

za II - gim razem trafiamy

k -* / +■ 2 a — k 3 - i + 2 a - / +1

trafiamy w wolne miejsce za / - tym razem

współczynnik zapełnienia tablicy: a = k/ (a + 1) , a + 1— rozmiar tablicy powiększonej