简介

数组（Array）是由相同类型的元素的集合所组成的数据结构。数组采用一块连续的内存空间来存储数据，利用数组下标索引可以随机存取对应的元素。数组元素的类型除了int、float、double和char等基本类型，还可以是类、枚举和结构体等复杂类型。借助数组可以实现线性表的顺序存储结构（即顺序表）。

在C#中，数组属于引用类型，数组变量本身是一个引用类型变量。**为了更好地学习后续的数据结构和算法，先介绍下C#中的变量类型。**C#变量类型分为值类型和引用类型，值类型包括基本类型（int、float、double、bool和char等类型）、结构体和枚举，引用类型包括数组、字符串、类、对象、接口和委托。

值类型变量直接存储变量的值，并将其存储在堆栈（Stack）中。引用类型变量实际的值则存放在托管堆（Heap）中（通过new关键字创建的实例变量的值都是存放在堆中），引用类型变量本身存储的是变量值在堆中存储的内存地址。但如果值类型嵌套进引用类型，即值类型作为引用类型的成员变量，则此时的值类型将作为引用类型的一部分存放在托管堆中。而引用类型即使嵌套进值类型，依然也是存放在托管堆中。

值类型由C#系统本身负责内存空间的分配和释放，当程序超过变量作用域范围后，就自动释放变量在栈中的内存空间。而引用类型由CLR中GC（Garbage Collector）负责内存空间的分配和释放，当对象不再使用或为null时，GC将会释放其在托管堆中的内存空间。栈的存储空间小，访问速度快；而堆的存储空间大，访问速度慢。

在C#中，所有的变量类型（值类型和引用类型）都间接或直接继承自System.Object类型，System.Object类型本身是引用类型。值类型继承自System.ValueType，而System.ValueType又继承自System.Object类型。System.ValueType重写了System.Object类型的Equals方法，用来比较两个变量的值是否相等。而引用类型几乎直接继承自System.Object类型，其Equals方法用来比较两个对象的引用地址是否相等。

值类型默认值为0，引用类型默认值为null。值类型转换为引用类型称为”装箱”，引用类型转换为值类型称为“拆箱”。由于值类型和引用类型之间的转换涉及到数据复制和类型转换，这些操作比较耗费性能，因此尽量避免频繁的"装箱"和"拆箱"操作。“装箱"和"拆箱"操作如下：

1
2
3
4
5
6
7
8

int i = 1; // 值类型
object o = new object(); // 引用类型

// 装箱
o = i; // 隐式转换

// 拆箱
i = (int)o; // 强制类型转换

经过上面的介绍，相信对C#中的值类型和引用类型有了一定的理解。在下边的数组拓展中，我会讲到动态数组和泛型列表的区别和联系。

优点

数组可以根据下标索引随机存取（访问）对应的元素。

缺点

由于数组采用一块连续的内存空间，因此增加或删除数组中的元素会导致内存中其他元素位置跟着移动，这会产生额外的性能消耗。此外，数组声明时必须指定数组长度大小，如果实际用到的数组长度小于声明时指定的长度，会产生内存碎片，造成内存空间的浪费。

如果大于声明时指定的数组长度，会造成内存空间不够用，只能新建一个更大的数组，因为数组不支持动态地增加或减少数组大小。正因为如此，数组中没有直接增加或删除数组元素的函数，需要我们自己去写。

应用场景

当我们需要经常访问数组元素，而不需要频繁改动数组大小（即知道实际所用数组的大小）时，可以使用数组。

基本操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

using System;

namespace ArrayExample
{
    class Client
    {
        // 增加数组元素
        public static T[] AddElement<T>(T[] oldArray, params T[] elements)
        {
            int oldLen = oldArray.Length;
            int eleLen = elements.Length;
            int newLen = oldLen + eleLen;
            T[] newArray = new T[newLen];

            //for (int i = 0; i < oldLen; i++)
            //{
            //    newArray[i] = oldArray[i];
            //}
            Array.Copy(oldArray, newArray, oldLen);

            //for (int i = 0; i < eleLen; i++)
            //{
            //    newArray[oldLen+i] = elements[i];
            //}
            elements.CopyTo(newArray, oldLen);

            return newArray;
        }

        public static void Main(string[] args)
        {
            // 初始化数组方式一
            //int[] numbers = new int[5];
          
            // 初始化数组方式二
            //int[] numbers2 = new int[5] { 1, 2, 3, 4, 5 };
          
            // 初始化数组方式三
            int[] numbers = { 1, 2, 3, 4, 5 };

            // 访问数组元素并修改元素值
            numbers[0] = 1;

            // 获取数组长度
            Console.WriteLine(numbers.Length);

            // 增加数组元素
            numbers = AddElement<int>(numbers, 6, 7, 8);
            foreach (int i in numbers)
            {
                Console.WriteLine(i);
            }
        }
    }
}

// 输出结果：512345678

拓展

多维数组

