Aún no tienes acceso a esta clase

Crea una cuenta y continúa viendo este curso

Hash Tables

8/25
Recursos

Aportes 25

Preguntas 3

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesión.

Para hacer esto más fácil de entender, básicamente una Hash Table es similar a un objeto JSON, a mi me gusta compararlo con arreglos asociativos en PHP o Mapas en C++.
.
La única diferencia es que, a la “key” que tu le pases se le va a aplicar una función que convertirá esa key en una referencia de memoria que es en donde se guardarán los valores que tu les pases.
.
Para obtener de regreso tus valores, tienes que usar esa misma key, que será convertida de nuevo en un hash con la referencia de memoria en donde están guardados tus valores y te los devolverá.

Las Hash Table funcionan similar a un Array, solo que en vez de índices numéricos se tienen índices o keys en caracteres, entonces es necesario una función intermedia que convierte el key en caracteres en índice numérico.

Hace tiempo vi este video que explica a fondo que son las tablas de hash esta muy bueno
https://www.youtube.com/watch?v=LluB6jU-SwY

🗂️ Hash Tables

<h4>Ideas/conceptos claves</h4>

hash function es poder asegurar generar un hash que se convierte en el address para acceder al valor

<h4>Apuntes</h4>
  • En JavaScript se pueden conocer como objetos o Maps [Aun les falta unos pasos para concretarlo]
  • En otros lenguajes como python son conocidos como Diccionarios [Python], Maps [Java, Go], Hashes [Ruby]
<h3>Hash Tables vs Objetos</h3>
  • Las hash tables son similares a los objetos porque tienen el concepto de guardar valores key, value
  • La diferencia es que tienen un paso extra que se convierte en caja negra la cual es una hash function
  • Funciona de una manera similar a los arreglos debido a que accedemos a través de un numero
<h3>Métodos</h3>
  • Insert ⇒ Insertar un elemento en la tabla
  • Search ⇒ Buscar un elemento por key
  • Delete ⇒ Borrar un elemento
<h3>Colisión de Hash Table</h3>
  • En ocasiones podemos pasar un key distintito puede generar el mismo hash
  • Colisionando con el anterior
  • Esto podrá depender de la cantidad de espacio disponible

RESUMEN: Las hash tables se parecen a los objetos porque podemos guardar valores por llave, valor. Pero su principal diferencia es que genera un hash para cada llave valor. El único problema es que se puede generar un mismo hash colisionando con el anterior

📑 Las Hash Tables permiten almacenar un conjunto de pares (clave : valor). Destacando las búsquedas de elementos en el menor tiempo posible.

Para los futuros developers : las hash tables son muy útiles en la modificación del DOM, en React

Es un tema muy importante tener claro qué es y cómo funciona, así como cómo implementar una función hash. Este es un tema que es muy común ver en entrevistas. 😄

Para aquellos a los que no les queda claro cuando usar un Objeto o un HashMap, recomiendo este artículo muy sencillo.
https://medium.com/front-end-weekly/es6-map-vs-object-what-and-when-b80621932373

MY NOTES FOR HASH TABLES

De inicio las hash tables son similares a los objetos ya que manejan cosas como las key o los value

La diferencia entre una hash table a un objeto es un paso extra el cual es que se convierte en una caja negra que seria una hash fuction.

¿ Como funcionan?

Esto es poder asegurar una hash que se convierte en el address para poder acceder al valor de lo que estamos guardando.

Metodos

Inser → Insertar un elemento en la tabla

search → buscar un elemento por key

delete → borrar un elemento

Colision de hash table

Trabajar con has table aveces puede causar problemas

En ocasiones pasar un key distinto me puede genrar el mismo hash y eso quiere decir que pueden quedar dos elementos guardado en un mismo indice(bucket)

No hay forma de evitarlo.

<h3>Hash Tables</h3>

En JS esta es una estructura de datos que no viene creada como tal. Esta estructura de datos tiene distintos nombres según el lenguaje, en js son los objetos, aunque no es lo mismo que un hast table 100%

  • Esta estructura de datos se caracteriza por tener la nomenclatura key: value / llave: valor
  • En js tenemos que hacer un paso extra y es que debemos crear una hash function, esto es una funcion que lo que hace es que a la key que le pasemos la comvertira en una referencia en memoria donde se guardaran los valores que asociadas a la llave.
  • Para acceder a lso valores debemos usar la misma llave, que sera parseada al hash, (que es la referencia en memoria donde se encuentras los valores).

HASH TABLES

