Preguntas Hashing ED 2021 I Jcarvajalu

ESTRUCTURAS DE DATOS
Preguntas Estructuras de acceso directo (Hashing)

Nombre del estudiante: Juan Nicolás Carvajal Useche
Preguntas:
1. ¿Defina una función hash (hash function)?
Una función hash es un algoritmo que permite la representación de un dato de

entrada en una cadena denominada “valor hash”.
Matemáticamente es una relación entre conjuntos, en la que el conjunto U es el
conjunto de entrada y el M el de salida, el conjunto M siempre tendrá valores
finitos, esta idea traduce que el objetivo de un hash es “compactar” estos datos
del conjunto U y representarlos mediante valores hash del conjunto M.
2. ¿Cuáles son las propiedades deseables de las funciones hash?

Las propiedades deseables en una función hash son:
Que sean de bajo costo computacional.

Que tenga algoritmos que maximicen la compresibilidad de los datos de entrada.
Debe tener algoritmos que eviten colisiones (o incluso que ni haya colisiones).
Debe tener un rango variable para que se pueda implementar como una estructura
de datos dinámica.
Debe ser inyectiva (función 1 a 1, sin colisiones).
Todos sus datos deben ser deterministas (un dato siempre debe tener el mismo
hash sin importar las circunstancias).
Que los datos de la función hash sean uniformes, es decir que sin importar los
demás datos del conjunto de entrada, un valor va a tener la misma probabilidad
de ser determinista.
3. Defina lo que son las colisiones.
Una colisión ocurre cuando dos o más datos de entrada producen una misma salida al
operarlo en el hash, es decir, varios datos tienen el mismo valor hash. Matemáticamente,
se puede decir que un hash tendrá colisiones es una función no inyectiva.
4. ¿Conceptualmente qué es la cardinalidad de una función hash y como se

relaciona con la implementación de las estructuras de datos de acceso directo o
basadas en hashing?
La cardinalidad es una característica de los conjuntos de la función hash, esto
define el número de elementos que tiene cada conjunto (el de entrada y el de
salida).
En la implementación de estructuras de datos, esto es importante en tanto que
según el tamaño de cada conjunto, la estructura podrá o no tener colisiones (Ej.
Si el conjunto de entrada tiene más datos que el conjunto de salida, podrán haber
colisiones).
5. Describa en que consiste en encadenamiento en las estructuras basadas en

hashing y para que se usa.
Hash abierto (encadenamiento separado):
En el hash abierto, los valores hash repetidos se almacenan en listas enlazadas adjuntas
a las celdas donde ocurren colisiones de una tabla hash.
Hash cerrado (encadenamiento interno):
En hash cerrado, todos los valores hash se almacenan en la propia tabla hash sin el uso
de listas enlazadas.
Esto se usa para el manejo de colisiones en un hash, aunque pueda aumentar el tiempo
amortizado de ciertas operaciones que involucren entrar a las listas enlazadas.
6. Considere la siguiente descripción y definición de la estructura de datos Map

(“mapa” o función):
Map
Store mapping from objects to other objects, for instance:

Filename → location of the file on disk
Student ID → student name
Contact name → contact phone number
Definition
Map from S to V is a data structure with methods HasKey(O), Get(O), Set(O, v),
where O ∈ S, v ∈ V .
a. Describa en sus propias palabras en qué consiste el método HasKey(O) y

cómo se realiza.
HasKey(O) verifica si la llave o el valor hash se encuentra dentro del conjunto
de salida y retorna un booleano. Esto se hace mediante la función hash, la cual
es aplicada y retornará true en caso de que arroje un valor de salida.
b. Describa en sus propias palabras en qué consiste el método Get(O) y cómo se

realiza.
Get(O) recupera el dato asociado a la llave o valor hash O del mismo. Esto se
hace aplicando la función hash y recuperando el valor que retorna para O.
c. Describa en sus propias palabras en qué consiste el método Set(O, v) y cómo

se realiza.
Set(O,v) le asigna un valor hash a un dato, en una hashtable le asigna un lugar

a un dato. Esto se realiza mediante los siguientes pasos:
1. Se aplica la función hash al dato.

