Murmur3哈希算法实现

简介

https://en.wikipedia.org/wiki/MurmurHash#MurmurHash3
Murmur哈希是一种非加密散列函数,适用于一般的基于散列的查找。它在2008年由Austin Appleby创建,最新版本约为lookup3速度的两倍。 它也存在许多变种,所有这些变种都已经被公开。 该名称来自两个基本操作,乘法(MU)和旋转(R),在其内部循环中使用。

原实现

当前方舟底层实现采用hash算法为字符依次左移累加,容易造成哈希冲突,同时速度较慢:

template<typename T>
static uint32_t ComputeHashForData(const T *data, size_t size, uint32_t hashSeed)
{
    uint32_t hash = hashSeed;
    Span<const T> sp(data, size);
    for (auto c : sp) {
        constexpr size_t SHIFT = 5;
        hash = (hash << SHIFT) - hash + c;
    }
    return hash;
}

Murmur3算法实现

尝试改为Murmur3算法,hash值为32位,支持入参字符串格式为UTF8或UTF16


    // use MurmurHash3 algorithm to compute hash code
    template<typename T>
    static uint32_t ComputeHashForData(const T *data, size_t size, uint32_t hashSeed)
    {
        return MurmurShift(hash, length);
    }

可能由于方舟内部存在utf8/utf16字符串拼接,将str1计算hash值作为str2的hashseed,计算出str1+str2字符串的hash的场景;与凭借字符串buffer后计算拼接buffer的hash值不一致,导致虚拟机部分功能逻辑有误。
hash算法暂且搁置。

评论

暂无评论