// 基于Node.js实现布隆过滤器，适用于员工上网监控软件的URL去重与违规检测
class BloomFilter {
  /**
   * 构造函数：初始化布隆过滤器
   * @param {number} n - 预估存储的元素个数（如员工上网监控软件的违规URL数量）
   * @param {number} p - 可接受的误判率（默认0.01）
   */
  constructor(n = 100000, p = 0.01) {
    // 计算位数组长度m：m = -n * ln(p) / (ln(2))^2
    this.m = Math.ceil((-n * Math.log(p)) / Math.pow(Math.log(2), 2));
    // 计算哈希函数个数k：k = m * ln(2) / n
    this.k = Math.ceil((this.m * Math.log(2)) / n);
    // 初始化位数组，使用Buffer存储以节省空间（Node.js中Buffer效率高于数组）
    this.bitArray = Buffer.alloc(Math.ceil(this.m / 8), 0);
  }
  /**
   * 哈希函数：生成元素的哈希值（多个独立哈希函数）
   * @param {string} value - 需要哈希的元素（如URL、IP地址）
   * @returns {number[]} 多个哈希值组成的数组
   */
  hashFunctions(value) {
    const hashes = [];
    let hash = 0;
    // 生成k个不同的哈希值，基于DJB2哈希算法优化
    for (let i = 0; i < this.k; i++) {
      hash = value.charCodeAt(0) * 31 + hash;
      hash = hash ^ (value.charCodeAt(i % value.length) << (i % 24));
      hash = hash & hash; // 确保哈希值为非负整数
      // 将哈希值映射到位数组的索引范围内
      const index = hash % this.m;
      hashes.push(index);
    }
    return hashes;
  }
  /**
   * 插入元素：将元素添加到布隆过滤器中
   * @param {string} value - 需要插入的元素（如违规URL、访问记录URL）
   */
  insert(value) {
    const hashes = this.hashFunctions(value);
    hashes.forEach((index) => {
      // 计算当前位所在的字节索引和位偏移量
      const byteIndex = Math.floor(index / 8);
      const bitOffset = index % 8;
      // 将对应位设置为1（使用或运算）
      this.bitArray[byteIndex] |= 1 << bitOffset;
    });
  }
  /**
   * 查询元素：判断元素是否可能存在于布隆过滤器中
   * @param {string} value - 需要查询的元素（如当前访问的URL）
   * @returns {boolean} 存在返回true（可能误判），不存在返回false（绝对准确）
   */
  contains(value) {
    const hashes = this.hashFunctions(value);
    // 遍历所有哈希值对应的位，若有一位为0则返回false
    for (const index of hashes) {
      const byteIndex = Math.floor(index / 8);
      const bitOffset = index % 8;
      // 使用与运算判断对应位是否为1
      if ((this.bitArray[byteIndex] & (1 << bitOffset)) === 0) {
        return false;
      }
    }
    return true;
  }
}
// -------------- 员工上网监控软件中的实际应用示例 --------------
// 1. 初始化布隆过滤器（预估违规URL数量10万条，误判率0.01）
const bloomFilter = new BloomFilter(100000, 0.01);
// 2. 模拟违规URL黑名单（实际应用中可从数据库/配置文件读取）
const illegalUrls = [
  "https://www.illegal-example1.com",
  "https://www.illegal-example2.com",
  "https://www.gambling-site.com",
  "https://www.porn-site.com",
  "https://www.malicious-site.com"
];
// 3. 将违规URL插入布隆过滤器
illegalUrls.forEach(url => bloomFilter.insert(url));
console.log("违规URL黑名单已加载到布隆过滤器");
// 4. 模拟员工上网访问记录，检测是否为违规URL
const employeeAccessRecords = [
  "https://www.baidu.com", // 正常URL
  "https://www.illegal-example1.com", // 违规URL
  "https://www.office365.com", // 正常URL
  "https://www.gambling-site.com", // 违规URL
  "https://www.company-intranet.com" // 正常URL
];
console.log("\n员工上网访问记录检测结果：");
employeeAccessRecords.forEach(url => {
  const isIllegal = bloomFilter.contains(url);
  if (isIllegal) {
    console.log(`URL: ${url} - 检测到违规访问，已阻断`);
  } else {
    console.log(`URL: ${url} - 访问正常，允许通行`);
  }
});
// 5. 模拟访问记录去重（避免重复存储同一URL的访问记录）
const duplicateAccessRecords = [
  "https://www.baidu.com",
  "https://www.baidu.com",
  "https://www.office365.com",
  "https://www.baidu.com",
  "https://www.company-intranet.com"
];
const uniqueAccessRecords = [];
console.log("\n员工上网访问记录去重结果：");
duplicateAccessRecords.forEach(url => {
  if (!bloomFilter.contains(url)) {
    bloomFilter.insert(url);
    uniqueAccessRecords.push(url);
    console.log(`新增访问记录：${url}`);
  } else {
    console.log(`重复访问记录：${url}，已过滤`);
  }
});
console.log("去重后的访问记录：", uniqueAccessRecords);