hashing.md - CB100 - Notas, resueltos y tps de la materia Algoritmos y Estructuras de Datos

Line numbers
   1 # Hashing
   2 
   3 Algoritmos y Estructuras de Datos (CB100) - FIUBA  
   4 Martin Klöckner - [mklockner@fi.uba.ar](mailto:mklockner@fi.uba.ar)  
   5 
   6 \vspace{-1.25em}
   7 \rule{\linewidth}{0.5pt}
   8 \vspace{-1.25em}
   9 
  10 Las tablas hash son estructuras de datos que se utilizan para almacenar un
  11 numero elevado de datos sobre los que se necesitan operaciones de búsqueda e
  12 inserción muy eficientes. Una tabla hash almacena un conjunto de pares (clave,
  13 valor). La clave es única para cada elemento de la tabla y es el dato que se
  14 utiliza para buscar un determinado valor.
  15 
  16 Un diccionario es un ejemplo de estructura que se puede implementar mediante una
  17 tabla de hash. Para cada par, la clave es la palabra a buscar, y el valor
  18 contiene su significado. El uso de esta estructura de datos es tan común en el
  19 desarrollo de aplicaciones que algunos lenguajes las incluyen como tipos básicos
  20 (como python por ejemplo)
  21 
  22 Una alternativa a los algoritmos de búsqueda basados en comparaciones entre las
  23 claves son aquellos que se basan en la trasformación de la clave. Aplican una
  24 operación aritmética sobre la clave para obtener su localización en la
  25 estructura de datos. Esta transformación aritmética sobre la clave se conoce
  26 como la función de hash. 
  27 
  28 <!-- La solución más optima se obtiene cuando la cantidad de claves es acotada. -->
  29 
  30 ## Función de hash
  31 
  32 El trabajo de la función de hash es asignar posiciones de la tabla de hash a las
  33 claves, esta posición debe ser fácil de obtener de manera que no se incremente
  34 el orden al leer y escribir en la tabla de hash. El principal objetivo es que
  35 distribuya uniformemente las claves en las posiciones de la tabla de hash.
  36 
  37 ### Ejemplo de calculo de hash
  38 
  39 Función de dispersión polinómica. Se utiliza comúnmente en algoritmos como
  40 Rabin-Karp para búsqueda de cadenas, o en funciones de hash de tablas hash.
  41 
  42 A continuación se muestra un ejemplo del calculo del hash de una cadena de
  43 caracteres `s`, en función de las constantes `R` y `M`
  44 
  45 ```c++
  46 int hash = 0;
  47 for (int i = 0; i < s.length(); ++i) {
  48     hash = (R * hash + s[i]) % M;
  49 }
  50 ```
  51 
  52 ## Colisiones
  53 
  54 Una colisión es cuando al aplicar la función de hash a dos claves distintas se
  55 obtiene la misma dirección.
  56 
  57 Una posible solución es agregar una lista de valores en la dirección en la que
  58 hay colisión, de esta forma se tienen múltiples valores y una única dirección.
  59 Una contra de esto es que se pierde tiempo de acceso (se pierde el orden de la
  60 tabla de hash) pero puesto a que es poco probable que ocurra colisiones en
  61 temimos de complejidad amortizada resulta beneficioso.
  62 
  63 ### Direccionamiento abierto (o hashing cerrado)
  64 
  65 Cuando dos claves generan la misma dirección de hash provocando una colisión en
  66 la tabla de hash se busca (o sondea) el próximo espacio secuencial disponible en
  67 la tabla de hash. Este sondeo puede ser lineal, cuadrático o puede que se haga
  68 un doble hasheo mediante otra función de hash adicional para resolver las
  69 colisiones. El problema de este tipo de resolución de colisiones es que al
  70 borrar una clave se deben reorganizar todas las claves insertadas mediante este
  71 método.
  72 
  73 #### Sondeo lineal
  74 
  75 En el sondeo lineal el intervalo entre cada intento es constante (típicamente 1)
  76 
  77 #### Sondeo cuadrático
  78 
  79 En el sondeo cuadrático el intervalo entre cada dos intentos aumenta linealmente
  80 (for lo que los indices son descritos por una ecuación cuadrática)
  81 
  82 #### Doble hasheo
  83 
  84 El intervalo entre dos intentos es constante para cada registro pero es
  85 calculado por otra función de hash adicional.
  86 
  87 
  88 ### Direccionamiento cerrado (o hashing abierto)
  89 
  90 En encadenamiento es otro tipo de resolución de colisiones en la cual en lugar
  91 de insertar los elementos en la tabla de hash secuencialmente, se crea una lista
  92 en la posición que colisiona, de esta forma las claves con la misma dirección
  93 quedan ordenadas en la lista.
  94 
  95 El direccionamiento cerrado es la técnica mas simple de encadenamiento, cada
  96 casilla de la tabla de hash referencia una lista con los registros insertados
  97 que colisionan en dicha casilla. La inserción consiste en encontrar la casilla e
  98 insertar al final de la lista, el borrado consiste en buscar y eliminar de la
  99 lista.