четверг, 7 апреля 2016 г.

C#: Why Dictionary with hashcode as key is dangerous

Recently, I encountered following code:

        private readonly Dictionary<int, View> _listCellsForDisposal;
            if (!_listCellsForDisposal.Contains(view.GetHashCode()))
             {
                _listCellsForDisposal.Add(view.GetHashCode(), view);
             }

The intent of that code is just add item to the list if it doesn't present. But is it doing work well? It doesn't. Let's see why.

At first, let's look at the signature of GetHashCode:

public override int GetHashCode()

So, it returns int. int in c# is platform-dependent. For example int32 takes 4 bytes, it's range is:

-2,147,483,648 to 2,147,483,647

(source: https://msdn.microsoft.com/ru-ru/library/5kzh1b5w.aspx)

But how many objects can we add to the dictionary?
Is it limited to about 4 billions (int32 can count) ? Obviously, not. It's limited just with computer's memory. That's the first point (1)

How do you think we access values of dictionary so fast? One of the simplest implementation of Dictionary is an array where key's hashcode is used as index. But 2 different objects can have same hashcode (at least because of (1)). So, how do we store that 2 objects? The only left solution is to keep not 1 object per hashcode but many, so use list. And to differentiate equals() comes into play.

(source: https://msdn.microsoft.com/en-us/library/4yh14awz(v=vs.110).aspx)

So, general rule to write equals and hashcode is:
1. hashcode may be same for 2 different objects
2. if equals() return true for 2 objects, than hashcode must be equal too

Keeping that in mind will return to code:

private readonly Dictionary<int, View> _listCellsForDisposal;
            if (!_listCellsForDisposal.Contains(view.GetHashCode()))
             {
                _listCellsForDisposal.Add(view.GetHashCode(), view);
             }

So, what does that code do? Keeping in mind that 2 different views can have same hashcode it just wount add 2nd object to dictionary. The proper solution will be:

private readonly Dictionary<View, View> _listCellsForDisposal;
            if (!_listCellsForDisposal.Contains(view))
             {
                _listCellsForDisposal.Add(view, view);
             }

Or simply:

private readonly HashSet<View> _listCellsForDisposal;
            if (!_listCellsForDisposal.Contains(view))
             {
                _listCellsForDisposal.Add(view);
             }

Комментариев нет:

Отправить комментарий