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

Я хочу хэшировать строку длиной до 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;
}

Ответы

Ответ 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.

Ответ 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.

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

Ответ 3

Я играл с реалиями Paul Hsieh и, кажется, быстро с небольшими коллизиями (для всех моих сценариев)

Ответ 4

Чтобы ускорить реализацию, вызов (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];