当前位置：首页 > C# > 正文

C#哈希查找详解（哈希冲突解决方法全解析）

主机测评网
C#
2025-12-21
837

在C#编程中，哈希查找是一种非常高效的数据检索方式。它通过将键（key）映射为数组下标，从而实现接近O(1)的平均时间复杂度。然而，在实际使用过程中，不同的键可能会被映射到同一个位置，这就产生了哈希冲突。本文将详细讲解C#中常见的哈希冲突解决方法，即使是编程小白也能轻松理解。

什么是哈希冲突？

哈希冲突是指两个或多个不同的键通过哈希函数计算后得到相同的哈希值（即数组索引）。例如，假设我们有一个哈希表大小为10，键 "apple" 和 "orange" 经过哈希函数后都返回索引5，那么它们就发生了冲突。

C#哈希查找详解（哈希冲突解决方法全解析） C#哈希查找哈希冲突解决哈希表实现 C#数据结构第1张

C#中常见的哈希冲突解决方法

在C#开发中，主要有两种经典方法来解决哈希冲突：链地址法（拉链法）和开放地址法。下面我们分别介绍这两种方法，并附上清晰的代码示例。

1. 链地址法（Separate Chaining）

链地址法的核心思想是：每个哈希表的槽位不再只存储一个元素，而是存储一个链表（或其它集合），所有哈希到该位置的元素都存入这个链表中。

这是C#中 Dictionary<TKey, TValue> 类内部采用的一种优化策略（虽然底层更复杂，但原理类似）。

// 简化的链地址法哈希表示例using System;using System.Collections.Generic;class SimpleHashTable{    private const int Capacity = 10;    private List<KeyValuePair<string, string>>[] buckets;    public SimpleHashTable()    {        buckets = new List<KeyValuePair<string, string>>[Capacity];        for (int i = 0; i < Capacity; i++)        {            buckets[i] = new List<KeyValuePair<string, string>>();        }    }    private int GetHash(string key)    {        // 简单的哈希函数：取字符串ASCII码之和模容量        int hash = 0;        foreach (char c in key)        {            hash += c;        }        return hash % Capacity;    }    public void Add(string key, string value)    {        int index = GetHash(key);        var bucket = buckets[index];        // 检查是否已存在该键        for (int i = 0; i < bucket.Count; i++)        {            if (bucket[i].Key == key)            {                bucket[i] = new KeyValuePair<string, string>(key, value);                return;            }        }        // 不存在则添加        bucket.Add(new KeyValuePair<string, string>(key, value));    }    public string Get(string key)    {        int index = GetHash(key);        var bucket = buckets[index];        foreach (var pair in bucket)        {            if (pair.Key == key)            {                return pair.Value;            }        }        throw new KeyNotFoundException($"Key '{key}' not found.");    }}// 使用示例class Program{    static void Main()    {        var hashTable = new SimpleHashTable();        hashTable.Add("name", "Alice");        hashTable.Add("city", "Beijing");        Console.WriteLine(hashTable.Get("name")); // 输出: Alice    }}

2. 开放地址法（Open Addressing）

开放地址法的思想是：当发生冲突时，按照某种探测策略在哈希表中寻找下一个空闲位置来存放新元素。常见的探测策略包括线性探测、二次探测和双重哈希。

下面是一个使用线性探测的简单实现：

// 线性探测的开放地址法哈希表示例using System;class LinearProbingHashTable{    private const int Capacity = 10;    private string[] keys = new string[Capacity];    private string[] values = new string[Capacity];    private int GetHash(string key)    {        int hash = 0;        foreach (char c in key) hash += c;        return hash % Capacity;    }    public void Add(string key, string value)    {        int index = GetHash(key);        // 线性探测：如果当前位置被占用，就向后找        while (keys[index] != null)        {            if (keys[index] == key)            {                values[index] = value; // 更新值                return;            }            index = (index + 1) % Capacity; // 循环到开头        }        keys[index] = key;        values[index] = value;    }    public string Get(string key)    {        int index = GetHash(key);        while (keys[index] != null)        {            if (keys[index] == key)            {                return values[index];            }            index = (index + 1) % Capacity;            // 如果绕了一圈还没找到，说明不存在            if (index == GetHash(key)) break;        }        throw new KeyNotFoundException($"Key '{key}' not found.");    }}