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

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

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;

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

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 方法。。。

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

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

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