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算法暂且搁置。

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论