先看一个题目:
给你一堆西安市的电话号码列表,数量大概在千万级,
要求从中找出所有重复的电话号码,需要时间复杂度尽可能小。
目前西安市的电话号码大概都以8开头,为8位,也就是
类似于82678578这样子
二重暴力搜索时间复杂度太高,这里我们不予考虑。
容易想到的办法就是建立一个标志数组,
int boolean都行,用相应的位置值来代替这个号码是否出现,
根据数组的可直接存取特性,来提高效率。
但是你是否想过或测试过
int[] a = new int[100000000];
boolean[] a = new boolean[100000000];
这样类似的语句是否可以通过编译并且执行。
再仔细思考下,就会发现,int型的字段太过于占空间,我们只需要知道这个号码存在与否,
所以最简单的0和1就够用了,能表示0和1的最小存储单位是什么呢?
是内存中的一位。
OK,这就是bitmap的思想。
将西安市的电话号码去掉开头的8,就可以将其映射到一个1到10000000的数组中。
8bit是1byte,1024byte是1kb,1024kb是1mb
所以10000000个bit占用的空间为
10000000/8/1024/1024mb大概为1mb多些,
这对于现在大家动不动几G的内存来说,完全是小菜一碟。
同时,java中也有对应的实现,java.util.BitSet,
完全是为这个量身定做的java类。
这个类从jdk1.0开始就有了,不过其中的某些方法是jdk1.4以后才有的,
大家用的时候要当心。
另外BitSet是非线程安全的,需要外部同步。
下面的简单代码给出了BitSet的例子:
print?
//创建一个具有10000000位的bitset 初始所有位的值为false
java.util.BitSet bitSet = new java.util.BitSet(10000000);
//将指定位的值设为true
bitSet.set(9999, true);
//输出指定位的值
System.out.println(bitSet.get(9999));
System.out.println(bitSet.get(9998));
分享到:
相关推荐
RoaringBitmap, 在Java中,一个更好的压缩 bitset RoaringBitmap Bitsets,也称为位图,通常用作快速数据结构。 不幸的是,他们可以使用太多的内存。 为了补偿,我们经常使用压缩位图。咆哮位图是压缩位图,它比传统...
Bitmap方法C语言实现,支持插入、删除和查找功能。
软件开发网在此之前给大家介绍过图片加载框架Glide的基本用法介绍,大家可以先参考一下,本篇内容更加深入的分析了Glide获取图片Path、Bitmap用法,以及实现的代码分析。 1. 获取Bitmap: 1)在图片下载缓存好之后...
Bitmap-->List
今天小编就为大家分享一篇关于海量数据去重排序bitmap(位图法)在java中实现的两种方法,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
bitmap是个省空间的数据结构,我的c实现
BitMap,BitMapFactory,android 主要为了处理图片,分享下
完全基于java实现的把一组图片转换为图片,值得收藏!
android Bitmap相关知识介绍~~~
Bitmap位图旋转范例 一个完整工程
标签:roaringbitmap、RoaringBitmap、中文文档、jar包、java; 使用方法:解压翻译后的API文档,用浏览器打开“index.html”文件,即可纵览文档内容。 人性化翻译,文档中的代码和结构保持不变,注释和说明精准翻译...
java实现的Bitmap类 用于自动生成Bitmap文件头和填充调色板等,目前只支持8位256色的Bitmap
android下的图片序列转换为视频,已精简so包,完全由javacv实现从图片或者Bitmap到视频的录制,有完整配置界面,支持录像和暂停以及重启需要导入lib文件夹下的javacv.jar和javacpp.jar两个包.rar,太多无法一一验证...
纯C++代码写文件的形式生成Bitmap。对于理解Bitmap的格式有着非常好的效果。 纯C++代码写文件的形式生成Bitmap。对于理解Bitmap的格式有着非常好的效果。
Linux中软件RAID的Bitmap功能实现分析.pdf
标签:roaringbitmap、RoaringBitmap、中英对照文档、jar包、java; 使用方法:解压翻译后的API文档,用浏览器打开“index.html”文件,即可纵览文档内容。 人性化翻译,文档中的代码和结构保持不变,注释和说明精准...
Transparent Bitmap实现透明的位图(7KB)
NULL 博文链接:https://chen592969029.iteye.com/blog/749100
jar包,官方版本,自测可用
一个基于android平台Bitmap 工具类,一个基于android平台Bitmap 工具类,一个基于android平台Bitmap 工具类,一个基于android平台Bitmap 工具类,一个基于android平台Bitmap 工具类,一个基于android平台Bitmap 工具...