Можно ли комбинировать хеш-коды для частных членов для генерации нового хеш-кода?

Ответ 1

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

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

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

Один из самых простых и простых в реализации - также один из лучших, 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), поэтому вы должны делать каждую структуру индивидуально.

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

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

Ответ 4

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

hash ^= item.GetHashCode();

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

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

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

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