如何使用bitset实现毫秒级查询

这篇文章主要为大家展示了“如何使用bitset实现毫秒级查询”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“如何使用bitset实现毫秒级查询”这篇文章吧。

bitset介绍

看jdk中的解释简直一头雾水，用我自己的理解概括一下

bitset的内部实现是long数组
2.set中每一个位的默认值为false（0）
3.bitset长度按需增长
4.bitset非线程安全

bitset关键方法分析

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();}

设置指定“位”为true，bitIndex参数为非负整数。假设我们执行以下代码,观察上面代码中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]二进制值的对应关系，得到一个结论，即：bitset中每一个long可以表示64个非负整数在bitSet中存在与否。例如：0001可以表示整数0在bitset中存在，1111可以表示整数3,2,1,0在bitset中存在。

进入正题，实现bitset毫秒级查询

想象一个场景，我们有一张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;

假设我们要查询“北京市18岁的女生”，那么对应的sql如下：

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

如何使用bitset实现同样的查询呢？

将user表数据加载进内存中

为user表建立address,age,gender维度的bitset索引

根据索引查询数据

1.将user表数据加载进内存中

将user表从数据库读取出来存入List

User实体类：

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.建立索引

创建bitset索引模型类

public class BitSetIndexModel { private String type;//索引类型：address，age，gender private ConcurrentHashMap<String, Integer> map;//索引类型和bitSet在bsList中下标的映射关系 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; }  public void createIndex(String str, int i) {  BitSet bitset = null;  //获取‘str'对应的bitset在bsList中的下标  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对应的位置为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);  } }   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; }  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; }  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; }  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; } }

为每一个user对象创建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;//存储所有的user数据 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>(); }  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();//可能会对user做修改操作,要保证内存原始数据不变  }  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.测试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("单次查询时间为：" + (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; }}

测试结果(查询2w次)：

数据量（users.size()） | 并发数 | 平均查询时间

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

测试机为thinkpad x240 i5 8g内存

4.总结

==优点==：

通过测试发现随着数据量的增大和并发数的提高，平均耗时并没有明显升高，并且响应时间都在10ms以内

==缺点==：

不适合数据量太大的情况,因为需要把数据全部加载进内存

不适合复杂查询

不适合对name,id等唯一值做查询

以上是“如何使用bitset实现毫秒级查询”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注编程网精选频道！