Создать уникальный ключ из хеш-кода

Question

У меня класс ниже

class Group
{
    public Collection<int> UserIds { get; set; }
    public int CreateByUserId { get; set; }
    public int HashKey { get; set; }
}

Я хочу сгенерировать несколько уникальных хеш-ключей на основе UsersIds[] и CreateByUserId, сохранить их в mongo и выполнить поиск по ним.

Условия:

1. каждый раз, когда хеш-ключ должен быть одинаковым для тех же UsersIds[] и CreateByUserId
2. хеш-ключ должен отличаться, когда число пользователей увеличивается в UsersIds[]

В душе для этого я переопределяю GetHashCode() функцию:

public override int GetHashCode()
{
    unchecked
    {
        var hash = (int)2166136261;
        const int fnvPrime = 16777619;

        List<int> users = new List<int>() { CreateByUserId };
        UserIds.ToList().ForEach(x => users.Add(x));
        users.Sort();

        users.ForEach(x => hash = (hash * fnvPrime) ^ x.GetHashCode());
        return hash;
    }
}

Это лучшее решение или предложить какое-то лучшее решение.

Answer 1

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

Функция GetHashCode не гарантирует получение уникального целочисленного хеш-ключа для каждого возможного объекта группы. Однако хорошая хеш-функция пытается минимизировать коллизии - случаи, когда один и тот же хеш-код генерируется для разных объектов. В этом ответе SO есть хорошие примеры хеш-функций: Каков наилучший алгоритм для переопределенного System.Object.GetHashCode?

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

Не было указано, какой тип равенства вы должны ожидать от объектов 'Group'. Представьте два объекта с одинаковым CreateByUserID и следующими идентификаторами пользователя: {1, 2} и {2, 1}. Они равны? Или порядок имеет значение?

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

class Group : IEquatable<Group>
{
    private readonly Collection<int> userIds;

    public ReadOnlyCollection<int> UserIds { get; }
    public int CreateByUserId { get; }
    public int HashKey { get; }

    public Group(int createByUserId, IList<int> createdByUserIDs)
    {
        CreateByUserId = createByUserId;
        userIds = createdByUserIDs != null 
           ? new Collection<int>(createdByUserIDs)
           : new Collection<int>();
        UserIds = new ReadOnlyCollection<int>(userIds);

        HashKey = GetHashCode();
    }

    public void AddUserID(int userID)
    {
        userIds.Add(userID);
        HashKey = GetHashCode();
    }

    //IEquatable<T> implementation is generally a good practice in such cases, especially for value types
    public override bool Equals(object obj) => Equals(obj as Group);

     public bool Equals(Group objectToCompare)
     {
        if (objectToCompare == null)
            return false;

        if (ReferenceEquals(this, objectToCompare))
            return true;

        if (UserIds.Count != objectToCompare.UserIds.Count || CreateByUserId != objectToCompare.CreateByUserId)
            return false;

        //If you need equality when order matters - use this
        //return UserIds.SequenceEqual(objectToCompare.UserIds);


        //This is for set equality. If this is your case and you don't allow duplicates then I would suggest to use HashSet<int> or ISet<int> instead of Collection<int>
        //and use their methods for more concise and effective comparison
        return UserIds.All(id => objectToCompare.UserIds.Contains(id)) && objectToCompare.UserIds.All(id => UserIds.Contains(id));
    }

    public override int GetHashCode()
    {
        unchecked // to suppress overflow exceptions
        {
            int hash = 17;          
            hash = hash * 23 + CreateByUserId.GetHashCode();

            foreach (int userId in UserIds)
                hash = hash * 23 + userId.GetHashCode();

            return hash;
        }
    }
}

Answer 2

Таким образом, если целью является сохранение значения хеш-функции в базе данных, не переопределяйте GetHashCode объекта, который предназначен для использования с HashTables (Dictionary, HashSet ..) в сочетании с Equals и не достаточно уникален для вашего цель. Вместо этого используйте установленную хеш-функцию, например, SHA1.

public string Hash(IEnumerable<int> values)
{
   using (var hasher = new SHA1Managed())
   {
    var hash = hasher.ComputeHash(Encoding.UTF8.GetBytes(string.Join("-", values)));
    return BitConverter.ToString(hash).Replace("-", "");
   }
}

Использование:

var hashKey = Hash(UsersIds.Concat(new[]{ CreateByUserId });

Сортировка UsersIds, если необходимо.

Answer 3

A HashKey - это значение, рассчитанное для проверки, может ли вызов Equals() дать результат, который true. Хэш-ключ используется для быстрого принятия решения, если элемент может быть правильным или если он наверняка является ложным.

Прежде всего, замените формулировку HashKey на Unique Id.

Если вам нужен уникальный Id, я бы порекомендовал использовать базу данных со столбцом Id, если вы все равно сохраните ее там, а затем получите Id с другими данными. + В БД mongo каждая запись также имеет собственный идентификатор: Смотри здесь

Каждый объект в Монго уже имеет идентификатор, и они могут быть отсортированы в порядок вставки. Что не так с получением коллекции пользователя объекты, перебирающие его и использующие в качестве увеличенного идентификатора? [...]

Таким образом: используйте БД для уникального идентификатора и вычислите HashKey (если вам это нужно больше) с помощью простой дешевой математики, такой как добавление идентификаторов пользователей.

Чтобы сделать это программно: Если вы хотите проверить его программно, а мы игнорируем идентификаторы из БД, вам необходимо реализовать функцию GetHashKey () и функцию Equals () для указанных объектов.

class Group
{
    public Collection<int> UserIds { get; set; }
    public int CreateByUserId { get; set; }

    public override bool Equals(object obj)
    {
        Group objectToCompare = (Group)obj;

        if (this.UserIds.Count != objectToCompare.UserIds.Count)
            return false;

        if (this.CreateByUserId != objectToCompare.CreateByUserId)
            return false;

        foreach (int ownUserId in this.UserIds)
            if (!objectToCompare.UserIds.Contains(ownUserId))
                return false;
        //some elements might be double, i.e. 1: 1,2,2 vs 2: 1,2,3 => not equal. cross check to avoid this error
        foreach (int foreignUserId in objectToCompare.UserIds)
            if (!this.UserIds.Contains(foreignUserId))
                return false;

        return true;
    }

    public override int GetHashCode()
    {
        int sum = CreateByUserId;
        foreach (int userId in UserIds)
            sum += userId;

        return sum;
    }
}

Использование:

Group group1 = new Group() { UserIds = ..., CreateByUserId = ...};
Group group2 = new Group() { UserIds = ..., CreateByUserId = ...};
group1.Equals(group2);

Вот ответ на вопрос «Зачем нам нужна функция GetHashCode при использовании Equals?»

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