时间戳

首页 > 解决方案 > 这是一个很好的短字符串散列函数吗？

c++ - 这是一个很好的短字符串散列函数吗？

问题描述

对于 10-50 个字符的字符串：

double hash(const std::string & str)
{
    double result = 0;
    int n=str.length();
    for(int i=0;i<n;i++)
    {
        result += (str[i] - '@')*pow(256.0,i);
    }
    return result;
}

这可以在生产代码中使用吗？

新版本的评论：

double hash(const std::string & str)
{
    double result = 0;
    int n=str.length();

    // maybe using multiple adders to do concurrently multiple chars
    // since they are not dependent
    for(int i=0;i<n;i++)
    {
        result += lookupCharDoubleType[str[i]]*lookupPow[i];
    }
    return result;
}

另一个评论的另一个版本：

double hash(const std::string & str)
{
    double result = 0;
    int n=str.length();

    for(int i=0;i<n;i++)
    {
        result = result * 256.0 + lookupCharDoubleType[str[i]];
    }
    return result;
}

标签： c++stringhash

解决方案

这是一个很好的短字符串散列函数吗？

不，这不是唯一性的好散列。您基本上是将字符串映射到double. 对于一个长度为 50 个字符的字符串，您将获得一个大约为 的值256 ^^ 50，即 2.58e120。这完全在双精度范围内，即 1.7e308，但您必须了解它double并不完全代表数字——毕竟它只有 8 个字节长。

您的代码将字符串映射到 a double，就好像字符是 base-256 数字一样，第一个字符是最低有效数字：

字符串hello映射如下：

'h' * 256^^0 + 'e'*256^^1 + 'l' * 256^^2 + 'l' * 256^^3 + 'o' * 256^^4

对于大于几个字节的字符串，最后一个字符将是结果中最重要的部分，所有其他字符将被完全删除，因为 adouble没有表示所有这些位的精度。

最终结果是您的哈希函数将只考虑最后几个字符。一个好的散列函数应该在字符串中的任何字符发生变化时发生变化，因此相似但不完全相同的字符串极不可能具有相同的散列值。使用您的函数，只要最后几个字符相同，哈希值就可能相同。

推荐阅读