使用bitset实现毫秒级查询(实例讲解)

发布时间：2020-05-23 13:30:54 所属栏目：Java 来源：互联网

导读：前言因为业务要求api的一次请求响应时间在10ms以内，所以传统的数据库查询操作直接被排除(网络io和磁盘io)。通过调研，最终使用了bieset,目前已经正常运行了很久

前言

因为业务要求api的一次请求响应时间在10ms以内，所以传统的数据库查询操作直接被排除(网络io和磁盘io)。通过调研，最终使用了bieset,目前已经正常运行了很久

bitset介绍

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

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

bitset关键方法分析

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

设置指定“位”为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实现同样的查询呢？

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

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

3.根据索引查询数据

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

 /**
  *
  * @param str
  * @param i
  */
 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);
  }
 }
 
 /**
  * 从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的与运算
  *
  * @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的或运算
  *
  * @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;
 }
 
}

为每一个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>();
 }

 /**
  * 构建索引
  * @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();//可能会对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;
 }

}

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!