Existen muchas formas
en las que un programa puede almacenar datos: Puede utilizar Arrays, listas
enlazadas de punteros, arboles binarios, etc... El tipo de estructura de datos
utilizada dependerá de la aplicación y del número y tamaño de los datos. En
cualquier caso, será necesario acceder a los datos, para buscar información, y
en algunos casos será conveniente ordenarlos.
Aquellos que quieran estudiar las técnicas de almacenamiento y búsqueda de datos
con un poco más de profundidad de la vista en clase, pueden consultar unos
apuntes de José Mañas, profesor de Fundamentos de Programación en Teleco de
Madrid:
Técnicas de almacenamiento y búsqueda
Unas de las técnicas explicadas en estos apuntes son las técnicas Hash. Un
ejemplo de esta técnica para un fichero diccionario es el siguiente:
HASH.ZIP.
Es importante tener en cuenta como aumenta el tiempo necesario para buscar u
ordenar datos, en función del número de datos. El análisis de algoritmos estudia
este problema. Quien esté interesado en este tema puede consultar unos apuntes
de José Mañas, profesor de Fundamentos de Programación en Teleco de Madrid:
Análisis de algoritmos: complejidad
Un ejemplo es el
estudio de la complejidad de los algoritmos de ordenación,
que analiza algunos algoritmos de ordenación de arrays.
Los datos que se manejan suelen ser estructuras más o menos ricas en información, de la cual nos interesa un sólo campo, k, usualmente llamado "clave":
TYPE clave= ...;
TYPE Elemento= RECORD
k: clave;
... otros campos ...
END;
Y las funciones que nos interesan son
PROCEDURE Inserta (E: Elemento);
FUNCTION Busca (K: clave): Elemento;
PROCEDURE Elimina (K: clave);
que respectivamente añaden nuevos elementos al almacén, recuperan un elemento dada su clave, y eliminan del almacén al elemento que responde a una cierta clave.
En general no se supone que las claves sean únicas, por lo que las operaciones de búsqueda y eliminación se encargan de algún elemento que responde a la clave dada, sin más precisiones. Hay problemas en los que las claves no pueden duplicarse, en cuyo caso la función de inserción suele detectar duplicados. Estos aspectos son pequeñas variantes que introducen detalles que por su nimiedad no consideraremos en lo que sigue.
Así mismo, nos limitaremos a detectar las situaciones anómalas tales como no poder insertar en una tabla saturada o no encontrar ningún elemento que responda a una clave. Queda a decidir lo que se hace en estos casos, según el problema concreto.
Para cada algoritmo, en primer sacaremos medidas de coste y luego órdenes de complejidad. Como coste nos centraremos principalmente en evaluar el número de comparaciones. Nótese que la comparación entre dos claves puede ser muy sencilla para claves que son tipos básicos de datos (enteros, típicamente); pero también puede irse complicando si la clave es una estructura de datos más compleja.
También suele medirse el número de copias de datos que hay que hacer. Las copias son siempre baratas, bien porque los datos son secillos, bien porque cuando los datos son voluminosos se suelen utilizar punteros a los datos, de forma que estos en realidad no se copian, y sólo se trabaja con punteros.
A efectos de complejidad, se suele utilizar como medida del tamaño del problema el número de datos en la tabla.
Sea un ARRAY lineal la estructura de datos que manejamos
CONST MAX= ...;
VAR T: ARRAY [1..MAX] OF Elemento;
L: INTEGER; (* Longitud de la tabla *)
T almacena los datos, y L es la última posición ocupada en T. En cada momento están ocupadas las entradas [1..L]. Si la tabla T está vacia, entonces L=0;
Insertar un nuevo elemento E es elemental:
IF L = MAX THEN "Error: tabla saturada"
INC (L);
T[L]:= E;
Para localizar un elemento con clave K, no nos queda más remedio que ir buscando por la tabla hasta encontrarlo:
Buscado:= 0;
FOR I:= 1 TO L DO
IF T[I].k = K THEN BEGIN Buscado:= I; BREAK; END;
END;
IF Buscado = 0 THEN
"Error: no se encuentra esa clave"
Por último, eliminar todos los elementos que responden a una clave K consiste en localizarlos uno a uno y eliminarlos. La forma más rápida de eliminar un elemento es machacarlo con el último de la tabla:
I:= 1;
WHILE I <= L DO BEGIN
IF T[I].k = K THEN BEGIN (* localizado *)
T[I]:= T[L]; (* machacado *)
DEC (L);
END
ELSE
INC (L);
END;
Insertar es una operación de coste constante: no hay que hacer ninguna operación de comparación, y basta 1 copia. Es una operación de orden O(1).
Buscar nos cuesta recorrar la lista hasta encontrarlo. No hay que hacer ninguna copia.
Respecto de comparaciones, cabe distinguir varios casos: En el caso mejor, lo encontraremos en la primera posición:
C= 1 que es O(1)
En el caso peor, tendremos que ir hasta el final, uno por uno (bien para encontrarlo, bien para detectar que no está):
C= L que es O(n)
Si bien por término medio podemos decir que recorreremos media tabla para encontrar nuestra clave:
C= L/2 que es O(n)
Nótese que el criterio de término medio es muy arbitrario. Si en el problema que nos ocupa lo más frecuente es buscar los primeros datos que se insertan, C disminuye drásticamente. Por el contrario, si lo más frecuente es buscar lo último que se metió, o buscar claves que no están, C crece. Si mezclamos eliminaciones (que reordenan elementos en la tabla) es aún más dificil de predecir.
La variación más habitual de este método es la utilización de estructuras dinámicas, es decir listas encadenadas:
TYPE Pnodo= ^nodo;
nodo= RECORD
E: Elemento;
sig: Pnodo;
END;
VAR Tabla: Pnodo; (* valor inicial: nil *)
La inserción suele poner al recien llegado en cabeza:
NEW (p);
IF p = nil THEN "Error: tabla saturada"
p^.E:= E;
p^.sig:= Tabla
Tabla:= p;
La búsqueda es un recorrido:
Buscado:= nil;
p:= Tabla;
WHILE p <> NIL DO
IF p^.E.k = K THEN BEGIN Buscado:= p; BREAK; END;
IF Buscado = nil THEN
"Error: no se encuentra esa clave"
Y la eliminación un juego con los punteros:
PROCEDURE Elimina (K: clave);
PROCEDURE Borralo (VAR Anterior: Pnodo);
VAR p: Pnodo;
BEGIN
IF Anterior = NIL THEN EXIT; (* no está *)
IF Anterior^.E.k = k THEN BEGIN (* hallado *)
p:= Anterior; (* dispón de *)
Anterior:= p^.sig;
DISPOSE (p);
END
Borralo (Anterior^.sig)
END {Borralo};
BEGIN
Borralo (Tabla);
END {Borra};
A efectos de complejidad, los algoritmos lineales sobre listas encadenadas son análogos a los que trabajan sobre tablas de tamaño máximo: lineales en los casos peor y medio.
Las tablas fijan el número de elementos en tiempo de compilación: si se prevén en exceso, estaremos desperdiciando espacio; si nos quedamos cortos, el programa fallará en ejecución. Lo bueno es que al compilar podemos garantizar sitio para MAX datos. Probablemente sean la mejor opción si se tiene de antemano una idea del número de datos que vamos a insertar.
Las listas encadenadas no fijan nada en tiempo de compilación, por lo que no se desperdicia sitio si en ejecución hay pocos datos. Así mismo, se pueden ir metiendo más y más datos hasta que se acabe la memoria del ordenador. Lo malo es que el límite práctico lo descubrimos en ejecución, siendo dificil de predecir. Por otra parte, los registros utilizados para construir la lista encadenada consumen su propio espacio. Probablemente sean la mejor opción si el número de datos es impredecible o puede variar en rangos muy amplios.
Aun siendo algoritmos de igual orden de complejidad, hay que destacar que los programas con listas encadenadas son más lentos pues las operaciones que hacen son más complejas. Además, el código es notablemente más complicado y es más fácil equivocarse.
Una variación muy interesante de las listas lineales consiste en disponer los datos por orden de claves. Esto estropea los algoritmos de inserción y eliminación, que deben mantener el orden; pero abre las puertas a una técnica del tipo divide y venceras en la búsqueda. Por ello, cuando un problema lo que hace son muchísimas más búsquedas que inserciones/eliminaciones, vale la pena considerar esta opción.
La inserción debe respetar el orden:
IF L = MAX THEN "Error: tabla saturada";
I:= L; (* el último *)
WHILE (TRUE) DO BEGIN
IF I = 0 THEN BREAK; (* el primero *)
IF T[I].k > E.k THEN BEGIN
T[I+1]:= T[I]; (* lo corro *)
DEC (I);
END
ELSE
BREAK;
END;
T[I]:= E; (* lo inserto *)
INC (L);
O, si se prefiere:
I:= L; (* el último *)
WHILE (I > 0) AND (T[I].k > E.k) DO BEGIN
T[I+1]:= T[I]; (* lo corro *)
DEC (I);
END;
T[I]:= E; (* lo inserto *)
INC (L);
Lo más emocionante es la búsqueda, que permite el uso de una técnica del tipo "divide y vencerás". La idea es colocarse en mitad de la tabla y ver si el elemento que buscamos está antes o después. En cualquier caso, a continuación podemos limitarnos a buscar en la media tabla en la que está.
A efectos de programarlo, vamos a diseñar una función auxiliar a la que le pasamos dos parámetros que son los límites de la zona en la que puede estar el dato. Esta función nos devuelve la posición del dato que buscamos:
FUNCTION BusquedaBinaria (A, Z: INTEGER; K: clave): INTEGER;
VAR m: INTEGER;
BEGIN
IF A > Z THEN (* no está *)
BusquedaBinaria:= 0
ELSE BEGIN
m:= (A+Z) DIV 2; (* la mitad *)
IF T[m].k = K THEN (* está aquí *)
BusquedaBinaria:= m;
ELSE IF T[m].k > K THEN (* estará antes *)
BusquedaBinaria:= BusquedaBinaria (A, m-1, K)
ELSE (* estará después *)
BusquedaBinaria:= BusquedaBinaria (m+1, Z, K);
END;
END {BusquedaBinaria};
Con esta función auxiliar es fácil programar la búqueda como
Buscado:= BusquedaBinaria (1, L, K);
y la eliminación de elementos:
I:= BusquedaBinaria (1, L, K);
WHILE I <> 0 DO BEGIN
FOR J= I+1 TO L DO
T[J-1]:= T[J];
DEC (L);
I:= BusquedaBinaria (1, L, K);
END;
Si las comparaciones son costosas, se pueden minimizar en inserción utilizando búsqueda binaria para identificar la posición en que debe insertarse el nuevo miembro. Esta versión se deja de ejercicio al lector.
Inserción:
comparaciones (y copias):
caso mejor: 1
caso peor: L --> O(n)
Búsqueda:
comparaciones:
caso mejor: 1
caso peor: 2*log2 (L) --> O(log n)
La
función BusquedaBinaria hace dos comparaciones por llamada, y se llama
recursivamente.
En la primera llamada, el segmento a buscar son los L datos.
En la segunda, L/2.
En la llamada k, hay L/2k.
Se detiene cuando L/2k < 1 => k >= log2 (L).
Eliminación:
comparaciones (las de la búsqueda binaria)
caso mejor: 1
caso peor: 2*log2 (L) --> O(log n)
copias:
caso mejor: 0
caso peor: L --> O(n)
Se pueden programar estos algoritmos con listas encadenadas. Las operaciones de insertar y borrar son similares en cuanto a comparaciones; pero son O(1) en cuanto a copias. Lo que es más lioso es la búsqueda binaria, que exige recorridos sistemáticos por la lista. Aunque laboriosos, estos recorridos son muy rápidos, y no involucran ni comparaciones ni copias.
Pero el código es tan lioso, que es muy muy raro que nadie tome esta opción. máxime, cuando existen los árboles binarios de búsqueda, que se ven en la sección siguiente, y son más fáciles de programar.
De alguna forma son una mezcla de listas encadenadas y tablas ordenadas.
Cada nodo del árbol puede tener dos hijos:
TYPE Pnodo= ^nodo;
nodo= RECORD E: Elemento; izq, der: Pnodo; END;
Se dice árbol binario de búsqueda cuando para todos los nodos N del árbol es cierto que todos sus hijos por la rama izquierda tienen claves menores que N, y todos los hijos por la rama derecha la tienen mayor. La definición hay que relajarla un poco si se admiten claves duplicadas.
Es equivalente decir que un árbol binario de búsqueda es aquel en el que los nodos aparecen ordenados por clave al hacer un recorrido en orden. ¡Póngase un ejemplo! Es obvio.
La inserción es relativamente complicada, requiriendo un procedimiento auxiliar. La idea es localizar la posición que debe ocupar el nuevo elemento (siempre una hoja) e insertarlo ahí.
PROCEDURE Insertalo (E: Elemento; VAR a: Pnodo);
BEGIN
IF a = NIL THEN BEGIN
NEW (a);
a^.E:= E;
a^.izq:= NIL;
a^.der:= NIL;
END
ELSE IF E.k < a^.E.k THEN
Insertalo (E, a^.izq)
ELSE
Insertalo (E, a^.der);
END {Insertalo};
La búsqueda es binaria por la propia estructura de datos:
FUNCTION Busca (k: clave; a: Pnodo): Pnodo;
BEGIN
IF a = NIL THEN (* no está *)
Busca:= nil
ELSE IF k = a^.E.k THEN
Busca:= a
ELSE IF k < a^.E.k THEN
Busca:= Busca (k, a^.izq)
ELSE
Busca:= Busca (k, a^.der)
END {Busca};
Lo más complicado es la eliminación de un nodo. Se dan tres casos:
Si el nodo carece de hijos, basta desgajarlo del árbol.
Si solo tiene un hijo, hay que pasarle este al padre.
Pero si tiene 2 hijos hay que remodelar el árbol. La remodelación consiste en localizar el menor descendiente por la derecha, desgajarlo, y colocarlo en el lugar del nodo a eliminar.
FUNCTION ExtraeMenor (VAR a: Pnodo): Pnodo;
VAR p: Pnodo;
BEGIN
IF a^.izq = NIL THEN BEGIN
p:= a;
a:= a^.der;
p^.der:= NIL;
ExtraeMenor:= p;
END
ELSE
ExtraeMenor:= ExtraeMenor (a^.izq)
END {ExtraeMenor};
Es análogo buscar al descendiente mayor por la izquierda, desgajarlo, y colocarlo en el lugar del nodo a eliminar.
El procedimiento principal queda así:
PROCEDURE Eliminalo (K: clave; VAR a: Pnodo);
VAR p, q: Pnodo;
BEGIN
IF a = NIL THEN "Error: no está"
ELSE IF K < a^.E.k THEN Eliminalo (K, a^.izq)
ELSE IF K > a^.E.k THEN Eliminalo (K, a^.der)
ELSE BEGIN
p:= a;
IF (a^.izq = NIL) AND (a^.der = NIL) THEN
a:= NIL
ELSE IF (a^.izq = NIL) THEN
a:= a^.der
ELSE IF (a^.der = NIL) THEN
a:= a^.izq
ELSE BEGIN
q:= ExtraeMenor (a^.der);
q^.izq:= a^.izq;
q^.der:= a^.der;
a:= q;
END;
DISPOSE (p);
END;
END {Eliminalo};
PROCEDURE Elimina (K: clave);
BEGIN
Eliminalo (K, Tabla);
END {Elimina};
Todo depende de la profundidad que alcance el árbol. Y esta depende del orden de las inserciones.
En el mejor caso, nos encontraremos con árboles balanceados (en el sentido AVL: las ramas izquierda y derecha difieren como mucho en 1 nivel de profundidad). En estos casos, la profundidad del árbol viene dada por Log2 (L).
En el peor de los casos nos encontraremos con árboles degenerados en los que cada nodo sólo tiene un hijo. Sea por la izquierda o por la derecha, el resultado es equivalente a estar trabajando con una lista encadenada.
Suponiendo árboles con una profundidad de orden log2(L) tendremos:
inserción:
comparaciones:
caso mejor: 1
caso peor: log2 (L) --> O(log n)
copias: 1 --> O(1)
búsqueda:
comparaciones:
caso mejor: 1
caso peor: log2 (L) --> O(log n)
copias: 0
eliminación:
comparaciones:
caso mejor: 1
caso peor: log2 (L) --> O(log n)
copias: 0 (siempre son punteros)
Nótese que todos estos algoritmos pasan de logarítmicos a lineales si el árbol se degrada.
Las variaciones más habituales buscan mantener el árbol lo suficientemente equilibrado. Los modelos más habituales son los árboles balanceados (AVL) y los árboles B.
La técnica de los árboles balanceados utiliza las mismas estructuras de datos que hemos venido viendo. Tras cada inserción y cada borrado, si el árbol se desequilibra, hay que restablecer su equilibrio. Para ello hay que "rotar" nodos de forma algo similar a lo que hicimos para eliminar un nodo intermedio con un par de hijos. Los detalles son más complicados.
La técnica de los árboles B consiste en usar nodos con holgura: pueden tener k o k+1 hijos. Hay un nodo excepcional, la raíz, que puede tener 0, 1, ..., k+1 hijos. Un caso muy habitual es usar k=2, que se conoce como árboles 2-3. En estos árboles es sencillo mantener el equilibrio, a costa de que el número de datos que caben en un árbol de h niveles de profundidad está entre 2h y 3h. Si intentamos insertar en un nodo con 2 hijos, basta meterle un tercero. Si ya tuviera tres, hay que desdoblar el nodo en dos nuevos nodos, cada uno con dos hijos. Entonces hay que ver si el padre puede soportar un hijo más, o si a su vez hay que desdoblarlo, y así recursivamente hasta llegar a la raíz.
En general, estos algoritmos son complejos de programar y de analizar, por lo que conviene consultar la literatura para analizar sus propiedades y copiar código en la medida en que sea posible.
Se traduce directamente por "picadillo" y se utiliza para referirse a una amplia familia de funciones que permiten clasificar los datos por claves.
En general, el universo de claves es muy amplio, muy superior al de claves concretas que aparecen en el conjunto de N datos que trata el programa en cada caso. Lo que buscaremos será una función
FUNCTION hash (K: clave): [0..H-1];
que clasifica cada dato en una clase.
Lo ideal sería disponer de tantas clases H como datos N, y una función "hash" que justamente coloca a cada dato en una clase distinta. Se dice que tenemos un "hash perfecto", y estudiaremos esta situaci¢n m s adelante. Pero vamos adelantando que esto sólo es posible cuando todos los datos son conocidos de antemano. Si no, tanto N como las claves concretas que nos encontremos serán impredecibles.
Si tenemos más clases que datos (H > N), lo ideal es que no caiga más de un dato por clase. Si al preparar el programa no sabemos qué datos concretos vamos a procesar, este ideal es imposible. A todos los efectos prácticos, hay que estar preparado para que se produzcan "colisiones", es decir que dos o más datos caigan en la misma clase.
Si tenemos más datos que clases (N > H), lo único que podemos pretender es que los datos se distribuyan uniformemente, a razón de N/H datos por clase. Las colisiones son inevitables.
Todos estos comentarios imponen unos requisitos difíciles de precisar sobre la función "hash". Para hacerlo aún más difícil, nótese que esta función está en el camino crítico de cualquier operación de inserción, búsqueda o eliminación, pues en cualquiera de éllas lo primero que hay que hacer es identificar a qué clase pertenece el dato. En consecuencia, "hash" debe ser una función de rápida evaluación.
Si H > N, y "hash" se comporta bien, habremos reducido el problema de tamaño N a un problema de O(1) (0 o 1 dato por clase).
Si N > H, y "hash" se comporta bien, habremos reducido el problema de tamaño N a un problema de tamaño N/H (de media). Este es un ejemplo de técnica "divide y vencerás", donde dividimos por H, que puede ser un número elevado.
Todos estos requisitos hacen de la elección de "hash" un verdadero arte. Además, será casi imprescindible analizar a posteriori (sobre datos reales) si la elección fue buena o no.
El uso de una técnica de "hashing" exige tomar dos decisiones: elegir una función "hash" y elegir un método para afrontar las colisiones. Vamos a describir en primer lugar los dos métodos más habituales para enfrentarse a las colisiones. Más adelante hablaremos sobre la función "hash".
Ante la aparición de colisiones hay dos soluciones fundamentales:
solución abierta: Se organizan de alguna forma los datos del mismo subproblema, de forma que "hash" me lleva simplemente al subproblema correspondiente a una clave K, y ahí se aplican de nuevo técnicas de gestión de tablas.
solución cerrada: Se retoca el valor de "hash (k)" hasta que no existe ninguna colisión. De alguna forma, si la "clase natural" ya está ocupada se le busca al dato una clase alternativa que esté libre. Esto sólo vale si H > N.
El conjunto de datos que colisionan en una misma clase se organiza de alguna forma: tabla, lista encadenada, árbol binario, hash a segundo nievl, ...
Sea xxx2 la función de inserción/búsqueda/eliminación en uno de los subproblemas. Entonces, la operación correspondiente a nivel de problema queda así:
Inserta (E: elemento) --> Inserta2 (E: elemento, hash (E.k));
Busca (K: clave) --> Busca2 (K: clave, hash (E.k));
Elimina (K: clave) --> Elimina2 (K: clave, hash (E.k));
Lo más habitual es la práctica es utilizar listas encadenadas. La razón es que estas listas no ocupan nada si no hay datos en una clase, y van adaptándose dinámicamente a un número variable de datos. Su complejidad es lineal; pero si logramos que trabajen sobre listas breves, esto tiene poco impacto.
A efectos de código, tenemos
VAR TT: ARRAY [0..H-1] OF Pnodo;
En tiempo de ejecución tenemos algo así:
| |
+-----+
| ----> k1 (* clase con 1 dato *)
+-----+
| NIL | (* clase sin datos *)
+-----+
| ----> k3 --> k4 --> k5 (* clase con 3 datos *)
+-----+
| ----> k13 (* clase con 1 dato *)
+-----+
| |
Si ante una clave
h0= hash (k)
nos encontramos que ya hay otro dato en la tabla, iremos probando alternativas
h1, h2, h3, ...
hasta que no colisione con nadie más.
El procedimiento de ir probando debe ser determinista para poder reproducirlo al insertar, al buscar y al eliminar.
Una técnica fácil es recorrer linealmente la tabla:
hi= (h0 + i) MOD H
(si una entrada no vale, se prueba la siguiente; si llegamos al final, volvemos a empezar por el principio). Pero la experiencia dice que este tratamiento no funciona bien en la práctica: los datos tienden a agruparse, haciendo de la búsqueda de un hueco un penoso deambular.
Esto le ocurre a cualquier método en el que el cálculo de hi se base exclusivamente en el valor de su predecesor, "olvidando la historia". Se forman cadenas de posiciones ocupadas de tal forma que basta que un nuevo dato caiga en algún sitio de esta cadena para que el algoritmo lo lleve hasta el final, alargando la cadena en una posición más. Las cadenas son cada vez más largas y es cada vez más probable que un nuevo dato caiga en "las garras de una cadena".
Por ello hay que buscar métodos que eviten la aparición de "mafias". El recorrido cuadrático es efectivo, y se utiliza habitualmente:
hi= (h0 + i*i) MOD H
que se codifica sin recurrir a multiplicaciones fijándonos en que los incrementosde los cuadrados siguen una ley simple:
1 4 9 16 25 36 49 64 81 ...
3 5 7 9 11 13 15 17 ...
2 2 2 2 2 2 2 ...
Un algoritmo de búsqueda íntegro tiene esta pinta:
FUNCTION Busca (K: clave): Elemento;
BEGIN
h:= hash (K);
d:= 1;
WHILE (TRUE) DO BEGIN
IF TT[h] = VACIA THEN "No está";
IF TT[h].k = K THEN BEGIN
Busca:= TT[h];
EXIT;
END;
h:= (h+d) MOD H;
d:= d+2;
IF d > H THEN "No está"; (* no cabría *)
END;
END {Busca};
Al principio todas las posiciones estan VACIAS, y se van llenando poco a poco. Si eliminamos datos, no podemos simplemente vaciar la posición que ocupaban, pues el método de busqueda por saltitos podría dar resultados diferentes según se encuentre las posiciones intermedias ocupadas o no. Es un poquito lioso de programar; pero nada más.
El rendimiento de esta técnica depende fuertemente del grado de saturación de la tabla. Sea S = N/H el coeficiente de utilización de entradas. Obviamente, S no puede llegar a 1.0, pues no cabrían más datos.
Coste de inserción y de búsqueda (cuando el dato no está):
1/(1-S) (1)
Coste de eliminación y de búsqueda (cuando el dato si está):
- ln (1-S) / S (2)
estas funciones se disparan al infinito cuando S-> 1.0.
|
S |
(1) |
(2) |
|
|
|
|
|
0.1 |
1.11 |
1.05 |
|
0.2 |
1.25 |
1.12 |
|
0.3 |
1.43 |
1.19 |
|
0.4 |
1.67 |
1.28 |
|
0.5 |
2.00 |
1.39 |
|
0.6 |
2.50 |
1.53 |
|
0.7 |
3.33 |
1.72 |
|
0.8 |
5.00 |
2.01 |
|
0.9 |
10.0 |
2.56 |
En la práctica no suele ser tolerable trabajar con S por encima de 0.8, imponiéndose un límite práctico de saturación máxima: 80%
Si arrancamos un problema con una tabla de tamaño H, y la tabla se va llenando, puede llegar a superar la cota heurística del 80%. En esta situación, o bien paramos el ordenador y empezamos de nuevo con una tabla más amplia, o redimensionamos la tabla. Es muy frecuente redimiensionar duplicando (pasamos a una tabla de 2H entradas). Nótese que si cambiamos H la función de hash cambia, los datos van a parar a sitios distintos ... vamos, que hay que reinsertar todos los datos en la nueva tabla.
Esta es la pregunta del millón, que hemos ido olvidando en todo lo anterior. Lo que pasa es que la respuesta no es ni fácil, ni obvia, ni aplicable universalmente. Hay que elegirla con arte, si bien se puede evaluar a posteriori el grado de idoneidad.
Si la clave es un entero, puede utilizarse algo tan simple como
hash (k) --> k MOD H
que funciona bien si el rango de k es muy amplio comparado con H (por ejemplo, el DNI para ordenar los alumnos de la ETSITM). A la hora de elegir H, suele ser buena idea optar por un número primo.
A veces se utilizan técnicas de truncado (sólo se usan unos cuantos dígitos), o se eleva el número al cuadrado y se eligen algunos dígitos del resultado (truncado, de nuevo), o se pliega el número sobre sí mismo (y se suman los dígitos que coinciden), o ... la imaginación tiene pocos límites.
Con identificadores es muy frecuente utilizar funciones que suman el ordinal de todos los caracteres, módulo H. Esto funciona aceptablemente bien con nombres de alumnos, pero no es muy lucido ante programas de ordenador (pues hay muchas variables cortitas que difieren en pocas letras).
Personalmente, la experiencia me ha llevado a utilizar
FUNCTION Hash (S: string): integer;
VAR h, i: integer;
BEGIN
h:= 0;
FOR i:= 0 TO Length (S) DO
h:= h*4 + ORD (S[i]);
Hash:= h MOD 1008;
END {Hash};
que funciona sorprendentemente bien con identificadores de programas, aunque nadie sabe muy bien por qué.
Si el elegir la función es un arte, evaluarla es un poquitín otro arte. A veces se hacen análisis estadísticos de uniformidad de la distribución (adecuación a una hipótesis de uniformidad); pero lo más frecuente es analizarlo experimentalmente.
Para cada posición h en la tabla TT, contamos en número de colisiones C(h). A continuación, contamos cuántos casos tenemos con cada número de colisiones, D(c).
Lo ideal es que este histograma sólo presente datos en ristras de N/H colisiones (1 dato arriba o abajo, pues las divisiones son enteras).
número de clases con C colisiones
^
| *
| *
| *
| *
| *
+-----------+---------------------> C
0 N/H número de colisiones
Lo peor que puede pasar es que los datos tiendan a concentrarse en unas pocas clases (muchas posiciones se quedan con 0 datos):
número de clases con C colisiones
^
|*
|*
|*
|* * *
|* * * * *
+-----------+---------------------> C
0 N/H número de colisiones
Lo normal es que se obtenga alguna forma de "campana", con un máximo en la posición N/H, algunos casos con menos colisiones que la media, y algunos casos con más colisiones que la media. Queda al buen criterio del ingeniero decidir si la dispersión de datos es aceptable o si hay que buscar otra función mejor.
Si H > N también hay que decidir cuántas clases vacantes toleramos. Usualmente este es el precio que hay que pagar para obtener una función "hash" rápida.
Se dice que una función de hash es perfecta cuando N=H y cae exactamente 1 dato en cada entrada. Estas funciones sólo se pueden lograr cuando el conjunto de datos de entrada es conocido de antemano. Existen técnicas que permiten diseñar "hash" para que satisfaga aquella importante propiedad.
Estas funciones se utilizan, por ejemplo, para identificar las palabras reservadas de un lenguaje (análisis léxico). Ante un identificador, basta evaluar su valor hash(id), y mirar la posición correspondiente en la tabla. O es esa palabra, o no está. Basta una comparación para tomar la decisión.
Las funciones de hash perfecto se suelen identificar utilizando técnicas de "backtracking" (prueba y error). A efectos de complejidad son muy costosas (O(n6)) pero nótese que esto se evalúa de una vez para siempre: una vez identificada, sólo hay que utilizarla.
Si el número de datos a procesar es pequeño (menor que 10), probablemente las técnicas lineales serán las más adecuadas.
Si el problema de un tamaño medio, (10..100), probablemente lo ideal sea una técnica logarítmica. La tabla ordenada garantiza un comportamiento logarítmico en el caso peor; pero es costosa para introducir y eliminar datos. Los árboles binarios de búsqueda son ágiles en todos los aspectos; pero se corre el riesgo de que el árbol se degenere en una secuencia (y los algoritmos pasen a lineales). Puede llegar a valer la pena el uso de algoritmos que mantienen el árbol balanceado.
Si el problema es grande (más de 1000 datos) el uso de técnicas de hashing es casi obligado. Lo ideal es elegir H holgadamente superior a N. Si esto no fuera posible hay que analizar el impacto de subproblemas de tamaño N/H que pueden requerir el uso de un árbol binario o un segundo "hashing" para tratar las colisiones.
Si el número de datos N es impredecible y puede variar en un rango muy amplio, probablemente los árboles binarios sean la solución obligada.