No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Hash Tables

10/29
Recursos

Aportes 33

Preguntas 5

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

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 鈥渒ey鈥 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

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

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

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.

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. 馃槃

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.

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

<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).

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.

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.

Bueno, s铆, en Java (ojo, no JS) podemos usar la clase Map para crear una HashTable, incluso lo podr铆amos hacer usando un array. Pero tambi茅n es bueno recordar que la API de Java ya tiene implementada la clase HashTable, en el paquete java.util. Te preguntar谩s que tiene que ver con JS, y a lo mejor nada, pero soy programadora de la vieja escuela y eso implica muchos a帽os de usar Java, y la verdad, considero que la API de Java es de mucha ayuda porque ya tiene muchas clases implementadas especializadas para estructuras de datos.

Para la primera parte del curso donde deb铆amos construir un prototipo de tipo Array, cre茅 este prototipo, me llev贸 tooda la tarde y probablemente es un poco verboso, definitivamente hardcodeado.

Tambi茅n lo desplegu茅 como paquete en npm y como repositorio en github, as铆 que pueden ir a checarlo con cualquiera de los dos:
GitHub || NPM ||
CLI command [ npm i @delalyra/arr ]

隆Cualquier feedback es infinitamente agradecido!

Para la primera parte del curso donde deb铆amos construir un prototipo de tipo Array, cre茅 este prototipo, me llev贸 tooda la tarde y probablemente es un poco verboso, definitivamente hardcodeado.

Tambi茅n lo desplegu茅 como paquete en npm y como repositorio en github, as铆 que pueden ir a checarlo con cualquiera de los dos:
GitHub || NPM ||
CLI command [ npm i @delalyra/datastructure ]

隆Cualquier feedback es infinitamente agradecido!

Hash Tables

Una hash table es una estructura de datos que se encarga de asignar claves a valores para una b煤squeda altamente eficiente, para implementar este tipo de estructura de datos podemos hacer uso por ejemplo de un simple arreglo de listas enlazadas y una funci贸n hash, la funci贸n hash ser谩 la encargada de transformar una clave dada en un hash o numero que identifiqu茅 f谩cilmente donde se ubica o almacena un valor.

En t茅rminos m谩s simples se puede decir que un hash table es una estructura de datos que se encarga de asociar llaves o claves, con valores espec铆ficos para una f谩cil b煤squeda.

https://dejuniorasenior.com/que-son-los-hash-tables-o-tablas-hash/

En JavaScript ya hay hash tables

Podemos encontrar mas informacion directo en la documentacion, aunque una dorma de verlo es asi:

>Documentacion<

const map1 = new Map();

La cual sirve para generar una Hash table y si vemos un caso de uso lo muestro a continuacion usando TypeScript.

const first = new Map<number, string>([
  [1, 'one'],
  [2, 'two'],
  [3, 'three'],
]);

Aqui puedo especificar el key y el value de la hash table.
Key => number
value => string

y usarla quedaria asi.

console.log(first.get(1)); // one

Gracias por leer c:

== Hash Table ==

  • Es una estructura de datos asociativa que relaciona una llave con un valor utilizando la funcion hash, dicha funci贸n se emplea para calcular el indice en el que van los elementos que estar谩n en la tabla.

Este video me ayudo a entender un poco m谩s https://www.youtube.com/watch?v=9tZsDJ3JBUA

S铆 est谩 algo complejo al comienzo

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:
鈥淯na 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 鈥渉ash鈥 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