.


:




:

































 

 

 

 





 

( ) N 0 N-1. i, kl (hash - , ):

 

i = H (kl) (5.9)

 

H - (-) ,

 

0 £ H(kl) £ N-1 (5.10)

 

, :

 

kl1 ¹ kl2 ==> H(kl1) ¹ H(kl2) (5.11)

 

. , :

kl1 ¹ kl2 && H(kl1) = H(kl2) (5.12)

 

 

(5.9) ( ), 1:

D = 1 (5.13)

, , (5.11). , , . , . . .

 

5.3.

 

x - (x = 0 255), t[i] - , 256, 0 255.

: : i = H(x) = x;

x = t[i] = t[H(x)] = t[x]

 

/* : 0, 1,..., 255 */

char x, t[256] = { 45, 19,..., 13 };

...

x = t[x]; /* x */

 

5.4. f(x) (x = 2, 2.01,..., 2.99)

x - , t[i] = f(x), 100, 0..99.

: : i = H(x) = 100*(x-2);

f(x) = t[i] = t[H(x)] = t[100*(x-2)].

/* f(x) (x = 2, 2.01,..., 2.99): */

/* f(2), f(2.01),..., f(2.99) */

float t[100] = { 3.51, 3.47,..., -0.74 };

 

 

: ( ), , -.

5.5. (. 5.7)

- ; . 5.7 - ; . 5.7 - . i = H(kl), (), (i 1 N) , , (. 5.7 ). , .

 

)   ) : , , , , ,  
kl H(kl)   )  
       
       
         
       
       
         
       
       
...        

. 5.7.

 

, (. 5.8, 5.9).

 

5.8. t

 

/* */

#define N... /* */

#define SVOB... /* */

_ t[N]; /* */

int ksv; /* - */

...

/* */

int i;

...

ksv = N-1; /* */

for (i=0; i<N; i++) t[i] = SVOB;

 

5.9. kl t ( 1)

_ kl; /* */

int i; /* */

/* kl t */

i = H(kl); /* H - */

while (t[i]!=kl && t[i]!=SVOB)

if (i < N-1) i++; else i=0; /* i = (i+1) % N; */

if (t[i]!= kl) /* */

{ /* kl t */

if (ksv==0) ... /* */

else /* */

{ ksv--; /* SVOB */

t[i] = kl; /* */

}

} else ... /* t[i] == kl */

"" , , . , .

"" . , . 5.7 , , . , , . . . (. 5.10). . 5.9 .

 

5.10. t[i] t, 5.9

int j; /* - */

int i; /* */

int r; /* H(t[i]) */

do /* t[i] */

{ j=i; t[j]=SVOB;

/* , */

do

{ if (i<N-1) i++; else i=0;

if (t[i]!=SVOB) r=H(t[i]);

} while (t[i]!= SVOB && /* r j i: */

(j<r && r<=i || i<j && (r<=i || j<r)));

if (t[i]!= SVOB) t[j] = t[i]; /* */

} while (t[i]!= SVOB);

ksv++; /* - */

"", , - . , . . . : N .

: , , !

( . 5.9) 0 N-1

D = (2 - s) / (2 - 2*s) ( s £ 0.85) (5.14)

s = m / N - ,

N - ,

m - ( ).

, s=0.8 D =3, . . 80% , , : 100 100000, ! .

2-4 ( ).

- .

(5.10) , , . :

H(kl) = ( kl) % N

N H(kl) , , - , : XA, XB, XC. N ( 1). ( ). , 2 ( , ^).

, i=H(kl) , kl. . ( ).

, (5.13), . . . , . - . - ( , ). i0, i1, i2,...,

i0 = H(kl),

ik = (i0+G(k)) % N k>0, (5.15)

H(kl) - ,

G(k) - .

G(k) = d*k, G k. () d ( . 5.9 d=1). - .

, , G(k) = k2.

G(k+1) = (k+1)2 = k2+2*k+1 = G(k)+d(k),

d(k) = 2*k+1;

: d(k+1) = 2*(k+1)+1 = d(k)+2.

( . 5.9)

i = i + d; if(i >= N) i = i - N; d = d + 2;

i = H(kl); d=1;

- , ( N - ), , , .

G H kl , .

 





:


: 2016-12-18; !; : 549 |


:

:

: , , , , .
==> ...

782 - | 716 -


© 2015-2024 lektsii.org - -

: 0.03 .