.NET 数据结构：哈希表

哈希表 (Hash Table)，也称为散列表，是一种以查找为主要目的的数据结构，数据之间并没有逻辑关系。

哈希表通过建立键值对 (Key-Value Pair)来存储数据。其核心优势在于，无论数据量多大，通过 Key 查找 Value 的时间复杂度理想情况下为 O(1)。

现实中，身份证号到个人信息的映射就是典型的哈希表模型：每一张唯一的身份证号（Key）都对应一份档案（Value）。

示例

假设有三个人，我们希望通过唯一的 Id 查找信息。

如果使用列表 (List)，为了找到目标，我们必须逐个遍历：

var group = new List<Person> {
                new Person("001", "AAA"), 
                new Person("002", "BBB"), 
                new Person("003", "CCC")};
	
Person target = null;
// 时间复杂度 O(n)
foreach(var person in group)
{
    if(person.Id == "003")
    {
        target = person;
        Console.WriteLine($"Found: {target.Name}");
        break;
    }
}

public class Person(string id, string name)
{
	public string Id {get; set;} = id;
	public string Name {get; set;} = name;
}

当数据量达到百万级时，这种线性查找效率极低。

如果使用哈希表（在 C# 中是 System.Collections.Generic.Dictionary）：

var group = new Dictionary<string, Person>();
group.Add("001", new Person("AAA"));
group.Add("002", new Person("BBB"));
group.Add("003", new Person("CCC"));

// 查找操作：时间复杂度 O(1)
if (group.TryGetValue("003", out Person? person))
{
    Console.WriteLine($"Found: {person.Name}");
}

public class Person(string name)
{
	public string Name {get; set;} = name;
}

代码示意图

使用 Dictionary 后，查找操作变得极其迅速，不再依赖数据量的大小。

常用操作

Dictionary<TKey, TValue> 的增删改查操作通常都是 O(1)。

// 初始化
var group = new Dictionary<string, Person>();

// 增：添加键值对
group.Add("001", new Person("AAA"));
// 或使用索引器（如果键存在则覆盖，不存在则添加）
group["002"] = new Person("BBB");

// 删：删除键为 002 的条目
group.Remove("002");

// 查：获取键为 001 的值
// 注意：直接使用索引器 group["xxx"] 如果键不存在会抛出异常
// 推荐使用 TryGetValue
if (group.TryGetValue("001", out var person))
{
    Console.WriteLine(person.Name);
}

遍历哈希表：

// 1. 遍历键值对 (KeyValuePair) - 推荐
foreach(var kvp in group)
{
    Console.WriteLine($"Key: {kvp.Key}, Value: {kvp.Value.Name}");
}

// 2. 仅遍历键
foreach(var key in group.Keys)
{
    // ...
}

// 3. 仅遍历值
foreach(var val in group.Values)
{
    // ...
}

实现原理

哈希表通常基于数组实现。核心问题是：如何将一个字符串（如 “003”）转化为数组的整数索引？这需要用到哈希函数 (Hash Function)。

简化流程如下：

计算哈希值：调用 key.GetHashCode() 得到一个整数。
映射索引：将哈希值对数组长度取模 (Modulo)，得到合法的数组索引。
存取数据：在数组的该位置存放或读取数据。

为了演示，我们假设 Key 本身就是整数，且不考虑哈希冲突：

/*  int: string 键值对 */
class Pair(int key, string value)
{
	public int Key { get; init; } = key;
	public string Value { get; init; } = value;
}

/* 简易哈希表实现 */
class SimpleHashTable {
	const int Capacity = 1000;
    // 使用数组作为底层存储
    Pair[] buckets = new Pair[Capacity];

	// 很简单的哈希函数：直接取模
	int GetBucketIndex(int key) => key % Capacity;

	public void Add(int key, string value) 
    {
        int index = GetBucketIndex(key);
        buckets[index] = new Pair(key, value);
    }

	public void Remove(int key) 
    {
        int index = GetBucketIndex(key);
        buckets[index] = null;
    }

	public string? GetValue(int key) 
    {
        int index = GetBucketIndex(key);
        return buckets[index]?.Value;
    }
}

哈希冲突 (Hash Collision)

在上面的简易实现中，我们不仅简化了哈希函数，还忽略了一个致命问题：不同的 Key 可能计算出相同的索引。

例如，对于长度 1000 的数组：

Key 114 -> 114 % 1000 = 114
Key 100114 -> 100114 % 1000 = 114

这两个 Key 都试图占据索引 114，后一个数据会覆盖前一个，这就是哈希冲突。

即使是最优秀的哈希算法也无法完全避免冲突（鸽巢原理）。为了解决这个问题，我们需要更精细的冲突解决策略（如链式地址法），而不仅仅是简单的覆盖。