¿Cómo crear un Hashmap en C desde cero? ¿Cuáles serían los parámetros tomados en consideración y qué cómo probarías el hashmap en cuanto a qué tan bueno es? Como en lo que serían los casos de prueba de referencia que necesita ejecutar antes de decir que su mapa hash está completo.Implementación de un HashMap
Bueno, si usted sabe los fundamentos detrás de ellos, no debería ser demasiado difícil.
En general, usted crea una matriz llamada "cubos" que contienen la clave y el valor, con un puntero opcional para crear una lista vinculada.
Cuando accede a la tabla hash con una tecla, procesa la tecla con una función hash personalizada que devolverá un número entero. A continuación, toma el módulo del resultado y esa es la ubicación de su índice de matriz o "cubo". Luego, comprueba la clave sin hit con la clave almacenada y, si coincide, encuentras el lugar correcto.
De lo contrario, ha tenido una "colisión" y debe rastrear a través de la lista vinculada y comparar claves hasta que coincida. (tenga en cuenta que algunas implementaciones utilizan un árbol binario en lugar de una lista vinculada para colisiones).
Compruebe hacia fuera esta aplicación tabla hash rápido:
El mejor enfoque depende de la distribución de clave esperada y el número de las colisiones. Si se esperan relativamente pocas colisiones, realmente no importa qué método se use. Si se esperan muchas colisiones , el uso dependerá del costo del reacondicionamiento o del sondeo en comparación con la manipulación de la estructura de datos del cucharón extensible.
Pero aquí es ejemplo de código fuente de An Hashmap Implementation in C
Como el post más adelante dice que necesitamos para manejar la colisión también. Además, la implementación hash tiene un table_size que es como fijo. Si queremos aumentar dinámicamente el tamaño del hashmap, sin que el programador sepa cómo se hace. ¿Podrías sugerir algo? – Thunderboltz
Cambiar el tamaño del espacio clave significa cambiar la función hash o al menos los parámetros de la función y volver a procesar todas las entradas. Cada mapa de diferentes tamaños requiere un conjunto diferente de funciones hash para mantener la distribución de claves deseada. – TStamper
El enlace ahora está roto –
hay otros mecanismos para manejar el desbordamiento que la simple lista enlazada de mentalidad de las entradas de desbordamiento, que, por ejemplo, desperdicia mucha memoria.
Qué mecanismo utilizar dependerá entre otras cosas si puede elegir la función de hash y posiblemente elegir más de uno (implementar, por ejemplo, doble hashing para manejar colisiones); si esperas a menudo agregar elementos o si el mapa está estático una vez que se completa; si tiene la intención de eliminar elementos o no; ...
La mejor manera de implementar esto es primero pensar en todos estos parámetros y luego no codificarlo usted mismo sino elegir una implementación existente madura. Google tiene algunas implementaciones buenas, p. http://code.google.com/p/google-sparsehash/
Si bien es relevante para los algoritmos, sparsehash es una implementación en C++ de un hashmap. Si está buscando algoritmos prematrimoniales puros C, busque otro lugar. –
El objetivo principal de un hashmap es almacenar un conjunto de datos y proporcionar búsquedas de tiempo casi constante con una clave única. Hay dos estilos comunes de aplicación HashMap:
El encadenamiento independiente es preferible si el hashmap puede tener una función hash pobre, no es deseable preasignar el almacenamiento para las ranuras potencialmente no utilizadas o las entradas pueden tener un tamaño variable. Este tipo de hashmap puede continuar funcionando relativamente eficiente incluso cuando el factor de carga excede 1.0.Obviamente, se requiere memoria extra en cada entrada para almacenar punteros de listas vinculadas.
Los Hashmaps que usan direccionamiento abierto tienen ventajas potenciales de rendimiento cuando el factor de carga se mantiene por debajo de un cierto umbral (generalmente alrededor de 0,7) y se usa una función hash razonablemente buena. Esto se debe a que evitan posibles fallas de caché y muchas asignaciones de memoria pequeñas asociadas con una lista vinculada, y realizan todas las operaciones en una matriz contigua y preasignada. La iteración a través de todos los elementos también es más barata. El truco es que los hashmaps que utilizan el direccionamiento abierto deben ser reasignados a un tamaño mayor y redirigidos para mantener un factor de carga ideal, o enfrentan una penalización de rendimiento significativa. Es imposible que su factor de carga exceda 1.0.
Algunos indicadores clave de rendimiento para evaluar la hora de crear un mapa hash incluiría:
Aquí hay una implementación flexible de hashmap que hice. Utilicé el direccionamiento abierto y el sondeo lineal para la resolución de colisiones.
Además de LLs y árboles, puede tener un mapa hash por cubo que use un hash diferente para manejar colisiones. – sudo