examples - hashtable c
Implementando un HashMap (4)
Bueno, si sabes lo básico detrás de ellos, no debería ser demasiado difícil.
En general, usted crea una matriz llamada "cubos" que contiene la clave y el valor, con un puntero opcional para crear una lista vinculada.
Cuando accede a la tabla hash con una clave, procesa la clave con una función hash personalizada que devolverá un 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).
Mira esta rápida implementación de la tabla hash:
¿Cómo crear un Hashmap en C desde cero? ¿Cuáles serían los parámetros tomados en consideración y cómo evaluarí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.
El mejor enfoque depende de la distribución de clave esperada y del número de colisiones. Si se esperan relativamente pocas colisiones, realmente no importa qué método se use. Si se esperan muchas colisiones, entonces, cuál usar dependerá del costo de reafilar o probar, en lugar de manipular la estructura de datos de cubeta extensible.
Pero aquí está el ejemplo del código fuente de una implementación de Hashmap en C
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 implementación de hashmap:
- Cadena separada: una con una variedad de cubos (listas enlazadas)
- Direccionamiento abierto: una única matriz asignada con espacio adicional para que las colisiones de índice se puedan resolver colocando la entrada en una ranura adyacente.
Se prefiere el encadenamiento independiente si el hashmap puede tener una función hash deficiente, 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 de rendimiento potencial cuando el factor de carga se mantiene por debajo de un cierto umbral (generalmente alrededor de 0.7) y se usa una función de 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.
Algunas métricas de rendimiento clave para evaluar al crear un hashmap incluirían:
- Factor de carga máximo
- Recuento de colisiones promedio en la inserción
- Distribución de colisiones: la distribución desigual (agrupamiento) podría indicar una función hash pobre.
- Tiempo relativo para varias operaciones: poner, obtener, eliminar entradas existentes y no existentes.
Aquí hay una implementación de hashmap flexible que hice. Utilicé el direccionamiento abierto y el sondeo lineal para la resolución de colisiones.
Existen otros mecanismos para manejar el desbordamiento que la simple lista vinculada vinculada de entradas de desbordamiento que, por ejemplo, desperdicia mucha memoria.
¿Qué mecanismo utilizar depende entre otras cosas si puede elegir la función 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 forma 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, por ejemplo, http://code.google.com/p/google-sparsehash/