哈希表是一种集合类型，它以提供快速插入、查找和删除操作的方式存储键值对。哈希表通常用于，但当然不限于，关联数组和数据缓存的实现。例如，网站可以使用以下模式跟踪哈希表中的活动会话:
HashTable<string, SessionState> _sessionStateCache;
...
public SessionState LoadSession(string sessionId)
{
SessionState state;
if (!_sessionStateCache.TryGetValue(sessionId, out state))
{
state = new SessionState(sessionId);
_sessionStateCache[sessionId] = state;
}
return state;
}在本例中，哈希表用于存储会话状态，会话标识作为键，会话状态作为值。当在哈希表中寻找会话状态时，如果没有找到，则添加新的会话状态对象，并且在任一情况下，返回与会话标识匹配的状态。
以这种方式使用哈希表允许快速插入和检索(平均)会话状态，而不管有多少活动会话同时发生。
关键和价值
为了理解哈希表是如何工作的，让我们看一下向哈希表中添加一个项目，然后找到该项目的概念概述。
我们将要存储的对象(以 JSON 格式显示)代表公司的一名员工。
{
"Name":"Robert Horvick",
"Hire Date":"11/2/2010",
"Department":"Engineering"
}回想一下，要在哈希表中存储一个项目，我们需要有一个键和值。我们的目标是价值，所以现在我们需要选择一把钥匙。理想情况下，我们会选择能够唯一代表存储对象的东西；但是，在这种情况下，我们将使用员工姓名(Robert Horvick)来演示密钥可以是任何数据类型。在实践中，Employee类将包含一个唯一的标识，用于区分多个同名员工，该标识将是我们使用的密钥。
后备数组
为了快速访问项目，哈希表由数组( O (1)随机访问)而不是列表( O ( n )随机访问)支持。在任何给定时刻，数组都有两个有趣的属性:
- 容量
- 填充因数
容量是数组可能容纳的项目数。例如，以下空数组的容量为 10:
图 12:容量为 10 的数组
填充因子是已填充(使用中)的数组项目的百分比。例如，以下数组的填充因子为 0.40 (40%):
图 13:容量为 10、填充系数为 0.40 (40%)的数组。
请注意，数组是以明显随机的方式填充的。虽然数组包含四个项，但这些项并不存储在索引 0–3 中，而是存储在索引 1、2、4 和 6 中。这是因为存储项目的索引是由哈希函数确定的，在我们的示例中，哈希函数采用关键组件“Robert Horvick”，并返回一个整数哈希码。然后使用模运算将这个哈希码调整到数组的大小。例如:
int index = hash(“Robert Horvick”) % Capacity;前面的代码示例调用名为hash的函数，该函数接受一个字符串并返回一个整数。该整数是所提供字符串的哈希代码。
在我们进一步讨论之前，让我们花点时间考虑一下哈希代码有多重要。那个。NET 框架要求所有类都从基类型System.Object派生。此类型提供了几个方法的基本实现，其中一个方法具有以下签名:
int GetHashCode()将此方法放在公共基类型上可以确保每种类型都能够生成哈希代码，因此能够存储在需要哈希代码的集合类型中。
那么，问题是任何给定对象实例的哈希代码应该是什么？一个像“Robert Horvick "这样的值的System.String如何产生一个适合用作哈希码的整数值？
该函数需要有两个属性。首先，哈希算法必须稳定。这意味着给定相同的输入，将总是返回相同的哈希值。第二，哈希算法必须统一。这意味着哈希函数以在整个输出范围内均匀分布的方式将输入值映射到输出值。
这里有一个(不好的)例子:
public int LengthHashCode(string input)
{
return input.Length;
}此哈希代码方法返回字符串长度作为哈希代码。这种方法是稳定的。字符串“罗伯特·霍维克”将始终返回相同的哈希代码(14)。但是这种方法没有均匀分布。如果我们有一百万个唯一的字符串，每个字符串都有 50 个字符长，会发生什么？他们每个人都有一个 50 的哈希码。这不是一个统一的分布，因此不是一个适合字符串的哈希算法。
这里有一个稍微好一点(不好)的例子:
private int AdditiveHash(string input)
{
int currentHashValue = 0;
foreach (char c in input)
{
unchecked
{
currentHashValue += (int)c;
}
}
return currentHashValue;
}这个哈希函数只比基于长度的哈希具有稍微好一点的一致性。虽然加法哈希确实允许相同长度的字符串产生不同的哈希，但这也意味着“罗伯特·霍维克”和“霍维克·罗伯特”将产生相同的哈希值。
现在我们知道了一个糟糕的哈希算法是什么样子，让我们来看看一个明显更好的字符串哈希算法。这种算法最早是由丹·伯恩斯坦(http://www.cse.yorku.ca/~oz/hash.html)报告的，它使用一种算法，对于要哈希的值(c)中的每个字符，将当前哈希值设置为hash = (hash * 33) + c。
// Hashing function first reported by Dan Bernstein.
// http://www.cse.yorku.ca/~oz/hash.html
private static int Djb2(string input)
{
int hash = 5381;
foreach (int c in input.ToCharArray())
{
unchecked
{
/* hash * 33 + c */
hash = ((hash << 5) + hash) + c;
}
}
return hash;
}只是为了好玩，让我们再看一个哈希算法。这种哈希算法被称为折叠哈希，它不逐个字符地处理字符串，而是以 4 字节块的形式处理。让我们看看 ASCII 字符串“罗伯特·霍维克”将如何被哈希。首先，字符串被分成 4 字节的块。由于我们使用的是 ASCII 编码，每个字符都是一个块，因此段是:
[Robe]
[rt H]
[orvi]
[ck]这些字符中的每一个都由一个 1 字节的数字 ASCII 码表示。这些字节是:
[0x52 0x6F 0x62 0x65]
[0x72 0x74 0x20 0x48]
[0x6F 0x72 0x76 0x69]
[0x63 0x6B]然后，这些字节被填充到 32 位的值中(由于它们是如何被加载到结果整数中的，所以字节在这里被反转。参见样例代码中的GetNextBytes方法。)
0x65626F52
0x48207472
0x6976726F
0x00006B63这些值相加，允许溢出发生，我们得到最终的哈希值:0x16F9C196。
// Treats each four characters as an integer, so
// "aaaabbbb" hashes differently than "bbbbaaaa".
private static int FoldingHash(string input)
{
int hashValue = 0;
int startIndex = 0;
int currentFourBytes;
do
{
currentFourBytes = GetNextBytes(startIndex, input);
unchecked
{
hashValue += currentFourBytes;
}
startIndex += 4;
} while (currentFourBytes != 0);
return hashValue;
}
// Gets the next four bytes of the string converted to an
// integer. If there are not enough characters, 0 is used.
private static int GetNextBytes(int startIndex, string str)
{
int currentFourBytes = 0;
currentFourBytes += GetByte(str, startIndex);
currentFourBytes += GetByte(str, startIndex + 1) << 8;
currentFourBytes += GetByte(str, startIndex + 2) << 16;
currentFourBytes += GetByte(str, startIndex + 3) << 24;
return currentFourBytes;
}
private static int GetByte(string str, int index)
{
if (index < str.Length)
{
return (int)str[index];
}
return 0;
}最后两个哈希函数在概念上很简单，实现起来也很简单。但是它们有多好呢？我创建了一个简单的测试，通过将 GUIDs 转换为字符串来生成一百万个唯一值。然后，我对这一百万个唯一的字符串进行哈希运算，并记录哈希冲突的次数，当两个不同的值具有相同的哈希值时，就会发生哈希冲突。结果是:
DJB2 唯一值:99.88282%
折叠唯一值:97.75495%
如您所见，两种哈希算法都相对均匀地分布哈希值，DJB2 的分布略好于折叠哈希。
正如我们在上一节中所看到的，一个好的哈希算法会将哈希值均匀地分布在哈希值的可能范围内，但是我们也看到即使是一个好的算法也可能会产生冲突。此外，我们知道哈希值最终将使用模运算符适合后备数组大小，因此当哈希值适合后备数组大小时，即使是完美的哈希算法也可能最终会发生冲突。
下一个开放插槽
下一个打开的插槽方法在后备数组中向前移动，搜索下一个打开的插槽，并将项目放在该位置。例如，在下图中，值 V1 和 V2 具有相同的哈希值。由于 V1 已经在哈希表中，V2 前进到哈希表中的下一个空位。
图 14:V1 和 V2 哈希值的冲突
在查找过程中，如果找到 V2 的值，就会找到 V1 的指数。V1 和 V2 的价值将被比较，他们不会匹配。由于正在使用下一个时隙冲突处理，哈希表需要检查下一个索引，以确定冲突是否向前移动。在下一个槽中，找到 V2 的值，并将其与所寻求的值 V2 进行比较。因为它们是相同的，所以找到了合适的后备数组索引。
我们可以看到这个方法有简单的插入和搜索规则，但不幸的是有复杂的移除逻辑。
想想如果 V1 被移除会发生什么:V1 曾经的第三指数现在是空的。如果搜索 V2，预期的索引将为空，因此将假设 V2 不在哈希表中，即使它在哈希表中。这意味着在删除过程中，需要检查与要删除的项目相邻的所有值，以查看它们是否需要移动。
这种冲突处理算法的一个缺点是删除很复杂，但是整个哈希表存储在一个连续的后备数组中。这可能会使它在内存资源有限或内存中的数据局部性极其重要的系统上具有吸引力。
链表链
处理冲突的另一种方法是让哈希表后备数组中的每个索引成为节点的链表。发生冲突时，新值会添加到链接列表中。例如:
图 15: V2 被添加到 V1 之后的链表中
对于支持联合类型的语言(例如 C++)，数组索引通常包含一个值，该值可以是没有任何冲突时的单个值，也可以是链表。下一节中的示例代码将始终创建一个链接列表，但只有在索引处添加项时才会这样做。
HashTableNodePair类是存储在哈希表数组中的键值对。不像。NET Framework KeyValuePair类，HashTableNodePair不允许在构造后分配键成员，因为该值用于确定哈希表中存储键-值对的索引。
/// <summary>
/// A node in the hash table array.
/// </summary>
/// <typeparam name="TKey">The type of the key of the key/value pair.</typeparam>
/// <typeparam name="TValue">The type of the value of the key/value pair.</typeparam>
public class HashTableNodePair<TKey, TValue>
{
/// <summary>
/// Constructs a key/value pair for storage in the hash table.
/// </summary>
/// <param name="key">The key of the key/value pair.</param>
/// <param name="value">The value of the key/value pair.</param>
public HashTableNodePair(TKey key, TValue value)
{
Key = key;
Value = value;
}
/// <summary>
/// The key. The key cannot be changed because it would affect the
/// indexing in the hash table.
/// </summary>
public TKey Key { get; private set; }
/// <summary>
/// The value.
/// </summary>
public TValue Value { get; set; }
}HashTableArrayNode类表示哈希表中的单个节点。它对用于处理冲突的链表执行惰性初始化。它提供了添加、删除、更新和检索存储在节点中的键值对的方法。此外，它还提供键和值的枚举，以支持哈希表的枚举要求。
internal class HashTableArrayNode<TKey, TValue>
{
// This list contains the actual data in the hash table. It chains together
// data collisions.
LinkedList<HashTableNodePair<TKey, TValue>> _items;
public void Add(TKey key, TValue value);
public void Update(TKey key, TValue value);
public bool TryGetValue(TKey key, out TValue value);
public bool Remove(TKey key);
public void Clear();
public IEnumerable<TValue> Values { get; }
public IEnumerable<TKey> Keys { get; }
public IEnumerable<HashTableNodePair<TKey, TValue>> Items { get; }
}| 行为 | 将键值对添加到节点，在添加第一个值时延迟初始化链表。如果要添加的键已经存在，则会引发异常。 | | 表演 | O (1) |
/// <summary>
/// Adds the key/value pair to the node. If the key already exists in the
/// list, an ArgumentException will be thrown.
/// </summary>
/// <param name="key">The key of the item being added.</param>
/// <param name="value">The value of the item being added.</param>
public void Add(TKey key, TValue value)
{
// Lazy init the linked list.
if (_items == null)
{
_items = new LinkedList<HashTableNodePair<TKey, TValue>>();
}
else
{
// Multiple items might collide and exist in this list, but each
// key should only be in the list once.
foreach (HashTableNodePair<TKey, TValue> pair in _items)
{
if (pair.Key.Equals(key))
{
throw new ArgumentException("The collection already contains the key");
}
}
}
// If we made it this far, add the item.
_items.AddFirst(new HashTableNodePair<TKey, TValue>(key, value));
}| 行为 | 查找具有匹配键的键-值对，并更新关联的值。如果找不到密钥，将引发异常。 | | 表演 | O ( n )，其中 n 为链表中的数值个数。一般来说，这将是一个 O (1)算法，因为不会有冲突。 |
/// <summary>
/// Updates the value of the existing key/value pair in the list.
/// If the key does not exist in the list, an ArgumentException
/// will be thrown.
/// </summary>
/// <param name="key">The key of the item being updated.</param>
/// <param name="value">The updated value.</param>
public void Update(TKey key, TValue value)
{
bool updated = false;
if (_items != null)
{
// Check each item in the list for the specified key.
foreach (HashTableNodePair<TKey, TValue> pair in _items)
{
if (pair.Key.Equals(key))
{
// Update the value.
pair.Value = value;
updated = true;
break;
}
}
}
if (!updated)
{
throw new ArgumentException("The collection does not contain the key.");
}
}| 行为 | 将输出参数值设置为与提供的键相关联的值，如果找到该键，则返回true。否则返回false。 |
| 表演 | O ( n )，其中 n 为链表中的数值个数。一般来说，这将是一个 O (1)算法，因为不会有冲突。 |
/// <summary>
/// Finds and returns the value for the specified key.
/// </summary>
/// <param name="key">The key whose value is sought.</param>
/// <param name="value">The value associated with the specified key.</param>
/// <returns>True if the value was found, false otherwise.</returns>
public bool TryGetValue(TKey key, out TValue value)
{
value = default(TValue);
bool found = false;
if (_items != null)
{
foreach (HashTableNodePair<TKey, TValue> pair in _items)
{
if (pair.Key.Equals(key))
{
value = pair.Value;
found = true;
break;
}
}
}
return found;
}| 行为 | 查找具有匹配键的键-值对，并从链表中删除键-值对。如果对被移除，则返回值true。否则返回false。 |
| 表演 | O ( n )，其中 n 为链表中的数值个数。一般来说，这将是一个 O (1)算法，因为不会有冲突。 |
/// <summary>
/// Removes the item from the list whose key matches
/// the specified key.
/// </summary>
/// <param name="key">The key of the item to remove.</param>
/// <returns>True if the item is removed; false otherwise.</returns>
public bool Remove(TKey key)
{
bool removed = false;
if (_items != null)
{
LinkedListNode<HashTableNodePair<TKey, TValue>> current = _items.First;
while (current != null)
{
if (current.Value.Key.Equals(key))
{
_items.Remove(current);
removed = true;
break;
}
current = current.Next;
}
}
return removed;
}| 行为 | 从链接列表中删除所有项目。注意:这个实现只是清除链表；然而，也可以将_items引用分配给null并让垃圾收集器回收内存。对Add的下一次调用将分配一个新的链表。 |
| 表演 | O (1) |
/// <summary>
/// Removes all the items from the list.
/// </summary>
public void Clear()
{
if (_items != null)
{
_items.Clear();
}
}键
| 行为 | 返回枚举链表中键的枚举数。 | | 表演 | O (1) |
/// <summary>
/// Returns an enumerator for all of the keys in the list.
/// </summary>
public IEnumerable<TKey> Keys
{
get
{
if (_items != null)
{
foreach (HashTableNodePair<TKey, TValue> node in _items)
{
yield return node.Key;
}
}
}
}价值观念
| 行为 | 返回枚举链表中值的枚举数。 | | 表演 | O (1) |
/// <summary>
/// Returns an enumerator for all of the values in the list.
/// </summary>
public IEnumerable<TValue> Values
{
get
{
if (_items != null)
{
foreach (HashTableNodePair<TKey, TValue> node in _items)
{
yield return node.Value;
}
}
}
}项目
| 行为 | 返回枚举链表中键值对的枚举数。 | | 表演 | O (1) |
/// <summary>
/// Returns an enumerator for all the key/value pairs in the list.
/// </summary>
public IEnumerable<HashTableNodePair<TKey, TValue>> Items
{
get
{
if (_items != null)
{
foreach (HashTableNodePair<TKey, TValue> node in _items)
{
yield return node;
}
}
}
}HashTableArray类是HashTable类的后备数组。它处理寻找合适的后备数组索引的工作，并遵从HashTableArrayNode类。
class HashTableArray<TKey, TValue>
{
HashTableArrayNode<TKey, TValue>[] _array;
/// <summary>
/// Constructs a new hash table array with the specified capacity.
/// </summary>
/// <param name="capacity">The capacity of the array.</param>
public HashTableArray(int capacity)
{
_array = new HashTableArrayNode<TKey, TValue>[capacity];
}
public void Add(TKey key, TValue value);
public void Update(TKey key, TValue value);
public bool Remove(TKey key);
public bool TryGetValue(TKey key, out TValue value);
public int Capacity { get; }
public void Clear();
public IEnumerable<TValue> Values { get; }
public IEnumerable<TKey> Keys { get; }
public IEnumerable<HashTableNodePair<TKey, TValue>> Items { get; }
// Maps a key to the array index based on the hash code.
private int GetIndex(TKey key);
}| 行为 | 将键值对添加到节点数组。如果该键已经存在于节点数组中，将引发异常。 | | 表演 | O (1) |
该方法的主要目的是延迟分配HashTableArrayNode实例，以便只有实际保存值的哈希表条目才分配一个实例。
/// <summary>
/// Adds the key/value pair to the node. If the key already exists in the
/// node array, an ArgumentException will be thrown.
/// </summary>
/// <param name="key">The key of the item being added.</param>
/// <param name="value">The value of the item being added.</param>
public void Add(TKey key, TValue value)
{
int index = GetIndex(key);
HashTableArrayNode<TKey, TValue> nodes = _array[index];
if (nodes == null)
{
nodes = new HashTableArrayNode<TKey, TValue>();
_array[index] = nodes;
}
nodes.Add(key, value);
}| 行为 | 更新键值对的值，键值对的键与提供的键匹配。如果该键不存在，则会引发异常。 |
| 表演 | O ( n )，其中 n 是存储在HashTableNodeArray实例中的项目数。这通常是一个 O (1)操作。 |
/// <summary>
/// Updates the value of the existing key/value pair in the node array.
/// If the key does not exist in the array, an ArgumentException
/// will be thrown.
/// </summary>
/// <param name="key">The key of the item being updated.</param>
/// <param name="value">The updated value.</param>
public void Update(TKey key, TValue value)
{
HashTableArrayNode<TKey, TValue> nodes = _array[GetIndex(key)];
if (nodes == null)
{
throw new ArgumentException("The key does not exist in the hash table", "key");
}
nodes.Update(key, value);
}| 行为 | 查找与提供的键关联的值，并将 out 参数设置为该值(否则为包含类型的默认值)。如果找到值，返回true。否则返回false。 |
| 表演 | O ( n )，其中 n 是存储在HashTableNodeArray实例中的项目数。这通常是一个 O (1)操作。 |
/// <summary>
/// Finds and returns the value for the specified key.
/// </summary>
/// <param name="key">The key whose value is sought.</param>
/// <param name="value">The value associated with the specified key.</param>
/// <returns>True if the value is found; false otherwise.</returns>
public bool TryGetValue(TKey key, out TValue value)
{
HashTableArrayNode<TKey, TValue> nodes = _array[GetIndex(key)];
if (nodes != null)
{
return nodes.TryGetValue(key, out value);
}
value = default(TValue);
return false;
}| 行为 | 删除其键与提供的键匹配的键-值对。如果找到并取出钥匙，返回true。否则返回false。 |
| 表演 | O( n ，其中 n 是存储在HashTableNodeArray实例中的项目数。这通常是一个 O (1)操作。 |
/// <summary>
/// Removes the item from the node array whose key matches
/// the specified key.
/// </summary>
/// <param name="key">The key of the item to remove.</param>
/// <returns>True if the item was removed; false otherwise.</returns>
public bool Remove(TKey key)
{
HashTableArrayNode<TKey, TValue> nodes = _array[GetIndex(key)];
if (nodes != null)
{
return nodes.Remove(key);
}
return false;
}| 行为 | 返回键哈希到的后备数组中的索引。 | | 表演 | O (1) |
// Maps a key to the array index based on the hash code.
private int GetIndex(TKey key)
{
return Math.Abs(key.GetHashCode() % Capacity);
}| 行为 | 从哈希表数组中移除所有项。 | | 表演 | O ( n )，其中 n 是表中包含数据的节点数。 |
/// <summary>
/// Removes every item from the hash table array.
/// </summary>
public void Clear()
{
foreach (HashTableArrayNode<TKey, TValue> node in _array.Where(node => node != null))
{
node.Clear();
}
}| 行为 | 返回哈希表数组的容量。注意:一定要记住哈希表数组的容量与哈希表的项目数不同。 | | 表演 | O (1) |
/// <summary>
/// The capacity of the hash table array.
/// </summary>
public int Capacity
{
get
{
return _array.Length;
}
}键
| 行为 | 返回哈希表数组中包含的所有键的枚举数。 | | 表演 | O ( n )，其中 n 是哈希表数组及其包含的所有节点中包含的项目总数。 |
/// <summary>
/// Returns an enumerator for all of the keys in the node array.
/// </summary>
public IEnumerable<TKey> Keys
{
get
{
foreach (HashTableArrayNode<TKey, TValue> node in
_array.Where(node => node != null))
{
foreach (TKey key in node.Keys)
{
yield return key;
}
}
}
}价值观念
| 行为 | 返回哈希表数组中包含的所有值的枚举数。 | | 表演 | O ( n )，其中 n 是哈希表数组及其包含的所有节点中包含的项目总数。 |
/// <summary>
/// Returns an enumerator for all of the values in the node array.
/// </summary>
public IEnumerable<TValue> Values
{
get
{
foreach (HashTableArrayNode<TKey, TValue> node in
_array.Where(node => node != null))
{
foreach (TValue value in node.Values)
{
yield return value;
}
}
}
}项目
| 行为 | 返回哈希表数组中包含的所有键值对的枚举数。 | | 表演 | O ( n )，其中 n 是哈希表数组及其包含的所有节点中包含的项目总数。 |
/// <summary>
/// Returns an enumerator for all of the Items in the node array.
/// </summary>
public IEnumerable<HashTableNodePair<TKey, TValue>> Items
{
get
{
foreach (HashTableArrayNode<TKey, TValue> node in
_array.Where(node => node != null))
{
foreach (HashTableNodePair<TKey, TValue> pair in node.Items)
{
yield return pair;
}
}
}
} public class HashTable<TKey, TValue>
{
// If the array exceeds this fill percentage, it will grow.
const double _fillFactor = 0.75;
// The maximum number of items to store before growing.
// This is just a cached value of the fill factor calculation.
int _maxItemsAtCurrentSize;
// The number of items in the hash table.
int _count;
// The array where the items are stored.
HashTableArray<TKey, TValue> _array;
/// <summary>
/// Constructs a hash table with the default capacity.
/// </summary>
public HashTable()
: this(1000)
{
}
/// <summary>
/// Constructs a hash table with the specified capacity.
/// </summary>
public HashTable(int initialCapacity)
{
if (initialCapacity < 1)
{
throw new ArgumentOutOfRangeException("initialCapacity");
}
_array = new HashTableArray<TKey, TValue>(initialCapacity);
// When the count exceeds this value, the next Add will cause the
// array to grow.
_maxItemsAtCurrentSize = (int)(initialCapacity * _fillFactor) + 1;
}
public void Add(TKey key, TValue value);
public bool Remove(TKey key);
public TValue this[TKey key] { get; set; }
public bool TryGetValue(TKey key, out TValue value);
public bool ContainsKey(TKey key);
public bool ContainsValue(TValue value);
public IEnumerable<TKey> Keys { get; }
public IEnumerable<TValue> Values { get; }
public void Clear();
public int Count { get; }
}| 行为 | 向哈希表中添加键-值对，如果表中已经存在该键，将引发异常。 | | 表演 | O (1)平均。 O ( n + 1)出现阵增长时。 |
这个方法在HashTableArray类上提供了一个抽象层次来处理当添加操作超过最大容量时后备数组的增长。当扩展后备数组时，它使用填充因子来确定给定当前后备数组容量的最大项目数。
/// <summary>
/// Adds the key/value pair to the hash table. If the key already exists in the
/// hash table, an ArgumentException will be thrown.
/// </summary>
/// <param name="key">The key of the item being added.</param>
/// <param name="value">The value of the item being added.</param>
public void Add(TKey key, TValue value)
{
// If we are at capacity, the array needs to grow.
if (_count >= _maxItemsAtCurrentSize)
{
// Allocate a larger array
HashTableArray<TKey, TValue> largerArray = new HashTableArray<TKey, TValue>(_array.Capacity * 2);
// and re-add each item to the new array.
foreach (HashTableNodePair<TKey, TValue> node in _array.Items)
{
largerArray.Add(node.Key, node.Value);
}
// The larger array is now the hash table storage.
_array = largerArray;
// Update the new max items cached value.
_maxItemsAtCurrentSize = (int)(_array.Capacity * _fillFactor) + 1;
}
_array.Add(key, value);
_count++;
}| 行为 | 用提供的键检索值。如果哈希表中不存在该键，则会引发异常。 | | 表演 | O (1)平均； O ( n )最坏的情况。 |
/// <summary>
/// Gets and sets the value with the specified key. ArgumentException is
/// thrown if the key does not already exist in the hash table.
/// </summary>
/// <param name="key">The key of the value to retrieve.</param>
/// <returns>The value associated with the specified key.</returns>
public TValue this[TKey key]
{
get
{
TValue value;
if (!_array.TryGetValue(key, out value))
{
throw new ArgumentException("key");
}
return value;
}
set
{
_array.Update(key, value);
}
}| 行为 | 查找与提供的键关联的值，并将 out 参数设置为该值(否则为包含类型的默认值)。如果找到值，返回true。否则返回false。 |
| 表演 | O (1)平均； O ( n )最坏的情况。 |
/// <summary>
/// Finds and returns the value for the specified key.
/// </summary>
/// <param name="key">The key whose value is sought.</param>
/// <param name="value">The value associated with the specified key.</param>
/// <returns>True if the value is found; false otherwise.</returns>
public bool TryGetValue(TKey key, out TValue value)
{
return _array.TryGetValue(key, out value);
}| 行为 | 删除其键与提供的键匹配的键-值对。如果找到并取出钥匙，返回true。否则返回false。 |
| 表演 | O (1)平均； O ( n )最坏的情况。 |
/// <summary>
/// Removes the item from the hash table whose key matches
/// the specified key.
/// </summary>
/// <param name="key">The key of the item to remove.</param>
/// <returns>True if the item is removed; false otherwise.</returns>
public bool Remove(TKey key)
{
bool removed = _array.Remove(key);
if (removed)
{
_count--;
}
return removed;
}| 行为 | 如果哈希表中存在指定的键，则返回true。否则返回false。 |
| 表演 | O (1)平均； O ( n )最坏的情况。 |
/// <summary>
/// Returns a Boolean indicating whether the hash table contains the specified key.
/// </summary>
/// <param name="key">The key whose existence is being tested.</param>
/// <returns>True if the value exists in the hash table; false otherwise.</returns>
public bool ContainsKey(TKey key)
{
TValue value;
return _array.TryGetValue(key, out value);
}| 行为 | 如果哈希表包含与提供的值匹配的值，则返回true。 |
| 表演 | O ( n ) |
| 
| 注意:重要的是要记住，虽然哈希表不包含冲突的键，但它可能包含相同值的多个实例。 |
/// <summary>
/// Returns a Boolean indicating whether the hash table contains the specified value.
/// </summary>
/// <param name="value">The value whose existence is being tested.</param>
/// <returns>True if the value exists in the hash table; false otherwise.</returns>
public bool ContainsValue(TValue value)
{
foreach (TValue foundValue in _array.Values)
{
if (value.Equals(foundValue))
{
return true;
}
}
return false;
}| 行为 | 从哈希表中移除所有项。 | | 表演 | O (1) |
/// <summary>
/// Removes all items from the hash table.
/// </summary>
public void Clear()
{
_array.Clear();
_count = 0;
}| 行为 | 返回哈希表中包含的项数。 | | 表演 | O (1) |
| | 注意:后备数组的容量和哈希表中存储的项目数不一样(填充因子小于 1 的永远不会一样)。 |
/// <summary>
/// The number of items currently in the hash table.
/// </summary>
public int Count
{
get
{
return _count;
}
}键
| 行为 | 返回哈希表中包含的所有键的枚举数。 | | 表演 | O ( n ) |
/// <summary>
/// Returns an enumerator for all of the keys in the hash table.
/// </summary>
public IEnumerable<TKey> Keys
{
get
{
foreach (TKey key in _array.Keys)
{
yield return key;
}
}
}价值观念
| 行为 | 返回哈希表中包含的所有值的枚举数。 | | 表演 | O ( n ) |
/// <summary>
/// Returns an enumerator for all of the values in the hash table.
/// </summary>
public IEnumerable<TValue> Values
{
get
{
foreach (TValue value in _array.Values)
{
yield return value;
}
}
}