大数据算法之BitMap

2018-11-06  本文已影响0人  机器不能学习

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

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

今天以BitMap进行入门。

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

基本原理

其基本原理并不难。

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

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

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

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

存在问题

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

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

上一篇下一篇

猜你喜欢

热点阅读