Red de conocimiento informático - Aprendizaje de código fuente - Pascal de clasificación de hash de puntero

Pascal de clasificación de hash de puntero

Tabla hash

El método de búsqueda mencionado anteriormente se basa en la comparación y la eficiencia de la búsqueda depende del número de comparaciones. De hecho, la esperanza de búsqueda ideal se puede obtener en un solo acceso. sin comparación Para que se busque el registro, se debe establecer una cierta correspondencia f entre la ubicación de almacenamiento del registro y su palabra clave. De esta manera, al buscar k, solo necesitamos encontrar la imagen f (k) del. valor dado k basado en esta correspondencia f. Esta correspondencia f se llama función hash. La tabla creada en base a esta idea se llama tabla hash (también llamada tabla hash). Las tablas hash son de fácil acceso pero propensas a colisiones durante el almacenamiento: es decir, diferentes palabras clave pueden corresponder a la misma dirección hash. La clave es cómo determinar la función hash y resolver conflictos.

1. Método de construcción de la función hash

Método de direccionamiento directo: H(k)=k

o H(k)=a*k+b ( Función lineal)

Por ejemplo: tabla de estadísticas de población

Dirección

1

2

3< / p>

...

100

Edad

1

2

3

p>

...

100

Número de personas

67

3533

244

...

4

Método de análisis numérico: tome varios dígitos de la palabra clave para formar una dirección hash

Por ejemplo: la palabra clave es la siguiente: si la longitud de la tabla hash es 100, los dos números decimales del medio se pueden utilizar como dirección hash.

81346532

81372242

81387422

81301367

81322817

81338967 p>

81354157

81368537

Método de cuadrar el medio: después de elevar al cuadrado la palabra clave, tome los pocos dígitos del medio para formar la dirección hash

Método de plegado: el número de clave se divide en varias partes con el mismo número de dígitos (el número de dígitos en la última parte puede ser diferente) y luego la suma de superposición de las partes (realización) se toma como dirección hash.

Método de división con resto: toma el resto obtenido después de dividir la palabra clave por un número p no mayor que la longitud de la tabla m como dirección hash.

H(k)=k

mod

p

p<=m

Método de números aleatorios :H(k)=aleatorio(k).

2. Método de manejo de conflictos

Supongamos que la dirección establecida es 0..n-1 y la dirección hash obtenida de la palabra clave es j (0<=j<= n- Ya existe un registro en la ubicación de 1), y manejar el conflicto es encontrar otra dirección hash "vacía" para el registro de esta palabra clave. Durante el procesamiento, se puede obtener una secuencia de direcciones Hi

i=1, 2,...k

0<=Hi<=n-1), es decir, si If otra dirección hash H1 obtenida aún entra en conflicto, luego busque la siguiente dirección H2. Si todavía hay un conflicto, busque H3... ¿Cómo llegar Hola?

Método de direccionamiento abierto: Hi=(H(k)+di)

mod

m

(H(k) es Función hash; m es la longitud de la tabla hash; di es la secuencia incremental)

Cuando di=1, 2, 3,...

m-1

se llama sondeo lineal y luego hash.

Cuando di=12, -12, 22, -22, 32, -32,..., k2, -k2, se llama detección secundaria y luego hash.

Cuando di=random(m), se denomina secuencia de detección pseudoaleatoria.

Ejemplo: Las claves de la tabla hash con longitud 11 son 17, 60, 29 respectivamente, y la función hash es H(k)=k

mod

11, la palabra clave del cuarto registro es 38 y las direcciones agregadas a la tabla hash según el método anterior son 8, 4 y 3 (número aleatorio = 9).

Método de repetición: Hi=RHi(key)

i=1,2,...,k, donde RHi son funciones hash diferentes.

Método de dirección en cadena: este método es muy similar a la clasificación por base. Los valores de palabras clave de la misma dirección se vinculan en la lista vinculada correspondiente.

Establezca un método de área de bienestar público: configure otra tabla de desbordamiento Independientemente de la dirección hash obtenida, una vez que ocurre un conflicto, la tabla de desbordamiento se completará.

3. Buscar en tabla hash

Ejemplo: el siguiente conjunto de palabras clave se calcula según la función hash H(k)=k

mod

La tabla hash a[0..15] obtenida por 13 y el procesamiento de colisiones de detección lineal:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

14

01

68

27

55

19

20

p>

84

79

23

11

10

Cuándo se da el valor k = 84, luego compárelo primero con a [6] y luego compárelo con a [7] y a [8]. El resultado es a [8] = 84 y la búsqueda es exitosa.

Cuando el valor dado k = 38, primero se compara con a[12] y luego con a[13]. Dado que a[13] no existe, la búsqueda no tiene éxito y el resultado. La palabra clave no existe en la tabla.

5.5

Encontrar el k-ésimo elemento pequeño

Encontrar el k-ésimo elemento pequeño significa encontrar el k-ésimo elemento pequeño entre n elementos (no ordenados). El método es el mismo que el de clasificación rápida, utilizando recursividad.

El programa es el siguiente:

program

kspv;

const

n=7;

tipo

arr=matriz[1..n]

de

entero;

var

b:arr;

i,k:entero;

función

p(s,t:entero):entero;

var

i,j,t1,x:integer;

comenzar

i:=s;j:=t;x: =b[ i];

repetir

mientras

(b[j]>=x)

y

(j>i)

hacer

j:=j-1;

si

j>i

luego

comenzar

t1:=b[i];

b[i]:=b[j];b[j ]:= t1;fin;

mientras

(b[i]<=x)

y

(i

hacer

i:=i+1;

si

i

entonces

comienzo

t1:=b[j];b[j]:=b[i];b[i]:=t1;

fin

hasta

i=j;

b[i]:=x;

p:=i;

end ;

función

find(s,t,k:integer):integer;

var

p1,q :entero;

comenzar

si

s=t

entonces

buscar:=b[s ]

otro

comenzar

p1:=p(s,t);

q:=p1-s+1;

si

k<=q

entonces

buscar:=buscar(s,p1,k)

else

buscar:=buscar(p1+1,t,k-q);

fin;

fin;

comenzar

escribir('entrada

datos:');

para

i:=1

para

n

hacer

read(b[i]);readln;

escribir('entrada

k: ');leer(k);

escribir('salida

datos:');

escribir('kthsmall:=',buscar (1, n,k));

fin.