多维数组是数组的数组，最常用的多维数组是二维数组。多维数组中的每一个元素都是数组，直到最内层数组为止，最内层数组就是一个普通的一维数组。以二维数组为例，可以把二维数组看做是一个矩阵，系统默认采用行优先存储。每一行就是一个一维数组，多个一维数组组成二维数组。

但要注意C#中的二维数组和C/C++、JAVA不同，C#中二维数组只能访问矩阵中的单个值，无法访问每一行或者每一列对应的数组。C/C++和JAVA中的二维数组在C#里称为交错数组，即可以访问每一行的一维数组。下面是二维数组在C#中的实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

using System;

namespace ArrayExample2
{
    class Client
    {
        public static void Main1(string[] args)
        {
            // C#二维数组
            // 初始化方式一
            //int[,] numbers = new int[3, 4];

            // 初始化方式二
            //int[,] numbers = new int[3, 4]
            //{
            //    { 1, 2, 3, 4 },
            //    { 5, 6, 7, 8 },
            //    { 9, 10, 11, 12 }
            //};

            // 初始化方式三
            int[,] numbers =
            {
                { 1, 2, 3, 4 },
                { 5, 6, 7, 8 },
                { 9, 10, 11, 12 }
            };
            int num = numbers[1, 2];
            //int[] nums = numbers[1]; 报错

            // C#交错数组
            // 初始化方式一，初始化时不能指定列数
            //int[][] numbers2 = new int[3][];

            // 初始化方式二
            //int[][] numbers2 = new int[3][]
            //{
            //    new int[1],
            //    new int[2],
            //    new int[3]
            //};

            // 不支持直接初始化赋值
            //int[][] numbers2 = {
            //    { 1 },
            //    { 1, 2 },
            //    { 1, 2, 3 }
            //};

            // 初始化方式三
            int[][] numbers2 = {
                new int[1] { 1 },
                new int[2] { 1, 2 },
                new int[3] { 1, 2, 3 }
            };
            // 支持直接访问行数组
            int[] nums2 = numbers2[1];
        }
    }
}
动态数组

由于数组（静态数组）不能动态修改大小，因此动态数组应运而生。C#中的动态数组由ArrayList类型表示，位于System.Collections命名空间下，因此使用时必须引入System.Collections命名空间。ArrayList可以动态地增加或删除数组元素，因此使用时不需要指定其数组长度大小。此外，由于ArrayList元素类型是System.Object类型，因此动态数组中的元素可以是任何类型的元素。因为，在C#中，所有变量或对象都是Object类型。

任何事物都有两面性。由于动态数组所有元素类型均采用Object类型，没有明确指定元素具体的类型，这会带来类型安全问题。因为使用动态数组时，很可能造成类型不匹配的问题。此外，如果动态数组实际的元素类型是值类型，那么存储元素时动态数组内部产生“装箱”操作，索引取值时就会产生"拆箱"操作，这样频繁的"装箱"和"拆箱"操会带来额外的性能消耗。下面是动态数组的基本操作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

using System;
using System.Collections;

namespace ArrayExample3
{
    class Client
    {
        public static void Main(string[] args)
        {
            // 声明并初始化
            ArrayList al = new ArrayList();

            // 添加元素
            al.Add(1);
            al.Add("test");

            // 删除元素
            al.Remove(1);

            // 索引取值
            al[0] = "test2";

            // 查找元素
            Console.WriteLine(al.Contains("test2")); // 输出True

            // 获取数组长度
            Console.WriteLine(al.Count); // 输出1
        }
    }
}
泛型列表

为了解决动态数组中频繁的"装箱"和"拆箱"操作，C#提供了泛型列表List来代替动态数组。**为了更好地理解泛型列表List，我们先介绍下什么是泛型。**泛型是指通过数据类型的替代参数来预先编写类或方法，等到类或方法实际使用时才去指定实际的数据类型。

换言之，泛型允许我们延迟绑定类或方法具体的数据类型，等到程序使用时才去指定具体的数据类型。这样可以最大程序的重用代码，保证数据的类型安全以及避免频繁的"装箱"和"拆箱"操作带来的性能开销问题。所以在实际开发中，不建议使用动态数组，而是用泛型列表代替。

泛型List位于System.Collections.Generic命名空间内，因此在使用时必须引用对应的命名空间。泛型List即结合了数组中利用下标索引随机存取元素的优点，又支持像动态数组一样动态地增加和删除数据元素，同时还避免了动态数组因频繁的"装箱"和"拆箱"操作带来的性能开销问题。下面是泛型List的基本操作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

using System;
using System.Collections.Generic;

namespace ArrayExample4
{
    class Client
    {
        public static void Main(string[] args)
        {
            // 声明并初始化
            List<int> numbers = new List<int>();

            // 添加元素
            numbers.Add(1);
            numbers.Add(2);

            // 删除元素
            numbers.Remove(2);

            // 索引取值
            Console.WriteLine(numbers[0]); // 输出1

        }
    }
}
哈希表

