C# - 哈希表

本文关键字：哈希表 | 更新日期: 2023-09-12 17:39:32

SortedList<TKey, TValue> 和 SortedList 是集合类，可以存储基于关联的键排序的键值对 IComparer 实现。 例如，如果键是基元类型，则按键的升序排序。

C# 支持泛型和非泛型SortedList。 建议使用泛型SortedList<TKey, TValue>，因为它比非泛型SortedList执行得更快、更不容易出错。

排序列表特征

• SortedList<TKey, TValue> 是按键排序的键值对数组。
• 在添加元素后立即对其进行排序。根据 IComparer<T>按升序对基元类型键和对象键进行排序。
• 属于System.Collection.Generic命名空间。
• 键必须是唯一的，不能为空。
• 值可以为 null 或重复。
• 可以通过在索引器中传递关联的键来访问值mySortedList[key]
• 包含类型为 KeyValuePair
• 它使用的内存比SortedDictionary.
• 排序后检索数据的速度更快，而SortedDictionary<TKey, TValue>插入和删除键值对的速度更快。

创建排序列表

以下示例演示如何创建泛型SortedList<TKey, TValue>，并在其中添加键值对。

//SortedList of int keys, string values 
SortedList<int, string> numberNames = new SortedList<int, string>();
numberNames.Add(3, "Three");
numberNames.Add(1, "One");
numberNames.Add(2, "Two");
numberNames.Add(4, null);
numberNames.Add(10, "Ten");
numberNames.Add(5, "Five");
//The following will throw exceptions
//numberNames.Add("Three", 3); //Compile-time error: key must be int type
//numberNames.Add(1, "One"); //Run-time exception: duplicate key
//numberNames.Add(null, "Five");//Run-time exception: key cannot be null

在上面的示例中，通过指定要存储的键和值的类型来创建通用SortedList<TKey, TValue>对象。 SortedList<int, string>将存储 int 类型的键和字符串类型的值。

Add() 方法用于在SortedList中添加单个键值对。 密钥不能为空或重复。如果找到，它将引发运行时异常。如果类型可为空，则值可以是重复的和 null。

使用集合初始值设定项语法在实例化时初始化具有多个键值对的SortedList，如下所示。

//Creating a SortedList of string keys, string values 
//using collection-initializer syntax
SortedList<string,string> cities = new SortedList<string,string>()
                                    {
                                        {"London", "UK"},
                                        {"New York", "USA"},
                                        { "Mumbai", "India"},
                                        {"Johannesburg", "South Africa"}
                                    };

添加键值对后，SortedList将按键的升序重新排列键值对。 下面的示例使用 foreach 循环显示所有键和值。

SortedList<int,string> numberNames = new SortedList<int,string>()
                                    {
                                        {3, "Three"},
                                        {5, "Five"},
                                        {1, "One"}
                                    };
Console.WriteLine("---Initial key-values--");
foreach(KeyValuePair<int, string> kvp in numberNames)
    Console.WriteLine("key: {0}, value: {1}", kvp.Key , kvp.Value );
numberNames.Add(6, "Six");
numberNames.Add(2, "Two");
numberNames.Add(4, "Four");
Console.WriteLine("---After adding new key-values--");
foreach(var kvp in numberNames)
    Console.WriteLine("key: {0}, value: {1}", kvp.Key , kvp.Value );

输出：

访问排序列表

在索引器sortedList[key]中指定键，以获取或设置SortedList中的值。

SortedList<int,string> numberNames = new SortedList<int,string>()
                                    {
                                        {3, "Three"},
                                        {1, "One"},
                                        {2, "Two"}
                                    };
Console.WriteLine(numberNames[1]); //output: One
Console.WriteLine(numberNames[2]); //output: Two
Console.WriteLine(numberNames[3]); //output: Three
//Console.WriteLine(numberNames[10]); //run-time KeyNotFoundException
numberNames[2] = "TWO"; //updates value
numberNames[4] = "Four"; //adds a new key-value if a key does not exists

上面，numberNames[10]将抛出一个KeyNotFoundException，因为排序列表中不存在指定的键10。 若要防止此异常，请使用ContainsKey()或TryGetValue()方法，如下所示。

SortedList<int, string> numberNames = new SortedList<int,string>()
                                    {
                                        {3, "Three"},
                                        {1, "One"},
                                        {2, "Two"}
                                    };
if(numberNames.ContainsKey(4)){
    numberNames[4] = "four";
}
int result;
if(numberNames.TryGetValue(4, out result))
    Console.WriteLine("Key: {0}, Value: {1}", 4, result); 

输出：

如果要使用 for 循环迭代SortedList，请使用 Keys 和 Values 属性。

SortedList<int, string> numberNames = new SortedList<int,string>()
                                    {
                                        {3, "Three"},
                                        {1, "One"},
                                        {2, "Two"}
                                    };
for (int i = 0; i < numberNames.Count; i++)
{
    Console.WriteLine("key: {0}, value: {1}", numberNames.Keys[i], numberNames.Values[i]);
}

输出：

从排序列表中删除元素

使用 Remove(key) 和 RemoveAt(index) 方法从SortedList中删除键值对。

SortedList<int,string> numberNames = new SortedList<int,string>()
                                    {
                                        {3, "Three"},
                                        {1, "One"},
                                        {2, "Two"},
                                        {5, "Five"},
                                        {4, "Four"}
                                    };
    
numberNames.Remove(1);//removes key 1 pair
numberNames.Remove(10);//removes key 1 pair, no error if not exists
numberNames.RemoveAt(0);//removes key-value pair from index 0 
//numberNames.RemoveAt(10);//run-time exception: ArgumentOutOfRangeException
foreach(var kvp in numberNames)
	Console.WriteLine("key: {0}, value: {1}", kvp.Key , kvp.Value );

输出：

排序列表类层次结构

下图说明了SortedList层次结构。