前言
前段開發(fā)項目試就發(fā)現(xiàn)丈莺，一部分的代碼實(shí)現(xiàn)存在著一些性能上的隱患哄孤。但當(dāng)時忙于趕進(jìn)度和由于卡發(fā)中的不穩(wěn)定因素悴势，想了許多解決方案也沒有機(jī)會實(shí)施钱贯。最近挫掏，正好趁個機(jī)會進(jìn)行一系列的改進(jìn)。
我在團(tuán)隊開發(fā)中負(fù)責(zé)開發(fā)服務(wù)器端秩命。所以在編寫業(yè)務(wù)邏輯層時尉共，常常遇到以下這樣的業(yè)務(wù)邏輯：
1. 判斷一個用戶是否為在自己的好友列表中
2. 判斷一條動態(tài)是否已被用戶翻閱
3. 判斷兩個用戶的標(biāo)簽的匹配度
4. .....等等
這些情況，我之前的方案是采用數(shù)據(jù)庫來解決弃锐，為每條記錄添加標(biāo)記袄友，需要查詢時則遍歷返回相應(yīng)的集合。
但是隨著用戶量的不斷增多霹菊、各個用戶之間的關(guān)系不斷地增加剧蚣、以及用戶使用軟件的一系列行為中這些情況是非常頻繁的，這樣頻繁遍歷大量的記錄的讀操作會給數(shù)據(jù)庫帶來難以承受的壓力旋廷。
那么如何需找一種更好的解決方案鸠按？
既能減少數(shù)據(jù)庫需要遍歷的記錄數(shù)量且快速索引，又能用少量的內(nèi)存表示大量的數(shù)據(jù)饶碘。
其實(shí)如果我們對這一類型的業(yè)務(wù)邏輯進(jìn)行抽象目尖，可以得到：本質(zhì)上就是判斷一個元素是否存在于集合中
所以我們可以采用位數(shù)組，通過數(shù)組的下標(biāo)能快速地定位某個元素扎运，用bit表示相應(yīng)的內(nèi)容能夠節(jié)省大量的空間卑雁。
但是這樣結(jié)構(gòu)依舊不夠完美，如果數(shù)據(jù)量相對較少绪囱，數(shù)組中會存在大量的無用數(shù)據(jù)测蹲， 如長度為1024的byte數(shù)組中的只有少量位被表示為1，大量位依然是0鬼吵。
此時我們可以采用游程編碼壓縮byte數(shù)組扣甲。如上圖的游程編碼后的結(jié)果可以表示為[3, 0, 2, 0, 2, 0, 1, 0 ]
bitmap介紹
bitmap：被設(shè)計為一種用bit數(shù)組來儲存表示2種狀態(tài)的緊湊、快速索引的數(shù)據(jù)結(jié)構(gòu)(當(dāng)然Java的util包中也實(shí)現(xiàn)這類型的數(shù)據(jù)結(jié)構(gòu)—BitSet(不過并不是Set))
bitmap主要原理
其實(shí)說開來，bitmap就是一個位數(shù)組而已琉挖，有著快速訪問優(yōu)勢(下標(biāo)訪問)启泣，以及極小占用(用1bit來表示)
bitmap的主要設(shè)計
有點(diǎn)美中不足的是，Java中并沒有提供bit這樣的數(shù)據(jù)類型示辈，即便是最小的數(shù)據(jù)類型byte也要占用8bit寥茫。這樣就需要進(jìn)行一些位運(yùn)算來完成相應(yīng)的操作，使得代碼變得稍微復(fù)雜矾麻。
1. bitmap的內(nèi)部通過byte數(shù)組實(shí)現(xiàn)
2. bitmap的基本操作：增刪改查
void Set(int position); /* 將某位置"1" */
boolean Get(int position); /* 判斷某位的值 */
void Clear(int postion); /* 將某位置"0" */
Set()的實(shí)現(xiàn)原理
廢話不多說纱耻，直接看圖
主要分為兩個步驟：
- 先將一個byte類型的"1"左移4位，得到結(jié)果
- 再進(jìn)行簡單的或運(yùn)算险耀，得到結(jié)果并覆蓋原來的值
Get()的實(shí)現(xiàn)原理
理解了上面的例子弄喘，相信這個應(yīng)該就很簡單了
同樣是兩步：
- 先將一個byte類型的"1"左移3位，得到結(jié)果
- 再進(jìn)行與操作甩牺，得到結(jié)果并覆蓋原來的值
或許這里會有些疑問蘑志，為什么不考慮用boolean？
首先贬派，Java規(guī)范中沒有強(qiáng)制規(guī)定boolean所占內(nèi)存的大小急但。而且大部分計算機(jī)允許分配的最小內(nèi)存單元為8bit
可以用運(yùn)用bitmap解決問題的實(shí)用場景
大多可以運(yùn)用的場景主要是兩個方面：
這里以標(biāo)簽匹配為例子，開發(fā)中一個用戶與各個用戶之間的標(biāo)簽匹配度是令人頭疼的問題搞乏，通過匹配標(biāo)簽字符串或者標(biāo)簽ID波桩，這樣的效果都不能太讓人滿意，在數(shù)據(jù)庫中的保存也頗為麻煩查描。
一突委、快速索引
假如柏卤，每個用戶都有一個這樣小小的長度為40的byte數(shù)組冬三，那么用戶就可以用它來表示320種標(biāo)簽。而且能夠快速的查詢缘缚，通過bitarray[tag_id]這樣的訪問方式可以極快查到勾笆，用戶是否選取了這個標(biāo)簽，能夠快速地計算與各個用戶之間的標(biāo)簽匹配度
二桥滨、數(shù)據(jù)壓縮
那么像第一點(diǎn)說的那樣窝爪，長度為40的byte數(shù)據(jù)便可以保存320種標(biāo)簽信息，但它內(nèi)存大小只有40B齐媒。而且這還是沒有進(jìn)行游程編碼壓縮之前的大小
Java實(shí)現(xiàn)
/**
* Created by 某拆遷大隊的二哈 on 17-6-7.
*/
public class BitMap {
public static final int DEFAULT_SIZE = 1024;
public static final boolean EXIST = true;
public static final boolean NULL = false;
public static final short bits = 8;
private byte[] bitArray;
private int size;
public BitMap(){
this(DEFAULT_SIZE);
}
public BitMap(byte[] bitArray){
this.size = bitArray.length * bits;
this.bitArray = bitArray;
}
public BitMap(int defaultSize) {
this.size = defaultSize * bits;
this.bitArray = new byte[defaultSize];
}
public BitMap(int size, boolean elem){
this(size);
if(EXIST == elem) {
for (int i = 0; i < bitArray.length; i++)
bitArray[i] = (byte) ~bitArray[i];
}
}
public int size(){
return size;
}
public int index(int position){
int idx = (position + bits - 1) / bits;
return idx - 1;
}
public int offset(int position){
int ofs = position % 8;
return (ofs == 0 ? ofs : 8 - ofs);
}
public void setBit(int position){
if(position > size)
return ;
int idx = index(position);
int ofs = offset(position);
bitArray[idx] |= (byte)(1 << ofs);
}
public boolean getBit(int position){
if(position > size)
return false;
int idx = index(position);
int ofs = offset(position);
byte tmp = (byte)(bitArray[idx] & (1 << ofs));
return tmp != 0;
}
public void setBitArray(byte[] bitArray){
this.bitArray = bitArray;
}
public byte[] getBitArray(){
return bitArray;
}
public String byteToStr(int position){
byte b = bitArray[index(position)];
StringBuffer sb = new StringBuffer("");
for(int i=bits-1; i>-1; i--)
sb.append((byte)((b >> i) & 0x1));
return sb.toString();
}
}
