Как создать уникальный хеш-код для объекта, основываясь на его содержимом?
Мне нужно создать уникальный хэш-код для объекта, основываясь на его содержимом, например. DateTime (2011,06,04) должен равняться DateTime (2011,06,04).
- Я не могу использовать .GetHashCode(), потому что он может генерировать один и тот же хеш-код для объектов с различным содержимым.
- Я не могу использовать .GetID из ObjectIDGenerator, поскольку он генерирует другой хэш-код для объектов с тем же содержимым.
- Если объект содержит другие под-объекты, ему необходимо рекурсивно проверить их.
- Он должен работать с коллекциями.
Почему мне нужно написать это? Я пишу слой кеширования с помощью PostSharp.
Обновление
Думаю, я, возможно, задавал неправильный вопрос. Как указал Джон Скит, чтобы быть в безопасности, мне нужно столько уникальных комбинаций в ключе кеша, сколько комбинаций потенциальных данных в объекте. Поэтому лучшим решением может быть создание длинной строки, которая кодирует публичные свойства объекта, используя отражение. Объекты не слишком большие, поэтому это очень быстро и эффективно:
- Он эффективен для создания ключа кеша (просто преобразуйте общедоступные свойства объекта в большую строку).
- Эффективен для проверки попадания в кеш (сравните две строки).
Ответы
Ответ 1
Если вам нужно создать уникальный хэш-код, вы в основном говорите о числе, которое может представлять столько состояний, сколько может иметь ваш тип. Я думаю, что для DateTime
, чем означает принятие значения Ticks и DateTimeKind
.
Вы можете уйти с предположением, что верхние два бита свойства Ticks
будут равны нулю и будут использовать те, которые будут хранить вид. Это означает, что вы все в порядке до 7307 года, насколько я могу судить:
private static ulong Hash(DateTime when)
{
ulong kind = (ulong) (int) when.Kind;
return (kind << 62) | (ulong) when.Ticks;
}
Ответ 2
Из комментария:
Мне нужно что-то вроде GUID на основе содержимого объектов. Я не возражаю, если иногда повторяются каждые 10 триллионов триллионов триллионов лет или около того
Это похоже на необычное требование, но, поскольку это ваше требование, сделайте математику.
Предположим, вы делаете миллиард уникальных объектов в год - тридцать в секунду - за 10 триллионов триллионов триллионов лет. Это 10 49 уникальных объектов, которые вы создаете. Разработка математики довольно проста; вероятность по крайней мере одного хеш-столкновения за это время превышает один из 10 18 когда размер бит хэша меньше 384.
Поэтому вам понадобится хотя бы 384-битный хеш-код, чтобы иметь тот уровень уникальности, который вам нужен. Это удобный размер, составляющий 12 int32. Если вы собираетесь делать более 30 объектов в секунду или хотите, чтобы вероятность была меньше одной из 10 18 тогда потребуется больше бит.
Почему у вас есть такие строгие требования?
Вот что я сделал бы, если бы у меня были ваши заявленные требования. Первая проблема состоит в том, чтобы преобразовать все возможные данные в самоописываемую последовательность бит. Если у вас уже есть формат сериализации, используйте это. Если нет, придумайте одно, которое может сериализовать все возможные объекты, которые вас интересуют в хешировании.
Затем, чтобы хэш-объект, сериализуем его в массив байтов, а затем запускаем массив байтов через алгоритм хэширования SHA-384 или SHA-512. Это создаст хеш-код 384 или 512 бит с профессиональным крипто-классом, который считается уникальным даже перед лицом нападавших, пытающихся вызвать столкновения. Этого количества бит должно быть более чем достаточно, чтобы обеспечить небольшую вероятность столкновения в три раза в три триллиона триллионов триллионов лет.
Ответ 3
Здесь вы не говорите о хэш-коде, вам нужно числовое представление вашего состояния - для того, чтобы оно было уникальным, оно может быть невероятно большим в зависимости от структуры вашего объекта.
Почему мне нужно написать это? я запись слоя кеширования с использованием PostSharp.
Почему бы вам вместо этого не использовать обычный хэш-код и не обрабатывать конфликты, фактически сравнивая объекты? Это, по-видимому, самый разумный подход.
Ответ 4
Добавление ответа BrokenGlass, которое я проголосовал и считаю правильным:
Использование метода GetHashCode
/Equals
означает, что если два объекта hash имеют одинаковое значение, вы будете полагаться на их реализацию Equals
, чтобы сказать вам, являются ли они эквивалентными.
Если эти объекты не переопределяют Equals
(что фактически означает, что они реализуют IEquatable<T>
, где T
- их тип), реализация по умолчанию Equals
будет выполнять сравнительное сравнение. Это, в свою очередь, означает, что ваш кеш ошибочно даст пропущенность для объектов, которые "равны" в бизнес-смысле, но были построены независимо.
Внимательно рассмотрите модель использования для вашего кэша, потому что если вы закончите использовать ее для классов, которые не являются IEquatable
, и таким образом, когда вы ожидаете проверки объектов без ссылки для равенства кеш окажется совершенно бесполезным.
Ответ 5
У нас было точно такое же требование, и вот функция, с которой я пришел. Это то, что хорошо работает для типов объектов, которые нам нужно кэшировать
public static string CreateCacheKey(this object obj, string propName = null)
{
var sb = new StringBuilder();
if (obj.GetType().IsValueType || obj is string)
sb.AppendFormat("{0}_{1}|", propName, obj);
else
foreach (var prop in obj.GetType().GetProperties())
{
if (typeof(IEnumerable<object>).IsAssignableFrom(prop.PropertyType))
{
var get = prop.GetGetMethod();
if (!get.IsStatic && get.GetParameters().Length == 0)
{
var collection = (IEnumerable<object>)get.Invoke(obj, null);
if (collection != null)
foreach (var o in collection)
sb.Append(o.CreateCacheKey(prop.Name));
}
}
else
sb.AppendFormat("{0}{1}_{2}|", propName, prop.Name, prop.GetValue(obj, null));
}
return sb.ToString();
}
Так, например, если у нас есть что-то вроде этого
var bar = new Bar()
{
PropString = "test string",
PropInt = 9,
PropBool = true,
PropListString = new List<string>() {"list string 1", "list string 2"},
PropListFoo =
new List<Foo>()
{new Foo() {PropString = "foo 1 string"}, new Foo() {PropString = "foo 2 string"}},
PropListTuple =
new List<Tuple<string, int>>()
{
new Tuple<string, int>("tuple 1 string", 1), new Tuple<string, int>("tuple 2 string", 2)
}
};
var cacheKey = bar.CreateCacheKey();
Кэш-ключ, сгенерированный вышеописанным методом, будет
PropString_test string | PropInt_9 | PropBool_True | PropListString_list строка 1 | PropListString_list строка 2 | PropListFooPropString_foo 1 строка | PropListFooPropString_foo 2 строка | PropListTupleItem1_tuple 1 строка | PropListTupleItem2_1 | PropListTupleItem1_tuple 2 строка | PropListTupleItem2_2 |
Ответ 6
Я не могу использовать .GetHashCode(), потому что он может генерировать один и тот же хэш-код для объектов с различным содержимым.
Это вполне нормально, если хэш-код имеет коллизии. Если ваш хеш-код имеет фиксированную длину (32 бита в случае стандартного хеш-кода .NET), то у вас есть столкновения с любыми значениями, диапазон которых больше этого (например, 64 бит в длину; n * 64 бит для массива из n longs и т.д.).
Действительно, для любого хеш-кода с конечной длиной N всегда будут столкновения для наборов из более чем N элементов.
То, о чем вы просите, в общем случае нецелесообразно.
Ответ 7
Будет ли этот метод расширения соответствовать вашим целям? Если объект является типом значения, он просто возвращает хэш-код. В противном случае он рекурсивно получает значение каждого свойства и объединяет их в один хэш.
using System.Reflection;
public static class HashCode
{
public static ulong CreateHashCode(this object obj)
{
ulong hash = 0;
Type objType = obj.GetType();
if (objType.IsValueType || obj is string)
{
unchecked
{
hash = (uint)obj.GetHashCode() * 397;
}
return hash;
}
unchecked
{
foreach (PropertyInfo property in obj.GetType().GetProperties())
{
object value = property.GetValue(obj, null);
hash ^= value.CreateHashCode();
}
}
return hash;
}
}
Ответ 8
Вы можете вычислить сумму ex md5 (или что-то в этом роде) из объекта, сериализованного в json.
Если вам нужны только некоторые свойства, вы можете создать анонимный объект на пути:
public static string GetChecksum(this YourClass obj)
{
var copy = new
{
obj.Prop1,
obj.Prop2
};
var json = JsonConvert.SerializeObject(ob);
return json.CalculateMD5Hash();
}
Я использую это для проверки того, что кто-то запутался в моей базе данных, хранящей данные на основе лицензии. Вы также можете добавить переменную json с некоторым семенем, чтобы усложнить материал