¿Qué es el mapa de bits? ¿Dónde lo usamos?

Los mapas de bits se encuentran entre las estructuras de datos más interesantes / útiles:

1. Mapa de bits Un mapa de bits le permite conocer la presencia de una característica en un conjunto de entidades de una manera muy resumida. Así que imagine que queremos anotar el característico “ciudadano de Barcelona” a la población mundial. Podríamos dar una identificación a cada miembro de la población mundial que mapea una posición en un vector de bits. Estableceremos el bit en 1 si la persona tiene la característica (es decir, ciudadano de Barcelona) y 0 en caso contrario.
2. Características . Un mapa de bits tiene algunas características interesantes: (i) ocupan un espacio mínimo, por lo que, dada la característica “ciudadano de Barcelona”, naturalmente ocupan asintóticamente un bit por ID, (ii) son altamente compresibles, por lo tanto, dada la gran cantidad de valores 0 , estos pueden estar muy comprimidos, reduciendo la cantidad de bits por ID mucho más, (iii) son fáciles de mapear, ya que la ID se puede usar para direccionar el bit en un mapeo directo.
3. Uso de mapas de bits . Se pueden usar en muchas situaciones diferentes, como en las implementaciones de operaciones de unión de bases de datos relacionales (consulte Índices de unión en uno de los documentos fundamentales sobre ellas), o para representar bases de datos de gráficos (consulte Gestión eficiente de gráficos basada en índices de mapa de bits).

De wiki: en informática, un mapa de bits es una asignación de algún dominio (por ejemplo, un rango de enteros) a bits, es decir, valores que son cero o uno. También se llama matriz de bits o índice de mapa de bits.

Puede usar un mapa de bits como un depósito para indicar si existe un número entero.

Por ejemplo: darle 1 millón de enteros (entre 1 y 10 millones). Luego, proporcione un número entero aleatorio y determine si existe en los números enteros. Y luego puede usar un mapa de bits para grabar estos números enteros. Y resuelva la consulta en O (1).

Los mapas de bits son listas ordenadas súper eficientes. Como los bits están estrictamente ordenados, se pueden agrupar sin pérdida de generalidad. Los grupos de bits pueden representar números, y los números pueden representar colores, presiones o profundidades, o respuestas sí / no, o cualquier otro aspecto cuantificable.

A veces, los mapas de bits se utilizan para representar imágenes, dividiendo la imagen en filas que se escanean de izquierda a derecha, o de derecha a izquierda, o en algún otro orden predeterminado. Los grupos de bits dentro del mapa de bits representan colores.

Otras veces, los mapas de bits se utilizan para representar montañas, valles y llanuras, al colocar una cuadrícula, nuevamente dividida en filas que se escanean en un orden predeterminado. y almacenar la altura del mundo en cada punto de la cuadrícula en la parte correspondiente del mapa de bits.

Otras veces, los mapas de bits se utilizan para realizar un seguimiento de, por ejemplo, qué espacios de estacionamiento o casilleros de almacenamiento están disponibles. Si cada casillero tiene su propia posición en la lista, podemos usar el número de casillero para ver rápidamente si el mapa de bits para las asignaciones de casilleros tiene un “0” o un “1” en la posición correspondiente. Simplemente aceptamos que (por ejemplo) “0” significa que el casillero no está en uso y “1” significa que el casillero está en uso.