 版权申明原创文章：本博所有原创文章，欢迎转载，转载请注明出处，并联系本人取得授权。 问题难点文本和数据的去重是经常要用到的重要操作，普通数量的文本处理并不存在技术上的难点，可以直接在内存中高效处理，但是如果涉及到的文本量达到了数十亿级别，直接在内存中处理文本去重工作几乎变成不可实现，例如假设有个文本中包含有20亿手机号码，每个手机号码共计11位数字，int最大值只能保存2^31-1=2147483647，不够表示手机号，因此只能用String或者long型来表示手机号。 Java基本数据类型byte 1字节 解决思路数据结构大文本去重最优的数据结构应该是使用Bitmap，那么具体要如何实现呢？ 如何计算我们可以直接申请一个1.165G存储空间当作手机的字典表，且所有位全部用0表示目前没有任何号码在我们的字典中。 运算因为Java中最小的数据类型为byte，占用1字节，因此用二进制表示为0000 0000，每一位分别有数据的表示我们可以定义一个数组如下： 新增手机号我们现在需要新增一个133 3333 3333 的手机号如何运算呢？ 删除手机号我们再次用133 3333 3333 号码举例，刚才我们已经知道了该手机号在字典表的第416,666,666个字符的第5位，如何删除呢： 判断手机号是否存在还是用刚才的例子 手机号133 3333 3333 在字典表的第416,666,666个字符的第5位，我们要判断这个位置是否为1 2、判断 1111 1111 == 原始数据 | (0010 0000 ^ 1111 1111) 算法实现代码package org.tcrow.datastructure;
