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

StackOverflow https://stackoverflow.com/questions/1079192

  •  21-08-2019
  •  | 
  •  

Вопрос

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

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

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

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

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

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

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

Это было полезно?

Решение

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top