The dictionary uses a hash code to calculate the number of bucket in which the record is stored. The number of buckets is selected as a prime number, and the bucket number for a particular key is calculated as the hash code of the key modulo the number of buckets. Since multiple objects can have the same hash code, and several hash codes can land in the same bucket when the key is in the bucket, it should also be compared for equality to ensure it is the correct key. If the wrong key is found in the bucket, the member of the nextincorrect record is used to search for the next place to search for the desired key.
, - O (1), , . , - .
.NET , .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;
}