C#

C#
7.8k words

Desc：

记录阅读源码中笔记

字符串优化：

引用

Image text

ArrayList:

原文

实现了 IList、ICloneable 接口

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public virtual void CopyTo(Array array) {
    CopyTo(array, 0);
}
 
// Copies this ArrayList into array, which must be of a 
// compatible array type.  
//
public virtual void CopyTo(Array array, int arrayIndex) {
    if ((array != null) && (array.Rank != 1))
        throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
    Contract.EndContractBlock();
    // Delegate rest of error checking to Array.Copy.
    Array.Copy(_items, 0, array, arrayIndex, _size);
}
    
// Copies a section of this list to the given array at the given index.
// 
// The method uses the Array.Copy method to copy the elements.
// 
public virtual void CopyTo(int index, Array array, int arrayIndex, int count) {
    if (_size - index < count)
        throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
    if ((array != null) && (array.Rank != 1))
        throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
    Contract.EndContractBlock();
    // Delegate rest of error checking to Array.Copy.
    Array.Copy(_items, index, array, arrayIndex, count);
}

数据存储实现是使用 Object[], 当存值类型数据时会发生装箱拆箱，默认容量为4

代码 
1
2
3
4
5
6
7
8
9
private Object[] _items;
[ContractPublicPropertyName("Count")]
private int _size;
private int _version;
[NonSerialized]
private Object _syncRoot;

private const int _defaultCapacity = 4;
private static readonly Object[] emptyArray = EmptyArray<Object>.Value;

确保容量足够，不足时拓容一倍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Ensures that the capacity of this list is at least the given minimum
// value. If the currect capacity of the list is less than min, the
// capacity is increased to twice the current capacity or to min,
// whichever is larger.
private void EnsureCapacity(int min) {
    if (_items.Length < min) {
        int newCapacity = _items.Length == 0? _defaultCapacity: _items.Length * 2;
        // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
        // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
        if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
        if (newCapacity < min) newCapacity = min;
        Capacity = newCapacity;
    }
}

Hashtable:

1
2
internal const Int32 HashPrime = 101;
private const Int32 InitialSize = 3;

比率越小，速度越快，内存消耗越大

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public Hashtable(int capacity, float loadFactor) {
    if (capacity < 0)
        throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
    if (!(loadFactor >= 0.1f && loadFactor <= 1.0f))
        throw new ArgumentOutOfRangeException("loadFactor", Environment.GetResourceString("ArgumentOutOfRange_HashtableLoadFactor", .1, 1.0));
    Contract.EndContractBlock();

    // Based on perf work, .72 is the optimal load factor for this table.  
    this.loadFactor = 0.72f * loadFactor;

    double rawsize = capacity / this.loadFactor;
    if (rawsize > Int32.MaxValue)
        throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));

    // Avoid awfully small sizes
    int hashsize = (rawsize > InitialSize) ? HashHelpers.GetPrime((int)rawsize) : InitialSize;
    buckets = new bucket[hashsize];

    loadsize = (int)(this.loadFactor * hashsize);
    isWriterInProgress = false;
    // Based on the current algorithm, loadsize must be less than hashsize.
    Contract.Assert( loadsize < hashsize, "Invalid hashtable loadsize!");
}
1
2
3
4
5
6
7
8
9
// The hash table data.
// This cannot be serialised
private struct bucket {
    public Object key;
    public Object val;
    public int hash_coll;   // Store hash code; sign bit means there was a collision.
}

private bucket[] buckets;

当冲突数达到上限时，重新选择比较器，更新哈希表

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#if FEATURE_RANDOMIZED_STRING_HASHING
#if !FEATURE_CORECLR
    if(buckets.Length > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(_keycomparer)) 
    {
        // PERF: We don't want to rehash if _keycomparer is already a RandomizedObjectEqualityComparer since in some
        // cases there may not be any strings in the hashtable and we wouldn't get any mixing.
        if(_keycomparer == null || !(_keycomparer is System.Collections.Generic.RandomizedObjectEqualityComparer))
        {
            _keycomparer = HashHelpers.GetRandomizedEqualityComparer(_keycomparer);
            rehash(buckets.Length, true);
        }
    }
