使用bitset實(shí)現(xiàn)毫秒級(jí)查詢(實(shí)例講解)

更新時(shí)間：2017年10月24日 08:56:25 作者：ncb

下面小編就為大家?guī)硪黄褂胋itset實(shí)現(xiàn)毫秒級(jí)查詢(實(shí)例講解)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧

前言

因?yàn)闃I(yè)務(wù)要求api的一次請(qǐng)求響應(yīng)時(shí)間在10ms以內(nèi)，所以傳統(tǒng)的數(shù)據(jù)庫(kù)查詢操作直接被排除(網(wǎng)絡(luò)io和磁盤io)。通過調(diào)研，最終使用了bieset,目前已經(jīng)正常運(yùn)行了很久

bitset介紹

看JDK中的解釋簡(jiǎn)直一頭霧水，用我自己的理解概括一下

1.bitset的內(nèi)部實(shí)現(xiàn)是long數(shù)組
2.set中每一個(gè)位的默認(rèn)值為false（0）
3.bitset長(zhǎng)度按需增長(zhǎng)
4.bitset非線程安全

bitset關(guān)鍵方法分析

/**
 * Sets the bit at the specified index to {@code true}.
 *
 * @param bitIndex a bit index
 * @throws IndexOutOfBoundsException if the specified index is negative
 * @since JDK1.0
 */
public void set(int bitIndex) {
 if (bitIndex < 0)
  throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

 int wordIndex = wordIndex(bitIndex);
 expandTo(wordIndex);

 words[wordIndex] |= (1L << bitIndex); // Restores invariants

 checkInvariants();
}

設(shè)置指定“位”為true，bitIndex參數(shù)為非負(fù)整數(shù)。假設(shè)我們執(zhí)行以下代碼,觀察上面代碼中worIndex，words[wordIndex]值的變化

BitSet bs = new BitSet()
bs.set(0);
bs.set(1);
bs.set(2);
bs.set(3);
bs.set(4);

bitIndex	words[wordIndex]	words[wordIndex]二進(jìn)制表示
0	1	0001
1	3	0011
2	7	0111
3	15	1111
4	31	0001 1111

通過上表，我們可以很清晰的根據(jù)bitIndex和words[wordIndex]二進(jìn)制值的對(duì)應(yīng)關(guān)系，得到一個(gè)結(jié)論，即：bitset中每一個(gè)long可以表示64個(gè)非負(fù)整數(shù)在bitSet中存在與否。例如：0001可以表示整數(shù)0在bitset中存在，1111可以表示整數(shù)3,2,1,0在bitset中存在。

進(jìn)入正題，實(shí)現(xiàn)bitset毫秒級(jí)查詢

想象一個(gè)場(chǎng)景，我們有一張user表

CREATE TABLE `user` (
 `id` int(11) NOT NULL AUTO_INCREMENT,
 `name` varchar(255) NOT NULL,
 `address` varchar(255) NOT NULL comment '地址',
 `gender` varchar(10) NOT NULL comment '性別',
 `age` varchar(10) NOT NULL,
 PRIMARY KEY (`uid`)
) ENGINE=InnoDB AUTO_INCREMENT=0 DEFAULT CHARSET=utf8;

假設(shè)我們要查詢“北京市18歲的女生”，那么對(duì)應(yīng)的sql如下：

select * from `user` where address='北京' and age='18' and gender='girl';

如何使用bitset實(shí)現(xiàn)同樣的查詢呢？

1.將user表數(shù)據(jù)加載進(jìn)內(nèi)存中

2.為user表建立address,age,gender維度的bitset索引

3.根據(jù)索引查詢數(shù)據(jù)

1.將user表數(shù)據(jù)加載進(jìn)內(nèi)存中

將user表從數(shù)據(jù)庫(kù)讀取出來存入List

User實(shí)體類：

public class User implements Cloneable {
 private String name;
 private String address;
 private String gender;
 private String age;

 @Override
 public String toString() {
  return "User [name=" + name + ", address=" + address + ", gender=" + gender + ", age=" + age + "]";
 }

 @Override
 public User clone() {
  User user = null;
  try {
   user = (User) super.clone();
  } catch (CloneNotSupportedException e) {
   e.printStackTrace();
  }
  return user;
 }
 //省略get set 方法。。。

2.建立索引

創(chuàng)建bitset索引模型類

public class BitSetIndexModel {
 private String type;//索引類型：address，age，gender
 private ConcurrentHashMap<String, Integer> map;//索引類型和bitSet在bsList中下標(biāo)的映射關(guān)系
 private List<String> list;//索引類型的值集合，例如gender：girl，boy
 private List<BitSet> bsList;//bitset集合

