( ) 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 , .