位图的实现(BitSet)

位图的实现(BitSet)

使用bloomfilter算法实现。可以解决缓存穿透问题。

思路：将数据库中表的键存储在bloomfilter中，前端访问该bloomfilter，若判断可能存在就放过，否则，直接返回非法访问。容错率不高，但也有效保证性能，将大量访问降低到少量访问。(防止黑客恶意攻击。)

问题：

怎么判断1亿 数据里面是否存在某个数据？要求算法的复杂度，控制在常数范围内！

14亿人身份证号码，怎么快速判断某个身份证号码在这个里面？

提出方案：

1. HashSet

   把14亿个字符串存在在HashSet 里面，使用HashSet的 判断是否存在某个值解决

2. TreeSet

   把14亿个字符串存在在TreeSet 里面，使用TreeSet 的 判断是否存在某个值解决

   

由于HashSet的时间复杂度(O(1))大于TreeSet的时间复杂度(O(logn)).

速度问题：使用Hash>>Tree

优缺点：

优点：非常简单，我们可以直接使用HashSet 来存储

缺点：当我们的数据量约大，它的存储的数据将无法估量，可能导致JVM 内存的溢出。程序被压垮。

HashSet 和TreeSet 直接存储字符串占用的内存太大了，都不是最优方案。我们需要去选择别的结构了

引入位集合

特点

1. 集合里面只能存储0/1 ,
2. 每个点都占用1 个bit

Hash概念

什么叫hash？

Hash 就是为把某个值，映射在一个有序的长度上面，得到一个映射值

hash 和hashCode

hash就是在一段长度的位置值

hashCode 不等于该位置的值，

hashCode 一般是个非常特殊的值，是通过一个质数做变化得来的.

hash和hashCode的关系:简单代码解释：通过hashCode才能得到一个位置值。

int pos = getPos(hashCode);
int getPos(int hashCode){
    Int pos = hashCode & (len-1) ;
}

hash冲突问题(hash碰撞)

有2 个值，他们的hash值及pos值都是相同的，这个时候就会产生冲突。

解决方案：

1. 拉链法解决

链表的方式链接到后面

2. 二次hash

我们若计算出来该值的hash 和之前的值有冲突，我们使用另一个hashCode函数再计算hashCode，得的不同的pos ，有新的pos

3. 跳跃法

位集合的使用

1. 获取hashCode值

package com.zxm.bitset;/*** 通过值获取hashCode值。*/
public class HashCodeFun {
    /*** 计算hashCode的关键*/private int seed;public HashCodeFun(int seed){
    this.seed = seed;}/*** 通过给出的value计算出hashCode*/public int hashCodeFun(String value){
    char[] chars = value.toCharArray();int h = 0;if (h == 0 && chars.length > 0) {
    char val[] = chars;for (int i = 0; i < chars.length; i++) {
    h = seed * h + val[i];}}return h;}
}

2. bloomfilter的实现

package com.zxm.bitset;import java.util.BitSet;public class Question {
    /*** 位集合的长度*/private int len = 12;/*** 创建一个位集合*/private BitSet bitSet = new BitSet(len);private int[] seeds = new int[]{
    31, 37, 43, 47};private HashCodeFun[] hashCodeFuns = new HashCodeFun[seeds.length];{
    for (int i = 0; i < seeds.length; i++) {
    hashCodeFuns[i] = new HashCodeFun(seeds[i]);}}/*** 给位集合里面设置一个值** @param value*/public void addValue(String value) {
    for (HashCodeFun hashCodeFun : hashCodeFuns) {
    int hashCode = hashCodeFun.hashCodeFun(value);// 通过质数计算hashCode的值。int pos = hashCode & (len - 1);System.out.println(pos);bitSet.set(pos, true);}}/*** 怎么判断该位集合里是否存在某个值* 1 判断集合里面的代表该value的4 个点** @param value* @return*/public boolean existValue(String value) {
    for (HashCodeFun hashCodeFun : hashCodeFuns) {
    int hashCode = hashCodeFun.hashCodeFun(value);int pos = hashCode & (len - 1);if (!bitSet.get(pos)) {
     //return false;}}return true;}public static void main(String[] args) {
    Question question = new Question();question.addValue("mayun");System.out.println(question.existValue("mayun"));}
}