C#算法之散列表

散列表简介

散列表是一种常用的数据结构，用于存储键值对。它通过计算键的哈希值，将键值对存储在一个数组中，从而实现高效的数据访问。在C#中，我们可以使用内置的Dictionary类来实现散列表。

散列函数

散列函数是将键映射到数组索引的函数。它的目标是尽可能地将不同的键映射到不同的索引，从而减少冲突。C#中的Dictionary类使用默认的散列函数，但我们也可以自定义散列函数。

散列函数示例

public int GetHash(string key)
{
    int hash = 0;
    for (int i = 0; i < key.Length; i++)
    {
        hash += (int)key[i];
    }
    return hash % capacity;
}

上述代码示例中，我们将键中每个字符的ASCII值相加，然后对散列表的容量取模，得到对应的索引。

解决冲突

由于散列函数的映射并不是一对一的，所以可能会出现不同的键映射到相同的索引的情况，这就是冲突。为了解决冲突，常用的方法有链地址法和开放寻址法。

链地址法

链地址法是将相同索引的键值对存储在一个链表中。当发生冲突时，我们将新的键值对添加到链表的末尾。在访问散列表中的键值对时，我们首先计算键的哈希值，然后在对应索引的链表中查找。

链地址法示例

public class HashTable
{
    private LinkedList<KeyValuePair<string, int>>[] table;
    public HashTable(int capacity)
    {
        table = new LinkedList<KeyValuePair<string, int>>[capacity];
    }
    public void Add(string key, int value)
    {
        int index = GetHash(key);
        if (table[index] == null)
        {
            table[index] = new LinkedList<KeyValuePair<string, int>>();
        }
        table[index].AddLast(new KeyValuePair<string, int>(key, value));
    }
    public int Get(string key)
    {
        int index = GetHash(key);
        if (table[index] == null)
        {
            throw new KeyNotFoundException();
        }
        foreach (var pair in table[index])
        {
            if (pair.Key == key)
            {
                return pair.Value;
            }
        }
        throw new KeyNotFoundException();
    }
}

上述代码示例中，我们使用LinkedList来实现链表，并将每个索引的键值对存储在对应的链表中。

开放寻址法

开放寻址法是将相同索引的键值对存储在散列表的其他位置。当发生冲突时，我们根据一定的规则，寻找下一个可用的位置。在访问散列表中的键值对时，我们根据规则依次查找，直到找到对应的键值对或者遇到空位置。

开放寻址法示例

public class HashTable
{
    private KeyValuePair<string, int>[] table;
    public HashTable(int capacity)
    {
        table = new KeyValuePair<string, int>[capacity];
    }
    public void Add(string key, int value)
    {
        int index = GetHash(key);
        while (table[index].Key != null)
        {
            index = (index + 1) % capacity;
        }
        table[index] = new KeyValuePair<string, int>(key, value);
    }
    public int Get(string key)
    {
        int index = GetHash(key);
        while (table[index].Key != null)
        {
            if (table[index].Key == key)
            {
                return table[index].Value;
            }
            index = (index + 1) % capacity;
        }
        throw new KeyNotFoundException();
    }
}

上述代码示例中，我们使用一个数组来存储键值对。当发生冲突时，我们通过线性探测的方式，依次查找下一个可用的位置。

总结

散列表是一种常用的数据结构，它可以高效地存储和访问键值对。使用散列函数将键映射到数组索引，可以减少冲突的发生。当发生冲突时，我们可以使用链地址法或开放寻址法来解决。

在C#中，我们可以使用内置的Dictionary类来实现散列表。如果需要自定义散列函数或解决冲突的方式，我们可以根据需求实现自己的散列表类。