数组/集合压缩技术

一个数据可能关联了多个年级，一般的做法是建一个年级关联表。数据为
data_key gradeId
1           1
1           3
2           1
这样的。但还有一种做法是把多个年级压缩为一个字段，不同值表示不同年级的组合。
压缩函数:
Integer zip(List gradeIds){
   int zip=0;
   for(Integer gradeId:gradeIds){
       zip+=Math.pow(2,gradeId);
   }
   return zip;

}
检查是否包含函数:
public boolean existGrade(Long gradeId,Integer gradeIds){
   if(gradeId ==null) {
        return false;
   }
   int g = (int)Math.pow(2,gradeId.intValue());
   if((g & gradeIds) ==g) return true;
   return false;

}

这里扩展一下按位与的运算”(g & gradeIds)==g“,表示gradeIds里包含g。为什么是这样算的？首先,g是2的n次，这个数在二进制形式上是一定是第1位为1,后面全是0,如1000. 其次,gradeIds的值是多个2的n(n>=1)次方的和,二制进形式没有明显规律。最后，按位与(&)的二进制性质有什么，0与任何数与都是0,1与1按位与才会得到1。那么，也可以这么写(g&gradeIds)!=0 。为什么？因为g除了第1位，别的位按位与的结果已经确定，都是0。而第1位，与之对应的gradeIds的所在位有两种可能，一种是1,另一种是0。就是说最后的结果只会有两种可能，要么是10000(g),要么是00000(0)。

这种方法，适合多少个数据以内的压缩?
log2(N)=Integer.MAX_VALUE
n=Math.log(Integer.MAX_VALUE)/Math.log(2)
30个以内的数都可以用这种方法。当然，用long的话，可以再扩点。

数据多时可以用布隆过滤器(BloomFilter),先把原始数据压缩到一个大的数里，比如Integer可以容纳20亿数，那么就对应了20亿个原始数据。
再后数据来了，要判断是否存在，先计算它映射击的数，如果这个数存在(可用二进制的位与计算)，那么可能存在此原始数据。如果数不存在，那么原始数据一定不存在。

文/程忠浏览次数：0次 2019-11-08 15:29:33

数组/集合压缩技术

相关阅读