Это хорошая функция хеширования для коротких строк?

Question

Для строк длиной 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;
}

Можно ли это использовать в производственном коде?

• увеличение общей пропускной способности хеширования при использовании с std :: hashпо ILP
• правильность / уникальность
• масштабируемость

новая версия по комментариям:

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;
}

Answer 1

Это хорошая функция хеширования для коротких строк?

Нет, это не очень хороший хеш для уникальности. Вы в основном отображаете строку наdouble.Для строки длиной 50 символов вы получите значение порядка 256 ^^ 50, равного 2.58e120.Это хорошо в пределах диапазона двойного , который равен 1.7e308, но вы должны понимать, что double точно не представляет числа - это всего лишь 8 байтов в конце концов.

ВашКод отображает строку в double, как если бы символы были цифрами от 256 до 256, причем первый символ является наименее значимой цифрой:

Строка hello отображается следующим образом:

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

Для строки размером более нескольких байтов последние символы будут, безусловно, самой значимой частью результата, а все остальные символы будут отброшены целиком, потому что double не имеет точности для представления всехэти биты.

Конечным результатом является то, что ваша хеш-функция будет учитывать только последние несколько символов. Хорошая хеш-функция должна меняться всякий раз, когда любой символов визменение строки, так что строки, которые похожи, но не совпадают, крайне маловероятно, чтобы иметь одинаковое значение хеш-функции.С вашей функцией хэш-значения, вероятно, будут одинаковыми, если последние несколько символов одинаковы.