局域网管理工具中的布隆过滤器Java语言算法实践

import java.util.Arrays;
import java.util.Random;
/**
 * 适配局域网管理工具的布隆过滤器实现
 * 用于设备MAC地址、IP地址等信息的快速合法性校验
 */
public class LanManagerBloomFilter {
    // 二进制向量（使用byte数组实现，1byte对应8个比特位）
    private final byte[] bitVector;
    // 二进制向量长度（比特位）
    private final int bitLength;
    // 哈希函数个数
    private final int hashCount;
    // 哈希函数种子（确保多个哈希函数的独立性）
    private final int[] hashSeeds;
    /**
     * 构造函数：初始化布隆过滤器参数
     * @param expectedN 预估插入的设备信息数量
     * @param falsePositiveRate 可接受的误判概率
     */
    public LanManagerBloomFilter(int expectedN, double falsePositiveRate) {
        // 校验输入参数合法性
        if (expectedN <= 0 || falsePositiveRate <= 0 || falsePositiveRate >= 1) {
            throw new IllegalArgumentException("参数不合法：expectedN需大于0，falsePositiveRate需在(0,1)区间");
        }
        // 计算最优二进制向量长度m
        this.bitLength = (int) Math.ceil(-(expectedN * Math.log(falsePositiveRate)) / Math.pow(Math.log(2), 2));
        // 计算最优哈希函数个数k
        this.hashCount = (int) Math.ceil((this.bitLength / (double) expectedN) * Math.log(2));
        // 初始化二进制向量（byte数组长度 = 比特位长度 / 8，不足1byte补1byte）
        this.bitVector = new byte[(int) Math.ceil(this.bitLength / 8.0)];
        // 初始化哈希种子（生成k个随机种子，确保哈希函数独立性）
        this.hashSeeds = new int[this.hashCount];
        Random random = new Random();
        for (int i = 0; i < this.hashCount; i++) {
            this.hashSeeds[i] = random.nextInt(1000) + 1; // 种子范围1-1000
        }
    }
    /**
     * 核心哈希函数：基于种子计算数据的哈希值（映射到二进制向量索引）
     * @param data 待哈希的数据（如设备MAC地址、IP地址）
     * @param seed 哈希种子
     * @return 映射后的二进制向量索引
     */
    private int hash(String data, int seed) {
        int hash = 0;
        for (char c : data.toCharArray()) {
            // 混合字符ASCII码与种子计算哈希值，提升分散性
            hash = seed * hash + c;
        }
        // 取模运算，确保哈希值落在二进制向量索引范围内
        return Math.abs(hash) % this.bitLength;
    }
    /**
     * 插入设备信息：将合法设备信息录入布隆过滤器
     * @param deviceInfo 待插入的设备信息（如"00:1B:44:11:3A:B7"）
     */
    public void insert(String deviceInfo) {
        if (deviceInfo == null || deviceInfo.isEmpty()) {
            throw new IllegalArgumentException("设备信息不能为空");
        }
        for (int seed : this.hashSeeds) {
            int index = hash(deviceInfo, seed);
            // 计算对应的byte索引和bit索引
            int byteIndex = index / 8;
            int bitIndex = index % 8;
            // 位运算：将对应bit位置置为1
            this.bitVector[byteIndex] |= (1 << bitIndex);
        }
    }
    /**
     * 校验设备合法性：判断设备信息是否在合法名单内
     * @param deviceInfo 待校验的设备信息
     * @return 合法（大概率存在）返回true，不合法（绝对不存在）返回false
     */
    public boolean isLegalDevice(String deviceInfo) {
        if (deviceInfo == null || deviceInfo.isEmpty()) {
            throw new IllegalArgumentException("设备信息不能为空");
        }
        for (int seed : this.hashSeeds) {
            int index = hash(deviceInfo, seed);
            int byteIndex = index / 8;
            int bitIndex = index % 8;
            // 位运算：判断对应bit位是否为1，若为0则直接返回false
            if ((this.bitVector[byteIndex] & (1 << bitIndex)) == 0) {
                return false;
            }
        }
        return true;
    }
    // 测试方法：模拟局域网管理工具的设备合法性校验场景
    public static void main(String[] args) {
        // 1. 初始化布隆过滤器（预估5000台合法设备，误判率0.001）
        LanManagerBloomFilter bloomFilter = new LanManagerBloomFilter(5000, 0.001);
        
        // 2. 模拟插入局域网合法设备信息（MAC地址）
        String[] legalDevices = {
            "00:1B:44:11:3A:B7", "00:1C:23:4D:5E:6F", "00:2D:3E:4F:5A:6B",
            "00:3E:4F:5A:6B:7C", "00:4F:5A:6B:7C:8D"
        };
        System.out.println("开始录入合法设备信息...");
        for (String device : legalDevices) {
            bloomFilter.insert(device);
            System.out.println("已录入合法设备：" + device);
        }
        
        // 3. 模拟局域网管理工具的设备接入校验场景
        String[] accessDevices = {
            "00:1B:44:11:3A:B7", // 合法设备
            "11:22:33:44:55:66", // 非法设备
            "00:1C:23:4D:5E:6F", // 合法设备
            "AA:BB:CC:DD:EE:FF", // 非法设备
            "00:2D:3E:4F:5A:6B"  // 合法设备
        };
        
        System.out.println("\n=== 局域网管理工具设备接入校验结果 ===");
        for (String device : accessDevices) {
            boolean isLegal = bloomFilter.isLegalDevice(device);
            String result = isLegal ? "合法设备，允许接入" : "非法设备，拒绝接入";
            System.out.println("设备MAC：" + device + " - 校验结果：" + result);
        }
    }
}