Implementando un HashMap en C [closed]

5 minutos de lectura

avatar de usuario
rayo

¿Cómo hacer para crear un Hashmap en C desde cero como está presente en C++ STL?

¿Qué parámetros se tendrían en cuenta y cómo probaría el hashmap? Como en, ¿cuáles serían los casos de prueba de referencia que ejecutaría antes de poder decir que su mapa hash está completo?

avatar de usuario
Desconocido

Bueno, si conoce los conceptos básicos detrás de ellos, no debería ser demasiado difícil.

Por lo general, 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 clave, procesa la clave con una función hash personalizada que devolverá un número entero. Luego toma el módulo del resultado y esa es la ubicación de su índice de matriz o “cubo”. Luego, verifica la clave sin cifrar con la clave almacenada, y si coincide, entonces encontró el lugar correcto.

De lo contrario, ha tenido una “colisión” y debe rastrear la lista vinculada y comparar las claves hasta que coincida. (tenga en cuenta que algunas implementaciones usan un árbol binario en lugar de una lista enlazada para las colisiones).

Echa un vistazo a esta rápida implementación de tabla hash:

https://attractivechaos.wordpress.com/2009/09/29/khash-h/

  • Además de LL y árboles, puede tener un mapa hash por depósito que use un hash diferente para manejar las colisiones.

    – sudo

    6 de octubre de 2016 a las 3:57


avatar de usuario
TStamper

El mejor enfoque depende de la distribución de claves 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, cuál usar depende del costo de repetir o sondear en comparación con manipular la estructura de datos del depósito extensible.

Pero aquí hay un ejemplo de código fuente de Una implementación de Hashmap en C

  • Como dice la publicación posterior, también debemos manejar la colisión. Además, la implementación hash tiene un table_size que es fijo. Si queremos aumentar dinámicamente el tamaño del hashmap, sin que el programador sepa cómo se hace. ¿Podrías sugerir algo?

    – Rayo

    8 de mayo de 2009 a las 5:58

  • Redimensionar el espacio de claves significa cambiar la función hash o al menos los parámetros de la función y volver a codificar todas las entradas. Cada mapa de tamaño diferente requiere un conjunto diferente de funciones hash para mantener la distribución de claves deseada.

    – T Stamper

    8 de mayo de 2009 a las 6:03

  • El código vinculado fue escrito por un estudiante. “Es la primera estructura de datos que escribí en C”. Por alguna razón, agregó un código de sincronización para que sea seguro para subprocesos.

    – Andreas Haferburg

    4 de abril de 2019 a las 19:52


El objetivo principal de un hashmap es almacenar un conjunto de datos y proporcionar búsquedas en tiempo casi constante utilizando una clave única. Hay dos estilos comunes de implementación de hashmap:

  • Encadenamiento separado: uno con una matriz de cubos (listas enlazadas)
  • Direccionamiento abierto: una sola matriz asignada con espacio adicional para que las colisiones de índice se puedan resolver colocando la entrada en una ranura adyacente.

El encadenamiento separado es preferible si el mapa hash puede tener una función hash deficiente, no es deseable preasignar almacenamiento para ranuras potencialmente no utilizadas, o si las entradas pueden tener un tamaño variable. Este tipo de hashmap puede continuar funcionando de manera relativamente eficiente incluso cuando el factor de carga supera 1,0. Obviamente, se requiere memoria adicional en cada entrada para almacenar punteros de lista enlazada.

Los mapas hash que utilizan direccionamiento abierto tienen ventajas de rendimiento potenciales cuando el factor de carga se mantiene por debajo de un cierto umbral (generalmente alrededor de 0,7) y se utiliza una función hash razonablemente buena. Esto se debe a que evitan posibles errores de caché y muchas asignaciones de memoria pequeñas asociadas con una lista vinculada, y realizan todas las operaciones en una matriz preasignada contigua. La iteración a través de todos los elementos también es más barata. El problema es que los hashmaps que usan direccionamiento abierto deben reasignarse a un tamaño mayor y volver a ajustarse para mantener un factor de carga ideal, o se enfrentan a una penalización de rendimiento significativa. Es imposible que su factor de carga supere 1,0.

Algunas métricas de rendimiento clave para evaluar al crear un hashmap incluirían:

  • Factor de carga máximo
  • Recuento promedio de colisiones en la inserción
  • Distribución de colisiones: la distribución desigual (agrupamiento) podría indicar una función hash deficiente.
  • Tiempo relativo para varias operaciones: poner, obtener, quitar de entradas existentes y no existentes.

Aquí hay una implementación flexible de hashmap que hice. Usé direccionamiento abierto y sondeo lineal para la resolución de colisiones.

https://github.com/DavidLeeds/hashmap

Hay otros mecanismos para manejar el desbordamiento además de la simple lista enlazada de entradas de desbordamiento que, por ejemplo, desperdicia mucha memoria.

El mecanismo a utilizar depende, entre otras cosas, de si puede elegir la función hash y si es posible elegir más de una (para implementar, por ejemplo, hash doble para manejar colisiones); si espera agregar elementos con frecuencia o si el mapa es estático una vez que se llena; si tiene la intención de eliminar elementos o no; …

La mejor manera de implementar esto es pensar primero en todos estos parámetros y luego no codificarlo usted mismo, sino elegir una implementación existente madura. Google tiene algunas buenas implementaciones, por ejemplo http://code.google.com/p/google-sparsehash/

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad