First implementation of Quadratic Probing HS. Hotspots: Comparisions with null. TODO: Allow primitives without a wrapper class.

gistfile1.cs

/* 
 * HashSet.cs: A quadratic probing implementation of a HashSet
 * Author: Cedric Van Goethem
 * Revision: 1
 */

using System;
using System.Collections.Generic;

namespace DataStructures
{
    public class HashSet<T> : ISet<T>
    {
  	private const uint DefaultSize = 31; /* Prime number */
		private const float LoadFactor = .75f;

		private int count = 0;

		private uint size;
		private float loadFactor;

		private T[] items;

		public HashSet(uint capacity, float factor)
		{
			loadFactor = factor;
			
			/* Find prime number for the table size */
			size = capacity == DefaultSize ? DefaultSize : GeneratePrime(capacity);
			items = new T[size];
		}

		public HashSet(uint size) : this(size, LoadFactor) { }
		public HashSet() : this(DefaultSize, LoadFactor) { }

		private uint FindPosition(T obj)
		{
			int hashCode = obj.GetHashCode();
			uint position = (uint)hashCode % size;
			uint i = 1; /* Quadratic probing value */
			while (null != items[position])
			{
				if (hashCode == items[position].GetHashCode())
					break;

				position += (i * i); /* Square probe offset */
				++i;
				position %= size;
			}
			return position;
		}

		/* Miller-rabin prime generation */
		private static uint GeneratePrime(uint n)
		{
			if (n % 2 == 0) /* Exclude even numbers, not prime */
				++n;

			while (!IsPrime(n))
				n += 2; /* Try the next non-even number */
			return n;
		}

		private static bool IsPrime(uint n)
		{
			if (n == 2 || n == 3)
				return true;
			else if (n == 1 || n % 2 == 0)
				return false;
			else
			{
				for (uint i = 3; i * i <= n; i += 2)
				{
					if (n % i == 0)
						return false;
				}
				return true; /* High possibility to be a prime number */
			}
		}

		private void Rehash(uint capacity)
		{
			T[] oldArray = items;
			uint oldSize = size;

			size = GeneratePrime(capacity);
			items = new T[size];
			for (int i = 0; i < oldSize; ++i)
			{
				T item = oldArray[i];
				if (item != null)
				{
					Add(item);
				}
			}
		}

		public bool Add(T item)
		{
			if (item == null) /* Do not allow null */
				return false;
			else
			{
				uint position = FindPosition(item);
				if (items[position] == null)
				{
					items[position] = item;
					++count;

					if (count / size >= loadFactor)
					{
						Rehash(size << 1); /* Double the size */
					}
					return true;
				}
				else return false; /* Already occupied */
			}
		}

		public void Clear()
		{
			for (int i = 0; i < size; ++i)
				items[i] = default(T);

			count = 0;
		}

		public bool Remove(T item)
		{
			if (item == null)
				return false;
			uint position = FindPosition(item);
			if (item.Equals(items[position]))
			{
				items[position] = default(T);
				return true;
			}
			else return false;
		}

		public bool Contains(T item)
		{
			if (item == null)
				return false;
			return item.Equals(items[FindPosition(item)]);
		}

		public int Count
		{
			get { return count; }
		}

		public bool IsReadOnly
		{
			get { throw new NotImplementedException(); }
		}

		

		public void ExceptWith(IEnumerable<T> other)
		{
			throw new NotImplementedException();
		}

		public void IntersectWith(IEnumerable<T> other)
		{
			throw new NotImplementedException();
		}

		public bool IsProperSubsetOf(IEnumerable<T> other)
		{
			throw new NotImplementedException();
		}

		public bool IsProperSupersetOf(IEnumerable<T> other)
		{
			throw new NotImplementedException();
		}

		public bool IsSubsetOf(IEnumerable<T> other)
		{
			throw new NotImplementedException();
		}

		public bool IsSupersetOf(IEnumerable<T> other)
		{
			throw new NotImplementedException();
		}

		public bool Overlaps(IEnumerable<T> other)
		{
			throw new NotImplementedException();
		}

		public bool SetEquals(IEnumerable<T> other)
		{
			throw new NotImplementedException();
		}

		public void SymmetricExceptWith(IEnumerable<T> other)
		{
			throw new NotImplementedException();
		}

		public void UnionWith(IEnumerable<T> other)
		{
			throw new NotImplementedException();
		}

		void ICollection<T>.Add(T item)
		{
			throw new NotImplementedException();
		}

		public void CopyTo(T[] array, int arrayIndex)
		{
			throw new NotImplementedException();
		}

		public IEnumerator<T> GetEnumerator()
		{
			foreach (var item in items)
			{
				if (item != null)
				{
					yield return item;
				}
			}
		}

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return GetEnumerator();
		}
	}
}