CODEWITHSUNDEEP
c#dictionaryhash
Blankman
Blankman

Reputation: 267030

Internally, how do hashes lookup the key to get the value?

Internally, how do hashes lookup the key to get the value?

Would it be bin sort?

Upvotes: 3

Views: 231

Answers (2)

Mark Byers
Mark Byers

Reputation: 838296

A Dictionary uses the hashcode to calculate the number of the bucket in which the entry is stored. The number of buckets is chosen to be a prime number and the bucket number for a specific key is calculated as the hash code of the key modulo the number of buckets. Because multiple objects can have the same hash code, and multiple hash codes can land in the same bucket, when a key is found in a bucket it must also be compared for equality to be sure it is the correct key. If an incorrect key is found in the bucket, the next member of the wrong entry is used to find the next place to search for the desired key.

The result of this algorithm is that when there are no collisions the correct bucket can be found very quickly - O(1), but in the worst case it can take linear time in the number of entries stored in the dictionary. I'm assuming here that the hash code for an object can be calculated in constant time.

The actual code in the .NET implementation can be seen by downloading the reference implementation source, or by using .NET Reflector:

private int FindEntry(TKey key)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }
    if (this.buckets != null)
    {
        int num = this.comparer.GetHashCode(key) & 0x7fffffff;
        for (int i = this.buckets[num % this.buckets.Length]; i >= 0; i = this.entries[i].next)
        {
            if ((this.entries[i].hashCode == num) && this.comparer.Equals(this.entries[i].key, key))
            {
                return i;
            }
        }
    }
    return -1;
}

Upvotes: 6

KevinDTimm
KevinDTimm

Reputation: 14376

A hash is just an algorithm run against a key that creates (hopefully) a unique value that points to which bucket to store an item in. So, when you compute the value to try to retrieve that item, your hope is that the hash will point you to the object that you saved earlier. If not, there should be a pointer about where to look for the next object that shares this hash value. When you find your item, it will return. If the end of the chain is reached, then your item cannot be found.

See Hash Tables and Hash Function for a fuller definition of hashing.

Upvotes: 0

Related Questions