Diccionario, - Tabla Hash - Estructura De Datos Por la importancia de este tipo de tabla, no se quiere finalizar la descripción de esta estructura sin hablar de la tabla «hash». El método «hash» apareció por primera vez en 1953 y se utilizó para desarrollar el ensamblador IBM 701. El método de acceso «hash» resuelve todos los inconvenientes que presenta la inserción o eliminación de un elemento en la tabla de acceso directo, y es mucho más rápido en los procesos de búsqueda y actualización con respecto a la tabla de búsqueda_lineal. El método «hash» es sencillo aunque parezca algo complejo de explicar: — Se dispone de un vector cuyo contenido es la dirección de las listas de los elementos de la tabla, y su dimensión el número máximo de elementos presentes en la tabla. Un elemento de la tabla es un elemento de una lista. Y consta de la clave, la información del elemento, y la dirección del siguiente elemento de la lista. — Para insertar un elemento en la tabla se busca su posición i en el vector mediante la función de acceso A(k), es decir i=A(k). Si la posición i del vector no apunta a ninguna lista se crea el primer elemento de la lista con la clave y la información a insertar. Si la posición i apunta a una lista se recorre ésta y al final de la misma se añade un nuevo elemento con la clave e información a incorporar. — Para eliminar un elemento de la tabla se realizan operaciones parecidas. Se busca su posición i=A(k) en el vector, si esta posición no apunta a ninguna lista se finalizará por error, y en caso contrario, se recorre la lista hasta localizar el elemento buscado. En ese instante se elimina el elemento de la lista. También se puede finalizar por error si el elemento no está en la lista. — Para buscar o actualizar un elemento de la lista se realizan las mismas operaciones que en la eliminación, con la diferencia de que cuando el elemento ha sido localizado se obtiene su información o se actualiza, según proceda. Como se dice que una imagen (o ejemplo) vale más que mil palabras, se va a aplicar todo lo dicho a la tabla del centro docente, que recogía por cada alumno su número identificativo y el nombre y apellidos del alumno. Si se supone que el centro tiene 205 alumnos (como se había comentado anteriormente), se define un vector «tabla_centro» con un 20% más de capacidad para una demanda futura, es decir, para 245 alumnos. La función «hash» que proporciona la posición i en el vector «tabla_centro» será de la forma: i= resto de dividir el número identificativo del alumno entre 245 +1, porque de esta forma el valor de i estará comprendido entre 1 y 245. Por ejemplo, a los números identificativos de los alumnos que se citan a continuación les corresponden las siguientes posiciones en el vector «tabla_centro».' nº identificativo función hash posición i 1 resto (1/245)+1 2 245 resto (245/245)+1 1 23200 resto (23200/245)+1 171 24365 resto (24365/245)+1 111 24500 resto (24500/245)+1 1 32200 resto (32200/245)+1 106 34405 resto (34405/245)+1 106 34545 resto (34545/245)+1 1 Por lo que si se realizan las inserciones (altas) de los siguientes alumnos: clave Información 24365 Alonso Fernández, Javier 23200 Alvarez Martínez, Luisa 34405 Bustos Soto, María 1 Calleja Toledo, Luis 245 Castilla Pérez, Teresa 24500 Dominguez López, Manuel 34545 Fernández Fernández, Luis 32200 Zuazu Pérez, Fernando A la clave 24365 le ha correspondido la posición 111 de la tabla que está vacía. A la clave 23200 le ha correspondido la posición la posición 171, también vacía. A la clave 34405 le ha correspondido la posición 106, también vacía. A la clave 1 le ha correspondido la posición segunda de la tabla, que está vacía. A la clave 245 le ha correspondido la posición primera de la tabla, que también está vacía. A la clave 24500 le ha correspondido la posición primera de la tabla, y como ya existe una lista con un elemento (el 245), se posiciona detrás de él. A la clave 34545 le ha correspondido también la primera posición de la tabla, por lo que se sitúa al final de la lista, es decir, detrás del elemento 24500. Y a la clave 32200 le ha correspondido la posición 106, en la que ya existe una lista con el elemento 34405, por lo que se sitúa detrás de él. La búsqueda, actualización o eliminación de un elemento consistiría en, dado un número identificativo (por ejemplo el 32200), calcular su posición en la tabla (en este caso i=106). Al acceder a esa posición se ve que existe una lista, que se va recorriendo hasta que coincide el número identificativo del alumno con la clave. En ese instante, se toma la información si es una búsqueda o se actualiza o se elimina todo el elemento según el caso. Aunque a primera vista parezca que el sistema de tabla «hash» no es eficiente, la realidad es que no es así, y que el número de accesos que hay que realizar en la tabla para encontrar el elemento buscado son como media 2 ó 3. Como conclusión a todo lo expuesto de la estructura en tabla, se puede señalar que: — Si la tabla es fija sin inserciones ni eliminaciones lo ideal es una tabla de acceso directo cuya búsqueda es inmediata. — Si la tabla presenta frecuentes inserciones y eliminaciones es aconsejable la tabla «hash». — En pocos casos se utiliza en informática una tabla normal de búsqueda_lineal. Lo más común es aplicar primero una función de acceso al principio de una parte de la tabla y posteriormente buscar linealmente el elemento solicitado. Como en el caso de un diccionario: primero se busca el índice de la palabra y posteriormente el resto de la misma.Enciclopedia, México, Colima, Revista Electronica Fumarola, Noticias LeeColima, Lee Colima

...

