С# Лучший способ создать уникальный идентификатор int32 для сложного объекта

У меня проблема с получением уникального идентификатора int32 с этими свойствами:

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

Мне нужен этот уникальный идентификатор для сравнения сложных объектов и работы с такими классами, как Dictionary‹> или HashSet‹> и т. д.

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

Псевдокод объекта:

    class ComplexObject
    {
        public readonly FirstEnum First; // ~50 different values
        public readonly IFirstModificator FirstModificator; // 4 implementations x 15 values (~60 values total)
        public readonly InternalObject[] Internal; //1-10 values in array 
    }

    class InternalObject
    {
        public readonly SecondEnum Second; // ~30 different values
        public readonly SecondModificator SecondModificator; //  ~15 different values
    }

Если это важно, моя доменная модель содержит около 100 000 уникальных объектов типа ComplexObject.

Я уже пробовал:

  • Сериализация объекта в json и получение хэша этой строки (используя метод string.GetHashCode()). Он создает коллизии даже в текущем экземпляре программы.
  • Подобный код также вызывает много коллизий:
    unchecked
    {
        int hash = 17;
        hash = hash * 31 + firstField.GetHashCode();
        hash = hash * 31 + secondField.GetHashCode();
        return hash;
    }

    unchecked 
    {
        int hash = (int) 17;
        hash = (hash * 31) ^ field1.GetHashCode();
        hash = (hash * 31) ^ field2.GetHashCode();
        return hash;
    }

ОБНОВЛЕНО:

IFirstModificator имеет разные реализации, но в целом выглядит так:

    class FirstModificator : IFirstModificator
    {
        public int Value {get;set;} //~15 values
    }

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

    class SecondModificator 
    {
        public int Value {get;set;} //~15 values
    }

Внешний интерфейс и данные, необходимые для создания экземпляра класса, аналогичны реализации IFrstModificator, но на самом деле это разные классы.


person CodeYourProfit    schedule 19.06.2020    source источник
comment
Int32 имеет всего 32 бита для игры, и этого просто недостаточно, чтобы гарантировать хеширование без коллизий для такого количества объектов (при условии, что вы не можете использовать какие-либо специальные свойства распределения значений). Обратите внимание, однако, что хеширование без коллизий не требуется для правильного использования таких классов, как Dictionary; коллизия просто означает, что производительность будет немного меньше, поскольку несколько объектов будут занимать одно и то же ведро. Поиск в списке 2 или 3 столкнувшихся объектов не намного медленнее, чем просто выборка одного.   -  person Jeroen Mostert    schedule 19.06.2020
comment
Если ваши замечания о количестве различных значений точны, может показаться, что на самом деле у вас не более 2^31 уникальных возможных объектов, а это означает, что вы определенно можете создать хэш, который уникальным образом хэширует уникальные объекты. По сути, это включает в себя присвоение уникального номера каждой комбинации, поэтому адаптируйте его к своему распределению (например, хешируйте InternalObject, сопоставив все значения SecondModificator с 0-15 и Second с 0-30, затем выполните SecondModificator * 16 + Second). Конечно, это может быть намного сложнее, чем просто общий хэш.   -  person Jeroen Mostert    schedule 19.06.2020
comment
Обратите внимание, что в случае, если ваше сравнение на равенство очень медленное и является узким местом при столкновениях (что может быть в случае с очень большими объектами), вы можете ускорить процесс, вычислив второй, больший хеш (даже Int64 будет достаточно) , сохраняя его вместе с вашим объектом (или отдельным ConditionalWeakTable) и проверяя его на совпадение, прежде чем выполнять полное сравнение на равенство. Однако ваши объекты не кажутся достаточно большими, чтобы гарантировать это, занимая не более нескольких байтов. Столкновения должны стать очень серьезными, прежде чем это действительно станет проблемой.   -  person Jeroen Mostert    schedule 19.06.2020
comment
Можете ли вы предоставить некоторые подробности о IFirstModificator и SecondModificator и их реализации? Кроме того, что составляет идентичность для объекта? Возможно ли иметь повторяющиеся объекты InternalObject или повторяющиеся объекты ComplexObject, которые должны рассматриваться как разные?   -  person NetMage    schedule 20.06.2020
comment
@jeroen-mostert Спасибо за совет. В этом случае важно, чтобы разные (не одинаковые по важным для модели предметной области параметрам) объекты не помещались в один и тот же ковш по множеству причин, а в случае коллизий, которые случаются иногда.   -  person CodeYourProfit    schedule 20.06.2020
comment
@netmage я обновил основной пост, чтобы ответить на ваши вопросы.   -  person CodeYourProfit    schedule 20.06.2020
comment
Возможно ли дублирование объектов InternalObject или дублирование объектов ComplexObject, которые должны рассматриваться как разные? Под дубликатами я подразумеваю объекты с одинаковыми значениями полей, которые должны обрабатываться по-разному для HashCode целей.   -  person NetMage    schedule 23.06.2020
comment
@netmage нет, это невозможно. Любые объекты с одинаковыми значениями полей равны по этому значению идентификатора (хешу).   -  person CodeYourProfit    schedule 29.06.2020
comment
Имеет ли значение порядок членов массива InternalObject? Должен ли хэш-код отражать, находятся ли они в другом порядке в двух ComplexObject?   -  person NetMage    schedule 30.06.2020


Ответы (1)


Итак, это пример реализации, который предлагал @JeroenMostert.

Во-первых, вы можете создать хэш-код InternalObject на основе возможных значений различных полей:

class InternalObject { // ~450 different values
    public readonly SecondEnum Second; // ~30 different values
    public readonly SecondModificator SecondModificator; //  ~15 different values

    public override int GetHashCode() {
        var hc = (int)Second; // use 5 bits
        // assume SecondModificator.Value values range from 0 - 15 or can be normalized
        hc = hc << 5 + SecondModificator.Value;
        return hc;
    }
}

Затем вы можете создать хэш-код для ComplexObject на основе возможных значений каждого поля. Эта реализация хэш-кода предполагает, что все поля IFirstModificator.Value будут иметь значения от 0 до 15, и что вы не хотите добавлять новое поле int в IFirstModificator, представляющее, какая реализация хранится в ComplexObject, поэтому вместо этого я использую Reflection для сопоставления фактического типа реализации с int от 1 до 4. Если какое-либо из свойств Value не является простым диапазоном от 0 до 15, вы должны нормализовать их до этого диапазона, используя их известные возможные значения.

class ComplexObject {
    public readonly FirstEnum First; // ~50 different values
    public readonly IFirstModificator FirstModificator; // 4 implementations x 15 values (~60 values total)
    public readonly InternalObject[] Internal; //1-10 values in array => ~4500 different values

    static Dictionary<Type, int> FirstModMap = new[] { typeof(FirstModificator1), typeof(FirstModificator2), typeof(FirstModificator3), typeof(FirstModificator4) }
                                                .Select((t, n) => new { t, n })
                                                .ToDictionary(tn => tn.t, tn => tn.n + 1);
    public override int GetHashCode() {
        var hc = (int)First; // use 6 bits
        // assume IFirstModificator.Value values are 0 - 14 or normalize to be so
        hc = hc << 6 + (FirstModificator.Value * FirstModMap[FirstModificator.GetType()]); // uses 6 bits
        // assume InternalObject[] order matters
        hc = hc << 12 + Internal.Select((io, n) => io.GetHashCode() * (n + 1)).Sum(); // uses 13 bits

        return hc;
    }
}
person NetMage    schedule 29.06.2020