`

JAVA海量数据处理之 BitMap

阅读更多

 路漫漫其修远兮,吾将上下而求索。想要更快,就要深入挖掘 JAVA 基础的数据结构,从来分析出所编写的 JAVA 代码为什么把内存耗尽,思考有什么办法可以节省内存呢? 啊哈!算法。这里采用了 BitMap 思想。

 

首先来看一个实验:

指定 VM 参数大小: -Xms256m -Xmx512m

 

import java.util.TreeSet;

public class Test {
    public static void main(String[] args) {
       TreeSet set = new TreeSet();

       for(long i=10000000000L;i<900000000000L;i++){
           set.add(i);
           System.out.println("i="+i);
       }
    }
}

 

一个简单的 FOR 循环,运行该类,可以看到当输出: i=10011703526 的时候报错了

 

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

 

如果把上面的例子中的   set.add(i);  修改成 set.add(i+"");    那结果又是什么呢?

当输出 i=10005851762 时报了同样的错,内存溢出。为什么往内存里放 Long 型的比 String 型的多了近一半的数据呢?

 

1024 个字节 =1KB , 1024KB=1MB , 1024MB=1GB 

 

 

Long  8 个字节 (64  )  11703526  Long 型数据约 91433KB   89M

String 内部是由 char 构成,一个 char  2 个字节, 11 位的数据是 22 个字节, 5851762  String 型数据 约合 125721KB  122M

11 位的 String 数据比 11 位的 Long 型数据要占内存多。

 

总结:内存溢出是由于自己没有做到节省内存,用 64 位的 Long 型数据或 176 位的 String 型数据来存储 11 位的数据。那能不能用内存里的 11 位即 11bit 来表示 11 位数据呢?

 

所谓的Bit-map 就是用一个bit 位来标记某个元素对应的Value , 而Key 即是该元素。由于采用了Bit 为单位来存储数据,因此在存储空间方面,可以大大节省。

 

 

如果说了这么多还没明白什么是Bit-map,那么我们来看一个具体的例子,假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素

没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个Bit(1Bytes),首先我们开辟1Byte的

空间,将这些空间的所有Bit位都置为0(如下图:)

然后遍历这5个元素,首先第一个元素是4,那么就把4对应的位置为1(可以这样操作 p+(i/8)|(0×01<<(i%8)) 当然了这里的操作涉及到Big-

ending和Little-ending的情况,这里默认为Big-ending),因为是从零开始的,所以要把第五位置为一(如下图):

然后再处理第二个元素7,将第八位置为1,,接着再处理第三个元素,一直到最后处理完所有的元素,将相应的位置为1,这时候的内存的Bit

位的状态如下:

然后我们现在遍历一遍Bit区域,将该位是一的位的编号输出(2,3,4,5,7),这样就达到了排序的目的。

下面给出java中实现Bit-Map思想的BitSet排序的实例。但是待排序的数中不能有负数。

package com.lang;

import java.util.BitSet;

public class BitTest2 {

	public static void main(String[] args) {
		//4,7,2,5,3
		BitSet bs = new BitSet(8);
		int[] ia = {4,7,2,5,3};
		for (int i : ia) {
			bs.set(i, true);
		}
		int size = bs.size();
		for (int j=0; j<size; j++) {
			boolean b = bs.get(j);
			if (b) 
				System.out.print(j + " ");
		}
		
	}
}

 

【适用范围】

可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下

【基本原理及要点】

使用bit数组来表示某些元素是否存在,比如8位电话号码

【扩展】

Bloom filter可以看做是对bit-map的扩展

【问题实例】

1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。

8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要99M个Bit==12.4MBytes,这样,就用了小小的12.4M左右的内存表示了所有的8位数的电话)

2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。

将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上,在遍历这些数的时候,如果对应位置的值是0,则将其置为1;如果是1,将其置为2;如果是2,则保持不变。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个2bit-map,都是一样的道理。

 

分享到:
评论

相关推荐

    JAVA大数据处理题.pdf

    Java大数据处理技术主要涉及到如何高效地处理海量数据,尤其是在内存受限的情况下。以下是对给定问题的详细解答: 1. 共享URL查找: - 方案1:采用分治策略,将大文件按哈希值分散到多个小文件中,然后两两比较小...

    《Java面试必知必会》-海量数据类高频问题和参考答案.pdf

    《Java面试必知必会》一书中,针对海量数据处理的部分涵盖了多个重要知识点,这些都是Java开发者在求职面试中经常遇到的问题。以下是对这些知识点的详细解释: 1. **基础知识** - **Bit与Byte**:计算机中最基本的...

    解析bitmap处理海量数据及其实现方法分析

    由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。 如果说了这么多还没明白什么是Bit-map,那么我们来看一个具体的例子,假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)...

    数据处理面试题.pdf

    在大数据领域,海量数据处理是不可或缺的一部分。随着数据量的日益增长,如何高效地存储、处理和操作这些数据成为了一个重要议题。尤其在面试中,候选人常常会被问到相关的问题来考察其对大数据处理的理解和实践能力...

    Springboot如何使用Redis bitmap实现签到功能含完整代码(值得珍藏)

    随着互联网技术的发展,大量的在线服务需要处理海量数据。特别是在社交媒体、在线教育等领域,如何高效地管理和统计用户的行为数据变得尤为重要。其中,“签到”作为一项常见且重要的用户行为,其统计与管理直接影响...

    大数据处理算法.pdf

    大数据处理算法在现代信息技术领域扮演着至关重要的角色,尤其是在面对海量数据时,高效的处理策略能够极大地提升数据分析的速度和准确性。本篇主要讨论三种大数据处理算法:Bitmap算法、Bloom Filter算法以及...

    物联网数据处理存储技术资源.docx

    而在物联网领域,为了满足海量数据的存储需求,通常会采用高性能的磁盘阵列或固态硬盘(SSD)作为主要的存储介质。这些介质的特点是读写速度快、可靠性高,非常适合存储大量数据。 **3. 就近存储原则** - **定义*...

    精选17道海量数量处理面试题!.pdf

    在大数据处理领域,面对海量数据的挑战,常常需要设计高效的算法和数据结构来解决实际问题。以下是基于给定的面试题解析的一些关键知识点: 1. **分治策略**: - 在第一题中,处理两个大文件(各50亿url)的共同...

    java排序算法使用及场景说明

    在这个场景中,我们有海量日志数据,问题是如何提取出某日访问百度次数最多的那个 IP? 解决方案 1:首先是这一天,并且是访问百度的日志中的 IP 取出来,逐个写入到一个大文件中,然后采用映射的方法,找出每个小...

    位图查询海量数字是否存在问题

    在处理海量数据时,传统的线性搜索效率低下,而位图查询利用位运算的特性,可以在几乎常数时间内完成查找操作,尤其适用于数据范围较小的情况。下面将详细解释这一技术及其应用。 位图(Bitmap)是一种数据结构,它...

    Android面试复习资料大全(包含java源码)

    29. **海量数据处理算法**:学习如拓扑排序、Kruskal算法、Prim算法、Dijkstra算法、Floyd算法等。 30. **剑指offer系列**:包含一系列算法题,涵盖了栈、队列、二叉树、查找、排序等问题。 31. **Android布局优化...

    Android秋招面试指南

    5. Android高级话题:如Android动画总结、内存泄漏总结、权限处理、热修复原理、插件化入门、推送技术解析、Apk安装过程、数据结构线性表、栈和队列、树、图、散列、排序等算法及海量数据处理方法。 6. 设计模式:在...

    android_interview_guide.pdf

    在数据结构和算法方面,文档提供了线性表、栈和队列、树、图、散列、查找、排序和海量数据处理算法等基础知识点的解析,以及一些经典的算法题目的解答,例如剑指offer中的二维数组中的查找、替换空格、从尾到头打印...

    狂神说redis笔记

    大数据时代的特征可以概括为“3V+3高”,即海量的数据量(Volume)、多样化的数据类型(Variety)、快速的数据流(Velocity),以及高并发、高可扩展性和高性能等要求。 通过狂神的Redis笔记,我们可以系统地学习...

    mn-mobile:漫画网络的移动客户端

    Java的类库丰富,提供了许多适用于移动应用开发的功能模块,如网络通信、数据存储、图形处理等,大大简化了开发流程。 在mn-mobile中,Java的多线程机制是实现流畅用户体验的关键。通过并发处理,应用可以在后台...

    实现点击图片变暗和变亮效果

    Bitmap对象代表了一个位图图像,它包含了图像的所有像素数据。通过Bitmap,我们可以对图片进行各种操作,比如调整亮度、对比度、饱和度等。 实现点击图片变暗和变亮的关键在于改变图片的像素值。Android提供了...

    WallPepper:从flickr中随机选择一张图片,并将其设置为Android的背景

    总之,WallPepper项目展示了Java在Android开发中的强大能力,以及如何通过网络请求、数据解析、图片处理等技术,实现从互联网获取内容并应用于本地。同时,该项目也提醒我们,良好的用户体验往往来源于对细节的关注...

    面试常见基础算法题总结

    18. **海量数据问题**:通常涉及数据压缩、分布式存储、MapReduce等技术,优化算法和数据结构以减少I/O操作。 19. **一致性哈希**:解决分布式系统中的负载均衡问题,通过哈希函数将键映射到有限的服务器集合,...

Global site tag (gtag.js) - Google Analytics