数据结构之-BitMap

数据结构之-BitMap
1 一个简单的问题
已知有n个正整数，这些整数范围是[0,100],请你设计一种数据结构，使用数组存储这些数据，并提供两种方法分别是addMember和isExist,下面是这种数据结构的类的定义，
addMember: 加入一个数字
isExist：判断是否存在
2 更快的方法
不论是for循环查找，还是用indexOf时间复杂度都是o(n),加入元素越多，isExist就越慢，我们需要一个时间时间复杂度为o(1)的算法，无论增加多少数据，isExist的执行速度都是常量时间

通过索引操作数据，时间复杂度就是o(1)的
3 更节省空间的算法
2中的反复短发已经很快，但是却面临一个问题，如果数据非常多，多大一个亿，每个整数是4个字节，一个亿个正整数就是4亿字节，1024字节是1kb，1024kb是1M,4亿字节就是381m的内存空间
我们需要一种算法，用很少的空间表达这一亿个数的存在与否

一个整数的字节是8个共32bit

为运算符
1<<2 1向左移动2位
或|
与&
二进制位运算
00000000 1<<2
00000100 8
或 |
00000100
00000010
结果
00000011
与&
00000100
00000010
结果
00000000
二进制的方法

function Bitmap(size) {
    var bit_arr = new Array(size);
    for (var i=0;i<bit_arr.length;i++) {
        bit_arr[i] = 0
    }
    this.addMember = function (member) {
       // 数组在那个索引上
       var arr_index = Math.floor(member/32);
       var bit_index = member%32;

        bit_arr[arr_index] =bit_arr[arr_index]|1<<bit_index;
        // console.log(bit_arr[arr_index]);
        // console.log(1<<bit_index)
        // console.log(bit_arr)
    }
    this.isExist  =function (member) {
        var arr_index = Math.floor(member/32);
        var bit_index = member%32;
        console.log(1<<bit_index);
        console.log(bit_arr[arr_index])
        if (bit_arr[arr_index]&1<<bit_index){
            return true
        }
        return false
    }

}

概念：
不知不觉中，我们实现了一种数据结构，这种数据结构基于位做映射，能够用很少的内存存储数据，和数组不同，他只能存储表示这个数是否存在，可以用于大数据去重，大数据排序，两个集合取交集
bitmap 方法只能操作没有重复的数据如果有重复的数据的操作是无效的除非你是排除重复的数

————————————————————————
5布隆过滤器
前面所讲的bitmap的确很厉害，可是有很强的局限性，bitmap只能处理整数，无法处理字符串，假设你有一个很强大的爬虫,每天爬数以亿计的网页，那么你就需要一种数据结构，能够存储你已经爬取过的url，这样，才不至于重复爬取，

你可能会想到用hash函数对url进行处理，转成整数，这样似乎又可以使用bitmap了，但是这样还是会有问题，假设bitmap能够映射的最大值是m,一个url的hash值
需要对m求模，这样就会产生冲突，而且随着储存数据的增多，冲突率会越来越大。
布隆过滤器的思想非常简单，其基本的思路和bitmap一样，可以吧布隆过滤器看做
是BitMap的扩展，为了解决冲突率，布隆过滤器要求使用k个hash函数，新增一个key时，把key散列成k个整数，然后在数组中将这个k个整数所对应的二进制位设置为1，就说明这个key存在，否则，这个key就不存在
对于一个布隆过滤器，有两个参数需要设置，一个是预估的最多参数的存放量，一个是可以接受的冲突率，
假设预估最多存放n个数据，可已接受的冲突率是p，那么就可以计算出来布隆过滤器所需要的bit位数m，也可以计算所需要的hash函数的个数k，计算公式如下：
m= Math.ceil(max_count(-Math.log(error_rate))/(Math.log(2)Math.log(2)))
k = Math.ceil(Math.log(2)*(max_count/error_rate))
这两个公式知道即可
-———————————————————————————————————
hash 函数
哈希函数就是将某个不定长的对象映射为另一个定长的对象，如果你对这个概念感到困惑，你就换一个理解方式，你给hash函数传入一个字符串，他返回一个整数，为了实现一个布隆过滤器，我们需要你个好的hash函数，计算快，冲突又少，很幸运，开源哈希算法，github上murmurhash的实现