哈希表（Hash Table，又称散列表），是根据关键码值（Key-Value键值对）直接访问元素的数据结构。即通过把一个关键码值映射到表中的一个位置来访问记录（元素），以加快查找速度。这个映射函数称为哈希函数或散列函数，存放记录的数组称为哈希表或散列表，表中的这个位置称为哈希地址。

哈希表中一个元素关键字值为key，则通过哈希函数f(key)处理后可以得到这个元素在表中的地址，从而直接通过地址访问该元素，这样可以加快该元素的访问速度。理想情况下，哈希表访问某个元素的时间复杂度为O(1)。但如果通过不同的关键码值得到了相同的表中元素地址，就会造成地址冲突，这称为哈希冲突。因为我们希望元素和表中地址是一一对应的，这样就不会在查找时对同一表中地址的多个元素进行值比较的情况，从而降低查找效率。

因此，哈希表在查找元素过程中，关键码的比较次数至关重要。产生的哈希冲突越少，关键码的比较次数就比较少，查找效率就高。反之，产生的哈希冲突越多，关键码就需要与同一地址的其他元素多次比较值，这样时间复杂度就会提高，查找效率变低。

哈希表最常见的例子是用学号来检索学生的成绩。对于学生来说，学号是唯一的，所以不存在哈希冲突。但如果以学生出生年月日的后三位为键，就会产生哈希冲突。因为会存在同年同月同日生的学生，这时就比较学生的实际信息了。但我们可以通过哈希函数，在构造哈希表时，将学生的出生日期映射成不同的键，降低冲突的发生率，从而提高查找效率。

因此要想构造一个成功的哈希表，就必须降低或减少哈希冲突的发生率，因为冲突无法避免。而降低哈希冲突发生率的关键在于哈希函数，如果哈希函数选取不好就会经常发生哈希冲突，这会非常影响哈希表的性能。常用的哈希函数有直接寻址法、数字分析法、平方取中法和随机数法等，处理冲突的方法有开放寻址法和再散列法等。

哈希表实际上是一个一维数组，如果考虑到哈希冲突，也可视为二维数组。哈希表通过关键值映射为地址来存储元素，哈希地址很难像数组地址一样均匀地连续分布，必然会出现空缺的地址。如果哈希函数选取不当，哈希地址之间间隔增大，会让哈希表变成一个稀疏数组。因此，存储相同数量的元素，哈希表所需内存空间比数组更大。

但与数组相比，哈希表的效率更高。哈希表增删改查的时间复杂度都是O(1)，而数组无法直接增加和删除元素，修改（修改之前要先查找）和查找元素的时间复杂度是O(n)。因为哈希表可以直接通过关键字的映射地址进行直接查找，而数组只能通过索引下标从前往后开始遍历查找，所以哈希表的效率更高。即哈希表是用空间换时间。

在C#中，哈希表是通过System.Collections命名空间下的HashTable类型来实现。但由于HashTable的元素类型为Object类型，使用时会造成频繁的”装箱“和”拆箱“操作，造成额外性能开销。因此C#推出了字典Dictionary<Tkey, TValue>，C#字典位于System.Collections.Generic命名空间下。

字典Dictionary<Tkey, TValue>是HashTable的泛型实现，效率更高。此外，字典是类型安全的，而HashTable会出现类型不匹配的情况。因此，在实际开发中，优先推荐使用字典Dictionary<Tkey, TValue>。C#字典中的键是唯一的，键和值都可以为任意类型，但键不能为空引用类型null。下面是C#字典的基本操作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

using System;
using System.Collections.Generic;

namespace HashTable
{
    class Client
    {
        public static void Main(string[] args)
        {
            // 新建一个学生生日信息字典，键为生日，值为姓名。
            Dictionary<string, string> students = new Dictionary<string, string>();

            // 添加学生生日信息
            students.Add("2月1日", "张三");
            students.Add("2月2日", "李四");
            students.Add("2月3日", "王五");
            students.Add("2月4日", "刘六");

            // 删除生日为2月2日的学生信息
            students.Remove("2月2日");

            // 直接访问并修改生日为“2月1日”的学生姓名
            students["2月1日"] = "王麻子";
            
            // 返回一个字符数组表示所有的生日，输出所有学生的生日
            foreach (var key in students.Keys)
            {
                Console.WriteLine(key); // 2月1日、2月3日、2月4日
            }

            // 返回一个字符数组表示所有的姓名，输出所有的学生姓名
            foreach (var value in students.Values)
            {
                Console.WriteLine(value);  // 王麻子、王五、刘六
            }

            // 该字典是否包含生日为”2月2日”的学生信息
            Console.WriteLine(students.ContainsKey("2月2日")); // False
            // 该字典是否包含姓名为”张三”的学生信息
            Console.WriteLine(students.ContainsValue("张三")); // False

            // 清空字典的所有数据
            students.Clear();

            // 获取字典的长度
            Console.WriteLine(students.Count); // 0
        }
    }
}