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

Question

Мне нужно сгенерировать уникальный хэш-код для объекта на основе его содержимого, например, DateTime (2011,06,04) должен равняться DateTime (2011,06,04).

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

Почему мне нужно это написать? Я пишу кеширующий слой, используя PostSharp.

Обновление

Думаю, я задавал не тот вопрос. Как отметил Джон Скит, чтобы быть в безопасности, мне нужно столько уникальных комбинаций в ключе кеша, сколько есть комбинаций потенциальных данных в объекте. Поэтому лучшим решением может быть создание длинной строки, которая кодирует общедоступные свойства объекта с использованием отражения. Объекты не слишком большие, поэтому это очень быстро и эффективно:

• Эффективно создавать ключ кэша (просто преобразовать открытые свойства объекта в большую строку).
• Эффективно проверять попадание в кеш (сравните две строки).

Answer 1

Из комментария:

Мне бы хотелось что-то вроде GUID на основе содержимого объектов. Я не против, если есть случайный дубликат каждые 10 триллионов триллионов лет или около того

Это кажется необычным требованием, но так как это ваше требование, давайте посчитаем.

Предположим, вы создаете миллиард уникальных объектов в год - тридцать в секунду - за 10 триллионов триллионов лет. Это 10 ⁴⁹ уникальных объектов, которые вы создаете. Выработать математику довольно легко; вероятность, по крайней мере, одного коллизии хэша за это время выше единицы в 10 ¹⁸ , когда размер бит хэша меньше 384.

Поэтому вам понадобится как минимум 384-битный хеш-код, чтобы иметь требуемый уровень уникальности. Это удобный размер, равный 12 int32s. Если вы собираетесь создавать более 30 объектов в секунду или хотите, чтобы вероятность была меньше единицы в 10 ¹⁸ , тогда потребуется больше битов.

Почему у вас такие строгие требования?

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

Затем, чтобы хэшировать объект, сериализовать его в байтовый массив, а затем запустить байтовый массив с помощью алгоритма хеширования SHA-384 или SHA-512. Это создаст хеш-код профессионального уровня 384 или 512 бит, который считается уникальным даже перед лицом атакующих, пытающихся вызвать столкновения. Этого количества бит должно быть более чем достаточно, чтобы обеспечить низкую вероятность столкновения на вашем таймфрейме в десять триллионов триллионов лет.

Answer 2

Если вам нужно создать уникальный хеш-код, тогда вы в основном говорите о числе, которое может представлять столько состояний, сколько может иметь ваш тип. Я полагаю, что для DateTime значение означает значение Ticks и значение DateTimeKind.

Возможно, вам удастся предположить, что верхние два бита свойства Ticks будут равны нулю, и использовать их для хранения вида. Это значит, что ты в порядке до 7307 года, насколько я могу судить:

private static ulong Hash(DateTime when)
{
    ulong kind = (ulong) (int) when.Kind;
    return (kind << 62) | (ulong) when.Ticks;
}

Answer 3

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

почему мне нужно это написать?Я пишу кеширующий слой, используя PostSharp.

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

Answer 4

Вы можете вычислить сумму 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 с некоторыми затравками для усложнения вещей

Answer 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 | PropInt_9 | PropBool_True | Строка PropListString_list 1 | Строка PropListString_list 2 | Строка PropListFooPropString_foo 1 | строка |

Answer 6

Дополнение к ответу BrokenGlass, за которое я проголосовал и считаю правильным:

Использование метода GetHashCode / Equals означает, что если два объекта хешируют одно и то же значение, вы будете полагаться в их реализации Equals, чтобы сообщить вам, эквивалентны ли они.

Если эти объекты не переопределяют Equals (что фактически означает, что они реализуют IEquatable<T>, где T - это их тип), реализация по умолчанию Equals выполнит сравнение ссылок. Это, в свою очередь, означает, что ваш кеш по ошибке даст пропущенный для объектов, которые «равны» в деловом смысле, но были сконструированы независимо.

Внимательно рассмотрите модель использования вашего кэша , потому что, если вы в конечном итоге используете ее для классов, которые не IEquatable, и таким образом, где вы ожидаете проверять объекты, не равные ссылкам равенство, кэш окажется совершенно бесполезным .

Answer 7

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

Вполне нормально, что хеш-код имеет коллизии.Если ваш хеш-код имеет фиксированную длину (32 бита в случае стандартного хеш-кода .NET), то вы неизбежно столкнетесь с любыми значениями, диапазон которых больше этого (например, 64 бита для длинных; n * 64)биты для массива из n длинных и т. д.).

Фактически для любого хеш-кода с конечной длиной N всегда будут коллизии для коллекций из более чем N элементов.

Что вы 'В общем случае просить нереально.

Answer 8

Подойдет ли этот метод расширения вашим целям?Если объект является типом значения, он просто возвращает свой хэш-код.В противном случае он рекурсивно получает значение каждого свойства и объединяет их в один хеш.

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;
    }
}