《javascript数据结构和算法》读书笔记（4）：BitMap
《javascript数据结构和算法》读书笔记（4）：BitMap
BitMap
引子
有n个整数，范围是[0,100]。试设计一种数据结构。储存这些数据，并提供两种方法。分别是
- add
- isExist
时间复杂度O(n)的实现
class FindClass{
constructor(){
this.datas=[]
}
add(item){
this.datas.push(item)
}
isExist(item){
return this.datas.indexOf(item)>=0;
}
}
var a= new FindClass();
a.add(1)
a.add(2)
console.log(a.isExist(2))复杂度的优化：活用索引值
不论是for循环还是indexof，元素越多，越慢。试实现时间复杂度为O（1）的算法。
改进add的逻辑：
class FindClass{
constructor(){
this.datas=new Array(100).fill(0)
}
add(item){
this.datas[item]=1;
}
isExist(item){
return this.datas[item]==1;
}
}
var a= new FindClass();
a.add(1)
a.add(2)
console.log(a.isExist(2))怎样更好节省内存：数据压缩
上面的操作把复杂度大大降低了。但是假设我存一亿个数，每个整数需要占用4个字节的空间。那么这个数组就占据381M的空间。如何通过合适的方法节省这么多的空间呢？
街边有8盏路灯，其中第2,5,7,8号是开着的。如何设计一种方法，表示这八盏灯的状态？
- 2578，
- 另外一种是75,转化为二进制就是=>01001011，刚好反映了路灯的状态。因此只要8个bit就可8盏灯的全部情况！
现在继续来看isExit。
设 value=00000000000000000000000000000000,add(0)存进来时，就把value的第 0位设为1
00000000 00000000 00000000 00000001此时value实际为1（10进制）
如果add(3)，就把value的第 3位设为1
00000000 00000000 00000000 00001001此时value为9，因此9可以表示0和3都存在的状态。
同理我可以最多add(31)=>于是这个32位的二进制数value，可以表示0-31数字的存在与否。
如果我以一个长度为10的数组把value存起来。那么这个数据结构就能够支持add(319)的储存。
datas[0]=>支持31
datas[1]=>支持32=>63
...
data[9]=>支持最多319因此，空间使用率为原来的1/32。
位运算
如何对整数的二进制位进行操作？这就是位运算的内容
按位与 &
相同二进制位的数字都为1时，则结果为1，否则为0
3&7=
3=>011
7=>111
结果=>011=>3
∴3&7=3按位或 |
相同二进制位的数字有一个为1时，则结果为1，否则为0，实际上就是加法
5|8=5=>01018=>10005|8=>1101=>13
左移 <<
二进制向左移动n位，在后面加n个0
3<<1=
3=>11=110=6以上运算优先级都是一致的。
练习
一组数为3,9,19,20，尝试以一个整数表示以上4位数.
var value=0;
value=value|1<<3
value=value|1<<9
value=value|1<<19
value=value|1<<20
console.log(value)//1573384这里value|1表示1.1左移n位，换算为2^n
因此，这个整数的数学意义实际上是：2^3+2^9+2^19+2^20=1573384
console.log(Math.pow(2,3)+Math.pow(2,9)+Math.pow(2,19)+Math.pow(2,20))BitMap的实现
来实现真正的BitMap吧！
回到需求，4个整数足以放表示128个数的存在状态。（长度为4的数组）；
根据item的范围用求模的方式获取index。
class FindClass{
constructor(){
this.datas=new Array(4).fill(0)
}
add(item){
let arr_index=parseInt(item/32);//确定所在数组索引
let bit_index=item%32;//确定二进制位移
let value=this.datas[arr_index];
value=value|1<<bit_index;
this.datas[arr_index]=value;
}
isExist(item){
// 检验对应位数
let arr_index=parseInt(item/32);//确定所在数组索引
let bit_index=item%32;//确定二进制位移
let value=this.datas[arr_index]&1<<bit_index;
return value!==0 ;//实际上就是1
}
}
var a= new FindClass();
a.add(1)
a.add(2)
console.log(a.isExist(2))//true
console.log(a.isExist(3))//false以上数据结构基于位操作作为映射，能够以很少的内存去操作数据（只能表示某个数存在）。最大值支持15亿的集合。可以用于大数据去重，大数据排序。两个集合取交集。等等。
应用
大数据排序
比如：有多达10亿个的无序整数，最大值为15亿，请对这10亿个数进行排序
为了简化这个思路。现将数组转化为：
var arr=[0,6,88,7,73,34,10,99,22]//最大99
var bit_map= new FindClass();
for(let i=0;i<arr.length;i++){
bit_map.add(arr[i])
}
var sort_arr=[];
for(let i=0;i<99;i++){
if(bit_map.isExist(i)){
sort_arr.push(i)
}
}
console.log(sort_arr)//[ 0, 6, 7, 10, 22, 34, 73, 88 ]缺陷是：不能有重复数据。如果数据很少差异太大，那么就空间利用率就太低了。
布隆过滤器
如果你写了一个强大的爬虫程序，每天可以爬取数以亿计的url。那么你需要一个结构，存储他们，同时才不至于重复爬取。
哈希函数
一个思路在于用hash函数对url进行处理。
他可以把一个不定长的对象转化为定长的对象。在题目中，是转化为定长的整数。
但是哈希函数可能会超过最大映射值M，同时转换可能产生冲突。
一次不靠谱
扩展
布隆过滤器实际上是bitmap的扩展。
为了解决冲突，布隆过滤器要求使用k个hash函数，新增一个key时，把key散列为k个整数。
然后在数组中将这k个整数所对应的二进制位数设置为1
如果判断key是否存在，还是对key进行散列。判断对应的整数位数是否都为1，如果是，这个key就存在了。
对于布隆过滤器，需要设置两个参数，一个是最大熟练n，一个是容忍的冲突率p。那么可以求得k值：
m=-(n*(ln^p))/（(ln2)^2）
k=(ln^2)*(m/n)下面就来实现吧
class BoolmFilter{
constructor(max_count,error_rate){
this.bit_map=[]//位图映射变量
this.max_count=max_count;//最多可存放的数量
this.error_rate=error_rate;//错误率
this.bit_size=Math.ceil(this.max_count*(-Math.log(this.error_rate)/(Math.log(2)*Math.log(2))));//变量长度
this.hash_count=Math.ceil(Math.log(2)*(this.bit_size/this.max_count))//哈希数量
}
//把key散列为k个值
set_bit(bit){
let arr_index=Math.floor(bit/32);
let bit_index=Math.floor(bit%32);
this.bit_map[arr_index]|=(1<<bit_index);
}
// 读取位的值
get_bit(bit){
let arr_index=Math.floor(bit/32);
let bit_index=Math.floor(bit%32);
return this.bit_map[arr_index]&=(1<<bit_index)
}
add(key){
if(this.isExist(key)){
return -1
}
for(let i=0;i<this.hash_count;i++){
// 获取哈希，传不同的种子（i）
let hash_value=murmurhash3_32_gc(key,i);
this.set_bit(Math.abs(Math.floor(hash_value%(this.bit_size))));
}
}
}