What will be the fastest way to access an element from a collection?

What will be the fastest way to access an element from a 开发者_如何转开发collection?

I am thinking should be in the order (low to high):

Indexing an Array <= indexing a collection/list <= use key on Dictionary

But I am not sure...

1) Is indexing an array has same speed as indexing a list?

2) And will the indexing speed will grows as the size of the array/list grows?

From my understanding... indexing array should kind of using a pointer to point to the index of the element, which is caculated by the element size. So it should has same speed as indexing collection/list?

From what I know if we use Dictionary to look for a value, the speed of getting a value will grows as the size of Dictionary grows.

3) I just wonder what will be the fastest way to access an element from a collection?

Have been wondering for long time is my assumption is correct :)

Thanks

In C# a List is backed by an array, so both an array and a list/collection can access elements by indexing in O(1) time. Performance for a Dictionary is similar because it is backed by a hash table. However, it should be noted that the performance of access on a hash table is relative to the quality of the hash function and the number of collisions which occur in a particular data set. In C#, each type may override GetHashCode(), which will determine the hash function and thus the performance of accessing such an object within a particular set of such objects in a dictionary.

The amortized cost of finding an element by key with a Dictionary is O(1) or constant (also see "Resizable hash tables and amortized analysis" for the CS fundamentals). The underlying data structure is not an array or list, but a hashtable - given an appropriate hashing function the speed of accessing a value cost does not grow significantly larger (hence is constant) with the number of elements, unless many or most of those elements have the same hash code.