| Pad Noticias | Windows Mobile Noticias

Por la importancia de este tipo de tabla, no se quiere finalizar la descripción de esta estructura sin hablar de la tabla «hash». El método «hash» apareció por primera vez en 1953 y se utilizó para desarrollar el ensamblador IBM 701. El método de acceso «hash» resuelve todos los inconvenientes que presenta la inserción o eliminación de un elemento en la tabla de acceso directo, y es mucho más rápido en los procesos de búsqueda y actualización con respecto a la tabla de búsqueda_lineal.

El método «hash» es sencillo aunque parezca algo complejo de explicar:

— Se dispone de un vector cuyo contenido es la dirección de las listas de los elementos de la tabla, y su dimensión el número máximo de elementos presentes en la tabla.

Un elemento de la tabla es un elemento de una lista. Y consta de la clave, la información del elemento, y la dirección del siguiente elemento de la lista.

— Para insertar un elemento en la tabla se busca su posición i en el vector mediante la función de acceso A(k), es decir i=A(k). Si la posición i del vector no apunta a ninguna lista se crea el primer elemento de la lista con la clave y la información a insertar. Si la posición i apunta a una lista se recorre ésta y al final de la misma se añade un nuevo elemento con la clave e información a incorporar.

— Para eliminar un elemento de la tabla se realizan operaciones parecidas. Se busca su posición i=A(k) en el vector, si esta posición no apunta a ninguna lista se finalizará por error, y en caso contrario, se recorre la lista hasta localizar el elemento buscado. En ese instante se elimina el elemento de la lista. También se puede finalizar por error si el elemento no está en la lista.

— Para buscar o actualizar un elemento de la lista se realizan las mismas operaciones que en la eliminación, con la diferencia de que cuando el elemento ha sido localizado se obtiene su información o se actualiza, según proceda.

Como se dice que una imagen (o ejemplo) vale más que mil palabras, se va a aplicar todo lo dicho a la tabla del centro docente, que recogía por cada alumno su número identificativo y el nombre y apellidos del alumno.

Si se supone que el centro tiene 205 alumnos (como se había comentado anteriormente), se define un vector «tabla_centro» con un 20% más de capacidad para una demanda futura, es decir, para 245 alumnos.

La función «hash» que proporciona la posición i en el vector «tabla_centro» será de la forma: i= resto de dividir el número identificativo del alumno entre 245 +1, porque de esta forma el valor de i estará comprendido entre 1 y 245.

Por ejemplo, a los números identificativos de los alumnos que se citan a continuación les corresponden las siguientes posiciones en el vector «tabla_centro».'

nº identificativo	función hash		posición i
1			resto (1/245)+1		2
245	  		resto 	(245/245)+1		1
23200			resto (23200/245)+1		171
24365			resto (24365/245)+1		111
24500			resto (24500/245)+1		1
32200			resto (32200/245)+1		106
34405			resto (34405/245)+1		106
34545			resto (34545/245)+1		1

Por lo que si se realizan las inserciones (altas) de los siguientes alumnos:

clave				Información
24365			Alonso Fernández, Javier
23200			Alvarez Martínez, Luisa
34405			Bustos Soto, María
1			Calleja Toledo, Luis
245			Castilla Pérez, Teresa
24500			Dominguez López, Manuel
34545			Fernández Fernández, Luis
32200			Zuazu Pérez, Fernando

A la clave 24365 le ha correspondido la posición 111 de la tabla que está vacía.

A la clave 23200 le ha correspondido la posición la posición 171, también vacía.

A la clave 34405 le ha correspondido la posición 106, también vacía.

A la clave 1 le ha correspondido la posición segunda de la tabla, que está vacía.

A la clave 245 le ha correspondido la posición primera de la tabla, que también está vacía.

A la clave 24500 le ha correspondido la posición primera de la tabla, y como ya existe una lista con un elemento (el 245), se posiciona detrás de él.

A la clave 34545 le ha correspondido también la primera posición de la tabla, por lo que se sitúa al final de la lista, es decir, detrás del elemento 24500.

Y a la clave 32200 le ha correspondido la posición 106, en la que ya existe una lista con el elemento 34405, por lo que se sitúa detrás de él.

La búsqueda, actualización o eliminación de un elemento consistiría en, dado un número identificativo (por ejemplo el 32200), calcular su posición en la tabla (en este caso i=106). Al acceder a esa posición se ve que existe una lista, que se va recorriendo hasta que coincide el número identificativo del alumno con la clave. En ese instante, se toma la información si es una búsqueda o se actualiza o se elimina todo el elemento según el caso.

Aunque a primera vista parezca que el sistema de tabla «hash» no es eficiente, la realidad es que no es así, y que el número de accesos que hay que realizar en la tabla para encontrar el elemento buscado son como media 2 ó 3.

Como conclusión a todo lo expuesto de la estructura en tabla, se puede señalar que:

— Si la tabla es fija sin inserciones ni eliminaciones lo ideal es una tabla de acceso directo cuya búsqueda es inmediata.

— Si la tabla presenta frecuentes inserciones y eliminaciones es aconsejable la tabla «hash».

— En pocos casos se utiliza en informática una tabla normal de búsqueda_lineal. Lo más común es aplicar primero una función de acceso al principio de una parte de la tabla y posteriormente buscar linealmente el elemento solicitado. Como en el caso de un diccionario: primero se busca el índice de la palabra y posteriormente el resto de la misma.

Sugerencia ... Búsqueda personalizada.