Tablas de Hashes, son similares a los objetos, pues manejan el paradigma de key-value La diferencia es un paso extra: usa una función que se convierte en una caja negra, que es una Hash Function. Lo que realiza, es configurar un hash que se convierte en el address para poder acceder al valor de lo que guardamos. Toma el Key que viene de nuestro objeto, lo convierte en un Hash, y ese Hash será el address donde guardamos el valor.
.
CÓMO FUNCIONAN?

  1. Va a pasar el Key mandarinas a la Hash Function.
  2. La Hash Function me va a generar un número, que siempre será el mismo cuando le pase ese valor.
  3. Ese hash se va a convertir en el address. Donde guardará el valor
  4. Esto se convierte en los Buckets, donde guardar el Key value.
  • Para acceder al valor:
  1. Se debe pasar el Key.
  2. La Hash Function devuelve el mismo número
  3. Tienes acceso al valor.

.
.
COLISIÓN DE HASHES
En ocasiones, pasar un valor distinto, me puede generar un mismo hash, lo que produce dos elementos guardados en un mismo bucket. Hash Tables funciona así, dependiendo de los buckets disponibles o libres, es la forma que va a regresar el Hash para guardar la información. Es casi imposible evitar las colisiones.
Es importante aprender cómo tratar una colisión.

  • Cuando hay dos valores en un mismo Bucket, la forma de acceder es:
  1. Si le paso el key de cerezas, sabiendo que ya existe el de mandarinas
  2. Me genera el hash pero devuelve el valor de las cerezas.

Conocia esto de C#

Un Hash Table es como un array pero el indice es un string=key y el adress un se crea atraves de una funcion.
🔴
Simils que se me ocurren son la generacion de IDs en el Backend y los Tuple de Typescritp o PropTypes.

Hola, esto fue lo que entendí de las hash tables, quedo atento a sus aportes 😃
Hash Tables
Es una estructura de Datos asociativa que relaciona una llave con su respectivo valor por medio de una funcion Hash, esta funcion devuelve un indice o index aleatorio , el cual es la posicion donde se guardará la Informacion en memoria.

La ventaja de usar hash Tables frente a los arrays convencionales es la velocidad con que se recupera la informacion, puesto que en una hash table para obtener de regreso los valores, basta con usar la llave(key), que sera convertida por la funcion hash en la referencia de memoria donde fue guardada la informacion, trayendola inmediatamente.

Creo que una forma de ver la Hash Function, seria como una funcion suprayectiva, en donde el x seria el key, y el f(x) seria el index

Definición de hash table según un recorte que encontré en google:
“Una tabla hash o mapa hash es una estructura de datos que asocia llaves o claves con valores. … Funciona transformando la clave con una función hash en un hash, un número que la tabla hash utiliza para localizar el valor deseado.”

Para los que tengan dudas sobre que es un “hash” les dejo este video, que lo deja bastante claro: https://www.youtube.com/watch?v=GctssJjiqG4. Créditos a David Ceja Zapata, quién trajo el video como aporte a otra clase!

La tabla hash es como un cubo, representado inicialmente como una matriz vacía. Al inicializar la tabla hash, creamos una matriz que contiene un número fijo de estos depósitos.

let allBuckets = [[], [], [], []]  
Y para insertar un valor dentro de nuestros depósitos, es decir, inserte una clave "x" con el valor 10  
1. Utilice la función has para obtener el índice del depósito. 
2. Introduzca el par clave-valor en el depósito.

Usar hastable es una forma muy conveniente para búsqueda, inserción y borrado, en la gran mayoría de casos son Big O(1), es decir en tiempo constante.

los Arrays tengo entendido son una estructura de datos al igual que los Stringsen teoria tambien manejan indices como el arreglo.

QUÉ SON
Es una estructura de datos (asociativa) que pretende la inserción, búsqueda y borrado elementos conformados por una llave y un valor, utilizando una función de Hash. Esta función se utiliza para calcular el índice en el que hay que guardar los elementos que se ingresan a la tabla.

COLISIONES
Ocurren cuando en un mismo índice se introducen varios elementos.
Existen diversas formas de solucionarlo pero la principal es la de generar una lista enlazada con los elementos ubicados en la misma posición.

Es una estructura de datos no lineal cuyo propósito final se centra en llevar a cabo las acciones básicas (inserción, eliminación y búsqueda de elementos) en el menor tiempo posible, mejorando las cotas de rendimiento respecto a un gran número de estructuras.

Una tabla hash almacena un conjunto de pares “(clave, valor)”. La clave es única para cada elemento de la tabla y es el dato que se utiliza para buscar un determinado valor.

COLISION DE HASH TABLE

En ocasiones pasar un valor puede generar el mismo hash, y esto puede hacer que dos elementos se guarden en un mismo bucket. Todo depende de los buckets libres tengamos. Esto se soluciona fácil accediendo con el valor de la key