import com.google.common.io.FileWriteMode;
import com.google.common.io.Files;
import javax.annotation.concurrent.ThreadSafe;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.regex.Pattern;
/**
* @author tcrow.luo
* @date 2018/8/27
* @description BitMap处理手机号去重，支持海量手机号数据去重，处理时间毫秒级，理论上经过改造可以支持更大的整数去重运算，但是初始化需要占用更多的存储空间
*/
@ThreadSafe
public class Mobile {
private final static int INIT_BUFFER_SIZE = 1024 * 1024;
/**
* 正则表达式：验证手机号
*/
private final static String REGEX_MOBILE = '^((10[0-9])|(11[0-9])|(12[0-9])|(13[0-9])|(14[0-9])|(15[0-9])|(16[0-9])|(17[0-9])|(18[0-9])|(19[0-9]))\\d{8}$';
/**
* 二进制1~8位分别为1的值，与原值进行或操作即可完成在号码库的新增操作
*/
private final static byte[] ARRAY_BYTE = {0b00000001, 0b00000010, 0b00000100, 0b00001000, 0b00010000, 0b00100000, 0b01000000, -0b10000000};
/**
* 二进制掩码，-1 用二进制表示 为 11111111
* 因此任何字节异或掩码后可以获得取反值，例如 00000001 ^ 11111111 = 11111110
*/
private final static byte MASK_BYTE = -1;
/**
* 用于存储手机号码是否存在
* 因为中国手机号码都是1开头，所以第一位省略
* 我们需要表示最大9999999999个号码是否存在
* 1字节 = 8 bit 最多可以表示8个号码
* 因此需要空间 9999999999 / 8 = 1249999999.875 约等于 125 * 10 ^ 7 字节 约为 1.165 G 空间
* 直接加载到内存中比较浪费，因此可以创建一个二进制文件直接表示，然后通过RandomAccessFile类读文件相应的位
*/
private File dictFile;
private RandomAccessFile file;
/**
* 读写全局锁，保证 读读共享, 读写互斥, 写写互斥
*/
private final static ReadWriteLock LOCK = new ReentrantReadWriteLock();
public Mobile(final String filePath) throws FileNotFoundException {
dictFile = new File(filePath);
if (!dictFile.exists()) {
try {
init();
} catch (IOException e) {
e.printStackTrace();
}
}
file = new RandomAccessFile(dictFile, 'rw');
}
private void init() throws IOException {
LOCK.writeLock().lock();
try {
Files.createParentDirs(dictFile);
int loop = 1250000000 / INIT_BUFFER_SIZE 1;
byte[] buffer = new byte[INIT_BUFFER_SIZE];
for (int i = 0; i < loop; i ) {
Files.asByteSink(dictFile, FileWriteMode.APPEND).write(buffer);
}
} finally {
LOCK.writeLock().unlock();
}
}
/**
* 新增电话号码到字典中
*
* @param mobile
*/
public void insert(String mobile) throws IOException {
if (!isMobile(mobile)) {
throwException(mobile);
}
if (hasMobile(mobile)) {
return;
}
long no = Long.parseLong(mobile) - 10000000000L;
int byteNum = (int) (no / 8);
int bit = (int) (no % 8);
byte b = read(byteNum);
//对应位或操作 e.g. 11100000 | 00000001 == 11100001 则成功插入了标志位
b = (byte) (b | ARRAY_BYTE[bit]);
write(byteNum, b);
}
/**
* 从字典中删除电话号码
* @param mobile
* @throws IOException
*/
public void delete(String mobile) throws IOException {
if (!isMobile(mobile)) {
throwException(mobile);
}
if (!hasMobile(mobile)) {
return;
}
long no = Long.parseLong(mobile) - 10000000000L;
int byteNum = (int) (no / 8);
int bit = (int) (no % 8);
byte b = read(byteNum);
//字节与操作 e.g. 00010001 & 11111110 == 00010000 则成功删除了标志位，对应标志位异或掩码得对应的补码 e.g. 00000001 ^ 11111111 == 11111110
b = (byte) (b & (ARRAY_BYTE[bit] ^ MASK_BYTE));
write(byteNum, b);
}
private void throwException(String mobile) {
throw new RuntimeException('The string \'' mobile '\' is not the mobile number.');
}
private void throwUnknownException() {
throw new RuntimeException('read data unknown exception');
}
public boolean hasMobile(String mobile) throws IOException {
if (!isMobile(mobile)) {
throwException(mobile);
}
long no = Long.parseLong(mobile) - 10000000000L;
int byteNum = (int) (no / 8);
int bit = (int) (no % 8);
byte b = read(byteNum);
// 01000111 & 00000010 == 00000010 01000101 & 00000010 == 0
// 10111111 | 11111101 == 11111111 == -1 10111101 | 11111101 == 11111101 != -1
// 两种判断方式都可以实现，取简单的方式直接按位与操作后等于判断位则表示标志位有值
if (ARRAY_BYTE[bit] == (byte) (b & ARRAY_BYTE[bit])) {
return true;
} else {
return false;
}
}
private boolean isMobile(String mobile) {
return Pattern.matches(REGEX_MOBILE, mobile);
}
private byte read(int byteNum) throws IOException {
LOCK.readLock().lock();
byte[] buffer = new byte[1];
try {
file.seek(byteNum);
int read = file.read(buffer);
if (read <= 0) {
throwUnknownException();
}
} finally {
LOCK.readLock().unlock();
}
return buffer[0];
}
private void write(int byteNum, byte b) throws IOException {
LOCK.writeLock().lock();
try {
file.seek(byteNum);
byte[] buffer = new byte[1];
buffer[0] = b;
file.write(buffer);
} finally {
LOCK.writeLock().unlock();
}
}
}
我这边为了节约内存，字典是直接在外部存储申请的空间，操作上会比内存中耗费稍微多一点时间，因为要读取外部存储的数据，但相应的可以对计算机内存的需求度降低到最少，有了这个算法，我们要实现海量手机号的去重就变得轻而易举了。 延伸阅读bit-map主要用于对存储空间大量压缩的情况，例如其他字符文本的去重也是可以使用的，例如要进行邮箱地址去重，可以将邮箱地址进行hash运算得到等长的字符串，然后转换成ascii码，再存储到bitmap中，就可以进行邮箱地址的去重了。 再进一步我们实际的场景中可能不止要对文本进行去重，还得进行热点扫描，例如百度的搜索热点，这个可以使用到Trie树的数据结构，可以最快速的查找并获得字典出现频率，我这里贴上一个简单的Trie树的实现代码。 好了本文结束，后续如果想学习更多算法和有意思的算法题目的实现，可以star我的github项目，地址如下：  large-895567_640.jpg
|
|
|
