纯java从0到1实现一个布隆过滤器

本文主要是介绍纯java从0到1实现一个布隆过滤器，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

纯java从0到1实现一个布隆过滤器

gitee地址

本文简介布隆过滤器原理

主要介绍如何使用java实现一个bloom filter

一、位图

我们知道布隆过滤器实际上就是一个超级大的位图；

上面维护了所有黑名单（或者白名单）数据。

一个key过来或根据hash运算获取到所有对应位图上的点位，判断这些点位是否全为1.

如果全为1，那么判定此key已经添加进了位图（存在一定误判率）
若果有一个不为1，那么此key一定没有添加进位图（不存在误判）

二、几个重要参数

样本量（个）：n
失误率（小数）：p
位图空间（bit即位）：m
使用hash函数个数：k

在生成初始化一个布隆过滤器时，用户需要选择的是样本量n，和失误率p。

然后根据公式计算得出当前的位图空间，使用的hash函数个数k，

最终计算得出真实的失误率p

三、公式

所需的位图空间m

m = -[n*ln§]/[ln(2)^2]
所需的hash函数个数k

k = ln(2)*(m/n)
真实的失误率P

P = {1-e^[-(n*K)/M]}K

代码

一、布隆过滤器主类

此类中维护了一个long的数组，作为过滤器的位图，也是实现布隆过滤器的关键。

private static final long[] MEMORY;

java中定义数组大小时使用的是int整数。

也就是数组大小最多是2^31-1个

去最大的2的指数就是2^30个

一个long保存2^6个信息

也就是MEMORY最多保存2^36个位信息即1TB内存空间。

由于我所使用的hash函数运算的结果都是32位的int型数据。

对应的是32根地址线，也就是2^32bit=512MB;

所以布隆过滤器位图的最大内存空间只有3=512MB；

分析一个32位的hashcode结果如何插入到对应的MEMORY数组中。

我们知道，一个long型变量占用8字节64位。

所以MEMORY数组中每一个元素可以存放64个元素（也就是2的6次方个元素）

那么2^{x位大小的位图空间，就需要开辟2}(x-6)个数组。

这是需要的总的地址位数就是x（前x-6表示数组下标，后6位表示对应数组的哪一位）。

假设现在有一个数32位的int数i要插入到位图对应的空间中

i的二进制表示为

i= 0100 1001 0101 1110 1001 0111 1011 1100

假设x = 30，也就是需要24位表示数组下标，6位表示对应元素

也就是i的中间第3到底27位需要作为数组的下标信息。

d= 0011 1111 1111 1111 1111 1111 1100 0000 使用d&i运算就得到了索引下标index

i= 0100 1001 0101 1110 1001 0111 1011 1100

index = 0000 1001 0101 1110 1001 0111 1000 0000

这个24也就对应了下面代码中的SAVE_SIZE

index的运算代码如下：

int index = (-1 >>> 32 - SAVE_SIZE << 6 & i) >>> 6

这里理清后，对应的布隆过滤器的插入和删除操作也就不在是难题了。

插入操作：

首先计算出对应的数组下标
然后获取i的后六位二进制信息code得到对应的数组位置。
最后将code插入到位图中

public static void insert(int i) {
        //索引下标   （生成索引下边的具体步骤请移步MathTest::getIndex）
        int index = (-1 >>> 32 - SAVE_SIZE << 6 & i) >>> 6;
        //获取i对应数组元素中的位下标（这里的计算方式和HashMap获取元素在数组的位置的方式一致）
        int code = i & 63;
        //将数组元素中对应位置为1
        MEMORY[index] = MEMORY[index] | (1 << code);
    }

检查操作

同样先获取对应的数组下标
然后获取后六位信息
然后获取对应数组索引下对应的位信息i1
判断这个位信息是否是1
- 如果是1代表这个i已经插入到了位图中（存在误差，这也就是布隆过滤器误判存在的根源）
- 如果是0代表这个i一定没有插插入过位图

 public static boolean check(int i) {
        int index = (-1 >>> 32 - SAVE_SIZE << 6 & i) >>> 6;//获取数组的位置下标
        int code = i & 63;//截取i的后六位信息（也就是此i对应MEMERY元素的哪个位）
        long i1 = MEMORY[index] >>> code;//将i对应的位右移code位将i对应的位移动到最低位
        long i2 = i1 & 1;//将i1与1进行与操作获取此i是否在MEMORY位图中。
        return i2 == 1;
    }

