一、List<T>
List<T>也就是泛型集合。看它的大小分配方式，要看两段代码
2 if (_items.Length < min) {
3 int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
4 if (newCapacity < min) newCapacity = min;
5 Capacity = newCapacity;
6 }
7 }
get { return _items.Length; }
set {
if (value != _items.Length) {
if (value < _size) {
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
}
if (value > 0) {
T[] newItems = new T[value];
if (_size > 0) {
Array.Copy(_items, 0, newItems, 0, _size);
}
_items = newItems;
}
else {
_items = _emptyArray;
}
}
}
}
系统默认分配的增长量是
private const int _defaultCapacity = 4;
所以，假设不设置List的默认大小。即默认为0，那么在类初始化的时候，数组分配大小是0.如下代码
// Constructs a List. The list is initially empty and has a capacity
// of zero. Upon adding the first element to the list the capacity is
// increased to 16, and then increased in multiples of two as required.
public List() {
_items = _emptyArray;
}
那么当第一次调用Add方法的时候，系统就会为List分配4个位置的大小。而超过4个则分配8个，超过8个就分配16个。也就是说，假设你添加了2049个值进去，那么实际分配的空间大小就是4096。分配5万个进去，就会分配65536个。额外多出来不少。而假如能自己判断出要添加的大概数量的话，那最好是预先分配大小了。预先分配大小，分配多少就是多少个。预先分配的大小一定要大于等于加进去的元素数量。否则，说不定比不分配更加糟糕。
if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
_items = new T[capacity];
}
二、Dictionary<TKey,TValue>
要是用List分配空间的方式来理解Dictionary，那就又错了。Dictionary有它自己的分配方式。
int size = HashHelpers.GetPrime(capacity);
buckets = new int[size];
for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;
entries = new Entry[size];
freeList = -1;
}
int newSize = HashHelpers.GetPrime(count * 2);
int[] newBuckets = new int[newSize];
for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
Entry[] newEntries = new Entry[newSize];
Array.Copy(entries, 0, newEntries, 0, count);
for (int i = 0; i < count; i++) {
int bucket = newEntries[i].hashCode % newSize;
newEntries[i].next = newBuckets[bucket];
newBuckets[bucket] = i;
}
buckets = newBuckets;
entries = newEntries;
}
internal static int GetPrime(int min)
{
if (min < 0)
throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
for (int i = 0; i < primes.Length; i++)
{
int prime = primes[i];
if (prime >= min) return prime;
}
//outside of our predefined table.
//compute the hard way.
for (int i = (min | 1); i < Int32.MaxValue;i+=2)
{
if (IsPrime(i))
return i;
}
return min;
}
假设未设置大小，那么它会从下面的数据中取得。
3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369
取得的时候有一个规则。比如未设置大小，第一次添加的时候，一定是取3个大小为初始值了。而到4个的时候，它会先取3的倍数6，而6小于7，那么它就取7。当第8个的时候，因为7的倍数是14，比11大，所以它就取17了。所以，假设存入50000个左右的key，到第467237 + 1个的时候，根据计算 75431 < 43627* 2 = 87254 < 90523，所以，它会为你分配90523个键值。浪费了吧，呵呵，而且在分配完成后，它会用循环的方式重新设置初始值。浪费几万次循环，实在可耻。
所以，如果判定存入的key的数量为50000左右的话，那么直接设置50000，它会取52361个，如果觉得不保险，那么设置成60000，就会分配62851。
sorry,上面计算有误，当5万个的时候，先取3，再取7，接着是17，37，89，197，431，919，1931，4049，8419，17519，36353，75431。意思是不设置初始大小的情况，第一个必然取3，再从上面的表中取比这个数的两倍大的最小值，依次类推。那么，存取5万个键值对，实际分配大小是75431个空间。而预先设置大小，它会在上表中找比设置大小大的数的最小值。所以存5万个，设置5万初始大小的话，那么实际分配52361个空间，觉得不保险，设置6万，则分配62851个空间。(2008年7月31日 9:07:39 修正。)
2008年7月31日 by yurow @http://www.cnblogs.com/birdshover/