diff options
Diffstat (limited to 'src/System.Private.CoreLib/shared/System/Collections/HashHelpers.cs')
| -rw-r--r-- | src/System.Private.CoreLib/shared/System/Collections/HashHelpers.cs | 40 |
1 files changed, 12 insertions, 28 deletions
diff --git a/src/System.Private.CoreLib/shared/System/Collections/HashHelpers.cs b/src/System.Private.CoreLib/shared/System/Collections/HashHelpers.cs index 49cff85b5..ba2c75c89 100644 --- a/src/System.Private.CoreLib/shared/System/Collections/HashHelpers.cs +++ b/src/System.Private.CoreLib/shared/System/Collections/HashHelpers.cs @@ -2,17 +2,18 @@ // The .NET Foundation licenses this file to you under the MIT license. // See the LICENSE file in the project root for more information. + using System.Diagnostics; -using System.Runtime.CompilerServices; -using System.Runtime.Serialization; -using System.Threading; namespace System.Collections { - internal static class HashHelpers + internal static partial class HashHelpers { public const int HashCollisionThreshold = 100; + // This is the maximum prime smaller than Array.MaxArrayLength + public const int MaxPrimeArrayLength = 0x7FEFFFFD; + public const int HashPrime = 101; // Table of prime numbers to use as hash table sizes. @@ -26,12 +27,14 @@ namespace System.Collections // hashtable operations such as add. Having a prime guarantees that double // hashing does not lead to infinite loops. IE, your hash function will be // h1(key) + i*h2(key), 0 <= i < size. h2 and the size must be relatively prime. + // We prefer the low computation costs of higher prime numbers over the increased + // memory allocation of a fixed prime number i.e. when right sizing a HashSet. 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}; + 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369 }; public static bool IsPrime(int candidate) { @@ -56,12 +59,13 @@ namespace System.Collections for (int i = 0; i < primes.Length; i++) { int prime = primes[i]; - if (prime >= min) return prime; + if (prime >= min) + return prime; } //outside of our predefined table. //compute the hard way. - for (int i = (min | 1); i < Int32.MaxValue; i += 2) + for (int i = (min | 1); i < int.MaxValue; i += 2) { if (IsPrime(i) && ((i - 1) % HashPrime != 0)) return i; @@ -74,7 +78,7 @@ namespace System.Collections { int newSize = 2 * oldSize; - // Allow the hashtables to grow to maximum possible size (~2G elements) before encoutering capacity overflow. + // Allow the hashtables to grow to maximum possible size (~2G elements) before encountering capacity overflow. // Note that this check works even when _items.Length overflowed thanks to the (uint) cast if ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize) { @@ -84,25 +88,5 @@ namespace System.Collections return GetPrime(newSize); } - - - // This is the maximum prime smaller than Array.MaxArrayLength - public const int MaxPrimeArrayLength = 0x7FEFFFFD; - - - // Used by Hashtable and Dictionary's SeralizationInfo .ctor's to store the SeralizationInfo - // object until OnDeserialization is called. - private static ConditionalWeakTable<object, SerializationInfo> s_serializationInfoTable; - - internal static ConditionalWeakTable<object, SerializationInfo> SerializationInfoTable - { - get - { - if (s_serializationInfoTable == null) - Interlocked.CompareExchange(ref s_serializationInfoTable, new ConditionalWeakTable<object, SerializationInfo>(), null); - - return s_serializationInfoTable; - } - } } } |