国外虚拟物品交易网站,杭州软件建设,如何看一个站点是不是有wordpress,html5设计在 C# 中#xff0c;DictionaryTKey, TValue 是一个基于哈希表#xff08;Hash Table#xff09;实现的键值对集合。它提供了高效的插入、删除和查找操作#xff0c;平均时间复杂度接近 O(1)。下面是 Dictionary 的核心实现原理#xff1a; 1. Dictionary 的核心数…在 C# 中DictionaryTKey, TValue 是一个基于哈希表Hash Table实现的键值对集合。它提供了高效的插入、删除和查找操作平均时间复杂度接近 O(1)。下面是 Dictionary 的核心实现原理 1. Dictionary 的核心数据结构
C# 的 DictionaryTKey, TValue 主要由以下几个部分组成
数组buckets存储哈希桶Bucket的索引。数组entries存储键值对哈希表中的实际数据。哈希函数GetHashCode将键映射到哈希桶。碰撞解决拉链法采用 链地址法Chaining with Linked List。负载因子Load Factor决定何时扩容默认为 0.75。
数据结构
private int[] buckets; // 哈希桶数组存储 entry 的索引
private Entry[] entries; // 存储实际的键值对
private int count; // 当前存储的元素个数
private int freeList; // 指向空闲 entry删除后形成的空位
private int freeCount; // 空闲 entry 的数量private struct Entry
{public int hashCode; // 计算出的哈希值public int next; // 指向下一个冲突的元素-1 表示无冲突public TKey key; // 键public TValue value; // 值
} 2. Dictionary 的主要操作
1添加元素
当调用 dictionary.Add(key, value) 时Dictionary 执行以下步骤 计算哈希值调用 key.GetHashCode() 计算哈希值 hashCode。 计算索引对哈希值取模index hashCode % buckets.Length确定应该存放的桶。 检查冲突 如果该桶为空则直接存储。此时count字段记录字典中元素个数。令bucket[index] count然后将内容存储到Entry[count]中随后count。如果发生哈希冲突则使用链地址法存储即将 entries 中的 next 指向旧的 Entry形成链表。 扩容如有必要 如果 count capacity * 0.75则触发扩容通常是 2 倍扩容。 public void Add(TKey key, TValue value) { int hashCode key.GetHashCode() 0x7FFFFFFF; // 计算哈希值int index hashCode % buckets.Length; // 计算桶的索引// 处理哈希冲突如果桶为空直接插入if (buckets[index] -1){buckets[index] count; // 将当前元素插入桶数组entries[count] new Entry { hashCode hashCode, key key, value value, next -1 };count;}else{// 发生哈希冲突遍历链表int current buckets[index];while (current 0){Entry entry entries[current];if (entry.hashCode hashCode EqualityComparerTKey.Default.Equals(entry.key, key)){entries[current].value value; // 如果找到相同的键更新值return;}current entry.next; // 查找下一个节点}// 如果没有找到插入新的元素到链表头部entries[count] new Entry { hashCode hashCode, key key, value value, next buckets[index] };buckets[index] count; // 更新桶的索引count;}// 扩容检查if (count buckets.Length * 0.75){Resize(); // 扩容}}
2查找元素
当调用 dictionary[key] 或 TryGetValue(key, out value) 时 计算哈希值hashCode key.GetHashCode()。 计算索引index hashCode % buckets.Length。 遍历链表 如果桶中第一个元素匹配则直接返回。如果有哈希冲突next ! -1遍历 entries 直到找到 key。 3删除元素
当调用 dictionary.Remove(key) 时
计算哈希值找到哈希桶索引。遍历链表找到匹配的 Entry。更新链表指针 如果是第一个元素则更新 buckets 指向 next 位置。如果在链表中则调整 next 以跳过该元素。 回收 entry 将 entry 记录到 freeList方便后续使用。
4扩容机制
当 count capacity * 0.75 时Dictionary 会进行 2 倍扩容
创建更大的 buckets 和 entries 数组通常是 2 倍大小。重新计算索引重新分配 buckets 和 entries。重新插入所有 Entry因为 hashCode % newCapacity 结果不同所有键值对需要重新计算索引。 3. Dictionary 的碰撞处理
C# 的 Dictionary 采用 链地址法 处理哈希冲突
entries 形成链表每个 Entry 记录 next 指向同一个桶的下一个 Entry。遍历链表时检查 hashCode 和 key 是否匹配。
示例假设 buckets 长度为 5并插入以下键值对
dict.Add(1, Apple);
dict.Add(6, Banana); // 6 % 5 1与 1 发生哈希冲突
哈希桶结构如下
buckets: [ -1, 0 - 1, -1, -1, -1 ] // index 1 存储链表 (1 → 6)
entries: 0: { hashCode1, key1, valueApple, next1 }1: { hashCode6, key6, valueBanana, next-1 }
查找 dict[6] 时
计算 index 6 % 5 1。遍历链表 entries[0] (key1) 不匹配继续遍历 next1。entries[1] (key6) 匹配返回 Banana。 4. Dictionary 的优缺点
优点
查找快平均时间复杂度 O(1)。插入删除快平均时间复杂度 O(1)。自动扩容避免手动管理大小。
缺点
内存占用大数组 链表可能浪费额外空间。哈希碰撞影响性能冲突越多查找速度降至 O(n)。不保证顺序Dictionary 无序存储键值对。 5. Dictionary 的替代方案
数据结构适用场景SortedDictionaryTKey, TValue需要按键排序基于 红黑树O(log n)SortedListTKey, TValue适用于小数据量查找快但插入慢HashSetT仅存储键不存储值ConcurrentDictionaryTKey, TValue多线程安全字典
