// ==++==
//
//   Copyright (c) Microsoft Corporation.  All rights reserved.
//
// ==--==
//============================================================
//
// Class:  Hashtable
//
// Purpose: Hash table implementation
//
//===========================================================  
namespace System.Collections
{
    using System;
    using System.Diagnostics;
    using System.Runtime.CompilerServices;

    // The Hashtable class represents a dictionary of associated keys and
    // values with constant lookup time.
    //
    // Objects used as keys in a hashtable must implement the GetHashCode
    // and Equals methods (or they can rely on the default implementations
    // inherited from Object if key equality is simply reference
    // equality). Furthermore, the GetHashCode and Equals methods of
    // a key object must produce the same results given the same parameters
    // for the entire time the key is present in the hashtable. In practical
    // terms, this means that key objects should be immutable, at least for
    // the time they are used as keys in a hashtable.
    //
    // When entries are added to a hashtable, they are placed into
    // buckets based on the hashcode of their keys. Subsequent lookups of
    // keys will use the hashcode of the keys to only search a particular
    // bucket, thus substantially reducing the number of key comparisons
    // required to find an entry. A hashtable's maximum load factor, which
    // can be specified when the hashtable is instantiated, determines the
    // maximum ratio of hashtable entries to hashtable buckets. Smaller load
    // factors cause faster average lookup times at the cost of increased
    // memory consumption. The default maximum load factor of 1.0 generally
    // provides the best balance between speed and size. As entries are added
    // to a hashtable, the hashtable's actual load factor increases, and when
    // the actual load factor reaches the maximum load factor value, the
    // number of buckets in the hashtable is automatically increased by
    // approximately a factor of two (to be precise, the number of hashtable
    // buckets is increased to the smallest prime number that is larger than
    // twice the current number of hashtable buckets).
    //
    // Each object provides their own hash function, accessed by calling
    // GetHashCode().  However, one can write their own object
    // implementing IHashCodeProvider and pass it to a constructor on
    // the Hashtable.  That hash function would be used for all objects in
    // the table.
    //
    // This Hashtable is implemented to support multiple concurrent readers
    // and one concurrent writer without using any synchronization primitives.
    // All read methods essentially must protect themselves from a resize
    // occurring while they are running.  This was done by enforcing an
    // ordering on inserts & removes, as well as removing some member variables
    // and special casing the expand code to work in a temporary array instead
    // of the live bucket array.  All inserts must set a bucket's value and
    // key before setting the hash code & collision field.  All removes must
    // clear the hash code & collision field, then the key then value field
    // (at least value should be set last).
    //
    // Version 1.30
    //| <include path='docs/doc[@for="Hashtable"]/*' />
    [CCtorIsRunDuringStartup]
    public class Hashtable : IDictionary, ICloneable
    {
        //
        //Implementation Notes:
//
        //This Hashtable uses double hashing.  There are hashsize buckets in
        //the table, and each bucket can contain 0 or 1 element.  We a bit to
        //mark whether there's been a collision when we inserted multiple
        //elements (ie, an inserted item was hashed at least a second time and
        //we probed this bucket, but it was already in use).  Using the
        //collision bit, we can terminate lookups & removes for elements that
        //aren't in the hash table more quickly.  We steal the most
        //significant bit from the hash code to store the collision bit.
//
        //Our hash function is of the following form:
//
        //h(key, n) = h1(key) + n*h2(key)
//
        //where n is the number of times we've hit a collided bucket and
        //rehashed (on this particular lookup).  Here are our hash functions:
//
        //h1(key) = GetHash(key);  // default implementation calls key.GetHashCode();
        //h2(key) = 1 + (((h1(key) >> 5) + 1) % (hashsize - 1));
//
        //The h1 can return any number.  h2 must return a number between 1 and
        //hashsize - 1 that is relatively prime to hashsize (not a problem if
        //hashsize is prime).  (Knuth's Art of Computer Programming, Vol. 3,
        //p. 528-9)
//
        //If this is true, then we are guaranteed to visit every bucket in
        //exactly hashsize probes, since the least common multiple of hashsize
        //and h2(key) will be hashsize * h2(key).  (This is the first number
        //where adding h2 to h1 mod hashsize will be 0 and we will search the
        //same bucket twice).
//
        //We previously used a different h2(key, n) that was not constant.
        //That is a horrifically bad idea, unless you can prove that series
        //will never produce any identical numbers that overlap when you mod
        //them by hashsize, for all subranges from i to i+hashsize, for all i.
        //It's not worth investigating, since there was no clear benefit from
        //using that hash function, and it was broken.
//
        //For efficiency reasons, we've implemented this by storing h1 and h2
        //in a temporary, and setting a variable called seed equal to h1.  We
        //do a probe, and if we collided, we simply add h2 to seed each time
        //through the loop.
//
        //A good test for h2() is to subclass Hashtable, provide your own
        //implementation of GetHash() that returns a constant, then add many
        //items to the hash table.  Make sure Count equals the number of items
        //you inserted.
//
        //Note that when we remove an item from the hash table, we set the key
        //equal to buckets, if there was a collision in this bucket.
        //Otherwise we'd either wipe out the collision bit, or we'd still have
        //an item in the hash table.
//
        //

        // Table of prime numbers to use as hash table sizes. Each entry is the
        // smallest prime number larger than twice the previous entry.
        private readonly static int[] primes = {
            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
        };

        private const String LoadFactorName = "LoadFactor";
        private const String VersionName = "Version";
        private const String ComparerName = "Comparer";
        private const String HashCodeProviderName = "HashCodeProvider";
        private const String HashSizeName = "HashSize";  // Must save buckets.Length
        private const String KeysName = "Keys";
        private const String ValuesName = "Values";

        private int GetPrime(int minSize) {
            if (minSize < 0)
                throw new ArgumentException("Arg_HTCapacityOverflow");
            for (int i = 0; i < primes.Length; i++) {
                int size = primes[i];
                if (size >= minSize) return size;
            }
            return primes[primes.Length-1];
        }

        // Deleted entries have their key set to buckets

        // 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;

        // The total number of entries in the hash table.
        private  int count;

        // The total number of collision bits set in the hashtable
        private int occupancy;

        private  int loadsize;
        private  int loadFactorPerc;    // 100 = 1.0

        private int version;
        private ICollection keys;
        private ICollection values;

        private IHashCodeProvider _hcp;  // An object that can dispense hash codes.
        private IComparer _comparer;

        //| <include path='docs/doc[@for="Hashtable.hcp"]/*' />
        protected IHashCodeProvider hcp
        {
            get
            {
                return _hcp;
            }
            set
            {
                _hcp = value;
            }
        }


        //| <include path='docs/doc[@for="Hashtable.comparer"]/*' />
        protected IComparer comparer
        {
            get
            {
                return _comparer;
            }
            set
            {
                _comparer = value;
            }
        }


        // Constructs a new hashtable. The hashtable is created with an initial
        // capacity of zero and a load factor of 1.0.
        //| <include path='docs/doc[@for="Hashtable.Hashtable"]/*' />
        public Hashtable() : this(0, 100) {
        }

        // Constructs a new hashtable with the given initial capacity and a load
        // factor of 1.0. The capacity argument serves as an indication of
        // the number of entries the hashtable will contain. When this number (or
        // an approximation) is known, specifying it in the constructor can
        // eliminate a number of resizing operations that would otherwise be
        // performed when elements are added to the hashtable.
        //
        //| <include path='docs/doc[@for="Hashtable.Hashtable1"]/*' />
        public Hashtable(int capacity) : this(capacity, 100) {
        }

        // [Bartok]:
        public Hashtable(int capacity, float loadFactor)
            : this(capacity, (int)(loadFactor * 100), null, null)
        {
        }

        // [Bartok]:
        public Hashtable(int capacity, float loadFactor, IHashCodeProvider hcp, IComparer comparer)
            : this(capacity, (int)(loadFactor * 100), hcp, comparer)
        {
        }

        // Constructs a new hashtable with the given initial capacity and load
        // factor. The capacity argument serves as an indication of the
        // number of entries the hashtable will contain. When this number (or an
        // approximation) is known, specifying it in the constructor can eliminate
        // a number of resizing operations that would otherwise be performed when
        // elements are added to the hashtable. The loadFactorPerc argument
        // indicates the maximum ratio of hashtable entries to hashtable buckets.
        // Smaller load factors cause faster average lookup times at the cost of
        // increased memory consumption. A load factor of 1.0 generally provides
        // the best balance between speed and size.
        //
        //| <include path='docs/doc[@for="Hashtable.Hashtable2"]/*' />

        public Hashtable(int capacity, int loadFactorPerc) : this(capacity, loadFactorPerc, null, null) {
        }

        // Constructs a new hashtable with the given initial capacity and load
        // factor. The capacity argument serves as an indication of the
        // number of entries the hashtable will contain. When this number (or an
        // approximation) is known, specifying it in the constructor can eliminate
        // a number of resizing operations that would otherwise be performed when
        // elements are added to the hashtable. The loadFactorPerc argument
        // indicates the maximum ratio of hashtable entries to hashtable buckets.
        // Smaller load factors cause faster average lookup times at the cost of
        // increased memory consumption. A load factor of 1.0 generally provides
        // the best balance between speed and size.  The hcp argument
        // is used to specify an Object that will provide hash codes for all
        // the Objects in the table.  Using this, you can in effect override
        // GetHashCode() on each Object using your own hash function.  The
        // comparer argument will let you specify a custom function for
        // comparing keys.  By specifying user-defined objects for hcp
        // and comparer, users could make a hash table using strings
        // as keys do case-insensitive lookups.
        //
        //| <include path='docs/doc[@for="Hashtable.Hashtable3"]/*' />
        public Hashtable(int capacity, int loadFactorPerc, IHashCodeProvider hcp, IComparer comparer) {
            if (capacity < 0)
                throw new ArgumentOutOfRangeException("capacity", "ArgumentOutOfRange_NeedNonNegNum");
            if (!(loadFactorPerc >= 10 && loadFactorPerc <= 100))
                throw new ArgumentOutOfRangeException("loadFactorPerc", String.Format("ArgumentOutOfRange_HashtableLoadFactor", 10, 100));

            // Based on perf work, .72 is the optimal load factor for this table.
            this.loadFactorPerc = (loadFactorPerc * 72) / 100;

            int hashsize = GetPrime ((int)(capacity / this.loadFactorPerc));
            buckets = new bucket[hashsize];

            loadsize = (int)(this.loadFactorPerc * hashsize) / 100;
            if (loadsize >= hashsize)
              loadsize = hashsize-1;

            this.hcp = hcp;
            this.comparer = comparer;
        }

        // Constructs a new hashtable using a custom hash function
        // and a custom comparison function for keys.  This will enable scenarios
        // such as doing lookups with case-insensitive strings.
        //
        //| <include path='docs/doc[@for="Hashtable.Hashtable4"]/*' />
        public Hashtable(IHashCodeProvider hcp, IComparer comparer) : this(0, 100, hcp, comparer) {
        }

        // Constructs a new hashtable using a custom hash function
        // and a custom comparison function for keys.  This will enable scenarios
        // such as doing lookups with case-insensitive strings.
        //
        //| <include path='docs/doc[@for="Hashtable.Hashtable5"]/*' />
        public Hashtable(int capacity, IHashCodeProvider hcp, IComparer comparer)
            : this(capacity, 100, hcp, comparer) {
        }

        // Constructs a new hashtable containing a copy of the entries in the given
        // dictionary. The hashtable is created with a load factor of 1.0.
        //
        //| <include path='docs/doc[@for="Hashtable.Hashtable6"]/*' />
        public Hashtable(IDictionary d) : this(d, 100) {
        }

        // Constructs a new hashtable containing a copy of the entries in the given
        // dictionary. The hashtable is created with the given load factor.
        //
        //| <include path='docs/doc[@for="Hashtable.Hashtable7"]/*' />
        public Hashtable(IDictionary d, int loadFactorPerc)
            : this(d, loadFactorPerc, null, null) {
        }

        //| <include path='docs/doc[@for="Hashtable.Hashtable8"]/*' />
        public Hashtable(IDictionary d, IHashCodeProvider hcp, IComparer comparer)
            : this(d, 100, hcp, comparer)  {
        }

        //| <include path='docs/doc[@for="Hashtable.Hashtable9"]/*' />
        public Hashtable(IDictionary d, int loadFactorPerc, IHashCodeProvider hcp, IComparer comparer)
            : this((d != null ? d.Count : 0), loadFactorPerc, hcp, comparer) {
            if (d == null)
                throw new ArgumentNullException("d", "ArgumentNull_Dictionary");

            IDictionaryEnumerator e = d.GetEnumerator();
            while (e.MoveNext()) Add(e.Key, e.Value);
        }

        // Computes the hash function:  H(key, i) = h1(key) + i*h2(key, hashSize).
        // The out parameter seed is h1(key), while the out parameter
        // incr is h2(key, hashSize).  Callers of this function should
        // add incr each time through a loop.
        private uint InitHash(Object key, int hashsize, out uint seed, out uint incr) {
            // Hashcode must be positive.  Also, we must not use the sign bit, since
            // that is used for the collision bit.
            uint hashcode = (uint) GetHash(key) & 0x7FFFFFFF;
            seed = (uint) hashcode;
            // Restriction: incr MUST be between 1 and hashsize - 1, inclusive for
            // the modular arithmetic to work correctly.  This guarantees you'll
            // visit every bucket in the table exactly once within hashsize
            // iterations.  Violate this and it'll cause obscure bugs forever.
            // If you change this calculation for h2(key), update putEntry too!
            incr = (uint)(1 + (((seed >> 5) + 1) % ((uint)hashsize - 1)));
            return hashcode;
        }

        // Adds an entry with the given key and value to this hashtable. An
        // ArgumentException is thrown if the key is null or if the key is already
        // present in the hashtable.
        //
        //| <include path='docs/doc[@for="Hashtable.Add"]/*' />
        public virtual void Add(Object key, Object value) {
            Insert(key, value, true);
        }

        // Removes all entries from this hashtable.
        //| <include path='docs/doc[@for="Hashtable.Clear"]/*' />
        public virtual void Clear() {
          if (count == 0)
            return;

          for (int i = 0; i < buckets.Length; i++) {
            buckets[i].hash_coll = 0;
            buckets[i].key = null;
            buckets[i].val = null;
          }

          count = 0;
          occupancy = 0;
        }

        // Clone returns a virtually identical copy of this hash table.  This does
        // a shallow copy - the Objects in the table aren't cloned, only the references
        // to those Objects.
        //| <include path='docs/doc[@for="Hashtable.Clone"]/*' />
        public virtual Object Clone()
        {
            bucket[] lbuckets = buckets;
            Hashtable ht = new Hashtable(count,hcp,comparer);
            ht.version = version;
            ht.loadFactorPerc = loadFactorPerc;
            ht.count = 0;

            int bucket = lbuckets.Length;
            while (bucket > 0) {
                    bucket--;
                    Object keyv = lbuckets[bucket].key;
                    if ((keyv != null) && (keyv != lbuckets)) {
                        ht[keyv] = lbuckets[bucket].val;
                  }
            }

            return ht;
        }

        // Checks if this hashtable contains the given key.
        //| <include path='docs/doc[@for="Hashtable.Contains"]/*' />
        public virtual bool Contains(Object key) {
            return ContainsKey(key);
        }

        // Checks if this hashtable contains an entry with the given key.  This is
        // an O(1) operation.
        //
        //| <include path='docs/doc[@for="Hashtable.ContainsKey"]/*' />
        public virtual bool ContainsKey(Object key) {
            if (key == null) {
                throw new ArgumentNullException("key", "ArgumentNull_Key");
            }

            uint seed;
            uint incr;
            // Take a snapshot of buckets, in case another thread resizes table
            bucket[] lbuckets = buckets;
            uint hashcode = InitHash(key, lbuckets.Length, out seed, out incr);
            int  ntry = 0;

            bucket b;
            do {
                int bucketNumber = (int) (seed % (uint)lbuckets.Length);
                b = lbuckets[bucketNumber];
                if (b.key == null) {
                    return false;
                }
                if (((b.hash_coll & 0x7FFFFFFF) == hashcode) &&
                    KeyEquals (b.key, key))
                    return true;
                seed += incr;
            } while (b.hash_coll < 0 && ++ntry < lbuckets.Length);
            return false;
        }



        // Checks if this hashtable contains an entry with the given value. The
        // values of the entries of the hashtable are compared to the given value
        // using the Object.Equals method. This method performs a linear
        // search and is thus be substantially slower than the ContainsKey
        // method.
        //
        //| <include path='docs/doc[@for="Hashtable.ContainsValue"]/*' />
        public virtual bool ContainsValue(Object value) {
            if (value == null) {
                for (int i = buckets.Length; --i >= 0;) {
                  if (buckets[i].key != null && buckets[i].val == null)
                    return true;
                }
            }
            else {
              for (int i = buckets.Length; --i >= 0;) {
                  Object val = buckets[i].val;
                  if (val != null && value.Equals(val)) return true;
              }
            }
            return false;
        }

        // Copies the keys of this hashtable to a given array starting at a given
        // index. This method is used by the implementation of the CopyTo method in
        // the KeyCollection class.
        private void CopyKeys(Array array, int arrayIndex) {
            bucket[] lbuckets = buckets;
            for (int i = lbuckets.Length; --i >= 0;) {
              Object keyv = lbuckets[i].key;
              if ((keyv != null) && (keyv != buckets)) {
                array.SetValue(keyv, arrayIndex++);
              }
            }
        }

        // Copies the keys of this hashtable to a given array starting at a given
        // index. This method is used by the implementation of the CopyTo method in
        // the KeyCollection class.
        private void CopyEntries(Array array, int arrayIndex) {
            bucket[] lbuckets = buckets;
            for (int i = lbuckets.Length; --i >= 0;) {
              Object keyv = lbuckets[i].key;
              if ((keyv != null) && (keyv != buckets)) {
                DictionaryEntry entry = new DictionaryEntry(keyv,lbuckets[i].val);
                array.SetValue(entry, arrayIndex++);
              }
            }
        }

        // Copies the values in this hash table to an array at
        // a given index.  Note that this only copies values, and not keys.
        //| <include path='docs/doc[@for="Hashtable.CopyTo"]/*' />
        public virtual void CopyTo(Array array, int arrayIndex)
        {
            if (array == null)
                throw new ArgumentNullException("array", "ArgumentNull_Array");
            if (array.Rank != 1)
                throw new ArgumentException("Arg_RankMultiDimNotSupported");
            if (arrayIndex < 0)
                throw new ArgumentOutOfRangeException("arrayIndex", "ArgumentOutOfRange_NeedNonNegNum");
            if (array.Length - arrayIndex < count)
                throw new ArgumentException("Arg_ArrayPlusOffTooSmall");
            CopyEntries(array, arrayIndex);
        }

        // Copies the values of this hashtable to a given array starting at a given
        // index. This method is used by the implementation of the CopyTo method in
        // the ValueCollection class.
        private void CopyValues(Array array, int arrayIndex) {
            bucket[] lbuckets = buckets;
            for (int i = lbuckets.Length; --i >= 0;) {
                Object keyv = lbuckets[i].key;
                if ((keyv != null) && (keyv != buckets)) {
                    array.SetValue(lbuckets[i].val, arrayIndex++);
                }
            }
        }

        // Returns the value associated with the given key. If an entry with the
        // given key is not found, the returned value is null.
        //
        //| <include path='docs/doc[@for="Hashtable.this"]/*' />
        public virtual Object this[Object key] {
          get {
            if (key == null) {
              throw new ArgumentNullException("key", "ArgumentNull_Key");
            }
            uint seed;
            uint incr;
            // Take a snapshot of buckets, in case another thread does a resize
            bucket[] lbuckets = buckets;
            uint hashcode = InitHash(key, lbuckets.Length, out seed, out incr);
            int  ntry = 0;

            bucket b;
            do
              {
                int bucketNumber = (int) (seed % (uint)lbuckets.Length);
                b = lbuckets[bucketNumber];
                if (b.key == null) {
                  return null;
                }
                if (((b.hash_coll & 0x7FFFFFFF) == hashcode) &&
                    KeyEquals (key, b.key))
                  return b.val;
                seed += incr;
              } while (b.hash_coll < 0 && ++ntry < lbuckets.Length);
            return null;
          }
          set {
            Insert(key, value, false);
          }
        }

        // Increases the bucket count of this hashtable. This method is called from
        // the Insert method when the actual load factor of the hashtable reaches
        // the upper limit specified when the hashtable was constructed. The number
        // of buckets in the hashtable is increased to the smallest prime number
        // that is larger than twice the current number of buckets, and the entries
        // in the hashtable are redistributed into the new buckets using the cached
        // hashcodes.
        private void expand()  {
            rehash( GetPrime( 1+buckets.Length*2 ) );
        }

        // We occasionally need to rehash the table to clean up the collision bits.
        private void rehash() {
            rehash( buckets.Length );
        }

        private void rehash( int newsize ) {

            // 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)) {
                    putEntry(newBuckets, oldb.key, oldb.val, oldb.hash_coll & 0x7FFFFFFF);
                }
            }

            // New bucket[] is good to go - replace buckets and other internal state.
            version++;
            buckets = newBuckets;
            loadsize = (int)(loadFactorPerc * newsize) / 100;

            if (loadsize >= newsize) {
                loadsize = newsize-1;
            }

