算法原理
BitMap的基本思想就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此可以大大节省存储空间。
BitMap可以看成一种数据结构。
假设有这样一个需求：在20亿个随机整数中找出某个数m是否存在其中，并假设32位操作系统，4G内存。
在Java中，int占4字节，1字节=8位（1 byte = 8 bit）。
如果每个数字用int存储，那就是20亿个int，因而占用的空间约为 (2000000000*4/1024/1024/1024)≈7.45G
如果按位存储就不一样了，20亿个数就是20亿位，占用空间约为 (2000000000/8/1024/1024/1024)≈0.233G
优点和缺点
优点：由于采用了Bit为单位来存储数据并建立映射关系来查找位置，因此可以大大减少存储空间，加快在大量数据中查询的时间。（有点哈希表的意思，但哈希中的value值数据类型可以丰富多样，而BitMap最终查到的value只能表示简单的几种状态。）
缺点：BitMap中的查询结果（value）能表达的状态有限，且所有的数据不能重复。即不可对重复的数据进行排序和查找。
算法实现（C#）
.NET中已经实现了BitMap的数据结构——BitArray，建议使用BitMap算法解决问题时直接使用官方的BitArray。
我参照.NET源码实现了一个简化版的BitMap，以int数组存储位值（最多存21亿个位值），代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
class BitMap{ public int Length{ get{ return m_length;} } private int[] m_array; private int m_length; public BitMap(int length): this(length, false) { } //索引根据需求添加 public bool this[int index] { get { return Get(index); } set { Set(index,value); } } //分配空间以容纳长度位值, 位数组中的所有值都设置为defaultValue。 public BitMap(int length, bool defaultValue) { if (length < 0) { throw new ArgumentOutOfRangeException("length", "长度值不能小于0"); } int arrayLength = length > 0 ? (((length - 1) / 32) + 1) : 0; m_array = new int[arrayLength]; m_length = length; int fillValue = defaultValue ? unchecked(((int)0xffffffff)) : 0; for (int i = 0; i < m_array.Length; i++) { m_array[i] = fillValue; } } //返回位置索引处的位值。 public bool Get(int index) { if (index < 0 || index >= Length) { throw new ArgumentOutOfRangeException("index", "索引值超出范围"); } return (m_array[index / 32] & (1 << (index % 32))) != 0; } //将位置索引处的位值设置为value。 public void Set(int index, bool value) { if (index < 0 || index >= Length) { throw new ArgumentOutOfRangeException("index", "索引值超出范围"); } if (value) { m_array[index / 32] |= (1 << (index % 32)); } else { m_array[index / 32] &= ~(1 << (index % 32)); } }} |
算法应用
问题1：
给40亿个不重复的unsigned int的整数，没有排过序，然后再给一个数，如果快速判断这个数是否在那40亿个数当中。（解决海量数据中的查询问题）
问题1解法：
建立一个位集合，全部初始化为0。遍历40亿个不重复的整数，通过上述提供的一种映射（每个不重复的整数映射到给定的位）找到其位的位置，标记为1。判断这个数是否在大整数集合中，即通过映射关系计算此整数的位位置，检查是否为1，若为1，则存在，若为0，则不存在
问题2：
数据库里存了很多800电话号码，数量特别大，以至于内存放不下，如何排序，时间比空间更重要？电话号码类似于800-810-5555。（高效排序）
问题2解法：
其实就是不重复的任意7位数及其之内的排序问题。我们用1位来表示电话是否出现，遍历整个电话号序列，设置相应的位，遍历位图收集位被设置的号码即可。查看上述的实现代码
以上就是c# 实现位图算法（BitMap）的详细内容，更多关于c# 位图算法的资料请关注服务器之家其它相关文章！
原文链接：https://www.cnblogs.com/timefiles/p/BitMap.html
