第一节：数组和集合、散列表
第一节：数组和集合、散列表
数组就是有限个数据类型一样的元素安排放在一起，用了一个变量名，然后通过编号可以按照顺序访问指定位置的元素的一个有效集合。每个元素都有它指定的下标（索引），一般是下标是从0开始计算的。
我们常说的数组指定的是一维数组，当然也用多维数组但是不常使用。多维数组其实就是一维数组中的某个元素再次划分出来的数组。
1、数组的存储结构
一维数组的存储结构如下：
| num[n] | ||||
| num[1] | num[2] | num[3] | num[4] | num[n-1] |
其实，我们先要确定一个值，也就是数组的长度，然后系统会根据我们声明的数据类型开辟一些空间（这里的开辟空间是由你声明多大的类型决定的）。这时，这些空间就归这个变量所有了。一般在编程语言中，这些空间会默认对我们声明的数据类型赋值，比如整数值是0，布尔值是false，等等。
所以有以下几种情况：
1)只声明了指定的长度空间，但没有初始值（默认的初始值是0）。
| num[5] | ||||
| 0 | 0 | 0 | 0 | 0 |
| num[1] | num[2] | num[3] | num[4] | num[5] |
2)声明了指定的长度空间，初始化了部分值。
| num[5] | ||||
| 1 | 2 | 3 | 0 | 0 |
| num[1] | num[2] | num[3] | num[4] | num[5] |
3)声明了指定的长度空间，初始化了全部的值。
| num[5] | ||||
| 1 | 2 | 3 | 4 | 5 |
| num[1] | num[2] | num[3] | num[4] | num[5] |
2、数组在编程语言中的初始化操作
例子1：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace arry
{
class Program
{
static void Main(string[] args)
{
int[] num1 = new int[10];
int[] num2 = { 1, 2, 3, 4 };
int[] num3 = new int[3];
num3[0] = 1;
num3[1] = 2;
num3[2] = 3;
//num1输出的都是0，因为没有给元素赋值，使用的都是默认的元素值
Console.WriteLine("num1:{0}\n",num1[0]);
Console.WriteLine("num1:{0}\n", num1[1]);
//num2输出的是3，因为下标是从0开始算的
Console.WriteLine("num2:{0}\n", num2[2]);
//num3输出的是2，num3分别给元素赋值
Console.WriteLine("num3:{0}\n", num3[1]);
}
}
}
数组常用的另一种方式是按照顺序访问每一个值，使用编程语言中的for循环语句实现
例子2：
namespace for_arry
{
class Program
{
static void Main(string[] args)
{
int[] num = { 1, 2, 3, 4, 5, 6 };
for (int i = 0; i<num.Length;i++)
{
Console.WriteLine("i的数组分别是:{0}\n",i);
}
}
}
}
注意：num.Length是可以获取数组的长度，大家可以发现length后面没有括号，length是数组内置的属性。
3、看一下二维数组的存储结构：
二维数组和一维数组没有太大的区别，只不过需要提前确认第1维和第2维的长度。
第1维长度为3，每维的元素长度为4的数组。
多维数组在编程语言中的初始化及操作
namespace to_arry
{
class Program
{
static void Main(string[] args)
{
int[,] num = new int[,] { { 1,2,3 }, { 4,5,6 }, { 7,8,9 }};
int a = num[1, 0];
//num的值是4
Console.WriteLine("num is:{0}", a);
}
}
}
4、数组的特点
1）固定长度
2) 按照顺序访问
5、数组的适用场景
数组其实是一个非常简单的数据结构，用起来也比较简单。但是数组是所有的数据结构的基础，必须掌握好数组，才能更好地学习其他数据结构和算法。
由于数组的长度是固定的，所以在不会出现变化的业务上比较合适使用数组。
例子1:
在我们玩RPG或者ARPG等类似游戏中会有一排的快捷键的技能格，比如：F1~F9这样9个快捷键，我们每个人可以把自己习惯用的技能拖动到这个技能格上，这样就可以通过技能栏上的快捷键操控技能了。一般这样的设计技能栏的快捷键就是固定的个数。于是，在程序里就可以使用通过数组的方式来存储每个人的技能快捷键对应的技能。（当然肯定会通过一定的映射关系存储到数据库或者某个硬盘上）。
例子2：
制作优酷8+1，优酷8+1是什么，打开优酷首页，会看到最上面的1个大图、8个小图，这就是优酷的8+1。
这样我们可以设置一个数组固定的长度为9的数组，里面每个元素是一个对象，这些对象至少应该包含图片的地址和URL地址。
总结数组：我们应该已经很清晰的了解和认识了数组的缺点和优点，那就是我们之前提到的数组的固定长度和按照顺序访问。
6、数组的升级版：集合
数组的致命的缺点就是长度固定，那么我们一开始不确定长度，该怎么办呢？这时候我们要用到集合了，其实集合是基于数组实现的。在许多高级语言中，集合是对数组的一个拓展，我们在向里放入数据时，想放多少就可以放入多少，不用在意到底能放多少。
7、什么是集合
集合主要是可变长度的列表（也叫做动态数组）
集合有几种：
1）列表：一般是有序的集合，特点就是有顺序，比如：链表、队列、栈等，会在后续的章节学到。
2）集：一般是无序的集合，特点就是没有顺序并且数据不能重复，多数语言是使用散列表实现的，支持对集进行添加、删除、查找包含的操作。
3）多重集：也是无序的集合，特点就是没有顺序，但是数据可以重复，支持对集进行添加、删除、查找一个元素在集合中的个数等操作。多重集一般可以通过排序转换为列表。
4）关系数组：其实多数语言是使用散列表实现的，就是可以通过键(Key)获取到值(Value)，同样没有顺序。
5）树、图：同样是集合，在后续的章节学到。
8、集合的实现
arraylist 它是一个数组的列表，其实就是数组的拓展，或者说是可变长度的数组。
arraylist里有一个属性，这个属性是一个数组。另外还会有一个属性记录了存放了多少数据，这样我们再向其中放数据时，就会知道该向这个内部数组的哪个位置放数据了，但是这个数组也会有长度的限制，如果超出了这个限制该怎么办呢？当超出了限制，其内部会创建一个具有更长的长度的数组，然后把旧的数组的数据复制给新的数组里面，这样就可以继续存放数据了。
集合的流程图：
注意：在面向对象编程中一般将成员变量定为属性。
集合在编程语言中的初始化及操作
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
namespace list_arry
{
class Program
{
static void Main(string[] args)
{
//创建 ArrayList 数组
ArrayList array = new ArrayList();
//用Add 方法往 ArrayList 添加数据
array.Add("ABC");
array.Add(123);
//用Insert 方法，传入下标和值的方式添加数据
array.Insert(2, "新插入的值");
//修改 ArrayList 里的数据
array[1] = 456;
//用 RemoveAt 方法根据下标移除 ArrayList 里的数据
array.RemoveAt(0);
//用 RemoveAt 方法删除数据，会删除集合中第一个和传入的数据相等的元素。
array.Remove("ABC");
//遍历 ArrayList里面的数据
foreach (var item in array)
{
Console.WriteLine("item is:{0}\n", item);
}
}
}
}
9、集合的特点
集合的特点，也和它的实现有关，那就是变长。内部还是通过数组实现的，只是在不够长时根据一定的策略生成一个更长的数组，把旧数组中的数据复制到新的数据组里使用。所以在正常情况下有两个系统开销，1个是数组总是比我们实际使用的长度长，所以存在空间浪费，另一个是当数组不够长时，需要新建一个更长的数组，同时把旧数组的数据复制到新数组中，这个操作会比较消耗系统的性能。
10、集合的适用场景
集合适用的场合很多，现在基本上所有批量查询及获得一定条件的数据列表，都适用变长数组。比如查询某游戏中一个玩家的包囊里的所有物品，若不清楚物品的数量，则会用变长数组去储存返回的结果。
博客的文章列表、评论列表等，只要涉及列表，就会使用集合的身影。
是否有了变长数组就够了？当然是不够的，在后面的算法学习中，我们会了解到数组的查询效率是很低的，所以要使用一些更复杂的其他数据结构，来帮助我们完成更高效的算法实现。
总结集合：虽然集合这个变长数组比普通数组高级一些，但它的本质上是基于数组实现的，所以与数组的性能差不多。对数组的操作，并不像我们看到的那么直观，计算机需要根据我们具体操作的位置，从头到尾一个个的寻找到指定的位置，所以在数组中添加元素、修改元素、获取元素等操作的时间复杂度都为O(n)。
变长数组也有性能消耗的问题，在插入元素时若发现其中的固定数组长度不够，则需要新建数组，还有复制元素，这样性能消耗就很大。
在算法中每种算法的性能指标一般有两个，第1个是时间复杂度，第2个是空间复杂度。就是性能和存储空的意思。
11、数组的其他应用：散列表
散列表也是集合的一种。为什么需要散列表呢？实际上顺序存储结构类型需要一个个的按照顺序访问元素，当这个总量很大且我们所要访问的元素比较靠后的时，性能就会很低。散列表是一种空间换时间的存储结构，是在算法中提升效率的一种比较常用的方法，但是所需要的空间太大的话也会造成性能降低，所以通常需要在二者之间权衡。
12、什么是散列表
让我们想一下，若在手机通信录中查找一个人，那我们应该不会从第1个人一直找下去，因为这样实在太慢了，我们其实是这样做的：首先看这个人的名字的首字母是什么，比如姓张，那么我们一定会滑到最后，因为“Z”姓的名字都在最后。还有查字典时，也是一样的道理。其实这里就用到散列表的思想，散列表，又叫哈希表，是能够通过给定的关键字的值直接进行访问到具体对应的值的一个数据结构。也就是说，关键表映射到一个表的位置来直接访问记录，已达到加快访问的速度。通常我们把这个关键字叫做Keys,把对应的记录叫做values，所以也可以说是通过keys访问一个映射表来得到values的地址。这个映射表，也叫做散列函数或者哈希函数，存放记录的数据叫做散列表。而通过不同的keys访问相同的地址，叫做碰撞。通过某一个keys，会得到唯一的values地址。
13、介绍几种常见的哈希函数
1）直接寻址法
取关键字或关键字的某一个线性数值为散列地址。
2）数字分析法
通过数据分析，分析出数据中冲突较少的部分，并构造散列地址。例如：学生的学号。
3）平方取中法
当无法确定关键字里哪几位的分布相对比较平均时，可以先求出关键字的平方值，然后按需要取平方值的中间几位做为散列地址。
4）取随机数法
使用一个随机函数，取关键之的随机值作为散列地址 ，这种方式通常用于关键字长度不同的场合。
5）除留取余法
取关键字被某个不大于散列表的长n的数m除后所得的余数p为散列地址。
14、散列表函数会产生几种冲突
1)开放地址法
实际上就是当需要存储值时，对keys哈希之后，发现这个地址已经有值了，这时候怎么办？不能放在这个地址，不然就会覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没有人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。
2）再哈希法
在产生冲突之后，使用关键字的其他部分继续计算地址，如果还有冲突，则继续使用其他部分再计算地址。这种方法就是时间增加了（缺点）。
3）链地址法
链地址法其实就是对keys通过哈希之后落在同一个地址上的值，做一个链表。
4）建立一个公共溢出区
这种方式是建立一个公共溢出区，当地址存在冲突时，把新的地址放在公共溢出区里。
15、散列表的存储结构
16、散列表的特点
1）访问速度快
由于散列表有散列函数，可以将指定的Keys都映射到一个地址上，所以在访问一个keys对应的value时，根本不需要一个个进行查找，可以直接跳到那个地址。所以对散列表的增、删、改、查等任何 操作速度都很快。
2）需要额外的空间
首先，散列表实际上是存不满的，如果一个散列表刚好能够存满，那么肯定是巧合。而且当散列表中的元素的使用率越来越高时，性能会下降，所以一般会选择扩容来解决这个问题。
3）无序
散列表还有一个非常明显的特点，那就是无序。为了能够更快的访问元素，散列表是根据散列函数直接查找存储地址的，这样访问的速度就更快，但是对于有序访问却没有办法对应。
4）可能会产生碰撞
没有完美的散列函数，无论如何总会产生冲突，这时候需要使用冲突解决方案，这也使得散列表更加复杂。
17、散列表的适用场景
1）缓存
在开发程序的时候，对一些常用的信息会做缓存，用的就是散列表，比如我们要存储用户的信息等。
2）快速查找
快速查找的场景很多，比如我们要在指定用户列表中查找是否存在指定的用户，这时候可以使用散列表了。