            return;
        }

        // Returns an enumerator for this hashtable.
        // If modifications made to the hashtable while an enumeration is
        // in progress, the MoveNext and Current methods of the
        // enumerator will throw an exception.
        //
        //| <include path='docs/doc[@for="Hashtable.IEnumerable.GetEnumerator"]/*' />
        IEnumerator IEnumerable.GetEnumerator() {
            return new HashtableEnumerator(this, HashtableEnumerator.DictEntry);
        }

        // Returns a dictionary enumerator for this hashtable.
        // If modifications made to the hashtable while an enumeration is
        // in progress, the MoveNext and Current methods of the
        // enumerator will throw an exception.
        //
        //| <include path='docs/doc[@for="Hashtable.GetEnumerator"]/*' />
        public virtual IDictionaryEnumerator GetEnumerator() {
            return new HashtableEnumerator(this, HashtableEnumerator.DictEntry);
        }

        // Internal method to get the hash code for an Object.  This will call
        // GetHashCode() on each object if you haven't provided an IHashCodeProvider
        // instance.  Otherwise, it calls hcp.GetHashCode(obj).
        //| <include path='docs/doc[@for="Hashtable.GetHash"]/*' />
        protected virtual int GetHash(Object key)
        {
            if (hcp != null)
                return hcp.GetHashCode(key);
            return key.GetHashCode();
        }

        // Is this Hashtable read-only?
        //| <include path='docs/doc[@for="Hashtable.IsReadOnly"]/*' />
        public virtual bool IsReadOnly {
            get { return false; }
        }

        //| <include path='docs/doc[@for="Hashtable.IsFixedSize"]/*' />
        public virtual bool IsFixedSize {
            get { return false; }
        }

        // Is this Hashtable synchronized?  See SyncRoot property
        //| <include path='docs/doc[@for="Hashtable.IsSynchronized"]/*' />
        public virtual bool IsSynchronized {
            get { return false; }
        }

        // Internal method to compare two keys.  If you have provided an IComparer
        // instance in the constructor, this method will call comparer.Compare(item, key).
        // Otherwise, it will call item.Equals(key).
        //
        //| <include path='docs/doc[@for="Hashtable.KeyEquals"]/*' />
        protected virtual bool KeyEquals(Object item, Object key)
        {
            if (comparer != null)
                return comparer.Compare(item, key)==0;
            return item.Equals(key);
        }

        // Returns a collection representing the keys of this hashtable. The order
        // in which the returned collection represents the keys is unspecified, but
        // it is guaranteed to be          buckets = newBuckets; the same order in which a collection returned by
        // GetValues represents the values of the hashtable.
        //
        // The returned collection is live in the sense that any changes
        // to the hash table are reflected in this collection.  It is not
        // a static copy of all the keys in the hash table.
        //
        //| <include path='docs/doc[@for="Hashtable.Keys"]/*' />
        public virtual ICollection Keys {
            get {
                if (keys == null) keys = new KeyCollection(this);
                return keys;
            }
        }

        // Returns a collection representing the values of this hashtable. The
        // order in which the returned collection represents the values is
        // unspecified, but it is guaranteed to be the same order in which a
        // collection returned by GetKeys represents the keys of the
        // hashtable.
        //
        // The returned collection is live in the sense that any changes
        // to the hash table are reflected in this collection.  It is not
        // a static copy of all the keys in the hash table.
        //
        //| <include path='docs/doc[@for="Hashtable.Values"]/*' />
        public virtual ICollection Values {
            get {
                if (values == null) values = new ValueCollection(this);
                return values;
            }
        }

        // Inserts an entry into this hashtable. This method is called from the Set
        // and Add methods. If the add parameter is true and the given key already
        // exists in the hashtable, an exception is thrown.
        private void Insert (Object key, Object nvalue, bool add) {
            if (key == null) {
                throw new ArgumentNullException("key", "ArgumentNull_Key");
            }
            if (count >= loadsize) {
                expand();
            }
            else if(occupancy > loadsize && count > 100) {
                rehash();
            }

            uint seed;
            uint incr;
            // Assume we only have one thread writing concurrently.  Modify
            // buckets to contain new data, as long as we insert in the right order.
            uint hashcode = InitHash(key, buckets.Length, out seed, out incr);
            int  ntry = 0;
            int emptySlotNumber = -1; // We use the empty slot number to cache the first empty slot. We chose to reuse slots
                                      // create by remove that have the collision bit set over using up new slots.

            do {
                int bucketNumber = (int) (seed % (uint)buckets.Length);

                // Set emptySlot number to current bucket if it is the first available bucket that we have seen
                // that once contained an entry and also has had a collision.
                // We need to search this entire collision chain because we have to ensure that there are no
                // duplicate entries in the table.
                if (emptySlotNumber == -1 && (buckets[bucketNumber].key == buckets) && (buckets[bucketNumber].hash_coll < 0))//(((buckets[bucketNumber].hash_coll & unchecked(0x80000000)) != 0)))
                    emptySlotNumber = bucketNumber;

                // Insert the key/value pair into this bucket if this bucket is empty and has never contained an entry
                // OR
                // This bucket once contained an entry but there has never been a collision
                if ((buckets[bucketNumber].key == null) ||
                    (buckets[bucketNumber].key == buckets && ((buckets[bucketNumber].hash_coll & unchecked(0x80000000))==0))) {

                    // If we have found an available bucket that has never had a collision, but we've seen an available
                    // bucket in the past that has the collision bit set, use the previous bucket instead
                    if (emptySlotNumber != -1) // Reuse slot
                        bucketNumber = emptySlotNumber;

                    // We pretty much have to insert in this order.  Don't set hash
                    // code until the value & key are set appropriately.
                    buckets[bucketNumber].val = nvalue;
                    buckets[bucketNumber].key  = key;
                    buckets[bucketNumber].hash_coll |= (int) hashcode;
                    count++;
                    version++;
                    return;
                }

                // The current bucket is in use
                // OR
                // it is available, but has had the collision bit set and we have already found an available bucket
                if (((buckets[bucketNumber].hash_coll & 0x7FFFFFFF) == hashcode) &&
                    KeyEquals (key, buckets[bucketNumber].key)) {
                    if (add) {
                        throw new ArgumentException("Argument_AddingDuplicate__" + buckets[bucketNumber].key);
                    }
                    buckets[bucketNumber].val = nvalue;
                    version++;
                    return;
                }

                // The current bucket is full, and we have therefore collided.  We need to set the collision bit
                // UNLESS
                // we have remembered an available slot previously.
                if (emptySlotNumber == -1) {// We don't need to set the collision bit here since we already have an empty slot
                    if (buckets[bucketNumber].hash_coll >= 0) {
                        buckets[bucketNumber].hash_coll |= unchecked((int)0x80000000);
                        occupancy++;
                    }
                }
                seed += incr;
            } while (++ntry < buckets.Length);

            // This code is here if and only if there were no buckets without a collision bit set in the entire table
            if (emptySlotNumber != -1) {
                    // We pretty much have to insert in this order.  Don't set hash
                    // code until the value & key are set appropriately.
                    buckets[emptySlotNumber].val = nvalue;
                    buckets[emptySlotNumber].key  = key;
                    buckets[emptySlotNumber].hash_coll |= (int) hashcode;
                    count++;
                    version++;
                    return;

            }

            // If you see this assert, make sure load factor & count are reasonable.
            // Then verify that our double hash function (h2, described at top of file)
            // meets the requirements described above. You should never see this assert.
            Debug.Assert(false, "hash table insert failed!  Load factor too high, or our double hashing function is incorrect.");
            throw new InvalidOperationException("InvalidOperation_HashInsertFailed");
        }

        private void putEntry (bucket[] newBuckets, Object key, Object nvalue, int hashcode)
        {
            Debug.Assert(hashcode >= 0, "hashcode >= 0");  // make sure collision bit (sign bit) wasn't set.

            uint seed = (uint) hashcode;
            uint incr = (uint)(1 + (((seed >> 5) + 1) % ((uint)newBuckets.Length - 1)));

            do {
                int bucketNumber = (int) (seed % (uint)newBuckets.Length);

                if ((newBuckets[bucketNumber].key == null) || (newBuckets[bucketNumber].key == buckets)) {
                    newBuckets[bucketNumber].val = nvalue;
                    newBuckets[bucketNumber].key = key;
                    newBuckets[bucketNumber].hash_coll |= hashcode;
                    return;
                }

                if (newBuckets[bucketNumber].hash_coll >= 0) {
                    newBuckets[bucketNumber].hash_coll |= unchecked((int)0x80000000);
                    occupancy++;
                }
                seed += incr;
            } while (true);
        }

        // Removes an entry from this hashtable. If an entry with the specified
        // key exists in the hashtable, it is removed. An ArgumentException is
        // thrown if the key is null.
        //
        //| <include path='docs/doc[@for="Hashtable.Remove"]/*' />
        public virtual void Remove(Object key) {
            if (key == null) {
                throw new ArgumentNullException("key", "ArgumentNull_Key");
            }
            uint seed;
            uint incr;
            // Assuming only one concurrent writer, write directly into buckets.
            uint hashcode = InitHash(key, buckets.Length, out seed, out incr);
            int ntry = 0;

            bucket b;
            int bn; // bucketNumber
            do {
                bn = (int) (seed % (uint)buckets.Length);  // bucketNumber
                b = buckets[bn];
                if (((b.hash_coll & 0x7FFFFFFF) == hashcode) &&
                    KeyEquals (key, b.key)) {
                    // Clear hash_coll field, then key, then value
                    buckets[bn].hash_coll &= unchecked((int)0x80000000);
                    if (buckets[bn].hash_coll != 0) {
                        buckets[bn].key = buckets;
                    }
                    else {
                        buckets[bn].key = null;
                    }
                    buckets[bn].val = null;  // Free object references sooner & simplify ContainsValue.
                    count--;
                    version++;
                    return;
                }
                seed += incr;
            } while (buckets[bn].hash_coll < 0 && ++ntry < buckets.Length);

        //throw new ArgumentException("Arg_RemoveArgNotFound");
        }

        // Returns the object to synchronize on for this hash table.
        //| <include path='docs/doc[@for="Hashtable.SyncRoot"]/*' />
        public virtual Object SyncRoot {
            get { return this; }
        }

        // Returns the number of associations in this hashtable.
        //
        //| <include path='docs/doc[@for="Hashtable.Count"]/*' />
        public virtual int Count {
            get { return count; }
        }

        // Returns a thread-safe wrapper for a Hashtable.
        //
        //| <include path='docs/doc[@for="Hashtable.Synchronized"]/*' />
        public static Hashtable Synchronized(Hashtable table) {
            if (table == null)
                throw new ArgumentNullException("table");
            return new SyncHashtable(table);
        }

        // Implements a Collection for the keys of a hashtable. An instance of this
        // class is created by the GetKeys method of a hashtable.
        private class KeyCollection : ICollection
        {
            private Hashtable _hashtable;

            internal KeyCollection(Hashtable hashtable) {
                _hashtable = hashtable;
            }

            public virtual void CopyTo(Array array, int arrayIndex) {
                if (array == null)
                    throw new ArgumentNullException("array");
                if (array.Rank != 1)
                    throw new ArgumentException("Arg_RankMultiDimNotSupported");
                if (arrayIndex < 0)
                    throw new ArgumentOutOfRangeException("arrayIndex", "ArgumentOutOfRange_NeedNonNegNum");
                if (array.Length - arrayIndex < _hashtable.count)
                    throw new ArgumentException("Arg_ArrayPlusOffTooSmall");
                _hashtable.CopyKeys(array, arrayIndex);
            }

            public virtual IEnumerator GetEnumerator() {
                return new HashtableEnumerator(_hashtable, HashtableEnumerator.Keys);
            }

            public virtual bool IsReadOnly {
                get { return true; }
            }

            public virtual bool IsSynchronized {
                get { return _hashtable.IsSynchronized; }
            }

            public virtual Object SyncRoot {
                get { return _hashtable.SyncRoot; }
            }

            public virtual int Count {
                get { return _hashtable.count; }
            }
        }

        // Implements a Collection for the values of a hashtable. An instance of
        // this class is created by the GetValues method of a hashtable.
        private class ValueCollection : ICollection
        {
            private Hashtable _hashtable;

            internal ValueCollection(Hashtable hashtable) {
                _hashtable = hashtable;
            }

            public virtual void CopyTo(Array array, int arrayIndex) {
                if (array == null)
                    throw new ArgumentNullException("array");
                if (array.Rank != 1)
                    throw new ArgumentException("Arg_RankMultiDimNotSupported");
                if (arrayIndex < 0)
                    throw new ArgumentOutOfRangeException("arrayIndex", "ArgumentOutOfRange_NeedNonNegNum");
                if (array.Length - arrayIndex < _hashtable.count)
                    throw new ArgumentException("Arg_ArrayPlusOffTooSmall");
                _hashtable.CopyValues(array, arrayIndex);
            }

            public virtual IEnumerator GetEnumerator() {
                return new HashtableEnumerator(_hashtable, HashtableEnumerator.Values);
            }

            public virtual bool IsReadOnly {
                get { return true; }
            }

            public virtual bool IsSynchronized {
                get { return _hashtable.IsSynchronized; }
            }

            public virtual Object SyncRoot {
                get { return _hashtable.SyncRoot; }
            }

            public virtual int Count {
                get { return _hashtable.count; }
            }
        }

        // Synchronized wrapper for hashtable
        private class SyncHashtable : Hashtable
        {
            protected Hashtable _table;

            internal SyncHashtable(Hashtable table) {
                _table = table;
            }

            public override int Count {
                get { return _table.Count; }
            }

            public override bool IsReadOnly {
                get { return _table.IsReadOnly; }
            }

            public override bool IsFixedSize {
                get { return _table.IsFixedSize; }
            }

            public override bool IsSynchronized {
                get { return true; }
            }

            public override Object this[Object key] {
                get {
                        return _table[key];
                }
                set {
                    lock (_table.SyncRoot) {
                        _table[key] = value;
                    }
                }
            }

            public override Object SyncRoot {
                get { return _table.SyncRoot; }
            }

            public override void Add(Object key, Object value) {
                lock (_table.SyncRoot) {
                    _table.Add(key, value);
                }
            }

            public override void Clear() {
                lock (_table.SyncRoot) {
                    _table.Clear();
                }
            }

            public override bool Contains(Object key) {
                return _table.Contains(key);
            }

            public override bool ContainsKey(Object key) {
                return _table.ContainsKey(key);
            }

            public override bool ContainsValue(Object key) {
                return _table.ContainsValue(key);
            }

            public override void CopyTo(Array array, int arrayIndex) {
                _table.CopyTo(array, arrayIndex);
            }

            public override Object Clone() {
                lock (_table.SyncRoot) {
                    return Hashtable.Synchronized((Hashtable)_table.Clone());
                }
            }

            public override IDictionaryEnumerator GetEnumerator() {
                return _table.GetEnumerator();
            }

            protected override int GetHash(Object key) {
                return _table.GetHash(key);
            }

            protected override bool KeyEquals(Object item, Object key) {
                return _table.KeyEquals(item, key);
            }

            public override ICollection Keys {
                get {
                    lock (_table.SyncRoot) {
                        return _table.Keys;
                    }
                }
            }

            public override ICollection Values {
                get {
                    lock (_table.SyncRoot) {
                        return _table.Values;
                    }
                }
            }

            public override void Remove(Object key) {
                lock (_table.SyncRoot) {
                    _table.Remove(key);
                }
            }
        }


        // Implements an enumerator for a hashtable. The enumerator uses the
        // internal version number of the hashtable to ensure that no modifications
        // are made to the hashtable while an enumeration is in progress.
        private class HashtableEnumerator : IDictionaryEnumerator, ICloneable
        {
            private Hashtable hashtable;
            private int bucket;
            private int version;
            private bool current;
            private int getObjectRetType;   // What should GetObject return?
            private Object currentKey;
            private Object currentValue;

            internal const int Keys = 1;
            internal const int Values = 2;
            internal const int DictEntry = 3;

            internal HashtableEnumerator(Hashtable hashtable, int getObjRetType) {
                this.hashtable = hashtable;
                bucket = hashtable.buckets.Length;
                version = hashtable.version;
                current = false;
                getObjectRetType = getObjRetType;
            }

            public Object Clone() {
                return MemberwiseClone();
            }

            public virtual Object Key {
                get {
                    if (version != hashtable.version) throw new InvalidOperationException("InvalidOperation_EnumFailedVersion");
                    if (current == false) throw new InvalidOperationException("InvalidOperation_EnumNotStarted");
                    return currentKey;
                }
            }

            public virtual bool MoveNext() {
                if (version != hashtable.version) throw new InvalidOperationException("InvalidOperation_EnumFailedVersion");
                while (bucket > 0) {
                    bucket--;
                    Object keyv = hashtable.buckets[bucket].key;
                    if ((keyv != null) && (keyv != hashtable.buckets)) {
                        currentKey = keyv;
                        currentValue = hashtable.buckets[bucket].val;
                        current = true;
                        return true;
                    }
                }
                current = false;
                return false;
            }

            public virtual DictionaryEntry Entry {
                get {
                    if (current == false) throw new InvalidOperationException("InvalidOperation_EnumOpCantHappen");
                    return new DictionaryEntry(currentKey, currentValue);
                }
            }


            public virtual Object Current {
                get {
                    if (current == false) throw new InvalidOperationException("InvalidOperation_EnumOpCantHappen");

                    if (getObjectRetType == Keys)
                        return currentKey;
                    else if (getObjectRetType == Values)
                        return currentValue;
                    else
                        return new DictionaryEntry(currentKey, currentValue);
                }
            }

            public virtual Object Value {
                get {
                    if (version != hashtable.version) throw new InvalidOperationException("InvalidOperation_EnumFailedVersion");
                    if (current == false) throw new InvalidOperationException("InvalidOperation_EnumOpCantHappen");
                    return currentValue;
                }
            }

            public virtual void Reset() {
                if (version != hashtable.version) throw new InvalidOperationException("InvalidOperation_EnumFailedVersion");
                current = false;
                bucket = hashtable.buckets.Length;
                currentKey = null;
                currentValue = null;
            }
        }
    }
}