HASH TABLE
Páginas: 7 (1605 palabras)
Publicado: 13 de diciembre de 2015
Universidad Técnica de Cotopaxi
Ingeniería en Informática y Ciencias Computacionales
[
Hash Table
]
Maria Belen Canchig
Cuarto Sistema Unico
18 de 07 de 2012
Latacunga Ecuador
Tabla de Contenidos
Objetivos
[Tema “1”]
[Tema “2”]
[Subtema “1”]
[Tema “3”]
[Subtema “1”]
[Subtema “2”]
Conclusiones
Bibliografía
Objetivos
Analizar el tema investigado para tener mayor conocimiento y una idea más clara y precisa de
lo que estamos viendo .
HASH TABLE
DEFINICION
Una tabla hash, mapa hash o tabla de dispersión es una estructura de datos que asocia
llaves o
claves con
valores
. La operación principal que soporta de manera eficiente es la
búsqueda
:
permite el acceso a los elementos (teléfono ydirección, por ejemplo) almacenados a partir de
una clave generada (usando el nombre o número de cuenta, por ejemplo). Funciona
transformando la clave con una función hash en un
hash
, un número que identifica la posición
(
casilla
o
cubeta
) donde la tabla hash localiza el valor deseado.
Ejemplo de tabla hash.
Las tablas hash se suelen implementar sobre
vectores de una dimensión, aunquese pueden
hacer implementaciones multi-dimensionales basadas en varias claves. Como en el caso de los
arrays, las tablas hash proveen tiempo constante de búsqueda promedio O(1)
,
1 sin importar el
número de elementos en la tabla. Sin embargo, en casos particularmente malos el tiempo de
búsqueda puede llegar a O(
n
), es decir, en función del número de elementos.
Comparada con otras estructurasde arrays asociadas, las tablas hash son más útiles cuando se
almacenan grandes cantidades de información.
Las tablas hash almacenan la información en posiciones pseudo-aleatorias, así que el acceso
ordenado a su contenido es bastante lento. Otras estructuras como árboles binarios
auto-balanceables son más rápidos en promedio (tiempo de búsqueda O(log
n
)) pero la
información está ordenada entodo momento.
EN QUE SE UTILIZAN
Las operaciones básicas implementadas en las tablas hash son:
inserción(llave, valor)
búsqueda(llave) que devuelve valor
La mayoría de las implementaciones también incluyen borrar(llave). También se pueden ofrecer
funciones como iteración en la tabla, crecimiento y vaciado. Algunas tablas hash permiten almacenar múltiples valores bajo la misma clave.
Para usar una
tabla hash
se necesita:
● Una estructura de acceso directo (normalmente un
array)
.
● Una estructura de datos con una clave
● Una
función resumen
(
hash
) cuyo dominio sea el espacio de claves y su imagen (o
rango) los números naturales.
Inserción
1. Para almacenar un elemento en la
tabla hash
se ha de convertir su clave a un número. Esto se consigue aplicando la
función resumen (hash)
a la clave del elemento.
2. El resultado de la función resumen ha de
mapearse
al espacio de direcciones del
arreglo
que se emplea como soporte, lo cual se consigue con la función
módulo
. Tras
este paso se obtiene un índice válido para la tabla.
3. El elemento se almacena en la posición de la tabla obtenido en el paso anterior.
a.Si en la posición de la tabla ya había otro elemento, se ha producido una
colisión. Este problema se puede solucionar asociando una
lista
a cada posición
de la tabla, aplicando otra función o buscando el siguiente elemento libre. Estas
posibilidades han de considerarse a la hora de recuperar los datos.
Búsqueda
1. Para recuperar los datos, es necesario únicamente conocer la clave del elemento, a la cual se le aplica la
función resumen
.
2. El valor obtenido se mapea al espacio de direcciones de la tabla.
3. Si el elemento existente en la posición indicada en el paso anterior tiene la misma clave
que la empleada en la búsqueda, entonces es el deseado. Si la clave es distinta, se ha
de buscar el elemento según la técnica empleada para resolver el problema de las ...
Ingeniería en Informática y Ciencias Computacionales
[
Hash Table
]
Maria Belen Canchig
Cuarto Sistema Unico
18 de 07 de 2012
Latacunga Ecuador
Tabla de Contenidos
Objetivos
[Tema “1”]
[Tema “2”]
[Subtema “1”]
[Tema “3”]
[Subtema “1”]
[Subtema “2”]
Conclusiones
Bibliografía
Objetivos
Analizar el tema investigado para tener mayor conocimiento y una idea más clara y precisa de
lo que estamos viendo .
HASH TABLE
DEFINICION
Una tabla hash, mapa hash o tabla de dispersión es una estructura de datos que asocia
llaves o
claves con
valores
. La operación principal que soporta de manera eficiente es la
búsqueda
:
permite el acceso a los elementos (teléfono ydirección, por ejemplo) almacenados a partir de
una clave generada (usando el nombre o número de cuenta, por ejemplo). Funciona
transformando la clave con una función hash en un
hash
, un número que identifica la posición
(
casilla
o
cubeta
) donde la tabla hash localiza el valor deseado.
Ejemplo de tabla hash.
Las tablas hash se suelen implementar sobre
vectores de una dimensión, aunquese pueden
hacer implementaciones multi-dimensionales basadas en varias claves. Como en el caso de los
arrays, las tablas hash proveen tiempo constante de búsqueda promedio O(1)
,
1 sin importar el
número de elementos en la tabla. Sin embargo, en casos particularmente malos el tiempo de
búsqueda puede llegar a O(
n
), es decir, en función del número de elementos.
Comparada con otras estructurasde arrays asociadas, las tablas hash son más útiles cuando se
almacenan grandes cantidades de información.
Las tablas hash almacenan la información en posiciones pseudo-aleatorias, así que el acceso
ordenado a su contenido es bastante lento. Otras estructuras como árboles binarios
auto-balanceables son más rápidos en promedio (tiempo de búsqueda O(log
n
)) pero la
información está ordenada entodo momento.
EN QUE SE UTILIZAN
Las operaciones básicas implementadas en las tablas hash son:
inserción(llave, valor)
búsqueda(llave) que devuelve valor
La mayoría de las implementaciones también incluyen borrar(llave). También se pueden ofrecer
funciones como iteración en la tabla, crecimiento y vaciado. Algunas tablas hash permiten almacenar múltiples valores bajo la misma clave.
Para usar una
tabla hash
se necesita:
● Una estructura de acceso directo (normalmente un
array)
.
● Una estructura de datos con una clave
● Una
función resumen
(
hash
) cuyo dominio sea el espacio de claves y su imagen (o
rango) los números naturales.
Inserción
1. Para almacenar un elemento en la
tabla hash
se ha de convertir su clave a un número. Esto se consigue aplicando la
función resumen (hash)
a la clave del elemento.
2. El resultado de la función resumen ha de
mapearse
al espacio de direcciones del
arreglo
que se emplea como soporte, lo cual se consigue con la función
módulo
. Tras
este paso se obtiene un índice válido para la tabla.
3. El elemento se almacena en la posición de la tabla obtenido en el paso anterior.
a.Si en la posición de la tabla ya había otro elemento, se ha producido una
colisión. Este problema se puede solucionar asociando una
lista
a cada posición
de la tabla, aplicando otra función o buscando el siguiente elemento libre. Estas
posibilidades han de considerarse a la hora de recuperar los datos.
Búsqueda
1. Para recuperar los datos, es necesario únicamente conocer la clave del elemento, a la cual se le aplica la
función resumen
.
2. El valor obtenido se mapea al espacio de direcciones de la tabla.
3. Si el elemento existente en la posición indicada en el paso anterior tiene la misma clave
que la empleada en la búsqueda, entonces es el deseado. Si la clave es distinta, se ha
de buscar el elemento según la técnica empleada para resolver el problema de las ...
Leer documento completo
Regístrate para leer el documento completo.