 public BitSetIndex() {
  
 }

 public BitSetIndexModel(String type) {
  this.type = type;
  map = new ConcurrentHashMap<String, Integer>();
  list = new ArrayList<String>();
  bsList = new ArrayList<BitSet>();
 }
 
 public String getType() {
  return type;
 }

 public void setType(String type) {
  this.type = type;
 }

 public Map<String, Integer> getMap() {
  return map;
 }

 public void setMap(ConcurrentHashMap<String, Integer> map) {
  this.map = map;
 }

 public List<String> getList() {
  return list;
 }

 public void setList(List<String> list) {
  this.list = list;
 }

 public List<BitSet> getBsList() {
  return bsList;
 }

 public void setBsList(List<BitSet> bsList) {
  this.bsList = bsList;
 }

 /**
  *
  * @param str
  * @param i
  */
 public void createIndex(String str, int i) {
  BitSet bitset = null;
  //獲取‘str'對(duì)應(yīng)的bitset在bsList中的下標(biāo)
  Integer index = this.getMap().get(str);
  if (index != null) {
   bitset = this.getBsList().get(index);
   if (bitset == null) {
    bitset = new BitSet();
    this.getBsList().add(index, bitset);
   }
   bitset.set(i, true);// 將str對(duì)應(yīng)的位置為true,true可省略
  } else {
   bitset = new BitSet();
   List<String> list = this.getList();
   list.add(str);
   index = list.size() - 1;
   bitset.set(i, true);
   this.getBsList().add(bitset);
   this.getMap().put(str, index);
  }
 }
 
 /**
  * 從entity里拿出符合條件的bitset
  *
  * @param str
  * @return
  */
 public BitSet get(String str) {
  BitSet bitset = null;
  str = str.toLowerCase();
  Integer index = this.getMap().get(str);

  if (index != null) {
   bitset = this.getBsList().get(index);
  } else {
   bitset = new BitSet();
  }
  return bitset;
 }

 /**
  * bitset的與運(yùn)算
  *
  * @param str
  * @param bitset
  * @return
  */
 public BitSet and(String str, BitSet bitset) {
  if (str != null) {
   str = str.toLowerCase();
   if (bitset != null) {
    bitset.and(get(str));
   } else {
    bitset = new BitSet();
    bitset.or(get(str));
   }
  }
  return bitset;
 }

 /**
  * bitset的或運(yùn)算
  *
  * @param str
  * @param bitset
  * @return
  */
 public BitSet or(String str, BitSet bitset) {
  if (str != null) {
   str = str.toLowerCase();
   if (bitset != null) {
    bitset.or(get(str));
   } else {
    bitset = new BitSet();
    bitset.or(get(str));
   }
  }
  return bitset;
 }

 /**
  * 獲取bitset值為true的 即 把 bitset翻譯為list的索引
  *
  * @param bitset
  * @return
  */
 public static List<Integer> getRealIndexs(BitSet bitset) {
  List<Integer> indexs = new ArrayList<Integer>();
  if (bitset != null) {
   int i = bitset.nextSetBit(0);
   if (i != -1) {
    indexs.add(i);
    for (i = bitset.nextSetBit(i + 1); i >= 0; i = bitset.nextSetBit(i + 1)) {
     int endOfRun = bitset.nextClearBit(i);
     do {
      indexs.add(i);
     } while (++i < endOfRun);
    }
   }
  }

  return indexs;
 }
 
}

為每一個(gè)user對(duì)象創(chuàng)建address,gender,age維度索引

public class UserIndexStore {

 private static final String ADDRESS = "address";
 private static final String GENDER = "gender";
 private static final String AGE = "age";
 private BitSetIndexModel address;
 private BitSetIndexModel gender;
 private BitSetIndexModel age;
 private ConcurrentHashMap<Integer, User> userMap;//存儲(chǔ)所有的user數(shù)據(jù)

 public static final UserIndexStore INSTANCE = getInstance();

 private UserIndexStore() {
  init();
 }

 public static UserIndexStore getInstance() {
  return UserIndexStoreHolder.instance;
 }

