hash.cs

C#写的类似于STL的集合类,首先是C#编写,可以用于.net变程.

                if (value < 0.25 || value > 0.95)
                    throw new ArgumentOutOfRangeException("value", value, Strings.InvalidLoadFactor);

                StopEnumerations();

                bool maybeExpand = value < loadFactor;    // May need to expand or shrink the table -- which?

                // Update loadFactor and thresholds.
                loadFactor = value;
                thresholdGrow = (int)(totalSlots * loadFactor);
                thresholdShrink = thresholdGrow / 3;
                if (thresholdShrink <= MINSIZE)
                    thresholdShrink = 1;

                // Possibly expand or shrink the table.
                if (maybeExpand)
                    EnsureEnoughSlots(0);
                else
                    ShrinkIfNeeded();
            }
        }

        /// <summary>
        /// Insert a new item into the hash table. If a duplicate item exists, can replace or
        /// do nothing.
        /// </summary>
        /// <param name="item">The item to insert.</param>
        /// <param name="replaceOnDuplicate">If true, duplicate items are replaced. If false, nothing
        /// is done if a duplicate already exists.</param>
        /// <param name="previous">If a duplicate was found, returns it (whether replaced or not).</param>
        /// <returns>True if no duplicate existed, false if a duplicate was found.</returns>
        public bool Insert(T item, bool replaceOnDuplicate, out T previous)
        {
            int hash, bucket, skip;
            int emptyBucket = -1;                      // If >= 0, an empty bucket we can use for a true insert
            bool duplicateMightExist = true;      // If true, still the possibility that a duplicate exists.

            EnsureEnoughSlots(1);            // Ensure enough room to insert. Also stops enumerations.

            hash = GetHashValues(item, out bucket, out skip);

            for (;;) {
                if (table[bucket].Empty) {
                    // Record the location of the first empty bucket seen. This is where the item will
                    // go if no duplicate exists.
                    if (emptyBucket == -1)
                        emptyBucket = bucket;  
                  
                    if (!duplicateMightExist ||  !table[bucket].Collision) {
                        // There can't be a duplicate further on, because a bucket with the collision bit
                        // clear was found (here or earlier). We have the place to insert.
                        break;
                    }
                }
                else if (table[bucket].HashValue == hash && equalityComparer.Equals(table[bucket].item, item)) {
                    // We found a duplicate item. Replace it if requested to.
                    previous = table[bucket].item;
                    if (replaceOnDuplicate) 
                        table[bucket].item = item;
                    return false;
                }
                else {
                    // The slot is used, but isn't our item. 
                    if (!table[bucket].Collision) {
                        // Since the collision bit is off, we can't have a duplicate. 
                        if (emptyBucket >= 0) {
                            // We already have an empty bucket to use.
                            break;
                        }
                        else {
                            // Keep searching for an empty bucket to place the item.
                            table[bucket].Collision = true;
                            duplicateMightExist = false;
                        }
                    }
                }

                bucket = (bucket + skip) & hashMask;
            }

            // We found an empty bucket. Insert the new item.
            table[emptyBucket].HashValue = hash;
            table[emptyBucket].item = item;

            ++count;
            if (!table[emptyBucket].Collision)
                ++usedSlots;
            previous = default(T);
            return true;
        }

        /// <summary>
        /// Deletes an item from the hash table. 
        /// </summary>
        /// <param name="item">Item to search for and delete.</param>
        /// <param name="itemDeleted">If true returned, the actual item stored in the hash table (must be 
        /// equal to <paramref name="item"/>, but may not be identical.</param>
        /// <returns>True if item was found and deleted, false if item wasn't found.</returns>
        public bool Delete(T item, out T itemDeleted)
        {
            int hash, bucket, skip;

            StopEnumerations();

            if (count == 0) {
                itemDeleted = default(T);
                return false;
            }

            hash = GetHashValues(item, out bucket, out skip);

            for (; ; ) {
                if (table[bucket].HashValue == hash && equalityComparer.Equals(table[bucket].item, item)) {
                    // Found the item. Remove it.
                    itemDeleted = table[bucket].item;
                    table[bucket].Clear();
                    --count;
                    if (!table[bucket].Collision)
                        --usedSlots;
                    ShrinkIfNeeded();
                    return true;
                }
                else if (!table[bucket].Collision) {
                    // No collision bit, so we can stop searching. No such element.
                    itemDeleted = default(T);
                    return false;
                }

                bucket = (bucket + skip) & hashMask;
            }
        }

        /// <summary>
        /// Find an item in the hash table. If found, optionally replace it with the
        /// finding item.
        /// </summary>
        /// <param name="find">Item to find.</param>
        /// <param name="replace">If true, replaces the equal item in the hash table
        /// with <paramref name="item"/>.</param>
        /// <param name="item">Returns the equal item found in the table, if true was returned.</param>
        /// <returns>True if the item was found, false otherwise.</returns>
        public bool Find(T find, bool replace, out T item)
        {
            int hash, bucket, skip;

            if (count == 0) {
                item = default(T);
                return false;
            }

            hash = GetHashValues(find, out bucket, out skip);

            for (; ; ) {
                if (table[bucket].HashValue == hash && equalityComparer.Equals(table[bucket].item, find)) {
                    // Found the item.  
                    item = table[bucket].item;
                    if (replace)
                        table[bucket].item = find;
                    return true;
                }
                else if (!table[bucket].Collision) {
                    // No collision bit, so we can stop searching. No such element.
                    item = default(T);
                    return false;
                }

                bucket = (bucket + skip) & hashMask;
            }
        }

        /// <summary>
        /// Enumerate all of the items in the hash table. The items
        /// are enumerated in a haphazard, unpredictable order.
        /// </summary>
        /// <returns>An IEnumerator&lt;T&gt; that enumerates the items
        /// in the hash table.</returns>
        public IEnumerator<T> GetEnumerator()
        {
            if (count > 0) {
                int startStamp = changeStamp;

                foreach (Slot slot in table) {
                    if (!slot.Empty) {
                        yield return slot.item;
                        CheckEnumerationStamp(startStamp);
                    }
                }
            }
        }

        /// <summary>
        /// Enumerate all of the items in the hash table. The items
        /// are enumerated in a haphazard, unpredictable order.
        /// </summary>
        /// <returns>An IEnumerator that enumerates the items
        /// in the hash table.</returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        /// <summary>
        /// Creates a clone of this hash table.
        /// </summary>
        /// <param name="cloneItem">If non-null, this function is applied to each item when cloning. It must be the 
        /// case that this function does not modify the hash code or equality function.</param>
        /// <returns>A shallow clone that contains the same items.</returns>
        public Hash<T> Clone(Converter<T,T> cloneItem)
        {
            Hash<T> clone = new Hash<T>(equalityComparer);
            clone.count = this.count;
            clone.usedSlots = this.usedSlots;
            clone.totalSlots = this.totalSlots;
            clone.loadFactor = this.loadFactor;
            clone.thresholdGrow = this.thresholdGrow;
            clone.thresholdShrink = this.thresholdShrink;
            clone.hashMask = this.hashMask;
            clone.secondaryShift = this.secondaryShift;
            if (table != null) {
                clone.table = (Slot[])table.Clone();

                if (cloneItem != null) {
                    for (int i = 0; i < table.Length; ++i) {
                        if (!table[i].Empty)
                            table[i].item = cloneItem(table[i].item);
                    }
                }
            }

            return clone;
        }

        #region Serialization

        /// <summary>
        /// Serialize the hash table. Called from the serialization infrastructure.
        /// </summary>
        void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context)
        {
            if (info == null)
                throw new ArgumentNullException("info");

            info.AddValue("equalityComparer", equalityComparer, typeof(IEqualityComparer<T>));
            info.AddValue("loadFactor", loadFactor, typeof(float));
            T[] items = new T[count];
            int i = 0;
            foreach (Slot slot in table)
                if (! slot.Empty)
                    items[i++] = slot.item;
            info.AddValue("items", items, typeof(T[]));
        }

        /// <summary>
        /// Called on deserialization. We cannot deserialize now, because hash codes
        /// might not be correct now. We do real deserialization in the OnDeserialization call.
        /// </summary>
        protected Hash(SerializationInfo serInfo, StreamingContext context)
        {
            // Save away the serialization info for use later. We can't be sure of hash codes
            // being stable until the entire object graph is deserialized, so we wait until then
            // to deserialize.
            serializationInfo = serInfo;
        }

        /// <summary>
        /// Deserialize the hash table. Called from the serialization infrastructure when 
        /// the object graph has finished deserializing.
        /// </summary>
        void IDeserializationCallback.OnDeserialization(object sender)
        {
            if (serializationInfo == null)
                return;

            loadFactor = serializationInfo.GetSingle("loadFactor");
            equalityComparer = (IEqualityComparer<T>) serializationInfo.GetValue("equalityComparer", typeof(IEqualityComparer<T>));

            T[] items = (T[])serializationInfo.GetValue("items", typeof(T[]));
            T dummy;

            EnsureEnoughSlots(items.Length);
            foreach (T item in items)
                Insert(item, true, out dummy);

            serializationInfo = null;
        }

        #endregion Serialization

