[DebuggerDisplay ("Count={Count}")]
[DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
public class HashSet<T> : ICollection<T>, ISerializable, IDeserializationCallback
-#if NET_4_0 || MOONLIGHT || MOBILE
+#if NET_4_0
, ISet<T>
#endif
{
}
}
- void Resize ()
+ void Resize (int size)
{
- int newSize = PrimeHelper.ToPrime ((table.Length << 1) | 1);
+ int newSize = HashPrimeNumbers.ToPrime (size);
// allocate new hash table and link slots array
var newTable = new int [newSize];
return false;
if (++count > threshold) {
- Resize ();
+ Resize ((table.Length << 1) | 1);
index = (hashCode & int.MaxValue) % table.Length;
}
public void TrimExcess ()
{
- Resize ();
+ Resize (count);
}
// set operations
return CheckIsSupersetOf (other_set);
}
- class HashSetEqualityComparer : IEqualityComparer<HashSet<T>>
- {
- public bool Equals (HashSet<T> lhs, HashSet<T> rhs)
- {
- if (lhs == rhs)
- return true;
-
- if (lhs == null || rhs == null || lhs.Count != rhs.Count)
- return false;
-
- foreach (var item in lhs)
- if (!rhs.Contains (item))
- return false;
-
- return true;
- }
-
- public int GetHashCode (HashSet<T> hashset)
- {
- if (hashset == null)
- return 0;
-
- IEqualityComparer<T> comparer = EqualityComparer<T>.Default;
- int hash = 0;
- foreach (var item in hashset)
- hash ^= comparer.GetHashCode (item);
-
- return hash;
- }
- }
-
- static readonly HashSetEqualityComparer setComparer = new HashSetEqualityComparer ();
-
public static IEqualityComparer<HashSet<T>> CreateSetComparer ()
{
- return setComparer;
+ return HashSetEqualityComparer<T>.Instance;
}
[SecurityPermission (SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
info.AddValue("Comparer", comparer, typeof(IEqualityComparer<T>));
info.AddValue("Capacity", (table == null) ? 0 : table.Length);
if (table != null) {
- T[] tableArray = new T[table.Length];
+ T[] tableArray = new T[count];
CopyTo(tableArray);
info.AddValue("Elements", tableArray, typeof(T[]));
}
empty_slot = NO_SLOT;
if (capacity > 0) {
- table = new int[capacity];
- slots = new T[capacity];
+ InitArrays(capacity);
T[] tableArray = (T[]) si.GetValue("Elements", typeof(T[]));
if (tableArray == null)
throw new InvalidOperationException ("HashSet have been modified while it was iterated over");
}
}
+ }
+
+ sealed class HashSetEqualityComparer<T> : IEqualityComparer<HashSet<T>>
+ {
+ public static readonly HashSetEqualityComparer<T> Instance = new HashSetEqualityComparer<T> ();
+
+ public bool Equals (HashSet<T> lhs, HashSet<T> rhs)
+ {
+ if (lhs == rhs)
+ return true;
- // borrowed from System.Collections.HashTable
- static class PrimeHelper {
-
- static readonly int [] primes_table = {
- 11,
- 19,
- 37,
- 73,
- 109,
- 163,
- 251,
- 367,
- 557,
- 823,
- 1237,
- 1861,
- 2777,
- 4177,
- 6247,
- 9371,
- 14057,
- 21089,
- 31627,
- 47431,
- 71143,
- 106721,
- 160073,
- 240101,
- 360163,
- 540217,
- 810343,
- 1215497,
- 1823231,
- 2734867,
- 4102283,
- 6153409,
- 9230113,
- 13845163
- };
-
- static bool TestPrime (int x)
- {
- if ((x & 1) != 0) {
- int top = (int) Math.Sqrt (x);
-
- for (int n = 3; n < top; n += 2) {
- if ((x % n) == 0)
- return false;
- }
-
- return true;
- }
+ if (lhs == null || rhs == null || lhs.Count != rhs.Count)
+ return false;
- // There is only one even prime - 2.
- return x == 2;
- }
+ foreach (var item in lhs)
+ if (!rhs.Contains (item))
+ return false;
- static int CalcPrime (int x)
- {
- for (int i = (x & (~1)) - 1; i < Int32.MaxValue; i += 2)
- if (TestPrime (i))
- return i;
+ return true;
+ }
- return x;
- }
+ public int GetHashCode (HashSet<T> hashset)
+ {
+ if (hashset == null)
+ return 0;
- public static int ToPrime (int x)
- {
- for (int i = 0; i < primes_table.Length; i++)
- if (x <= primes_table [i])
- return primes_table [i];
+ IEqualityComparer<T> comparer = EqualityComparer<T>.Default;
+ int hash = 0;
+ foreach (var item in hashset)
+ hash ^= comparer.GetHashCode (item);
- return CalcPrime (x);
- }
+ return hash;
}
}
}