hashtable.cs

来自「没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没」· CS 代码 · 共 1,511 行 · 第 1/3 页

/*
 * Hashtable.cs - Implementation of the
 *			"System.Collections.Hashtable" class.
 *
 * Copyright (C) 2001, 2003  Southern Storm Software, Pty Ltd.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

namespace System.Collections
{

using System;
using System.Private;
using System.Runtime.CompilerServices;
using System.Runtime.Serialization;

public class Hashtable : ICloneable, ICollection, IDictionary, IEnumerable
#if CONFIG_SERIALIZATION
	, ISerializable, IDeserializationCallback
#endif
{

	// Contents of a hash bucket.
	private struct HashBucket
	{
		public Object key;
		public Object value;

	}; // struct HashBucket

	// Internal state.
	private IHashCodeProvider hcp__;
	private IComparer         comparer__;
	private int				  capacity;
	private int				  capacityLimit;
	private int				  num;
	private float			  loadFactor;
	private HashBucket[]	  table;
	private int				  generation;
#if CONFIG_SERIALIZATION
	private SerializationInfo info;
#endif

	// Place holder for a removed object.
	private static readonly Object removed = new Object();
	// Table of the first 400 prime numbers.
	private static readonly int[] primes = {
		2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
		53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
		109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
		173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
		233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
		293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359,
		367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431,
		433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491,
		499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571,
		577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
		643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709,
		719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787,
		797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859,
		863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
		947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019,
		1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087,
		1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153,
		1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229,
		1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297,
		1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381,
		1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453,
		1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523,
		1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597,
		1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663,
		1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741,
		1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823,
		1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901,
		1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993,
		1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063,
		2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131,
		2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221,
		2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293,
		2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371,
		2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437,
		2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539,
		2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621,
		2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689,
		2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741};

	// Constructors.
	public Hashtable()
			{
				hcp__ = null;
				comparer__ = null;
				capacity = 0;
				capacityLimit = 0;
				num = 0;
				try
				{
					loadFactor = 1.0f;
				}
				catch(NotImplementedException)
				{
					// The runtime engine does not support floating point,
					// but we still need hash tables when no FP.
				}
				table = null;
				generation = 0;
			}
	public Hashtable(int capacity)
			{
				if(capacity < 0)
				{
					throw new ArgumentOutOfRangeException
						("capacity", _("ArgRange_NonNegative"));
				}
				hcp__ = null;
				comparer__ = null;
				this.capacity = capacity;
				capacityLimit = capacity;
				num = 0;
				try
				{
					loadFactor = 1.0f;
				}
				catch(NotImplementedException)
				{
					// The runtime engine does not support floating point,
					// but we still need hash tables when no FP.
				}
				if(capacity != 0)
				{
					table = new HashBucket [capacity];
				}
				else
				{
					table = null;
				}
				generation = 0;
			}
	public Hashtable(IHashCodeProvider hcp, IComparer comparer)
			{
				hcp__ = hcp;
				comparer__ = comparer;
				capacity = 0;
				capacityLimit = 0;
				num = 0;
				try
				{
					loadFactor = 1.0f;
				}
				catch(NotImplementedException)
				{
					// The runtime engine does not support floating point,
					// but we still need hash tables when no FP.
				}
				table = null;
				generation = 0;
			}
	public Hashtable(int capacity, IHashCodeProvider hcp, IComparer comparer)
			{
				if(capacity < 0)
				{
					throw new ArgumentOutOfRangeException
						("capacity", _("ArgRange_NonNegative"));
				}
				hcp__ = hcp;
				comparer__ = comparer;
				this.capacity = capacity;
				capacityLimit = capacity;
				num = 0;
				try
				{
					loadFactor = 1.0f;
				}
				catch(NotImplementedException)
				{
					// The runtime engine does not support floating point,
					// but we still need hash tables when no FP.
				}
				if(capacity != 0)
				{
					table = new HashBucket [capacity];
				}
				else
				{
					table = null;
				}
				generation = 0;
			}
	public Hashtable(IDictionary d)
			{
				if(d == null)
				{
					throw new ArgumentNullException("d");
				}
				hcp__ = null;
				comparer__ = null;
				capacity = d.Count;
				capacityLimit = capacity;
				num = 0;
				try
				{
					loadFactor = 1.0f;
				}
				catch(NotImplementedException)
				{
					// The runtime engine does not support floating point,
					// but we still need hash tables when no FP.
				}
				if(capacity != 0)
				{
					table = new HashBucket [capacity];
				}
				else
				{
					table = null;
				}
				generation = 0;
				AddDictionaryContents(d);
			}
	public Hashtable(IDictionary d, IHashCodeProvider hcp, IComparer comparer)
			{
				if(d == null)
				{
					throw new ArgumentNullException("d");
				}
				hcp__ = hcp;
				comparer__ = comparer;
				capacity = d.Count;
				capacityLimit = capacity;
				num = 0;
				try
				{
					loadFactor = 1.0f;
				}
				catch(NotImplementedException)
				{
					// The runtime engine does not support floating point,
					// but we still need hash tables when no FP.
				}
				if(capacity != 0)
				{
					table = new HashBucket [capacity];
				}
				else
				{
					table = null;
				}
				generation = 0;
				AddDictionaryContents(d);
			}

#if !ECMA_COMPAT

	// Non-ECMA constructors.
	public Hashtable(int capacity, float loadFactor)
			{
				if(capacity < 0)
				{
					throw new ArgumentOutOfRangeException
						("capacity", _("ArgRange_NonNegative"));
				}
				if(loadFactor >= 0.1f && loadFactor <= 1.0f)
				{
					hcp__ = null;
					comparer__ = null;
					this.capacity = capacity;
					capacityLimit = (int)(capacity * loadFactor);
					num = 0;
					this.loadFactor = loadFactor;
					if(capacity != 0)
					{
						table = new HashBucket [capacity];
					}
					else
					{
						table = null;
					}
					generation = 0;
				}
				else
				{
					throw new ArgumentOutOfRangeException
						("loadFactor", _("ArgRange_HashLoadFactor"));
				}
			}
	public Hashtable(int capacity, float loadFactor,
					 IHashCodeProvider hcp, IComparer comparer)
			{
				if(capacity < 0)
				{
					throw new ArgumentOutOfRangeException
						("capacity", _("ArgRange_NonNegative"));
				}
				if(loadFactor >= 0.1f && loadFactor <= 1.0f)
				{
					hcp__ = hcp;
					comparer__ = comparer;
					this.capacity = capacity;
					capacityLimit = (int)(capacity * loadFactor);
					num = 0;
					this.loadFactor = loadFactor;
					if(capacity != 0)
					{
						table = new HashBucket [capacity];
					}
					else
					{
						table = null;
					}
					generation = 0;
				}
				else
				{
					throw new ArgumentOutOfRangeException
						("loadFactor", _("ArgRange_HashLoadFactor"));
				}
			}
	public Hashtable(IDictionary d, float loadFactor)
			{
				if(d == null)
				{
					throw new ArgumentNullException("d");
				}
				if(loadFactor >= 0.1f && loadFactor <= 1.0f)
				{
					hcp__ = null;
					comparer__ = null;
					capacity = d.Count;
					capacityLimit = (int)(capacity * loadFactor);
					num = 0;
					this.loadFactor = loadFactor;
					if(capacity != 0)
					{
						table = new HashBucket [capacity];
					}
					else
					{
						table = null;
					}
					generation = 0;
					AddDictionaryContents(d);
				}
				else
				{
					throw new ArgumentOutOfRangeException
						("loadFactor", _("ArgRange_HashLoadFactor"));
				}
			}
	public Hashtable(IDictionary d, float loadFactor,
					 IHashCodeProvider hcp, IComparer comparer)
			{
				if(d == null)
				{
					throw new ArgumentNullException("d");
				}
				if(loadFactor >= 0.1f && loadFactor <= 1.0f)
				{
					hcp__ = hcp;
					comparer__ = comparer;
					capacity = d.Count;
					capacityLimit = (int)(capacity * loadFactor);
					num = 0;
					this.loadFactor = loadFactor;
					if(capacity != 0)
					{
						table = new HashBucket [capacity];
					}
					else
					{
						table = null;
					}
					generation = 0;
					AddDictionaryContents(d);
				}
				else
				{
					throw new ArgumentOutOfRangeException
						("loadFactor", _("ArgRange_HashLoadFactor"));
				}
			}

#endif // !ECMA_COMPAT

#if CONFIG_SERIALIZATION

	protected Hashtable(SerializationInfo info, StreamingContext context)
			{
				// Save the serialization information for the later call
				// to "OnDeserialization".
				this.info = info;
			}

#endif // CONFIG_SERIALIZATION
	// Add the contents of a dictionary to this hash table.
	private void AddDictionaryContents(IDictionary d)
			{
				IDictionaryEnumerator enumerator = d.GetEnumerator();
				while(enumerator.MoveNext())
				{
					Add(enumerator.Key, enumerator.Value);
				}
			}

	// Add a hash entry to the table directly, with no error checking.
	// This assumes that there is at least one spare bucket available.
	private void AddDirect(Object key, Object value)
			{
				int hash = GetHash(key);
				hash = (int)(((uint)hash) % ((uint)capacity));
				for(;;)
				{
					if(table[hash].key == null || table[hash].key == removed)
					{
						// We've found an empty slot, so add the entry.
						table[hash].key = key;
						table[hash].value = value;
						break;
					}
					hash = (hash + 1) % capacity;
				}
				++num;
			}

	// Expand the hash table and add a new entry.
	private void ExpandAndAdd(Object key, Object value)
			{
				HashBucket[] orig;
				int origSize;
				int newCapacity;

				// Copy the original table.
				orig = table;
				origSize = capacity;

				// Expand the size of the hash table.
				if(capacity == 0)
				{
					newCapacity = 2;
				}
				else
				{
					newCapacity = capacity * 2;
					if(newCapacity <= primes[primes.Length - 1])
					{
						// Search for the next value in the "primes" table.
						int left, right, middle;
						left = 0;
						right = primes.Length - 1;
						while(left <= right)
						{
							middle = (left + right) / 2;
							if(newCapacity < primes[middle])
							{
								right = middle - 1;
							}
							else if(newCapacity > primes[middle])
							{
								left = middle + 1;
							}
							else
							{
								right = middle;
								break;
							}
						}
						newCapacity = primes[right];
					}
					else
					{
						// We've run out of primes, so make the number odd
						// and assume that the result is close enough to
						// prime that it will be useful for our purposes.
						++newCapacity;
					}
				}
				table = new HashBucket [newCapacity];
				capacity = newCapacity;
				num = 0;

				// Determine the new capacity limit.
				try
				{
					capacityLimit = (int)(capacity * loadFactor);
				}
				catch(NotImplementedException)
				{
					// The runtime engine does not support floating point,
					// so assume a load factor of 1.
					capacityLimit = capacity;
				}

				// Copy the original entries to the new table.