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

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:

• Ingresamos una ENTRY (par key-value) a la hash table.
• La función hash toma la key que ingresamos previamente como argumento y mediante una fórmula calcula y retorna un número entero. Luego este número entero es dividido por el tamaño que tiene la hash table (el tamaño generalmente se declara al momento de crear la hash table). El resto de dicha división dará como resultado el índice.
• Este índice no es otra cosa que la posición dentro del array donde se almacenará dicha key y el valor asociada a ella. Este lugar del array donde se almacena la entry (par key-value) también se conoce como BUCKET.
• Puede suceder (y es algo frecuente) que la función hash determine un mismo índice para entries (pares key-value) distintas, por ende, pueden haber dos entries distintas ocupando el mismo bucket o posición del array. Esto se denomina COLISIÓN.
• Para lidiar con una colisión, generalmente se trata a cada bucket como una LinkedList (lista enlazada). Esto permite manejar con eficiencia las entries al momento de consultarlas, ya que, siguiendo el comportamiento de toda lista enlazada, cada entry del bucket apunta a la posición de la siguiente entry que ocupa el mismo bucket.

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

• Java
  • HashMap
  • Set
• JavaScript
  • Map
• Python
  • Dict

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.

• Inserción
  • Para las inserciones tenemos una complejidad de O(1), es decir, tiempo constante. Por lo que esta estructura de datos es muy eficiente al momento de insertar información.
• Búsqueda
  • En el caso promedio, tendremos también una complejidad de O(1) al momento de buscar elementos dentro de la hash table.
  • Pero en el peor de las casos, ya sea por una función hash implementada de manera inadecuada o un método de manejo de colisiones poco eficiente, la complejidad de búsqueda de valores puede ser O(N), es decir, lineal. A mayor cantidad de elementos, mayor consumo de recursos.

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.

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 👋