 private static class UserIndexStoreHolder {
  private static UserIndexStore instance = new UserIndexStore();
 }

 private void init() {
  this.address = new BitSetIndexModel(ADDRESS);
  this.gender = new BitSetIndexModel(GENDER);
  this.age = new BitSetIndexModel(AGE);
  userMap = new ConcurrentHashMap<Integer, User>();
 }

 /**
  * 構(gòu)建索引
  * @param users 
  */
 public void createIndex(List<User> users) {
  if (users != null && users.size() > 0) {
   for (int index = 0; index < users.size(); index++) {
    User user = users.get(index);
    getAddress().update(user.getAddress(), index);
    getGender().update(user.getGender(), index);
    getAge().update(user.getAge(), index);
    this.userMap.put(index, user);
   }
  }
 }

 public BitSet query(String address, String gender, String age) {
  BitSet bitset = null;
  bitset = getAddress().and(address, bitset);
  bitset = getGender().and(gender, bitset);
  bitset = getAge().and(age, bitset);
  return bitset;
 }

 public User findUser(Integer index) {
  User user = this.userMap.get(index);
  if (user != null) {
   return user.clone();//可能會(huì)對(duì)user做修改操作,要保證內(nèi)存原始數(shù)據(jù)不變
  }
  return null;
 }

 public BitSetIndexModel getAddress() {
  return address;
 }

 public void setAddress(BitSetIndexModel address) {
  this.address = address;
 }

 public BitSetIndexModel getGender() {
  return gender;
 }

 public void setGender(BitSetIndexModel gender) {
  this.gender = gender;
 }

 public BitSetIndexModel getAge() {
  return age;
 }

 public void setAge(BitSetIndexModel age) {
  this.age = age;
 }

}

3.測(cè)試bitset

public class BitSetTest {

 public static void main(String[] args) {
  List<User> users = buildData();
  UserIndexStore.getInstance().createIndex(users);
  ExecutorService executorService = Executors.newFixedThreadPool(20);
  int num = 2000;
  long begin1 = System.currentTimeMillis();
  for (int i = 0; i < num; i++) {
   Runnable syncRunnable = new Runnable() {
    @Override
    public void run() {
     List<Integer> indexs = BitSetIndexModel.getRealIndexs(UserIndexStore.getInstance().query("北京", "girl", "18"));
     for (Integer index : indexs) {
      UserIndexStore.getInstance().findUser(index);
     }
    }
   };
   executorService.execute(syncRunnable);
  }
  executorService.shutdown();
  while (true) {
   try {
    if (executorService.awaitTermination(1, TimeUnit.SECONDS)) {
     System.out.println("單次查詢時(shí)間為：" + (System.currentTimeMillis() - begin1) / num + "ms");
     break;
    }
   } catch (InterruptedException e) {
    e.printStackTrace();
   }
  }
 }

 private static List<User> buildData() {
  String[] addresss = { "北京", "上海", "深圳" };
  String[] ages = { "16", "17", "18" };
  List<User> users = new ArrayList<>();
  for (int i = 0; i < 200000; i++) {
   User user = new User();
   user.setName("name" + i);
   int rand = ThreadLocalRandom.current().nextInt(3);
   user.setAddress(addresss[ThreadLocalRandom.current().nextInt(3)]);
   user.setGender((rand & 1) == 0 ? "girl" : "boy");
   user.setAge(ages[ThreadLocalRandom.current().nextInt(3)]);
   users.add(user);
  }
  return users;
 }

}

測(cè)試結(jié)果(查詢2w次)：

數(shù)據(jù)量（users.size()） | 并發(fā)數(shù) | 平均查詢時(shí)間

---|---|---
20w | 10 | 1ms
50w | 20 | 3ms
100w| 50 | 9ms

測(cè)試機(jī)為thinkpad x240 i5 8g內(nèi)存

4.總結(jié)

==優(yōu)點(diǎn)==：

通過測(cè)試發(fā)現(xiàn)隨著數(shù)據(jù)量的增大和并發(fā)數(shù)的提高，平均耗時(shí)并沒有明顯升高，并且響應(yīng)時(shí)間都在10ms以內(nèi)

==缺點(diǎn)==：

1.不適合數(shù)據(jù)量太大的情況,因?yàn)樾枰褦?shù)據(jù)全部加載進(jìn)內(nèi)存

2.不適合復(fù)雜查詢

3.不適合對(duì)name,id等唯一值做查詢

后記