C# Dictionary字典源碼分析與自定義Dictionary字典
C# Dictionary字典源碼分析與自定義Dictionary字典
官網(wǎng)源碼地址：
https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs
關(guān)鍵點(diǎn)
- Dictionary實(shí)際容器為Entry[] entries 結(jié)構(gòu)體數(shù)組
private struct Entry
{
public int hashCode;
public int next;
public TKey key;
public TValue value;
}
- entries數(shù)組默認(rèn)長(zhǎng)度為3
- 如果初始化指定長(zhǎng)度 entries數(shù)組長(zhǎng)度為大于指定長(zhǎng)度最接近的質(zhì)數(shù)
- Dictionary查找元素的時(shí)間復(fù)雜度接近
O(1)是因?yàn)?- 定義了一個(gè)int[] buckets Hash桶數(shù)組
- 獲取key了hashCode
- 用hashCode除buckets長(zhǎng)度取余做為索引（這也是為什么長(zhǎng)度為質(zhì)數(shù)的原因）
- 防止hashCode沖突Dictionary使用了拉鏈法
- 使用Entry.next保存沖突項(xiàng)索
- 當(dāng)添加值時(shí)沖突達(dá)到100次會(huì)使用新的hashCode方法解決
- 當(dāng)Entry[] entries或int[] buckets滿了的時(shí)候會(huì)自動(dòng)擴(kuò)了當(dāng)前容量的2倍
- 擴(kuò)容后會(huì)重現(xiàn)計(jì)算hashcode賦值索引
- 查找元素是會(huì)判斷hashcode和key.Equals
優(yōu)化點(diǎn)
- 已知容器大小的情況 直接初始化對(duì)應(yīng)大小
- key最好用簡(jiǎn)單類型
- 如果一定要用枚舉或引用類型
- 初始化字典的時(shí)候賦值對(duì)比函數(shù)
- 或者實(shí)現(xiàn)IEquatable
- 獲取值得時(shí)候使用TryGetValue不需要先判斷ContainsKey
自定義Dictionary字典
using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.Serialization;
public interface IMyDictionary<TKey, TValue> : IEnumerable, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>
{
TValue this[TKey key] { get; set; }
ICollection<TKey> Keys { get; }
ICollection<TValue> Values { get; }
void Add(TKey key, TValue value);
bool ContainsKey(TKey key);
bool Remove(TKey key);
bool TryGetValue(TKey key, out TValue value);
}
public class MyDictionary<TKey, TValue>
{
private struct Entry
{
public int hashCode;
public int next;
public TKey key;
public TValue value;
}
/// <summary>
/// Hash桶
/// </summary>
private int[] buckets;
/// <summary>
/// 所有鍵值對(duì)條目數(shù)組
/// </summary>
private Entry[] entries;
/// <summary>
/// 當(dāng)前entries的index位置
/// </summary>
private int count;
/// <summary>
/// 當(dāng)前版本，防止迭代過程中集合被更改
/// </summary>
private int version;
/// <summary>
/// entries空閑索引
/// </summary>
private int freeList;
/// <summary>
/// entries空閑數(shù)量
/// </summary>
private int freeCount;
/// <summary>
/// 對(duì)比函數(shù)
/// </summary>
private IEqualityComparer<TKey> comparer;
/// <summary>
/// key集合
/// </summary>
private KeyCollection keys;
/// <summary>
/// value集合
/// </summary>
private ValueCollection values;
public MyDictionary() : this(0, null) { }
public MyDictionary(IEqualityComparer<TKey> comparer) : this(0, comparer) { }
public MyDictionary(IDictionary<TKey, TValue> dictionary) : this(dictionary, null) { }
public MyDictionary(int capacity) : this(capacity, null) { }
public MyDictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer) : this(dictionary != null ? dictionary.Count : 0, comparer)
{
if (dictionary == null) { return; }//異常
foreach (KeyValuePair<TKey, TValue> pair in dictionary)
{
Add(pair.Key, pair.Value);
}
}
public MyDictionary(int capacity, IEqualityComparer<TKey> comparer)
{
if (capacity < 0) { throw new Exception("capacity 異常"); }
if (capacity > 0) Initialize(capacity);
this.comparer = comparer ?? EqualityComparer<TKey>.Default;
}
public TValue this[TKey key]
{
get
{
int i = FindEntry(key);
if (i >= 0) return entries[i].value;
throw new Exception("TKey 異常");
}
set
{
Insert(key, value, false);
}
}
public IEqualityComparer<TKey> Comparer
{
get { return comparer; }
}
public KeyCollection Keys
{
get
{
if (keys == null) keys = new KeyCollection(this);
return keys;
}
}
public ValueCollection Values
{
get
{
if (values == null) values = new ValueCollection(this);
return values;
}
}
public int Count
{
get { return count - freeCount; }
}
public void Add(TKey key, TValue value)
{
Insert(key, value, true);
}
public void Clear()
{
if (count > 0)
{
for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;
Array.Clear(entries, 0, count);
freeList = -1;
count = 0;
freeCount = 0;
version++;
}
}
public bool ContainsKey(TKey key)
{
return FindEntry(key) >= 0;
}
public bool ContainsValue(TValue value)
{
if (value == null)
{
for (int i = 0; i < count; i++)
{
if (entries[i].hashCode >= 0 && entries[i].value == null) return true;
}
}
else
{
EqualityComparer<TValue> c = EqualityComparer<TValue>.Default;
for (int i = 0; i < count; i++)
{
if (entries[i].hashCode >= 0 && c.Equals(entries[i].value, value)) return true;
}
}
return false;
}
public Enumerator GetEnumerator()
{
return new Enumerator(this, Enumerator.KeyValuePair);
}
public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
{
}
public virtual void OnDeserialization(object sender)
{
}
public bool Remove(TKey key)
{
if (key == null)
{
throw new Exception("異常");
}
if (buckets != null)
{
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
int bucket = hashCode % buckets.Length;
int last = -1;
for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next)
{
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
{
if (last < 0)
{
buckets[bucket] = entries[i].next;//找到元素后，如果last< 0，代表當(dāng)前是bucket中最后一個(gè)元素，那么直接讓bucket內(nèi)下標(biāo)賦值為 entries[i].next即可
}
else
{
entries[last].next = entries[i].next;//last不小于0，代表當(dāng)前元素處于bucket單鏈表中間位置，需要將該元素的頭結(jié)點(diǎn)和尾節(jié)點(diǎn)相連起來,防止鏈表中斷
}
entries[i].hashCode = -1;
entries[i].next = freeList;
entries[i].key = default(TKey);
entries[i].value = default(TValue);
freeList = i;//freeList等于當(dāng)前的entry位置，下一次Add元素會(huì)優(yōu)先Add到該位置
freeCount++;
version++;
return true;
}
}
}
return false;
}
public bool TryGetValue(TKey key, out TValue value)
{
int i = FindEntry(key);
if (i >= 0)
{
value = entries[i].value;
return true;
}
value = default(TValue);
return false;
}
/// <summary>
/// 初始化
/// </summary>
/// <param name="capacity">容量</param>
private void Initialize(int capacity)
{
int size = HashHelpers.GetPrime(capacity);//獲取該容量匹配的質(zhì)數(shù)
buckets = new int[size];//初始化桶數(shù)組
for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;//桶數(shù)組全部賦值為-1
entries = new Entry[size];//初始化容量
freeList = -1;
}
/// <summary>
/// 插入
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
/// <param name="add"></param>
private void Insert(TKey key, TValue value, bool add)
{
if (key == null)
{
throw new Exception("key == null 異常");
}
if (buckets == null) Initialize(0);
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;//01111111 11111111 11111111 11111111 忽略符號(hào)位
int targetBucket = hashCode % buckets.Length;//獲得hashCode在buckets中存放在位置
int collisionCount = 0;//沖突數(shù)量
//從hash桶中獲取索引 i = entries[i].next 繼續(xù)獲取拉鏈下一個(gè)數(shù)據(jù)
for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next)
{
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))//如果鍵值對(duì)條目數(shù)組索引位置hashCode等于key的hashCode 且key相等 賦值
{
if (add)
{
throw new Exception("key已存在 異常");
}
entries[i].value = value;
version++;
return;
}
//如果不相等 沖突+1
collisionCount++;
}
//如果entries[i].next=-1 下一個(gè)拉鏈數(shù)據(jù)為空則執(zhí)行下面的操作
//創(chuàng)建一個(gè)拉鏈數(shù)據(jù)
int index;
if (freeCount > 0)//有空閑位置
{
index = freeList;
freeList = entries[index].next;
freeCount--;
}
else
{
if (count == entries.Length)//如果鍵值對(duì)條目數(shù)組已滿
{
Resize();//調(diào)整大小
targetBucket = hashCode % buckets.Length;//重現(xiàn)獲取hashCode在buckets中存放在位置
}
index = count;//取鍵值對(duì)條目數(shù)組空閑的位置
count++;
}
entries[index].hashCode = hashCode;
entries[index].next = buckets[targetBucket];//把原h(huán)ash桶中索引的鍵值對(duì)條目索引賦值到當(dāng)前鍵值對(duì)條目的下一個(gè)位
entries[index].key = key;
entries[index].value = value;
buckets[targetBucket] = index;//替換hash桶位的指向
version++;
// 如果碰撞次數(shù)大于設(shè)置的最大碰撞次數(shù)，那么觸發(fā)Hash碰撞擴(kuò)容
if (collisionCount > 100 && (comparer == null || comparer == EqualityComparer<TKey>.Default))
{
comparer = EqualityComparer<TKey>.Default;//使用新的對(duì)比hash函數(shù)
Resize(entries.Length, true);
}
}
/// <summary>
/// 查找鍵值對(duì)條目
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
private int FindEntry(TKey key)
{
if (key == null)
{
throw new Exception("key 異常");
}
if (buckets != null)
{
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next)
{
//判斷hashCode相等且key相等 則返回索引 如果不想等 獲取next
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
}
}
return -1;
}
/// <summary>
/// 調(diào)整大小
/// </summary>
private void Resize()
{
Resize(HashHelpers.ExpandPrime(count), false);
}
/// <summary>
/// 調(diào)整大小
/// </summary>
/// <param name="newSize">新da'xia</param>
/// <param name="forceNewHashCodes">強(qiáng)制使用新的hashcode方法</param>
private void Resize(int newSize, bool forceNewHashCodes)
{
if (newSize >= entries.Length == false) throw new Exception("newSize 異常");
int[] newBuckets = new int[newSize];//新的hash桶
for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
Entry[] newEntries = new Entry[newSize];//新的鍵值對(duì)條目數(shù)組
Array.Copy(entries, 0, newEntries, 0, count);//拷貝老的鍵值對(duì)條目數(shù)組到新的鍵值對(duì)條目數(shù)組
if (forceNewHashCodes)//強(qiáng)制使用新的hashcode
{
for (int i = 0; i < count; i++)
{
if (newEntries[i].hashCode != -1)//過濾未使用的
{
newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF);//使用新HashCode函數(shù)重新計(jì)算Hash值
}
}
}
for (int i = 0; i < count; i++)
{
int bucket = newEntries[i].hashCode % newSize;//獲取hash桶索引
newEntries[i].next = newBuckets[bucket];//第一次 newBuckets[bucket]==-1 第n次 newBuckets[bucket]==上次賦值索引
newBuckets[bucket] = i;//賦值到hash桶
}
buckets = newBuckets;
entries = newEntries;
}
private void CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
{
if (array == null)
{
throw new Exception("異常");
}
if (index < 0 || index > array.Length)
{
throw new Exception("異常");
}
if (array.Length - index < Count)
{
throw new Exception("異常");
}
int count = this.count;
Entry[] entries = this.entries;
for (int i = 0; i < count; i++)
{
if (entries[i].hashCode >= 0)
{
array[index++] = new KeyValuePair<TKey, TValue>(entries[i].key, entries[i].value);
}
}
}
public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>,
IDictionaryEnumerator
{
private MyDictionary<TKey, TValue> dictionary;
private int version;
private int index;
private KeyValuePair<TKey, TValue> current;
private int getEnumeratorRetType; // What should Enumerator.Current return?
internal const int DictEntry = 1;
internal const int KeyValuePair = 2;
internal Enumerator(MyDictionary<TKey, TValue> dictionary, int getEnumeratorRetType)
{
this.dictionary = dictionary;
version = dictionary.version;
index = 0;
this.getEnumeratorRetType = getEnumeratorRetType;
current = new KeyValuePair<TKey, TValue>();
}
public bool MoveNext()
{
if (version != dictionary.version)
{
throw new Exception("異常");
}
// Use unsigned comparison since we set index to dictionary.count+1 when the enumeration ends.
// dictionary.count+1 could be negative if dictionary.count is Int32.MaxValue
while ((uint)index < (uint)dictionary.count)
{
if (dictionary.entries[index].hashCode >= 0)
{
current = new KeyValuePair<TKey, TValue>(dictionary.entries[index].key, dictionary.entries[index].value);
index++;
return true;
}
index++;
}
index = dictionary.count + 1;
current = new KeyValuePair<TKey, TValue>();
return false;
}
public KeyValuePair<TKey, TValue> Current
{
get { return current; }
}
public void Dispose()
{
}
object IEnumerator.Current
{
get
{
if (index == 0 || (index == dictionary.count + 1))
{
throw new Exception("異常");
}
if (getEnumeratorRetType == DictEntry)
{
return new System.Collections.DictionaryEntry(current.Key, current.Value);
}
else
{
return new KeyValuePair<TKey, TValue>(current.Key, current.Value);
}
}
}
void IEnumerator.Reset()
{
if (version != dictionary.version)
{
throw new Exception("異常");
}
index = 0;
current = new KeyValuePair<TKey, TValue>();
}
DictionaryEntry IDictionaryEnumerator.Entry
{
get
{
if (index == 0 || (index == dictionary.count + 1))
{
throw new Exception("異常");
}
return new DictionaryEntry(current.Key, current.Value);
}
}
object IDictionaryEnumerator.Key
{
get
{
if (index == 0 || (index == dictionary.count + 1))
{
throw new Exception("異常");
}
return current.Key;
}
}
object IDictionaryEnumerator.Value
{
get
{
if (index == 0 || (index == dictionary.count + 1))
{
throw new Exception("異常");
}
return current.Value;
}
}
}
public sealed class KeyCollection : ICollection<TKey>, ICollection
{
private MyDictionary<TKey, TValue> dictionary;
public KeyCollection(MyDictionary<TKey, TValue> dictionary)
{
if (dictionary == null)
{
throw new Exception("dictionary == null 異常");
}
this.dictionary = dictionary;
}
public Enumerator GetEnumerator()
{
return new Enumerator(dictionary);
}
public void CopyTo(TKey[] array, int index)
{
if (array == null)
{
throw new Exception("array == null 異常");
}
if (index < 0 || index > array.Length)
{
throw new Exception("index < 0 || index > array.Length 異常");
}
if (array.Length - index < dictionary.Count)
{
throw new Exception("異常");
}
int count = dictionary.count;
Entry[] entries = dictionary.entries;
for (int i = 0; i < count; i++)
{
if (entries[i].hashCode >= 0) array[index++] = entries[i].key;
}
}
public int Count
{
get { return dictionary.Count; }
}
bool ICollection<TKey>.IsReadOnly
{
get { return true; }
}
void ICollection<TKey>.Add(TKey item)
{
throw new Exception("異常");
}
void ICollection<TKey>.Clear()
{
throw new Exception("異常");
}
bool ICollection<TKey>.Contains(TKey item)
{
return dictionary.ContainsKey(item);
}
bool ICollection<TKey>.Remove(TKey item)
{
throw new Exception("異常");
}
IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator()
{
return new Enumerator(dictionary);
}
IEnumerator IEnumerable.GetEnumerator()
{
return new Enumerator(dictionary);
}
void ICollection.CopyTo(Array array, int index)
{
if (array == null)
{
throw new Exception("異常");
}
if (array.Rank != 1)
{
throw new Exception("異常");
}
if (array.GetLowerBound(0) != 0)
{
throw new Exception("異常");
}
if (index < 0 || index > array.Length)
{
throw new Exception("異常");
}
if (array.Length - index < dictionary.Count)
{
throw new Exception("異常");
}
TKey[] keys = array as TKey[];
if (keys != null)
{
CopyTo(keys, index);
}
else
{
object[] objects = array as object[];
if (objects == null)
{
throw new Exception("異常");
}
int count = dictionary.count;
Entry[] entries = dictionary.entries;
try
{
for (int i = 0; i < count; i++)
{
if (entries[i].hashCode >= 0) objects[index++] = entries[i].key;
}
}
catch (ArrayTypeMismatchException)
{
throw new Exception("異常");
}
}
}
bool ICollection.IsSynchronized
{
get { return false; }
}
Object ICollection.SyncRoot
{
get { return ((ICollection)dictionary).SyncRoot; }
}
[Serializable]
public struct Enumerator : IEnumerator<TKey>, System.Collections.IEnumerator
{
private MyDictionary<TKey, TValue> dictionary;
private int index;
private int version;
private TKey currentKey;
internal Enumerator(MyDictionary<TKey, TValue> dictionary)
{
this.dictionary = dictionary;
version = dictionary.version;
index = 0;
currentKey = default(TKey);
}
public void Dispose()
{
}
public bool MoveNext()
{
if (version != dictionary.version)
{
throw new Exception("異常");
}
while ((uint)index < (uint)dictionary.count)
{
if (dictionary.entries[index].hashCode >= 0)
{
currentKey = dictionary.entries[index].key;
index++;
return true;
}
index++;
}
index = dictionary.count + 1;
currentKey = default(TKey);
return false;
}
public TKey Current
{
get
{
return currentKey;
}
}
Object System.Collections.IEnumerator.Current
{
get
{
if (index == 0 || (index == dictionary.count + 1))
{
throw new Exception("異常");
}
return currentKey;
}
}
void System.Collections.IEnumerator.Reset()
{
if (version != dictionary.version)
{
throw new Exception("異常");
}
index = 0;
currentKey = default(TKey);
}
}
}
public sealed class ValueCollection : ICollection<TValue>, ICollection
{
private MyDictionary<TKey, TValue> dictionary;
public ValueCollection(MyDictionary<TKey, TValue> dictionary)
{
if (dictionary == null)
{
throw new Exception("異常");
}
this.dictionary = dictionary;
}
public Enumerator GetEnumerator()
{
return new Enumerator(dictionary);
}
public void CopyTo(TValue[] array, int index)
{
if (array == null)
{
throw new Exception("異常");
}
if (index < 0 || index > array.Length)
{
throw new Exception("異常");
}
if (array.Length - index < dictionary.Count)
{
throw new Exception("異常");
}
int count = dictionary.count;
Entry[] entries = dictionary.entries;
for (int i = 0; i < count; i++)
{
if (entries[i].hashCode >= 0) array[index++] = entries[i].value;
}
}
public int Count
{
get { return dictionary.Count; }
}
bool ICollection<TValue>.IsReadOnly
{
get { return true; }
}
void ICollection<TValue>.Add(TValue item)
{
throw new Exception("異常");
}
bool ICollection<TValue>.Remove(TValue item)
{
throw new Exception("異常");
}
void ICollection<TValue>.Clear()
{
throw new Exception("異常");
}
bool ICollection<TValue>.Contains(TValue item)
{
return dictionary.ContainsValue(item);
}
IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator()
{
return new Enumerator(dictionary);
}
IEnumerator IEnumerable.GetEnumerator()
{
return new Enumerator(dictionary);
}
void ICollection.CopyTo(Array array, int index)
{
if (array == null)
{
throw new Exception("異常");
}
if (array.Rank != 1)
{
throw new Exception("異常");
}
if (array.GetLowerBound(0) != 0)
{
throw new Exception("異常");
}
if (index < 0 || index > array.Length)
{
throw new Exception("異常");
}
if (array.Length - index < dictionary.Count)
throw new Exception("異常");
TValue[] values = array as TValue[];
if (values != null)
{
CopyTo(values, index);
}
else
{
object[] objects = array as object[];
if (objects == null)
{
throw new Exception("異常");
}
int count = dictionary.count;
Entry[] entries = dictionary.entries;
try
{
for (int i = 0; i < count; i++)
{
if (entries[i].hashCode >= 0) objects[index++] = entries[i].value;
}
}
catch (ArrayTypeMismatchException)
{
throw new Exception("異常");
throw new Exception("異常");
}
}
}
bool ICollection.IsSynchronized
{
get { return false; }
}
Object ICollection.SyncRoot
{
get { return ((ICollection)dictionary).SyncRoot; }
}
[Serializable]
public struct Enumerator : IEnumerator<TValue>, System.Collections.IEnumerator
{
private MyDictionary<TKey, TValue> dictionary;
private int index;
private int version;
private TValue currentValue;
internal Enumerator(MyDictionary<TKey, TValue> dictionary)
{
this.dictionary = dictionary;
version = dictionary.version;
index = 0;
currentValue = default(TValue);
}
public void Dispose()
{
}
public bool MoveNext()
{
if (version != dictionary.version)
{
throw new Exception("異常");
}
while ((uint)index < (uint)dictionary.count)
{
if (dictionary.entries[index].hashCode >= 0)
{
currentValue = dictionary.entries[index].value;
index++;
return true;
}
index++;
}
index = dictionary.count + 1;
currentValue = default(TValue);
return false;
}
public TValue Current
{
get
{
return currentValue;
}
}
Object System.Collections.IEnumerator.Current
{
get
{
if (index == 0 || (index == dictionary.count + 1))
{
throw new Exception("異常");
}
return currentValue;
}
}
void System.Collections.IEnumerator.Reset()
{
if (version != dictionary.version)
{
throw new Exception("異常");
}
index = 0;
currentValue = default(TValue);
}
}
}
}
using System;
public class HashHelpers
{
public static readonly int[] primes = {
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};
/// <summary>
/// 獲取質(zhì)數(shù)
/// </summary>
/// <param name="min">最小值</param>
/// <returns></returns>
public static int GetPrime(int min)
{
if (min < 0) { return -1; }//異常
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) % 101 != 0))
return i;
}
return min;
}
/// <summary>
/// 判斷是否為質(zhì)數(shù)（素?cái)?shù)）
/// </summary>
/// <param name="candidate"></param>
/// <returns></returns>
public static bool IsPrime(int candidate)
{
//與0000 0001位運(yùn)算 可以把奇數(shù)偶數(shù) 刷選出來，因?yàn)榕紨?shù)不是質(zhì)數(shù)（2除外）
if ((candidate & 1) != 0)
{
int limit = (int)Math.Sqrt(candidate);//求根號(hào) 相當(dāng)于乘法中的中位數(shù)
for (int divisor = 3; divisor <= limit; divisor += 2)//每次+2是跳過 偶數(shù)
{
if ((candidate % divisor) == 0)
return false;
}
return true;
}
return (candidate == 2);//最后這個(gè)保證2也是質(zhì)數(shù)
}
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 > 0x7FEFFFFD && 0x7FEFFFFD > oldSize)
{
throw new Exception("oldSize 異常");
}
return GetPrime(newSize);
}
}
浙公網(wǎng)安備 33010602011771號(hào)