I try to understand how .net C# Dictionary works. I always heard its search mechanism is fast.
While looking at the implementation i saw the following code. The following is the FindEntry function as show in: MSDN implementation
private int FindEntry(TKey key) {
if( key == null) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (buckets != null) {
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
}
}
return -1;
}
Can someone please explain to me, why the above code is faster than a simple loop and simple check of the value? Example:
private int FindEntry(TKey key) {
if( key == null) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
for (i >= 0; i = entries[i].next) {
if (entries[i].key == key) return i;
}
}
return -1;
}
User contributions licensed under CC BY-SA 3.0