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 );

输出:

---Initial key-values--
key: 1, value: One
key: 3, value: Three
key: 5, value: Five
---After adding new key-values--
key: 1, value: One
key: 2, value: Two
key: 3, value: Three
key: 4, value: Four
key: 5, value: Five
key: 6, value: Six

访问排序列表

在索引器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); 

输出:

Key:4, Value: Four

如果要使用 for 循环迭代SortedList,请使用 KeysValues 属性。

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]);
}

输出:

key: 1, value: One
key: 2, value: Two
key: 3, value: Three

从排序列表中删除元素

使用 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 );

输出:

key: 3, value: Three
key: 4, value: Four
key: 5, value: Five

排序列表类层次结构

下图说明了SortedList层次结构。