Быстрая хеш-функция для строки в C #

Question

Я хочу хэшировать строку длиной до 30. Какая будет лучшая идея сделать это, если время будет моей заботой.Функция будет вызываться более 100 миллионов раз.В настоящее время я использую следующий код,

static UInt64 CalculateHash(string read, bool lowTolerance)
{
    UInt64 hashedValue = 0;
    int i = 0;
    while (i < read.Length)
    {
        hashedValue += read.ElementAt(i) * (UInt64)Math.Pow(31, i);
        if (lowTolerance) i += 2;
        else i++;
    }
    return hashedValue;
}

Answer 1

static UInt64 CalculateHash(string read)
{
    UInt64 hashedValue = 3074457345618258791ul;
    for(int i=0; i<read.Length; i++)
    {
        hashedValue += read[i];
        hashedValue *= 3074457345618258799ul;
    }
    return hashedValue;
}

Это хэш Кнута.Вы также можете использовать Jenkins .

Answer 2

Прежде всего, рассмотрите возможность использования GetHashCode().

Простое улучшение существующей реализации:

static UInt64 CalculateHash(string read, bool lowTolerance)
{
    UInt64 hashedValue = 0;
    int i = 0;
    ulong multiplier = 1;
    while (i < read.Length)
    {
        hashedValue += read[i] * multiplier;
        multiplier *= 37;
        if (lowTolerance) i += 2;
        else i++;
    }
    return hashedValue;
}

Это позволяет избежать дорогостоящих вычислений с плавающей запятой и накладных расходов ElementAt.

Кстати (UInt64)Math.Pow(31, i) не подходит для длинных струн. Округление с плавающей точкой приведет к умножению 0 для символов старше 15 или около того.

Answer 3

Чтобы ускорить реализацию, вызов (UInt64)Math.Pow(31, i) должен быть заменен поиском: предварительно рассчитайте таблицу из первых 30 степеней 31 и используйте ее во время выполнения.Поскольку ограничение на длину составляет 30, вам нужно только 31 элемент:

private static unsigned long[] Pow31 = new unsigned long[31];

static HashCalc() {
    Pow31[0] = 1;
    for (int i = 1 ; i != Pow31.Length ; i++) {
        Pow31[i] = 31*Pow31[i-1];
    }
}

// In your hash function...
hashedValue += read.ElementAt(i) * Pow31[i];

Answer 4

Я играл с реализациями Пола Се, и, кажется, быстр с небольшими коллизиями (в любом случае для моих сценариев)

• http://www.azillionmonkeys.com/qed/hash.html