Generate unique key from hashcode

Question

I am having class below

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

I want to generate some unique hashkey based on UsersIds[] and CreateByUserId and store it to mongo and search on it.

Conditions:

1. each time the hashkey should me same for same UsersIds[] and CreateByUserId
2. hashkey should be different when number of users increases in UsersIds[]

In a soultion for this I am overriding GetHashCode() function:

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

Is it a better solution or suggest some better solution.

Answer 1

So if the intention is to save the hash value in the database dont override GetHashCode on the object, that is for use with HashTables (Dictionary, HashSet..) in conjunction with Equals and not unique enough for your purpose. Instead use an established hash function such as SHA1 for example.

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("-", "");
   }
}

Usage:

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

Sort UsersIds if so desired.

Answer 2

A HashKey is a value calculated to check if a call of Equals() may yield a result that's true. The hashkey is used to make a fast desicion if the element may be the right one or if it's for sure the false one.

First thing is, replace the wording HashKey with Unique Id.

If you want a unique Id, I'd recommend using the database with a Id column if you store it there anyway and then fetch the Id with the other data. + In mongo DB, each entry also already has a own Id: See 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?[...]

That way: Use the DB for the unique ID and calculate your HashKey (if you need it anymore) with simple cheap math like adding up the user Ids.

To make it programatically: If you want to check it programatically and we ignore Ids from the DB, you need to implement the GetHashKey()-Function and the Equals()-Function of the given objects.

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

Usage:

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?"

Note: This is for sure not the most performant solution for the Equals()-Method here. Adjust as needed.

Answer 3

In general, without some extra information about the data, you cannot create unique integer from a whole bunch of other integers. You cannot create unique int key even from a single long value if there are no constraints on its range of allowed values.

The GetHashCode function does not guarantee that you get unique integer hash key for every possible Group object. However, the good hash function tries to minimize collisions - cases when the same hashcode is generated for different objects. There are good examples of hash functions in this SO answer: What is the best algorithm for an overridden System.Object.GetHashCode?

Usually you need GetHashCode to store object as a key in dictionaries and hashsets. Like the previous answer said you need to override Equals method for that case because hashtables like dictionaries and hashsets resolve the collision by storing items with the same hashcode in lists called buckets. They use Equals method to identify the item in the bucket. It is recommended practice to override Equals when you are overriding GetHashCode just as a precaution.

It was not specified what type of equality should you expect from 'Group' objects. Imagine two objects with the same CreateByUserID and the following UserIds: {1, 2} and {2, 1}. Are they Equal? Or the order matters?

It's not a good idea to allow changes for Group fields from any place. I would implemented it with read only fields like this:

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