#if DEBUG
        /// <summary>
        /// Print out basic stats about the hash table.
        /// </summary>
        internal void PrintStats()
        {
            Console.WriteLine("count={0}  usedSlots={1}  totalSlots={2}", count, usedSlots, totalSlots);
            Console.WriteLine("loadFactor={0}  thresholdGrow={1}  thresholdShrink={2}", loadFactor, thresholdGrow, thresholdShrink);
            Console.WriteLine("hashMask={0:X}  secondaryShift={1}", hashMask, secondaryShift);
            Console.WriteLine();
        }

        /// <summary>
        /// Print out the state of the hash table and each of the slots. Each slot looks like:
        ///     Slot    4: C 4513e41e hello
        /// where the "C" indicates the collision bit is on
        /// the next hex number is the hash value
        /// followed by ToString() on the item.
        /// </summary>
        internal void Print()
        {
            PrintStats();
            for (int i = 0; i < totalSlots; ++i) 
                Console.WriteLine("Slot {0,4:X}: {1} {2,8:X} {3}", i, table[i].Collision ? "C" : " ", 
                    table[i].HashValue, table[i].Empty ? "<empty>" : table[i].item.ToString());
            Console.WriteLine();
        }

        /// <summary>
        /// Check that everything appears to be OK in the hash table.
        /// </summary>
        internal void Validate()
        {
            Debug.Assert(count <= usedSlots);
            Debug.Assert(count <= totalSlots);
            Debug.Assert(usedSlots <= totalSlots);
            Debug.Assert(usedSlots <= thresholdGrow);
            Debug.Assert((int)(totalSlots * loadFactor) == thresholdGrow);
            if (thresholdShrink > 1)
                Debug.Assert(thresholdGrow / 3 == thresholdShrink);
            else
                Debug.Assert(thresholdGrow / 3 <= MINSIZE);
            if (totalSlots > 0) {
                Debug.Assert((totalSlots & (totalSlots - 1)) == 0);  // totalSlots is a power of two.
                Debug.Assert(totalSlots - 1 == hashMask);
                Debug.Assert(GetSecondaryShift(totalSlots) == secondaryShift);
                Debug.Assert(totalSlots == table.Length);
            }

            // Traverse the table. Make sure that count and usedSlots are right, and that
            // each slot looks reasonable.
            int expectedCount = 0, expectedUsed = 0, initialBucket, skip;
            if (table != null) {
                for (int i = 0; i < totalSlots; ++i) {
                    Slot slot = table[i];
                    if (slot.Empty) {
                        // Empty slot
                        if (slot.Collision)
                            ++expectedUsed;
                        Debug.Assert(object.Equals(default(T), slot.item));
                    }
                    else {
                        // not empty.
                        ++expectedCount;
                        ++expectedUsed;
                        Debug.Assert(slot.HashValue != 0);
                        Debug.Assert(GetHashValues(slot.item, out initialBucket, out skip) == slot.HashValue);
                        if (initialBucket != i)
                            Debug.Assert(table[initialBucket].Collision);
                    }
                }
            }

            Debug.Assert(expectedCount == count);
            Debug.Assert(expectedUsed == usedSlots);
        }

#endif //DEBUG

    }
}