其他操作

布隆过滤器的主要业务逻辑都在插入和检查中

下面简略介绍一些额外的操作

读取配置文件

过滤器主类获取n(样本量)和p(期望误判率)的方式是通过配置文件的方式获取的。

读取到所需的配置项后返回一个Map集合（这个集合在静态代码块中使用）

/**
     * read config properties file ,and return params map
     * @return
     */
    public static Map<String,Object> initProperties(){
        HashMap<String, Object> map = new HashMap<>();
        Properties properties = new Properties();
        // 使用ClassLoader加载properties配置文件生成对应的输入流
        ClassLoader classLoader = BloomFilter.class.getClassLoader();
        logger.info(classLoader);
        InputStream in = classLoader.getResourceAsStream("config/config.properties");
        // 使用properties对象加载输入流
        String n = null;
        String memoryStr = n;
        MemorySize mb = null;
        String p = null;
        try {
            properties.load(in);
            //memoryStr = properties.getProperty("memory");
            n = properties.getProperty("number");
            p = properties.getProperty("missProbability");
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (n == null || p == null) {
            throw noPropertiesException;
        }
        map.put("NUMBER",Long.parseLong(n));
        map.put("MISSPROBABILITY",Double.parseDouble(p));
        return map;
    }

静态代码块

调用读取配置文件的initProperties方法，给全部的静态常量赋值。

包括 NUMBER样本个数
MISSPROBABILITY期望的失误率
REALMISSPROBABILITY;真实失误率
REALSIZE实际开辟内存空间（返回的是一个可视化的字符串）
K_USEHASHCODENUMBER使用的hashcode函数个数
REALMEMORYBIT实际开辟内存空间（位）

/**
     * 静态代码块
     * 所有的计算性质都放置在静态代码块中实现，当类初始化时一次性计算生成，避免重复计算浪费性能
     */
    static {
        Map<String, Object> npMap = initProperties();
        NUMBER =(Long) npMap.get("NUMBER");
        MISSPROBABILITY =(Double) npMap.get("MISSPROBABILITY");
        long m = getNeedMemorySize(NUMBER, MISSPROBABILITY);
        int k = getHashCodeMethodNumber(NUMBER, m);
        REALMEMORYBIT = getRealMemorySize(NUMBER, MISSPROBABILITY);
        REALMISSPROBABILITY = getRealMissProbability(NUMBER, REALMEMORYBIT, k);
        REALSIZE = MemoryForAddressNumber.inBitOutSize(REALMEMORYBIT);
        int save_size = 0;
        long flag = REALMEMORYBIT;
        while (((flag=flag>>1)&1)==0){
            save_size++;
        }
        SAVE_SIZE = save_size -5;
        int size = 1 << SAVE_SIZE;
        MEMORY = new long[size];
        K_USEHASHCODENUMBER = getHashCodeMethodNumber(NUMBER, REALMEMORYBIT);

        logger.info("MOVE:"+ SAVE_SIZE);
        logger.info("realMemorySize = " + REALMEMORYBIT);
        logger.info("实际开辟的空间："+REALSIZE);
        logger.info("K:"+k);
        logger.info("m"+m);

    }

读取配置文件后就可以计算的出其余各项的值，一些计算方法都放在了主类的最后

主类的完整代码

package top.boking.bloom;

import org.apache.log4j.Logger;

import top.boking.exception.HashCodeMethodNumberOutOfException;
import top.boking.exception.HashCodeOutofMemoryException;
import top.boking.exception.NoPropertiesException;
import top.boking.utils.HashCodeLib;
import top.boking.utils.MemoryUtils;

import java.io.IOException;
import java.io.InputStream;
import java.util.HashMap;
import java.util.Map;
import java.util.Properties;

/**
 * 采用long型数组存储元素
 */
public class BloomLong {
    private BloomLong() {

    }

    private static Logger logger = Logger.getLogger(BloomFilter.class);//log4j日志对象
    private static final long[] MEMORY;//位图数组，布隆过滤器数据集合，黑名单一旦加入不可删除（或者说暂不支持删除亦或者说极难删除）。
    private static final int HASHCODEMETHODNUMBER;//HashCodeLib提供的hash函数个数
    private static final int SAVE_SIZE;//生成对应的内存空间的数组大小的保留位数（不太好理解，或许有更好的方式实现）。
    //非不可变属性一定得是私有的。

    private static long nowDataNumber = 0;//当前的实际样本量
    //公有参数一定得是final不可变的，这里的公有参数可以全部设计成私有，然后提供get方法。
    public static final long NUMBER;//样本个数
    public static final double MISSPROBABILITY;//需求的失误率
    public static final double REALMISSPROBABILITY;//真实失误率
    public static final String REALSIZE;//实际开辟内存空间(可视化的字符串类型)
    public static final int K_USEHASHCODENUMBER;//使用hash函数个数

    public static final long REALMEMORYBIT;//实际开辟内存空间（位）
    //定义异常
    private static HashCodeOutofMemoryException hashCodeOutofMemoryException = new HashCodeOutofMemoryException();
    private static HashCodeMethodNumberOutOfException numberOutOfException = new HashCodeMethodNumberOutOfException();
    private static NumberFormatException numberformatexception = new NumberFormatException();
    private static NoPropertiesException noPropertiesException = new NoPropertiesException();


    /**
     * 静态代码块，从配置文件中获取
     * 所有的计算性质都放置在静态代码块中实现，当类初始化时一次性计算生成，避免重复计算浪费性能
     */
    static {
        HASHCODEMETHODNUMBER = HashCodeLib.getHashcodemethodnumber();
        Map<String, Object> npMap = initProperties();
        NUMBER = (Long) npMap.get("NUMBER");
        MISSPROBABILITY = (Double) npMap.get("MISSPROBABILITY");
        long m = getNeedMemorySize(NUMBER, MISSPROBABILITY);
        int k = getHashCodeMethodNumber(NUMBER, m);
        REALMEMORYBIT = getRealMemorySize(NUMBER, MISSPROBABILITY);
        REALMISSPROBABILITY = getRealMissProbability(NUMBER, REALMEMORYBIT, k);
        REALSIZE = MemoryUtils.inBitOutSize(REALMEMORYBIT);
        int save_size = 0;
        long flag = REALMEMORYBIT;
        while (((flag = flag >> 1) & 1) == 0) {
            save_size++;
        }
        SAVE_SIZE = save_size - 5;
        int size = 1 << SAVE_SIZE;
        MEMORY = new long[size];
        K_USEHASHCODENUMBER = getHashCodeMethodNumber(NUMBER, REALMEMORYBIT);
        if (K_USEHASHCODENUMBER > HASHCODEMETHODNUMBER) {
            throw hashCodeOutofMemoryException;
        }
        logger.info("MOVE:" + SAVE_SIZE);
        logger.info("realMemorySize = " + REALMEMORYBIT);
        logger.info("实际开辟的空间：" + REALSIZE);
        logger.info("实际使用的hashcode个数" + k);
        logger.info("m" + m);

    }

    public static void init() {

    }

    /**
     * read config properties file ,and return params map
     *
     * @return
     */
    public static Map<String, Object> initProperties() {
        HashMap<String, Object> map = new HashMap<>();
        Properties properties = new Properties();
        // 使用ClassLoader加载properties配置文件生成对应的输入流
        ClassLoader classLoader = BloomFilter.class.getClassLoader();
        logger.info(classLoader);
        InputStream in = classLoader.getResourceAsStream("config/config.properties");
        // 使用properties对象加载输入流
        String n = null;
        String memoryStr = n;
        MemorySize mb = null;
        String p = null;
        try {
            properties.load(in);
            //memoryStr = properties.getProperty("memory");
            n = properties.getProperty("number");
            p = properties.getProperty("missProbability");
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (n == null || p == null) {
            throw noPropertiesException;
        }
        map.put("NUMBER", Long.parseLong(n));
        map.put("MISSPROBABILITY", Double.parseDouble(p));
        return map;
    }

    /**
     * 将对应输入的i插入到位图memory中
     * 应该是private属性，测试用时，可以放开成public进行指定i的插入测试。
     *
     * @param i 输入的hashcode值
     */
    public static void insert(int i) {
        //索引下标   （生成索引下边的具体步骤请移步MathTest::getIndex）

        int index = (-1 >>> 32 - SAVE_SIZE << 6 & i) >>> 6;
        //获取i对应数组元素中的位下标（这里的计算方式和HashMap获取元素在数组的位置的方式一致）
        int code = i & 63;
        //将数组元素中对应位置为1
        MEMORY[index] = MEMORY[index] | (1L << code);
    }

    /**
     * 对外的insert方法，
     * 调用NUMBER次对内的insert()方法，将此key对应的所有标志插入到memory中
     *
     * @param key
     * @return
     */
    public static boolean insertKey(String key) {
        if (nowDataNumber >= NUMBER) {
            logger.warn("警告：插入的样本已经超过设计值NUMBER，继续插入失误率可能会超出预设范围");
        }
        try {
            for (int i = 0; i <= K_USEHASHCODENUMBER; i++) {
                Integer integer = HashCodeLib.choiceHashMethod(key, i);
                logger.trace(i);
                insert(integer);
            }
        } catch (Exception e) {
            return false;
        }
        nowDataNumber++;//添加成功后将实际样本量加1。
        return true;
    }

    /**
     * 快速插入，无差错控制
     * @param key
     * @return
     */
    public static void insertFast(String key) {
            for (int i = 0; i <= K_USEHASHCODENUMBER; i++) {
                Integer integer = HashCodeLib.choiceHashMethod(key, i);
                logger.trace(i);
                insert(integer);
            }
        nowDataNumber++;//添加成功后将实际样本量加1。
    }


    /**
     * 同步代码块包裹的插入方法方法
     * 简单对insertKey进行了包裹
     * 应该还可以优化
     *
     * @param key
     * @return
     */
    public static boolean insertKeySecurity(String key) {
        synchronized (BloomFilter.class) {
            return insertKey(key);
        }
    }

    /**
     * 针对特定的输入i进行检测
     * 检测对应位图上是否置1，
     *
     * @param i
     * @return
     */
    public static boolean check(int i) {
        int index = (-1 >>> 32 - SAVE_SIZE << 6 & i) >>> 6;//获取数组的位置下标
        int code = i & 63;//截取i的后五位信息（也就是此i对应MEMERY元素的哪个位）
        long i1 = MEMORY[index] >>> code;//将i对应的位右移code位将i对应的位移动到最低位
        long i2 = i1 & 1;//将i1与1进行与操作获取此i是否在MEMORY位图中。
        return i2 == 1;

        //五步合并后，编译器化简的最终结果，这结果神仙应该也不知道这是在干啥吧。
//              return  1==((MEMORY[(-1 >>> 32 - MOVE << 6 & i ) >>> 6] >>> (i & 63))&1);
    }

    /**
     * 对外的check方法
     * 调用NUMBER次对内的check()方法，检查此key是否在名单里
     * 一旦某次check()返回位false则可确保
     *
     * @param key
     * @return
     */
    public static boolean checkKey(String key) {

        for (int i = 0; i < K_USEHASHCODENUMBER; i++) {
            Integer code = HashCodeLib.choiceHashMethod(key, i);
            if (!check(code))
                return false;
        }

        return true;
    }


    //以下是计算方法

    /**
     * 根据样本量和失误率计算所需空间的公式：
     * m = - [n*ln(p)]/[(ln2)^2]
     *
     * @param n 样本量（个）
     * @param p 失误率（小数）
     * @return 理论所需空间（bit）
     */
    public static long getNeedMemorySize(long n, double p) {
        double high = n * Math.log(p);
        double low = Math.log(2) * Math.log(2);
        long m = (long) -(high / low);//这里需要向上取整所以number要+1，但是进行
        return m + 1;
        //long number = m +1-1;
        /*long flag = Long.MIN_VALUE;
        while ((flag & m) == 0) {
            flag >>>= 1;
        }
        return flag<<1;*/

    }

    /**
     * 计算出实际分配的内存空间（位）
     *
     * @param n 样本量
     * @param p 所需失误率
     * @return 实际分配的内存空间（位）
     */
    public static long getRealMemorySize(long n, double p) {
        long m = getNeedMemorySize(n, p) - 1;

        long flag = Long.MIN_VALUE;
        while ((flag & m) == 0) {
            flag >>>= 1;
        }
        return flag << 1;

    }

    /**
     * 根据样本量和理论所需空间计算所需的hash函数个数k
     *
     * @param n 样本量
     * @param m 理论所需空间
     * @return
     */
    public static int getHashCodeMethodNumber(long n, long m) {
        int k = (int) (Math.log(2) * (m / n));
        return k + 1;
    }

    /**
     * 计算实际的失误率
     *
     * @param n 样本量
     * @param m 实际分配空间（位）
     * @param k 实际的hash函数个数
     * @return 真实失误率
     */
    public static double getRealMissProbability(long n, long m, int k) {
        float f = n * k;
        float e = f / m;
        return Math.pow((1 - Math.pow(Math.E, -e)), k);
    }

    /**
     * 返回当前实际的样本量。
     *
     * @return
     */
    public static long getNowDataNumber() {
        return nowDataNumber;
    }

    public static double getNowMissProbability() {

        double f = nowDataNumber * K_USEHASHCODENUMBER;
        double e = f / REALMEMORYBIT;
        return Math.pow((1 - Math.pow(Math.E, -e)), REALMEMORYBIT);
    }


}

二、工具类

hash函数工具类

此工具类为过滤器主类提供方法支持

主要工作逻辑是：

在静态代码块中，通过反射获取到本类中的hash函数个数

将它们添加到全局的methodList集合中

然后在过滤器调用choiceHashMethod方法时通过反射的方式执行对应的hashcode

（这样设计，方便hash函数的扩容，但是，可能会影响性能，可以将反射执行的方式更换为Switch语句直接执行方法，来提高性能，这样就失去了hash函数动态扩展的能力）

包括16个添加了@HashType()注解的hash函数

package top.boking.utils;

import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.HashMap;

/**
 * @author shxl
 * 哈希函数工具类库，集合了我自定义的各种hash函数
 */
public class HashCodeLib {
    private HashCodeLib() {
    }

    //hash当前类的函数个数
    private static final int HASHCODEMETHODNUMBER;

    private static final ArrayList<Method> methodList;//其实直接使用ArrayList就已经可以实现了。而且效率甚至更高

    /**
     * 通过反射获取当前类中的hash函数方法的个数，赋值给hashcodemethodnumber
     * （静态代码块编写，仅在类加载时执行一次，减少开销）
     */
    static {
        Method[] methods = HashCodeLib2.class.getDeclaredMethods();
        methodList = new ArrayList<>();
        int count = 0;
        if(methods != null){
            for(Method method : methods){
                HashType annotation = method.getAnnotation(HashType.class);
                if(annotation == null)
                    continue;
                methodList.add(method);
            }
        }
        methodList.forEach((k)->{
            System.out.println(k);
        });
        HASHCODEMETHODNUMBER = methodList.size();
    }

    public static int getHashcodemethodnumber(){
        return HASHCODEMETHODNUMBER;
    }
    public static Integer choiceHashMethod(String key, int kind) {
        Method method = methodList.get(kind);
        Class stringClass = String.class;
        try {
            int sxl =(int) method.invoke(stringClass,key);
            return sxl;
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        } catch (InvocationTargetException e) {
            e.printStackTrace();
        }
        /*switch (kind) {
            case 0:
                return hashCodeADD(key);
            case 1:
                return hashCodeRotating(key);
            case 2:
                return hashCodeFNV(key);
            case 3:
                return hashCodeRS(key);
            case 4:
                return hashCodeFNVandADD(key);
            case 5:
                return hashCodeFNVandRS(key);
            case 6:
                return hashCodeFNVandRS(key);
            case 7:
                return hashCodeFNVandRS(key);
            case 8:
                return hashCodeFNVandRS(key);
            case 9:
                return hashCodeFNVandRS(key);
            case 10:
                return hashCodeFNVandRS(key);
            case 11:
                return hashCodeFNVandRS(key);
            case 12:
                return hashCodeFNVandRS(key);
            case 13:
                return hashCodeFNVandRS(key);
            case 14:
                return hashCodeFNVandRS(key);
            case 15:
                return hashCodeFNVandRS(key);
            case 16:
                return hashCodeFNVandRS(key);

        }*/
        return null;
    }

    /**
     * FNV的hash算法
     *
     * @param key
     * @return 返回32位hash函数值
     */
    @HashType(HashLevel.HIGH)
    public static int hashCodeFNV(String key) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < key.length(); i++) {

            hash = (hash ^ key.charAt(i)) * p;
            hash += hash << 13;
            hash ^= hash >> 7;
            hash += hash << 3;
            hash ^= hash >> 17;
            hash += hash << 5;
        }
        return hash;
    }

    /**
     * 加法型hash
     *
     * @param key hash输入值
     * @return
     */
    @HashType(HashLevel.NORMAL)
    public static int hashCodeADD(String key) {

        int hash, i;
        for (hash = key.length(), i = 0; i < key.length(); i++)
            hash += key.charAt(i);
        return hash;

    }

    /**
     * 标准的旋转hash， 通过先移位，在进行各种位运算。 比如某个学校同一系的新生，学号前5位相同，最后2位不同，
     * 将最后2位旋转放置前两位，其余的右移。这样只要输入前两位，就可以快速查出学生的信息。
     * @param key hash key
     */
    @HashType(HashLevel.NORMAL)
    private static int hashCodeRotating(String key) {
        int hash;
        int i;
        for (hash = key.length(), i = 0; i < key.length(); i++) {
            hash = (hash<<4)^(hash>>28)^key.charAt(i);
        }
        return hash ;  //除以 一个prime的目的只是为了保证结果的范围
    }

    /**
     * 乘以一个不断该不变的数
     * @param key hash key
     * @return hash value
     */
    @HashType(HashLevel.NORMAL)
    public static int hashCodeRS(String key) {
        int b = 37855;
        int a = 63689;
        int hash = 0;
        for (int i = 0; i < key.length(); i++) {
            hash = hash * a + key.charAt(i);
            a = a * b;
        }
        return hash ;
    }



    @HashType(HashLevel.NORMAL)
    private static int hashCodeFNVandADD(String key){

        return hashCodeFNV(key)&hashCodeADD(key);
    }
    @HashType(HashLevel.NORMAL)
    private static int hashCodeFNVorADD(String key){
        return hashCodeFNV(key) | hashCodeADD(key);
    }
    @HashType(HashLevel.NORMAL)
    private static int hashCodeFNVxorADD(String key){
        return hashCodeFNV(key) ^ hashCodeADD(key);
    }


    @HashType(HashLevel.NORMAL)
    private static int hashCodeRotatingxorADD(String key){
        return hashCodeRotating(key) ^ hashCodeADD(key);
    }
    @HashType(HashLevel.NORMAL)
    private static int hashCodeRotatingorADD(String key){
        return hashCodeRotating(key) | hashCodeADD(key);
    }
    @HashType(HashLevel.NORMAL)
    private static int hashCodeRotatingandADD(String key){
        return hashCodeRotating(key)& hashCodeADD(key);
    }



    @HashType(HashLevel.NORMAL)
    private static int hashCodeRotatingorRS(String key){
        return hashCodeRotating(key) | hashCodeRS(key);
    }
    @HashType(HashLevel.NORMAL)
    private static int hashCodeRotatingandRS(String key){
        return hashCodeRotating(key) &  hashCodeRS(key);
    }
    @HashType(HashLevel.NORMAL)
    private static int hashCodeRotatingxorRS(String key){
        return hashCodeRotating(key) ^  hashCodeRS(key);
    }

    @HashType(HashLevel.NORMAL)
    private static int hashCodeFNVorRS(String key){
        return hashCodeFNV(key) | hashCodeRS(key);
    }
    @HashType(HashLevel.NORMAL)
    private static int hashCodeFNVandRS(String key){
        return hashCodeFNV(key) &  hashCodeRS(key);
    }
    @HashType(HashLevel.NORMAL)
    private static int hashCodeFNVxorRS(String key){
        return hashCodeFNV(key) ^  hashCodeRS(key);
    }




}

