使用C++ Bitset实现布隆过滤器检测恶意URL时触发std::out_of_range错误的原因排查

Hey, let's break down why you're hitting this error! That giant number in the message (18446744073709551587) is actually the unsigned integer representation of -1—this tells us your hash function is returning a negative value, which gets converted to an enormous unsigned index that's way outside your 100-bit bitset.

为什么哈希函数会返回负数？ #

• 在C++里，char默认是有符号类型（取决于编译器）。如果你的数据集里的URL包含ASCII值大于127的字符（比如特殊符号、非拉丁字符或者编码异常的内容），这些char会被解析成负数。
• 当你把这些负数累加到value变量后，value也会变成负数。C++中负数对正数取模的结果还是负数（比如-1 % 100等于-1），所以你的hash1函数最终返回了一个负的ll值。
• 当你把这个负数传给bitset::set时，它会被隐式转换为size_t（无符号整数类型）。负数转成无符号数会变成超大的数值，远远超过100位bitset的上限，于是就触发了越界错误。

修复方案 #

修改你的哈希函数，确保所有字符值在参与计算前都是非负的，同时保证最终结果落在0到m-1范围内：

ll hash1(string str) {
    ll value = 0;
    for(ll i = 0; i < str.size(); i++) {
        // 将char转为无符号类型，避免高ASCII字符带来的负数问题
        value = (value + static_cast<unsigned char>(str[i])) % m;
    }
    // 额外保障：确保结果非负（虽然上面的转换已经能处理，但多一层保险）
    if (value < 0) {
        value += m;
    }
    return value;
}

额外优化建议 #

• 你现在只使用了1个哈希函数（k=1），这会让布隆过滤器的误判率非常高。建议添加多个不同的哈希函数（比如基于不同基数或移位操作的实现）来提升准确性。
• 100位的bitset对于大多数真实URL数据集来说太小了，很容易出现冲突。可以用布隆过滤器的标准计算公式，根据你预期的恶意URL数量来估算更合适的bitset大小。
• 解析数据集时可以增加额外检查，更优雅地处理空行或格式错误的行，避免row[0]或row[1]出现越界问题。

内容的提问来源于stack exchange，提问作者MercuryVapor