海量数据去重排序bitmap(位图法)在java中实现的两种方法
在海量数据中查找出重复出现的元素或者去除重复出现的元素是面试中常考的文图。针对此类问题,可以使用位图法来解决。例如:已知某个文件内包含若干个电话号码,要求统计不同的号码的个数,甚至在O(n)时间复杂度内对这些号码进行排序。
位图法需要的空间很少(依赖于数据分布,但是我们也可以通过一些放啊发对数据进行处理,使得数据变得密集),在数据比较密集的时候效率非常高。例如:8位整数可以表示的最大十进制数值为99999999,如果每个数组对应于一个bit位,那么把所有的八进制整数存储起来只需要:99Mbit=12.375MB.
实际上,javajdk1.0已经提供了bitmap的实现BitSet类,不过其中的某些方法是jdk1.4之后才有的。
下面我先自己实现一下bitmap的原理,然后再直接调用jdk的BitSet类分别实现bitmap,方便比较理解:
packageswordoffer; //去除重复并排序 importjava.util.Arrays; importjava.util.BitSet; importjava.util.Random; /** *@authorGavenyeah *@dateTime: *@des: */ publicclassBitMap{ intARRNUM=800; intLEN_INT=32; intmmax=9999; intmmin=1000; intN=mmax-mmin+1; publicstaticvoidmain(Stringargs[]){ newBitMap().findDuplicate(); newBitMap().findDup_jdk(); } publicvoidfindDup_jdk(){ System.out.println("*******调用JDK中的库方法--开始********"); BitSetbitArray=newBitSet(N); int[]array=getArray(ARRNUM); for(inti=0;i总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对毛票票的支持。如果你想了解更多相关内容请查看下面相关链接