大数据算法之BitMap

大数据算法：在给定的资源约束下，以大数据为输入，在给定时间约束内可以计算出给定问题加过的算法

所谓的大数据算法，个人理解是在超大数据的情况下，进行的一种牺牲精准而得到时间空间的算法。

今天以BitMap进行入门。

其用处是统计数据。比如想验证用户是否签过到等。

基本原理

其基本原理并不难。

应用的就是一个byte数组，key是int的值，而value是一个byte值。一个byte有8个bit，一个bit可以代表一个数字的有无。那么一个亿的数据量大概12m就可以解决。用byte的好处是极大的节约了内存。

key值一般是具体的数字或者是字符串。他们都可以用取膜或者hash等算法，让他们映射到这个数组中。

需要注意的是，相同字符串或者数字应该使用同样的计算方式，这样保证第二次也能到达该key。

到达该key后，我们可以把value值从0变到1。表示该值来过。但是这里我们需要考虑一下字符串，因为字符串是通过hash计算，常见的hash问题就是碰撞问题。通过一层hash计算，有很大的概率会发生不同的字符串映射到同一个值(当然这个概率还取决于数组的大小)。

存在问题

存在的问题也很吐出，比如hash冲突和数组稀疏。

为了解决这些问题也诞生了相应的算法解决。