Tablas Hash

Una tabla hash o mapa hash es una estructura de datos que asocia llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el acceso a los elementos (teléfono y dirección, por ejemplo) almacenados a partir de una clave generada (usando el nombre o número de cuenta, por ejemplo). 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.
Las tablas hash se suelen implementar sobre arrays de una dimensión, aunque se pueden hacer implementaciones multi-dimensionales basadas en varias claves. Como en el caso de los arrays, las tablas hash proveen tiempo constante de búsqueda promedio O,[1] sin importar el número de elementos en la tabla. Sin embargo, en casos particularmente malos el tiempo de búsqueda puede llegar a O(n), es decir, en función del número de elementos.

Comparada con otras estructuras de arrays asociadas, las tablas hash son más útiles cuando se almacenan grandes cantidades de información.

Las tablas hash almacenan la información en posiciones pseudo-aleatorias, así que el acceso ordenado a su contenido es bastante lento. Otras estructuras como árboles binarios auto-balanceables son más lentos en promedio (tiempo de búsqueda O(log n)) pero la información está ordenada en todo momento.

Ejemplo
Para comenzar pensemos en esta tabla como un arreglo:

Para saber donde vamos a guardar a nuestro jugador modulamos la clave por el tamaño de la tabla

Con este algoritmo si quisiéramos accesar un jugador en particular usaremos una ecuación simple como: player = table[key % 10];
Este algoritmo nos daría el elemento inmediatamente y tuviera una notación de gran O de O(c)
Uno de los problemas con tablas hash es que choques pueden ocurrir frecuentemente.
Por ejemplo intenten insertar los jugadores con las claves 143,674 y 645,394
No se puede por que los dos tratarían de ocupar la celda 4
Para resolver esto utilizamos una función de hashing o modificamos la tabla para que choques no ocurran

Una alternativa sería de sumar los dígitos
143,674 = 1 + 4 + 3 + 6 + 7 + 4 = 25
645,394 = 6 + 4 + 5 + 3 + 9 + 4 = 31
9 + 9 + 9 + 9 + 9 + 9 = 54
Hashing doble

Utilizar el mismo algoritmo u otro para hash la clave obtenida la primera vez

143,674 = 1 + 4 + 3 + 6 + 7 + 4 = 25
645,394 = 6 + 4 + 5 + 3 + 9 + 4 = 31
25 = 2 + 5 = 7
31 = 3 + 1 = 4

Hay muchas funciones de hashing que se pueden hacer sobre enteros pero es imposible de que no ocurran choques en las tablas
El otro tipo de dato que usualmente se le aplica hashing es a las cadenas de caracteres
El siguiente algoritmo hace un buen trabajo en hash cadenas en enteros con muy pocos choques

unsigned long int StringHash( const char* p_string )
{
unsigned long int hash = 0;
int i;
int length = strlen( p_string );
for( i = 0; i < onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"

Así que ninguna tabla hash es perfecta lo mas seguro es que nos vamos a encontrar con choques. Simplemente hay que encontrar maneras de manejar los choques.
Uno de los métodos comunes es de sobreflujo lineal (linear overflow.) Este método simplemente chequea si el índice está lleno y si lo está sube el valor del índice por uno hasta que encuentre uno vacío.

Este método no sirve para nada y destruye lo que una tabla hash quiere hacer. Vuelve el algoritmo de hash de O(c) a O(n). También existe el sobre flujo cuadrático
1 exp 2 (1) and then 2 exp 2 (4) and then 3 exp 2 (9)

Unos de los mejores métodos es el de sobreflujo enlazado
Este método realiza una lista enlazada en cada celda de la tabla
Supongamos que tenemos un arreglo de 10 celdas y utilizamos el algoritmo de módulo 10 sobre la clave para insertar objetos en el arreglo
Player 1: 345,752
Player 2: 546,182
Player 3: 798,500
Player 4: 123,430

Las claves se simplifican a 2, 2, 0, 0
Antes esto nos habría dado problemas pero como ahora tenemos una lista enlazada en cada celda no hay dificultades

Un Ejemplo


[+/-] Ejemplo...