esvdev_logo

Estructuras de datos III - Hash Tables

Publicado: 25/01/24

| Actualizado: 29/06/24

Otra estructura importante y muy utilizada en el desarrollo de software

¿Que es una hash table? (Agarrate eh)

Las hash tables (tablas hash) son una estructura de datos que almacenan valores dado su hash. El hash es el resultado de un proceso llamado “hashing”, utilizado para identificar objetos de forma única y almacenar cada objeto en un índice precalculado llamado “key” (llave). Lo normal es que los hash sean valores de tipo int (entero) o long.

Cada objeto puede ser buscado luego usando esa key, de modo que podemos definir a las hash tables como una colección de pares key-value (llave-valor). Cada par key-value también es conocido como entry (entrada).

Funcionamiento interno

Generalmente las hash tables son implementadas utilizando arrays vacíos (con un tamaño previamente definido al momento de crear la hash table) y linked lists. A grandes rasgos, el mecanismo interno de una hash table funciona de la siguiente manera:

Hash table en distintos lenguajes

Esta estructura se presenta de la siguiente manera en algunos de los lenguajes de programación más utilizados:

💡 Es importante destacar que la eficiencia de una hash table se verá influida por el tamaño de la hash table, cómo esté implementada la función hash y el método que se utilice para abordar colisiones, entre otros.

Casos de uso: las hash tables son usadas para indexar bases de datos, donde se requiere una recuperación rápida de registros basada en claves. También son utilizadas para el caching (donde se necesita acceso rápido a valores previamente computados para mejorar el rendimiento del sistema) y la implementación de diccionarios en lenguajes de programación.

Tipo de estructura: generalmente las hash tables son no lineales y dinámicas, pero esto está sujeto a la manera en que estén implementadas. Pueden ser homogéneas o heterogéneas según la necesidad.

Complejidad algorítmica

Mucho texto! 🥱

Hasta ahora hemos abarcado info teórica que puede servirte si tenés que estudiar sobre el tema para una entrevista o para tener en cuenta al momento de practicar. Sin embargo, nada como un recurso visual para comprender mejor un tópico complejo como este.

Por eso te comparto el siguiente video que te va a ayudar (tal como lo hizo conmigo) a comprenderlo mejor. Los ejemplos están hechos con personajes de Bob Esponja así que no tenés excusa para aburrirte (?

El video está en inglés, pero no creo que sea tan difícil de comprender ya que el creador habla con voz alta, clara y a una velocidad comprensible.

Conclusión

No te culpes o te sientas mal si no entendiste de una como funciona una hash table. Es un concepto complejo que requiere repasarlo varias veces y, como es obvio, ponerlo en práctica en reiteradas oportunidades para afianzarlo. A ver, ¿quién dijo que tenemos que lograr todo al primer intento, no? 😉

Además del video que te compartí, quiero mejorar la calidad didáctica de este post con imágenes que ilustren un poco más los conceptos acá explicados. Espero mejorar este artículo con el tiempo, así que date una vuelta cada tanto para ver su evolución.

Espero que este breve resúmen haya aportado a tu conocimiento. Si encontraste este artículo en Google o te lo compartieron, te invito a pasarte por el "artículo central" sobre Estructuras de datos, ya que allí también encontrarás enlaces a futuros artículos que iré publicando al respecto.

Hasta otra 👋

Tags:
#data-structures #software-development

Escrito por:

Elias Velazquez photo

Elias Velazquez

Python / ETL dev | Data Engineer en progreso | Musico | Nerd de yerbas varias