performance - resolucion - tablas hash c++
Tabla hash: ¿por qué es más rápido que las matrices? (6)
¿Por qué [es] que [las tablas hash realizan búsquedas por clave mejor que las matrices (O (1) vs O (n))]? Quiero decir: tengo una clave, lo tengo ... Tengo el hash ... ¿no debería el algoritmo comparar este hash contra el hash de cada elemento? Creo que hay algún truco detrás de la disposición de la memoria, ¿no?
Una vez que tenga el hash, le permite calcular una ubicación "ideal" o esperada en la matriz de cubetas: comúnmente:
cubo ideal = hash% num_buckets
El problema es que es posible que otro valor ya se haya asignado a ese depósito, en cuyo caso la implementación de la tabla hash tiene dos opciones principales:
1) prueba otro cubo
2) deje que varios valores distintos "pertenezcan" a un segmento, tal vez haciendo que el contenedor mantenga un puntero en una lista vinculada de valores
Para la implementación 1, conocida como direccionamiento abierto o hash cerrado , saltas sobre otros segmentos: si encuentras tu valor, genial; si encuentra un segmento nunca utilizado, puede almacenar su valor allí si lo inserta o sabe que nunca encontrará su valor al realizar la búsqueda. Existe la posibilidad de que la búsqueda sea aún peor que O (n) si la forma en que atraviesa los segmentos alternativos termina buscando en el mismo contenedor varias veces; por ejemplo, si usa sondeos cuadráticos , intente con el índice de cubeta ideal +1, luego +4, luego +9, luego +16 y así sucesivamente, pero debe evitar el acceso al cubo fuera de límites usando, por ejemplo, % num_buckets , por lo que si hay, por ejemplo, 12 cubos, luego ideal + 4 e ideal + 16 buscan en el mismo cubo. Puede ser costoso rastrear los cubos que se han buscado, por lo que puede ser difícil saber cuándo darse por vencido también: la implementación puede ser optimista y asumir que siempre encontrará el valor o un cubo no usado (arriesgando el giro para siempre), puede tener un contador y después de un umbral de intentos, renunciar o iniciar una búsqueda lineal por segmento.
Para la implementación 2, conocida como direccionamiento cerrado o encadenamiento separado , tiene que buscar dentro del contenedor / estructura de datos de los valores que todos los hashed al cubo ideal. Cuán eficiente es esto depende del tipo de contenedor utilizado. En general, se espera que el número de elementos que colisionan en un cubo sea pequeño, lo que es cierto de una buena función hash con entradas no adversarias, y normalmente es lo suficientemente fiel incluso para una función hash mediocre especialmente con un número primo de cubetas. Por lo tanto, a menudo se usa una lista vinculada o una matriz contigua, a pesar de las propiedades de búsqueda O (n): las listas vinculadas son fáciles de implementar y operar, y las matrices empaquetan los datos para mejorar la ubicación de memoria caché y la velocidad de acceso. Sin embargo, el peor caso posible es que todos los valores de la tabla se procesen en el mismo depósito, y el contenedor en ese depósito ahora contiene todos los valores: toda la tabla hash es entonces tan eficiente como el contenedor del contenedor. Algunas implementaciones de tablas hash de Java han comenzado a usar árboles binarios si la cantidad de elementos hash en los mismos intervalos supera un umbral, para asegurarse de que la complejidad nunca sea peor que O (log2n).
Los hash de Python son un ejemplo de 1 = direccionamiento abierto = hashing cerrado. C ++ std::unordered_set es un ejemplo de direccionamiento cerrado = encadenamiento separado.
En los casos en que tengo una clave para cada elemento y no sé el índice del elemento en una matriz, las tablas tienen un rendimiento mejor que las matrices (O (1) frente a O (n)).
¿Porqué es eso? Quiero decir: tengo una clave, lo tengo ... Tengo el hash ... ¿no debería el algoritmo comparar este hash contra el hash de cada elemento? Creo que hay algún truco detrás de la disposición de la memoria, ¿no?
En los casos en que tengo una clave para cada elemento y no sé el índice del elemento en una matriz, las tablas tienen un rendimiento mejor que las matrices (O (1) frente a O (n)).
La búsqueda de la tabla hash realiza O (1) en el caso promedio. En el peor de los casos, la búsqueda de la tabla hash realiza O (n): cuando tiene colisiones y la función hash siempre devuelve la misma ranura. Uno puede pensar "esta es una situación remota", pero un buen análisis debería considerarlo. En este caso, debe recorrer todos los elementos como en una matriz o listas vinculadas (O (n)).
¿Porqué es eso? Quiero decir: tengo una clave, lo tengo ... Tengo el hash ... ¿no debería el algoritmo comparar este hash contra el hash de cada elemento? Creo que hay algún truco detrás de la disposición de la memoria, ¿no?
Tienes una clave, hash ... tienes hash: el índice de la tabla hash donde el elemento está presente (si se ha localizado antes). En este punto, puede acceder al registro de la tabla hash en O (1). Si el factor de carga es pequeño, es poco probable que vea más de un elemento allí. Entonces, el primer elemento que veas debe ser el elemento que estás buscando. De lo contrario, si tiene más de un elemento, debe comparar los elementos que encontrará en la posición con el elemento que está buscando. En este caso, tiene O (1) + O (number_of_elements).
En el caso promedio, la complejidad de búsqueda en la tabla hash es O (1) + O (factor_carga) = O (1 + factor_de_carga).
Recuerde, load_factor = n en el peor de los casos. Entonces, la complejidad de la búsqueda es O (n) en el peor de los casos.
No sé a qué te refieres con "truco detrás de la disposición de la memoria". Bajo algunos puntos de vista, la tabla hash (con su estructura y resolución de colisiones mediante encadenamiento) puede considerarse un "truco inteligente".
Por supuesto, los resultados del análisis de la tabla hash pueden ser probados por las matemáticas.
Creo que respondiste tu propia pregunta allí. "no debería el algoritmo comparar este hash contra el hash de cada elemento". Eso es lo que hace cuando no conoce la ubicación del índice de lo que está buscando. Compara cada elemento para encontrar el que está buscando:
Por ejemplo, digamos que estás buscando un elemento llamado "Coche" dentro de una matriz de cadenas. Necesitará revisar cada elemento y marcar el ítem. Mantenga () == "Coche" .Hash () para descubrir que ese es el ítem que está buscando. Obviamente, no utiliza el hash cuando busca siempre, pero el ejemplo permanece. Entonces tienes una tabla hash. Lo que hace una tabla hash es crear una matriz dispersa, o a veces una serie de cubos como el tipo mencionado anteriormente. Luego usa el "Carro" .Hash () para deducir en qué parte de la matriz dispersa está el elemento "Coche". Esto significa que no tiene que buscar en toda la matriz para encontrar su artículo.
Las tablas hash son un poco más complejas. Ponen elementos en diferentes cubos basados en su hash% algún valor. En una situación ideal, cada cubo contiene muy pocos elementos y no hay muchos cubos vacíos.
Una vez que conoce la clave, calcula el hash. Basado en el hash, sabes qué cubo buscar. Y como se indicó anteriormente, la cantidad de elementos en cada segmento debe ser relativamente pequeña.
Las tablas hash están haciendo mucha magia internamente para asegurarse de que los cubos sean lo más pequeños posible sin consumir demasiada memoria para los cubos vacíos. Además, mucho depende de la calidad de la tecla -> función hash.
Wikipedia proporciona una descripción muy completa de la tabla hash .
Una Tabla hash no tendrá que comparar todos los elementos en la Hash. Calculará el hashcode según la clave. Por ejemplo, si la clave es 4, entonces hashcode puede ser - 4 * x * y. Ahora el puntero sabe exactamente qué elemento elegir.
Mientras que si ha sido una matriz, tendrá que atravesar toda la matriz para buscar este elemento.
Con matrices : si conoce el valor, debe buscar en promedio la mitad de los valores (a menos que estén ordenados) para encontrar su ubicación.
Con hash : la ubicación se genera en función del valor. Entonces, dado ese valor nuevamente, puede calcular el mismo hash que calculó al insertar. A veces, más de 1 valor da como resultado el mismo hash, por lo que en la práctica cada "ubicación" es en sí misma una matriz (o lista vinculada) de todos los valores que hash a esa ubicación. En este caso, solo se necesita buscar esta matriz mucho más pequeña (a menos que sea un hash incorrecto).