2. El resultado de la función hash ha de mapearse a un espacio en la estructura de
datos, lo cual se consigue con la función módulo. Tras este paso se obtiene una
posición válida en el mapa.
3. El dato se almacena en la posición del mapa obtenido en el paso anterior. Si en la
posición de la tabla ya había otro dato, se ha producido una colisión.
d. ¿Cuál es el orden del tiempo de ejecución de cada uno de los tres métodos
HasKey, Get y Set?
Es de orden O(1), sin embargo cuando hay colisiones puede extenderse hasta
O(n).
7. Escriba la definición de la estructura de datos Set (conjunto).
La estructura de datos set es una estructura de datos tipo conjunto que permite
almacenar una colección de elementos no necesariamente ordenados de cualquier tipo
de dato, en esta estructura no pueden existir elementos repetidos.
8. Describa en sus propias palabras en qué consiste el método Find(O) de la

estructura de datos Set y cómo se realiza.
Este método funciona para encontrar un valor en el set y retorna su ID.

9. Describa en sus propias palabras en qué consiste el método Add(O) de la
estructura de datos Set y cómo se realiza. A continuación está el pseudocódigo
de este método:
Add(O)
L ← A[h(O)]
for O′ in L:
if O′ == O:
return
L.Append(O)
Add(O) funciona para agregar un dato al set, primero se debe verificar que el
elemento a añadir no se encuentre dentro del set, esto mediante un ciclo que compara
cada dato con el elemento a agregar, una vez comprobado esto, se agrega el nuevo
elemento, si ya está en el Set, no se agrega nada.
10. Describa en sus propias palabras en que consiste el método Remove(O) de la
estructura de datos Set y como se realiza. A continuación está el pseudocódigo
de este método:
Remove(O)
if not Find(O):
return
L ← A[h(O)]
L.Erase(O)
Remove(O) quita el elemento O del Set, para ello primero se verifica si O está en el set,
si no se encuentra este dato, no se hace nada, si lo encuentra lo elimina, quedando esta
posición del set vacía.
11. Explique las dos formas de implementar la estructura de datos Set. Resalte las
diferencias entre estas dos formas de implementación.
La estructura de datos Set se puede implementar a partir de la unión de listas

enlazadas o árboles, la principal diferencia es que en tiempo de ejecución las
implementaciones mediante árboles resultan en operaciones más eficientes, ya
que se aplican operaciones como combinar árboles y comprimir la altura del árbol,
mientras que para el caso de las listas enlazadas simplemente se unen listas, lo
que hace que algunas operaciones tengan un costo amortizado de O(n).
12. Describa el significado de los parámetros n, m, c y alfa (factor de carga) de una

tabla hash.
n es el número de llaves en uso, M es el número de registros por celda y c es el
número de celdas, alfa es el factor de carga que representa el grado de
ocupación del hash.

Preguntas Hashing ED 2021 I Jcarvajalu

Cargado por

Copyright:

Formatos disponibles

Preguntas Hashing ED 2021 I Jcarvajalu

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Preguntas Hashing ED 2021 I Jcarvajalu

Cargado por

Copyright:

Formatos disponibles

ESTRUCTURAS DE DATOS

Preguntas Estructuras de acceso directo (Hashing)

Una función hash es un algoritmo que permite la representación de un dato de

2. ¿Cuáles son las propiedades deseables de las funciones hash?

Que sean de bajo costo computacional.

3. Defina lo que son las colisiones.

4. ¿Conceptualmente qué es la cardinalidad de una función hash y como se

5. Describa en que consiste en encadenamiento en las estructuras basadas en

Hash abierto (encadenamiento separado):

Hash cerrado (encadenamiento interno):

6. Considere la siguiente descripción y definición de la estructura de datos Map

Store mapping from objects to other objects, for instance:

a. Describa en sus propias palabras en qué consiste el método HasKey(O) y

b. Describa en sus propias palabras en qué consiste el método Get(O) y cómo se

c. Describa en sus propias palabras en qué consiste el método Set(O, v) y cómo

Set(O,v) le asigna un valor hash a un dato, en una hashtable le asigna un lugar

1. Se aplica la función hash al dato.

7. Escriba la definición de la estructura de datos Set (conjunto).

8. Describa en sus propias palabras en qué consiste el método Find(O) de la

Este método funciona para encontrar un valor en el set y retorna su ID.

La estructura de datos Set se puede implementar a partir de la unión de listas

12. Describa el significado de los parámetros n, m, c y alfa (factor de carga) de una

También podría gustarte