Tablas Hash

Tablas Hash

Una tabla hash es un tipo de estructura de datos que almacena información asignándole claves a los valores, esto se puede interpretar como asignarle un tipo de identificación a un valor cuando se nos pida ubicarlo en el arreglo.

Una tabla hash utiliza una función hash para calcular un índice, también llamado código hash, en una matriz de cubos o ranuras, a partir de los cuales se puede encontrar el valor buscado. Durante la búsqueda, se aplica un hash a la clave y el hash resultante indica dónde se almacena el valor correspondiente.

Idealmente, la función hash asignará cada clave a un valor único, pero la mayoría de los diseños de tablas hash emplean una función hash imperfecta, lo que podría causar colisiones hash donde la función hash genera el mismo índice para más de una clave. Una forma de resolver esto es usando listas ligadas a las claves repetidas.

Funciones Hash

Una función Hash tiene el objetivo de funcionar sobre el valor objetado y ubicarlo en una parte del arreglo. Una función Hash se denota h(n), y tiene la forma h(n)=mod m, dónde el módulo es la función de reducción, esto llamado así porque el módulo de esta función va a tener el objetivo de hacer que el valor “quepa” en el arreglo.

La función hash que usé es h(n)=n mod m, donde m es el tamaño de arreglo (m-1). Esta función es efectiva, pues a todo múltiplo de un numero logra asignarlo uniformemente en el arreglo sin mayor problema, además de ser fácil de utilizar.

La otra función hash fue h(n)=  n+1 mod 3, la cual tiene la intención de dividir los valores y reducir su tamaño, cosa que no tuvo un muy buen funcionamiento, pero para algunas cantidades de valores tuvo su aplicación.

Conclusiones

Las tablas Hash son un algoritmo de estructura de datos bastante efectivo y muy atractivo para ciertas aplicaciones, pues permite la identificación de los valores con una clave muy específica. Debo admitir que fue especialmente complicada su implementación, pero sus usos y aplicaciones cuentan mucho para aprenderlo. Personalmente, me gustan más las Tablas Hash que las Skip Lists, pero cada una tiene su campo de aplicación.

Gerardo Escamilla Morales

...