从哈希码生成唯一密钥

Question

我下面有 class

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

我想根据 UsersIds[] 和 CreateByUserId 生成一些唯一的哈希键并将其存储到 mongo 并在其上搜索。

条件：

对于相同的 UsersIds[] 和 CreateByUserId
hashkey 在 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

A HashKey 是一个计算值，用于检查 Equals() 的调用是否会产生 true 的结果。如果元素可能是正确的或者肯定是错误的，则哈希键用于快速做出决定。

首先，将 HashKey 替换为 Unique Id。

如果您想要一个唯一的 Id，我建议您使用带有 Id 列的数据库，如果您无论如何都将它存储在那里，然后使用其他数据获取 Id。 + 在 mongo DB 中，每个条目也已经有自己的 ID：参见 here

Each object in mongo already has an id, and they are sortable in insertion order. What is wrong with getting collection of user objects, iterating over it and use this as incremented ID?[...]

这种方式：使用数据库作为唯一 ID，并使用简单的廉价数学计算您的 HashKey（如果您不再需要它），例如将用户 ID 相加。

以编程方式实现：如果您想以编程方式检查它并且我们忽略来自数据库的 ID，则需要实现给定对象的 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);

Here is the answer to "Why do we need the GetHashCode-Function when we use Equals?"

注意：对于此处的 Equals()-方法，这肯定不是最高效的解决方案。根据需要进行调整。

Answer 2

一般来说，如果没有关于数据的一些额外信息，您无法从一大堆其他整数中创建唯一的整数。如果对其允许值的范围没有限制，即使是单个 long 值也不能创建唯一的 int 键。

GetHashCode 函数不保证您为每个可能的组对象获得唯一的整数哈希键。但是，好的散列函数会尽量减少冲突 - 为不同对象生成相同散列码的情况。这个 SO 答案中有很好的哈希函数示例： What is the best algorithm for an overridden System.Object.GetHashCode?

通常您需要 GetHashCode 将对象作为键存储在字典和哈希集中。就像前面的回答所说，您需要为这种情况覆盖 Equals 方法，因为像字典和哈希集这样的哈希表通过将具有相同哈希码的项目存储在称为桶的列表中来解决冲突。他们使用 Equals 方法来识别桶中的项目。作为预防措施，建议在覆盖 GetHashCode 时覆盖 Equals。

未指定您希望 'Group' 对象具有哪种类型的相等性。假设两个对象具有相同的 CreateByUserID 和以下 UserId：{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 3

因此，如果打算将哈希值保存在数据库中，请不要覆盖对象上的 GetHashCode，这是为了与 HashTables（字典、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。

从哈希码生成唯一密钥

Generate unique key from hashcode

.net

c#

gethashcode