526互联

字符串hash相关

发布时间 2023-11-23 15:40:25作者: tianlonghuangwu

哈希

c++里常用的hash是map和unordered_map
前者是平衡树实现的, O(logn)的插入和搜索, 后者是O(1)的插入和搜索
但是前者有序, 后者无序
本文讲的是后者

关于实现

基本类型可以视所需空间大小选择不同的hash办法
而我着重讲一下字符串的hash

在字符串hash里

  1. DJB hash
  2. SDBM hash
  3. BKDR hash

这些都是常见的hash

关于空间

这里提一下, hash有"负载因子"一说

负载因子 衡量哈希表满的程度的指标, 当元素数量/桶数量 > 负载因子时, hash表会进行重新hash

用unordered_map的时候一开始就要reverse扩容到自己需要的空间, 不然随着元素增多, 他会rehash, 浪费性能

自己写hash表的时候, 我听说一般都是直接开4N的空间, 原理未知, 可能是性价比比较高吧, 在我看来, 肯定是空间允许的话, 开的越大越好

关于碰撞

碰撞我一般直接直接链起来, 来判断即可.
比较简单

hash算法碰撞测试

测一下两个简单的hash, djb和bkdr

#include <bits/stdc++.h>
#include <chrono>
using namespace std;

#define HASH_SIZE 100000
#define HASH_TABLE_SIZE (HASH_SIZE << 2)
#define MOD (HASH_TABLE_SIZE)
int m_count[HASH_TABLE_SIZE];

vector<string> generate_string(int num, int max_length)
{
    vector<string> strings;
    strings.reserve(num);
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> length_dist(1, max_length);
    uniform_int_distribution<> char_dist(32, 126);
    for (int i = 0; i < num; i++)
    {
        int len = length_dist(gen);
        string str;
        str.reserve(len);
        for (int j = 0; j < len; j++)
        {
            str.push_back(static_cast<char>(char_dist(gen)));
        }
        strings.push_back(str);
    }
    return strings;
}

unsigned long long BKDRhash(char *c)
{
    unsigned long long seed = 131;
    unsigned long long hash = 0;
    while (*c)
    {
        hash *= seed;
        hash += (*c++);
    }
    return hash % MOD;
}

unsigned long long DJBhash(char *c)
{
    unsigned long long hash = 5381;
    while (*c)
    {
        hash += (hash << 5);
        hash += (*c++);
    }
    return hash % MOD;
}

void test(std::function<unsigned long long(char *c)> f, std::vector<string> &strings)
{
    memset(m_count, 0, sizeof(m_count));
    auto start = std::chrono::high_resolution_clock::now();
    for (auto &str : strings)
    {
        m_count[f(&str[0])]++;
    }
    int collision = 0;
    for (int i = 0; i < HASH_TABLE_SIZE; i++)
    {
        if (m_count[i] > 1)
        {
            collision++;
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "Time taken by function: " << duration.count() << " milliseconds" << std::endl;
    cout << "collision: " << collision << endl;
}

int main()
{
    vector<string> strs = generate_string(100000, 1000);
    test(BKDRhash, strs);
    test(DJBhash, strs);
    return 0;
}

上面代码跑出来结果是

Time taken by function: 144 milliseconds
collision: 10659
Time taken by function: 161 milliseconds
collision: 10696

然后我把哈希表又放大了4倍, 果然跟我想的一样, 碰撞少了

collision: 2934
collision: 3059

那其实没有什么空间要开多大的说法, 本来就是允许的话越大越好.
而且bkdr的hash性能似乎更好一些, 虽然我也看不懂为什么乘法会比位移更好
不懂, 反正事实如此, 开完O2后两个差不多, 那看来可能是没优化吧
seed的选择也相当无所谓, 我是没测出来素数好在哪