依赖的注解类

在HashCodeLib的方法上添加@HashType注解，表示这是一个hash函数计算方法。

枚举类代表这些hash函数的优劣（没有进行特别的检测，性能都是随便标识的）

package top.boking.utils;

import java.lang.annotation.*;

@Target(ElementType.METHOD)
//暂时将这个注解的作用域设置成runtime，如有必要再进行修改
@Retention(RetentionPolicy.RUNTIME)
/**
 * 本注解配合HsahLevel枚举类，补充HashCodeLib类库中的hashcodemethod的信息
 */
public @interface HashType {
    HashLevel value() default HashLevel.NORMAL;

}

/**
 * 配合HashType注解
 * 标记HashCodeLib基础类库的各种hash的性能等级
 * <p>
 * 分为四个等级默认是NORMAL能级
 * HIGH
 * MIDDLE
 * NORMAL
 * LOW
 */
enum HashLevel {

    HIGH, MIDDLE, NORMAL, LOW
}

内存转换工具类

package top.boking.utils;

import top.boking.bloom.MemorySize;

/**
 * 存储空间换算工具类
 */
public class MemoryUtils {

    /**
     * 输入地址位数，换算成可视化的存储空间大小返回
     *
     * @param adnum
     * @return
     */
    public static String getMemorySize(int adnum) {
        if(adnum<=3){
            return "to small";
        }
        String dw = "B";
        for (int j = 0; j < 5; j++) {
            if (j == 0) {
                dw = "B";
            }
            if (j == 1) {
                dw = "KB";
            }
            if (j == 2) {
                dw = "MB";
            }
            if (j == 3) {
                dw = "GB";
            }
            if (j == 4) {
                dw = "TB";
            }
            for (int i = 0; i < 10; i++) {
                if (adnum == (j * 10) + i + 3) {
                    int w = 1 << i;
                    return w + dw;
                }
            }
        }
        return "error";

    }

