Можно ли объединить хеш-коды для закрытых членов, чтобы создать новый хеш-код?

У меня есть объект, для которого я хочу создать уникальный хэш (переопределить GetHashCode()), но я хочу избежать переполнения или чего-то непредсказуемого.

Код должен быть результатом объединения хеш-кодов небольшой коллекции строк.

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

Будет ли что-то вроде этого достаточно И есть ли лучший способ сделать это?

int hash = 0;
foreach(string item in collection){
    hash += (item.GetHashCode() / collection.Count)
}
return hash;

РЕДАКТИРОВАТЬ: Спасибо за ответы до сих пор. @ Джон Скит: Нет, порядок не важен

Я предполагаю, что это почти другой вопрос, но поскольку я использую результат для генерации ключа кэша (строки), имеет ли смысл использовать криптографическую хеш-функцию, такую ​​как MD5, или просто использовать строковое представление этого int?

Источник

4 ответа

Решение

Фундаментальные основы, указанные Марком и Джоном, неплохие, но они далеки от оптимальных с точки зрения равномерности распределения результатов. К сожалению, подход "умножения на простые числа", скопированный многими людьми из Кнута, не является лучшим выбором во многих случаях. Лучшее распределение может быть достигнуто за счет более дешевых вычисляемых функций (хотя это очень мало для современного оборудования). Фактически, добавление простых чисел во многие аспекты хеширования не является панацеей.

Если эти данные используются для хеш-таблиц значительно большего размера, я рекомендую прочитать отличное исследование Брета Малви и объяснение различных современных (и не очень современных) методов хеширования, легко выполненных с помощью C#.

Обратите внимание, что поведение со строками различных хеш-функций сильно смещено в сторону того, являются ли строки короткими (грубо говоря, сколько символов хешируется до того, как биты начинают переполняться) или длинными.

Один из самых простых и простых в реализации, также один из лучших, Jenkins One за раз хэш.

private static unsafe void Hash(byte* d, int len, ref uint h)
{
    for (int i = 0; i < len; i++)
    {
        h += d[i];
        h += (h << 10);
        h ^= (h >> 6);
    }
}

public unsafe static void Hash(ref uint h, string s)
{
    fixed (char* c = s)            
    {
        byte* b = (byte*)(void*)c;
        Hash(b, s.Length * 2, ref h);
    }
}

public unsafe static int Avalanche(uint h)
{
    h += (h<< 3);   
    h ^= (h>> 11);  
    h += (h<< 15);  
    return *((int*)(void*)&h);
}

затем вы можете использовать это так:

uint h = 0;
foreach(string item in collection) 
{
    Hash(ref h, item);
}
return Avalanche(h);

Вы можете объединить несколько разных типов, например так:

public unsafe static void Hash(ref uint h, int data)
{ 
    byte* d = (byte*)(void*)&data;
    AddToHash(d, sizeof(int), ref h);
}

public unsafe static void Hash(ref uint h, long data)
{ 
    byte* d= (byte*)(void*)&data;
    Hash(d, sizeof(long), ref h);
}

Если у вас есть доступ к полю только как к объекту без знания внутренних элементов, вы можете просто вызвать GetHashCode() для каждого и объединить это значение следующим образом:

uint h = 0;
foreach(var item in collection) 
{
    Hash(ref h, item.GetHashCode());
}
return Avalanche(h);

К сожалению, вы не можете сделать sizeof(T), поэтому вы должны делать каждую структуру отдельно.

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

Если вы хотите избежать небезопасного кода, вы можете использовать методы маскирования битов, чтобы извлечь отдельные биты из целых чисел (и символов, если имеешь дело со строками) без особых проблем.

Источник

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

Простое добавление, как правило, не очень хорошая идея, а деление, конечно, не очень. Вот подход, который я обычно использую:

int result = 17;
foreach (string item in collection)
{
    result = result * 31 + item.GetHashCode();
}
return result;

Если вы в противном случае находитесь в проверенном контексте, вы можете сознательно сделать его неконтролируемым.

Обратите внимание, что это предполагает, что порядок важен, т. Е. {"A", "b" } должны отличаться от {"b", "a" }. Пожалуйста, дайте нам знать, если это не так.

Источник

В этом подходе нет ничего плохого, если члены, чьи хеш-коды вы комбинируете, следуют правилам хеш-кодов. Короче...

  1. Хеш-код закрытых членов не должен изменяться в течение всего времени жизни объекта
  2. Контейнер не должен изменять объект, на который указывают частные члены, чтобы в свою очередь не изменить хеш-код контейнера.
Источник

Если порядок элементов не важен (т. Е. {"A","b"} такой же, как {"b","a"}), то вы можете использовать исключительные или комбинировать хэш-коды:

hash ^= item.GetHashCode();

[Редактировать: как отметил Марк в комментарии к другому ответу, у этого недостатка также является то, что он также дает коллекциям, таким как {"a"} и {"a","b","b"} один и тот же хэш-код.]

Если порядок важен, вы можете вместо этого умножить на простое число и добавить:

hash *= 11;
hash += item.GetHashCode();

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

Источник
Другие вопросы по тегам