#endif // !FEATURE_CORECLR
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
    [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
    private void rehash( int newsize, bool forceNewHashCode ) {

        // reset occupancy
        occupancy=0;
    
        // Don't replace any internal state until we've finished adding to the 
        // new bucket[].  This serves two purposes: 
        //   1) Allow concurrent readers to see valid hashtable contents 
        //      at all times
        //   2) Protect against an OutOfMemoryException while allocating this 
        //      new bucket[].
        bucket[] newBuckets = new bucket[newsize];

        // rehash table into new buckets
        int nb;
        for (nb = 0; nb < buckets.Length; nb++){
            bucket oldb = buckets[nb];
            if ((oldb.key != null) && (oldb.key != buckets)) {
                int hashcode = ((forceNewHashCode ? GetHash(oldb.key) : oldb.hash_coll) & 0x7FFFFFFF);                              
                putEntry(newBuckets, oldb.key, oldb.val, hashcode);
            }
        }
        
        // New bucket[] is good to go - replace buckets and other internal state.
#if !FEATURE_CORECLR
        Thread.BeginCriticalRegion();            
#endif
        isWriterInProgress = true;
        buckets = newBuckets;
        loadsize = (int)(loadFactor * newsize);
        UpdateVersion();
        isWriterInProgress = false;
#if !FEATURE_CORECLR            
        Thread.EndCriticalRegion();   
#endif         
        // minimun size of hashtable is 3 now and maximum loadFactor is 0.72 now.
        Contract.Assert(loadsize < newsize, "Our current implementaion means this is not possible.");
        return;
    }

拓展时取最近的素数，减少冲突的概率

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// Returns size of hashtable to grow to.
public static int ExpandPrime(int oldSize)
{
    int newSize = 2 * oldSize;

    // Allow the hashtables to grow to maximum possible size (~2G elements) before encoutering capacity overflow.
    // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
    if ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize)
    {
        Contract.Assert( MaxPrimeArrayLength == GetPrime(MaxPrimeArrayLength), "Invalid MaxPrimeArrayLength");
        return MaxPrimeArrayLength;
    }

    return GetPrime(newSize);
}

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
public static bool IsPrime(int candidate) 
{
    if ((candidate & 1) != 0) 
    {
        int limit = (int)Math.Sqrt (candidate);
        for (int divisor = 3; divisor <= limit; divisor+=2)
        {
            if ((candidate % divisor) == 0)
                return false;
        }
        return true;
    }
    return (candidate == 2);
}

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
public static int GetPrime(int min) 
{
    if (min < 0)
        throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
    Contract.EndContractBlock();

    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) && ((i - 1) % Hashtable.HashPrime != 0))
            return i;
    }
    return min;
}

List:

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private const int _defaultCapacity = 4;

private T[] _items;
[ContractPublicPropertyName("Count")]
private int _size;    
static readonly T[]  _emptyArray = new T[0];     

public List(int capacity) {
    if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
    Contract.EndContractBlock();

    if (capacity == 0)
        _items = _emptyArray;
    else
        _items = new T[capacity];
}

接口：

IList：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Object this[int index] {
    get;
    set;
}

int Add(Object value);

bool Contains(Object value);

void Clear();

int IndexOf(Object value);
    
void Insert(int index, Object value);
    
void Remove(Object value);
    
void RemoveAt(int index);

ICollection:

1
void CopyTo(Array array, int index);

IDictionary:

1
2
3
4
5
6
7
void Add(Object key, Object value);
    
void Clear();
 
new IDictionaryEnumerator GetEnumerator();
    
void Remove(Object key);

IEnumerable

1
2
IEnumerator GetEnumerator();

IEnumerator

1
2
3
4
5
6
7
bool MoveNext();

Object Current {
    get; 
}

void Reset();

IComparer

1
2
int Compare(Object x, Object y);