    /**
     * 已废弃
     *
     * @param ms
     * @return
     */
    @Deprecated
    public static int getNumberSize(MemorySize ms) {
        switch (ms) {
            case MB64:
                return 29;
            case MB128:
                return 30;

            case MB256:
                return 31;
            case MB512:
                return 32;
            case GB:
                return 33;
            case GB4:
                return 34;

            case GB8:
                return 35;
        }
        return -1;
    }

    /**
     * 输入存储的位数，输出可视化的存储空间大小返回
     * （位数只能是2指数）
     *
     * @param l
     * @return
     */
    public static String inBitOutSize(long l) {
        long copy = l;
        if (l == 0) {
            return "input is zero";
        }

        int size = 0, left = 0;
        while ((l & 1) == 0) {
            l >>>= 1;
            size++;
        }
        while ((copy & Long.MIN_VALUE) == 0) {
            copy <<= 1;
            left++;
        }
        if (left + size == 63)
            return getMemorySize(size);
        return "input formatter error";
    }

    /**
     * 判断输入值是否是2的指数
     * @param num
     * @return
     */
    private static boolean isFacByTwo(long num) {
        if (num == 0) {
            return false;
        }
        long copy = num;
        int left = 0, right = 0;
        while ((num & 1) == 0) {
            num >>>= 1;
            left++;
        }
        while ((copy & Long.MIN_VALUE) == 0) {
            copy <<= 1;
            right++;
        }

        return 63 == (right + left);
    }
    
    public static void main(String[] args) {

        String s = inBitOutSize(1L << 33);
        System.out.println("s = " + s);


    }

}

这篇关于纯java从0到1实现一个布隆过滤器的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程