Una función de Hash es una caja negra que tiene como entrada una llave y como salida una dirección h(K)=address\ Ejemplo: h(LOWELL)=4 |  | | --- | Figura 9.1 \ El hashing es similar al indexamiento en el sentido de asociación entre llaves y direcciones relativas de registros\ Pero difiere de los índices en 2 cosas: * La dirección generada por Hash suele ser aleatoria (random). * No hay una relación aparente entre la llave y la localización del registro correspondiente * El Hash permite que 2 llaves puedan producir la misma salida --> direcciones iguales, a esto se le conoce como "colisión". Existen distintos grados de colisiones Figura 9.2 |  | | --- | Figura 9.2 --- ## \ 9\.3 Colisiones En el ejemplo que mostramos en la sección anterior la función de Hash se basa en lo siguiente: * Se obtiene el código ASCII de las 2 primeras letras de la llave * Se multiplican dichos números * La dirección serán los 3 últimos digitos de dicho resultado (esto para limitar nuestro archivo únicamente a 1000 direcciones) | *Llave* | *ASCII* | *Producto* | *Dirección* | | ----- | ----- | -------- | --------- | | BALL | 66 65 | 66x65=4290 | 290 | | LOWELL | 76 79 | 76x79=6004 | 004 | | TREE | 84 82 | 84x82=6888 | 888 | A simple vista notamos que nuestra función de hash es pobre ya que fácilmente habrán llaves que generen la misma dirección ej (OLIVIER), a éstas llaves que generan las mismas direcciones se les llama "sinónimas".\ \ Idealmente lo que se buscaría es tener un "algoritmo de hash perfecto" en el cual no ocurran colisiones y siempre nos garantice direcciones diferentes. Pero desafortunadamente esto es casi imposible, se dice que 1 de 10^120000 algoritmos evitarían dichas colisiones, así que hay que acostumbrarse a la idea de trabajar y lidiar con colisiones.\ \ Para reducir el número de colisiones se tienen algunas soluciones: * Propagar los registros: Buscar funciones que distribuyan muy aleatoriamente los registros podemos evitar "agrupaciones" de llaves que produzcan las mismas direcciones * Usar memoria extra: En el ejemplo anterior planteamos tener una dirección de entre 1000 posibles, el uso de memoria extra se basa en proponer un espacio de direcciones posibles mucho más grande que el número de registros a usar, de modo que si vamos a insertar 100 registros un espacio de 500 direcciones nos una mejor opción de esparcir mejor. * Colocar más de un registro en una dirección: A diferencia de los casos anteriores donde cada dirección almacena únicamente un registro, este concepto se basa en "buckets" o cubetas de datos en cada dirección, ahí se colocan algunos (casi todos) los registros que colisionan de manera que al hacer una búsqueda debemos recuperar la cubeta entera y ahi buscar por el registro deseado. --- ### \ 9\.3.1 Un Algoritmo de Hash > No existe una fórmula "única" para hash, pero el producirla es un algoritmo que básicamente se presenta en 3 pasos:\ > \ > 1) Representar la llave de manera numérica (siempre que no sea de por sí un número)\ > Una buena opción es usar los valores ASCII o bien los Unicode de las letras\ > \ > LOWELL= L O W E L L _ _ _ _ _ _\ > 76 79 87 69 76 76 32 32 32 32 32 32\ > \ > \ > 2) Plegar y Agregar\ > Combinar algunos de estos números para generar pequeños trozos con los que podamos trabajar\ > 76 79 | 87 69 | 76 76 | 32 32 | 32 32 | 32 32\ > \ > De manera que podemos hacer algunas operaciones matemáticas con dichos números para finalmente obtener un número del cual obtendremos la dirección\ > \ > 7679 + 8769 + 7676 + 3232 + 3232 = 30 588\ > \ > Nota: Respecto a la implementación se puede dar el caso de formar números demasiado grandes, tanto que llegue al overflow del tipo de datos que estemos usando. Para solucionar esto podemos usar funciones como el "mod" intermedias para no tener ese problema.\ > \ > 3) Dividir por un número primo y usar el resultado como dirección\ > Los archivos de hash por lo general suelen limitarse a un cierto rango de direcciones posibles para aprovechar mejor el concepto de memoria. de manera que podemos concluir nuestro algoritmo con la fórmula: > > a= s mod n\ > \ > donde a es la dirección resultante, s es la suma o resultado de los pasos anteriores y n el número de direcciones posibles en el archivo\ > \ > Existen innumerables operaciones adicionales que pueden aplicarse en las fórmulas, así como las técnicas para limitar el valor final. Entre ellas se encuentran: elevar a alguna *potencia, raíz cuadrada, convertir los números de base (hexadecimal, octal)*, etc... --- ### \ 9\.3.2 Distribución de un archivo de Hash Continuando con las soluciones para colisiones analicemos el uso de memoria.\ Es posible predecir cómo se van a distribuir los registros en un archivo, esto se hace a través de probabilidades.\ \ *La Distribución e Poisson*\ Probabilidad de que la dirección "b" sea escogida p(B) = b = 1/ N\ \ N= número de direcciones posibles\ \ Probabilidad de que la dirección no sea escogida "a" p(A) = a = (N-1)/N = 1 - (1/N)\ \ La probabilidad de que una posición sea escogida 2 veces p(BB)= b x b\ \ De manera más general tenemos la función de Poisson para nuestros fines: La probabilidad de que "x" registros tengan la misma dirección\ \ p(x)= \[ (r/N)^x e^(- r/N) \]/ x!\ \ donde N es el número de direcciones disponibles\ r es el número de registros a insertar\ x número de registros asignados a alguna dirección\ \ Ejemplo: N=1000 y r= 1000\ \ p(2)= 0.184\ p(3)= 0.061\ p(4)= 0.015 Por otro lado si tenemos N direcciones, el número de direcciones con x colisiones será: Np(x) *Densidad del archivo* Para complementar las probabilidades anteriores podemos analizar otro dato más, la densidad del archivo.\ \ Número de registros / Número de espacios = r / N = densidad del archivo\ \ Si tenemos por ejemplo un archivo donde estamos considerando 100 direcciones (espacios) y tenemos 75 registros entonces la densidad será de:\ \ 75 / 100 = 0.75 = 75 %\ \ Este valor no nos indica el porcentaje de espacio en el archivo real, es solo la relación entre el espacio físico y el de direcciones, **mientras más densa sea la relación mayor será el número de colisiones** --- ### 9.3.3 Resolución de Colisiones por el método "Progressive Overflow" El algoritmo es el más popular y de hecho bastante simple: * Cuando insertamos un registro obtenemos su dirección con la función Hash * Si la dirección esta libre entonces lo insertamos ahí * En caso contrario se busca la primer dirección subsecuente que esté disponible y ahí se inserta * Es importante recordar que nuestro archivo puede (debe en muchos casos) tener un número fijo de direcciones posibles, de manera que si alcanzamos ese número máximo de direcciones entonces debemos buscar un espacio disponible desde el inicio del archivo. Si no queda ninguno entonces quizás tuvimos un error en nuestros cálculos y planeación del archivo. \ Nota: con espacio disponible nos referimos a un espacio "reutilizado" o bien a un espacio vacío, considerando que al eliminar un registro lo que hacemos es reutilizar su espacio. |  | | --- | Figura 9.3\ \ Para las búsquedas * Se obtiene el hash correspondiente * A parte de esa dirección empezamos a buscar por el registro deseado o un espacio vacío * En caso de encontrar un espacio totalmente vacío (nuevo, no reutilizable) entonces podemos afirmar que el registro no se encuentra en nuestro archivo. * Si se alcanza el final del archivo y no se encuentra el registro buscado ni un espacio vacío entonces seguimos buscando desde el inicio del archivo hasta volver al punto de partida (dirección original del hash). |  | | --- | Figura 9.4 --- ### \ 9\.3.4 Almacenando más de un registro por dirección (Buckets) La idea es muy similar a la que se presentó en la sección anterior, sólo existen algunas diferencias notables:\ \ Cada dirección representa una agrupación de datos (cubeta)\ Aquí el porcentaje de colisiones es mayor, así debe ser para aprovechar el concepto de agrupación\ Cuando una cubeta se llena (Figura 9.5) entonces tenemos un overflow y debemos buscar una cubeta disponible para seguir insertando. Afortunadamente este caso no sucede muy a menudo | Green... | Hall... | | | -------- | ------- | --- | | | | | | Jenks... | | | | King... | Land... | Marks... | Figura 9.5\ \ Distribución en el almacenamiento por cubetas\ \ Respecto a las fórmulas de distribución la expresión de Poisson permanece intacta ya que el cálculo es igual solo que aquí nos interesa tener un mayor número de colisiones por dirección.\ \ Por otro lado para la densidad si tendremos una ligera variación, de manera que el cálculo ahora se obtendrá como:\ \ r / bN = Número de registros / (Registros por cubeta X Número de espacios o direcciones ) --- ### \ 9\.3.5 Otras soluciones para las Colisiones a) Double Hashing\ Esta técnica se basa en la idea de generar otro hash, quizás con un formula diferente.\ De manera que si el hash de una llave nos da por ejemplo 5 y ya existe un registro en esa posición entonces se vuelve a aplicar otro hash que nos de una dirección más dispersa por ejemplo 505 y de alguna manera nos garantice menos colisiones. Es importante aclarar que este método no eliminar las colisiones solo no ayuda a encontrar más rapidamente un registro en un espacio donde de antemano sabemos que existe este problema.\ \ b) Chained Progressive Overflow\ La idea, como se muestra en la figura 9.6, es muy simple y se basa en crear una lista ligada entre los distintos registros "sinónimos" de manera que nos podemos desplazar entre aquellos que colisionan de una manera más ágil y natural. |  | | --- | Figura 9.6 c) Chaining with Separate Overflow Area\ Aquí se emplea nuevamente el concepto de encadenamiento a través de una lista ligada, con la diferencia que aquellos registros "sinónimos" que colisionan se van almacenando en un archivo aparte llamado "Overflow Area" (figura 9.7), de manera que en el archivo de datos (Primary Data Area) sólo se almacena la cabeza de dicha lista. |  | | --- | Figura 9.7 d) Scatter Tables\ La idea es parecida a la anterior sólo que aquí no existe un área primaria de datos, sólo apuntadores hacia distintas cabeceras de listas donde residen aquellas llaves "sinónimas" que producen la misma dirección (figura 9.8). Los detalles de implementación pueden variar, desde algunas no muy convenientes como el usar muchos archivos para las diversas listas o bien el implementar en un solo archivo una "lista de listas". |  | | --- | Figura 9.8 ## \ 9\.4 Hash Extendido En la sección 9.3 se mencionaron varias técnicas relacionadas con Hash y el manejo de colisiones, dichas técnicas se basan en una estructura estática, es decir, se calcula un cierto número de posiciones posibles (registros) y en base a este supuesto se amplía el espacio de direcciones y en consecuencia se disminuyen las colisiones.\ Desafortunadamente este esquema "estático" no es muy adecuado para la mayoría de las aplicaciones ya que normalmente no se tiene un estimado del número de registros que se almacenarán, de manera que se requiere una estructura también basada en Hash pero que sea más dinámica de modo que permita "crecer" y adecuarse a cualquier número de elementos; así surge el Hash Extendido.\ \ El algoritmo de Hash Extendido se basa en una estructura de recuperación conocida como "trie", la cual se encuentra dentro del grupo de búsquedas por radio, esto debido a que se presenta un árbol donde cada rama presenta un radio de posibilidades hacia donde moverse. en la figura 9.9 tenemos un radio de 26 que son las letras del alfabeto. |  | | --- | Figura 9.9 \ De manera que el "radio" definirá el número de ramas posibles desde cada nodo, en la figura 9.10 el radio es igual a 10 ya que únicamente emplea números. |  | | --- | Figura 9.10 Para el caso del hash extendido, el trie que se emplea es de radio 2, utilizando como valores posibles el 1 y el 0, significando un bit. De manera que las decisiones de "a qué rama moverse" se definirá como una decisión bit por bit. Así, si buscamos alguna llave cuyo hash produce una dirección empieza con "11" entonces recuperaremos la "cubeta C". |  | | --- | Figura 9.11 \ Como se puede observar le "trie" es una estructura en forma de árbol, pero si tratamos de manejarlo como tal tendremos un caso similar al indexamiento tradicional resultando la mejor solución en un B-Tree. Así que para poder aprovechar los beneficios del trie lo que se hace es representarlo a manera de arreglo de registros (cubetas en la mayoría de los casos) contiguos, al cual se le conoce como "directorio".\ Para convertir el trie a directorio lo primero que se debe hacer es representar el árbol como una estructura completa donde existan al mismo nivel el máximo número de hojas posible (Figura 9.12a), posteriormente elaboramos el arreglo en un archivo de manera que utilicemos todo el rango de direcciones posibles (00,01,10,11) donde cada dirección contendrá un apuntador a la cubeta correspondiente. |  | | --- | Figura 9.12 \ \ Manejando el overflow\ La gran ventaja de esta estructura es que permite de una manera muy sencilla manejar el overflow en las cubetas, supongamos que existe un overflow en "A", gracias a que de antemano teníamos reservada una dirección extra (la rama adicional del árbol) simplemente usamos esa dirección para apuntar hacia la nueva cubeta "D". |  | | --- | Figura 9.13 \ Por otro lado supongamos que el overflow ahora ocurre en "B", a diferencia del ejemplo anterior aquí no tenemos una dirección extra para relacionar a la nueva cubeta "D". De manera que dinámicamente el trie deberá crecer ahora a 3 bits de profundidad (figura 9.14a).\ Nuevamente completamos el árbol de 3 niveles para tener todas las hojas completas (figura 9.14b) y para formar el directorio debemos hacer un "ajuste" de manera que ahora el rango de direcciones irá de 000 hasta 111 (Figura 9.14c). |  | | --- | Figura 9.14\ \ En esta sección se omiten los detalles de implementación, pero cabe mencionar algunos de ellos: * Las direcciones obtenidas por el hash suelen leerse de derecha a izquierda, ejemplo: * Supongamos que vamos a ingresar la llave 45 y su hash nos da 000 0010 1110 0011, naturalmente a la izquierda siempre tendremos muchos 0s así que tendríamos muchas colisiones para esos valores así que se opta por empezar a la derecha, de modo que tendríamos 1100 0111 0100 0000, y por lo tanto la llave se almacenaría en la cubeta "C" * Para la eliminación lo que se debe hacer es "colapsar" el directorio de registros, buscando aquellas cubetas que sean vecinas. --- #### \ Concluyendo: * El concepto de Hash es un caso ideal en la recuperación de información O(1) * El Hash tradicional es muy eficiente pero tiene 2 problemas principales: colisiones y el hecho de ser estático * El Hash extendido es una estructura relativamente moderna que promete ser mejor que el B-Tree, desafortunadamente existen algunas deficiencias que lo limitan, entre ellas: * No se tienen algunas métricas importantes acerca de la capacidad de cada cubeta * Al igual que el BTree la estructura crece dinámicamente y permite búsquedas de alta velocidad; pero para el acceso secuencial (B+Tree) es una ventaja que sigue ganando la competencia. # Enlaces de interés [http://carlosproal.com/ir/ir09.html#:\~:text=9.4%20Hash%20Extendido&text=El%20algoritmo%20de%20Hash%20Extendido,de%20posibilidades%20hacia%20donde%20moverse.](http://carlosproal.com/ir/ir09.html#:\~:text=9.4%20Hash%20Extendido&text=El%20algoritmo%20de%20Hash%20Extendido,de%20posibilidades%20hacia%20donde%20moverse.)

# Hash criptomonedas [https://economipedia.com/definiciones/hash-criptomonedas.html](https://economipedia.com/definiciones/hash-criptomonedas.html)