首页  思维导图  详情

数据结构(C语言版)

2024-12-09 14:20:30   0  举报





AI智能生成

数据结构(C语言版)

大学

程序员

作者其他创作

大纲/内容

数据结构与算法

数据结构概述

概念

数据：数据是信息的载体

数据元素：数据元素是数据的基本单位（一个学生的信息就是一个数据元素）

数据项：一个元素有一个或多个数据项，一个数据项就是该元素的一种属性

数据结构

逻辑结构：数据的逻辑结构

存储结构：数据元素及数据之间的逻辑关系在计算机存储器中的表示

运算：对数据施加的操作

逻辑结构

线性结构

线性表

栈

队列

非线性结构

集合结构

树状结构

图状结构

存储结构

顺序存储结构：用一段地址连续的存储单元存储线性表的数据元素，如数组

优点：可以快速的查找表中任意位置的元素，时间复杂度为O(1)

缺点

插入和删除操作需要移动大量元素

难以确定存储空间的容量，造成存储空间的"碎片"

链式存储结构：每个数据元素（结点）由两部分组成：数据域和指针域。数据域用于存储数据元素的值，而指针域则用于存储指向下一个节点的指针

索引存储结构：主要由数据表和索引表组成，通过索引表来快速索引数据所存放的位置。在索引表中，每一项被称为索引项，而索引项的一般形式为（关键字，地址）

优点

可以动态地分配和释放存储空间

插入和删除放方便

缺点

因为多了一个指针域，所以需要额外的空间开销

访问链表中元素时，需要通过指针逐个遍历，访问速度慢

散列存储结构：根据结点的关键字直接映射出该结点的存储位置

算法及算法分析

算法及其特性

算法的重要特性

输入：一个算法应该有零个或多个输入

有穷性：一个算法必须在执行有穷步骤之后正常结束，不能形成无限循环

确定性：算法中的每一条指令必须有确切的含义，不能产生多义性

可行性：算法中的每一条指令必须是切实可行的

输出：一个算法应该有一个或多个输出

算法描述

框图算法描述：使用流程图N-S描述算法

非形式算法描述：使用自然语言（中文或英文）和程序设计语言中的语句来描述算法

类高级语言算法描述：使用伪语言来描述算法

高级语言算法描述：使用高级语言来描述算法

算法是对解决问题的方法的具体描述，程序是对算法在计算机中的具体实现；程序是算法，算法不一定是程序；

算法分析

算法设计的要求

正确性：算法应该能正确的实现预定的功能和处理要求

易读性：算法应该易于阅读和理解，便于调试、修改和扩充

健壮性：当遇到非法输入时应能作适当的反应或处理，而不会产生不需要或不正确的结果

高效性：解决同一问题所耗费的执行时间越短，算法的时间效率就越高

低存储量：解决同一问题所占用的存储空间越少，算法的空间效率越高

影响算法运行时间的因素

计算机硬件

实现算法的语言

编译生成的目标代码的质量

问题的规模

算法的时间复杂度：计算算法的时间复杂度只需要计算算法中执行频度最高的语句的执行频度

常用的算法时间复杂度的顺序：O(1)<O(lgn)<O(n)<O(nlgn)<O(n^2)<O(n^3)<...<O(2^n)<O(n^n)

线性结构

线性表

顺序表（线性表的顺序存储）

定义：线性表以顺序存储结构的方式进行存储

基本操作

顺序表的初始化

求顺序表的长度

取表元（取值）

按值查找

插入操作

删除操作

链表（线性表的链式存储）

有关概念

结点的组成

数据域

指针域

链表组成：头指针、头节点、开始结点、尾结点

单链表

不带头节点的单链表

带头节点的单链表

优点：元素个数不受限制，动态分配和释放存储空间；插入和删除元素方便，时间复杂度为O(n)

缺点：需要额外的空间开销；查找元素效率差

基本操作

链表的建立

头插法建立单链表

尾插法建立带头结点单链表

求表长

链表的查找

链表的插入

链表的删除

链表销毁

循环链表：一个首尾相连的链表，它是单链表的另一种形式

双向链表

概述：在单链表的每个结点再添加一个指向其直接前驱结点的指针域prior，这样形成的链表有两个不同方向的链，称为双向链表

基本操作（在单链表的基础上增加的）

前插操作

删除当前结点

栈

顺序栈（栈的顺序存储）

定义：栈的顺序存储称为顺序栈

顺序栈的基本操作

置栈空

判栈空

判栈满

进栈

退栈

取栈顶元素

链栈（栈的链式存储）

定义：栈的链式存储结构称为链栈

链栈的基本操作

置栈空

判栈空

进栈

退栈

取栈顶元素

队列

顺序队列

顺序队列的定义：队列的顺序存储结构称为顺序队列，它是运算受限的顺序表

顺序队列的基本操作

入队

出队

顺序队列的溢出现象

下溢：当队列为空时，做出队操作所产生的溢出现象为下溢

真上溢：当队列满时，做入队操作所产生的空间溢出现象称为真上溢

假上溢

循环队列

循环队列的定义：把向量空间的元素首尾相连的顺序队列称为循环队列

队列空满的处理方法

设一标志变量flag

少用一个元素的空间

使用一个计数器count记录队列中元素的总数

循环队列基本操作

置队空

判队空

判栈队满

入队

出队

取队头元素

链队列

链队列的定义：队列的链式存储称为链队列，他是限制仅在表头删除和在表尾插入的单链表

链队列的基本操作

置队空

判队空

入队

出队

取队头元素

非线性结构

树

树的定义：顾名思义

树的表示

树形图表示法：把树倒过来的表示形式

嵌套集合表示法：用集合的包含关系描述树结构

凹入表表示法：类似于书的目录

树的基本术语

结点的度：一个结点拥有的子树的个数称为该结点的度

结点之间的关系

孩子结点

双亲结点

兄弟节点

堂兄弟

祖先和子孙

路径

路径的长度：路径所经过的边的数目

结点的层数和树的深度

结点的层数：例如根节点的层数为1

堂兄弟

树的深度：树中结点最大层数称为树的深度

有序树和无序树：若将树中每个结点的各子树看成是从左到右有次序的，则称该树为有序树，否则称为无序树

森林：互不相交的树的集合。删除一棵树的根就得到一个森林，反之，加上一个结点作树根，森林就变为一棵树。

二叉树

二叉树的定义：每个结点最多只能有两棵子树，且有左右之分

二叉树的五种形态

空集

左、右子树都为空

左子树为空

右子树为空

左右子树都存在

二叉树的性质

性质1：二叉树第i层上的结点数目最多为2的（i-1）次方

性质2：深度为k的二叉树至多有2的k次方-1

性质3：在任意一颗非空二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

性质4：具有n个结点的完全二叉树的深度为[lgn](下括号)+1或[lg(n+1)](上括号)，其中[lgn](下括号)表示取小于或等于lgn的整数部分，[lg(n+1)](上括号)表示取大于或等于的整数部分，lg表示以2为底的对数

特殊二叉树

满二叉树

定义：每一层上的结点数都达到最大值的二叉树

特点

一棵深度为k且有2^k-1个结点的树称为满二叉树

满二叉树中不存在度数为1的结点

完全二叉树

定义：在满二叉树的最下一层上，从最右边开始连续删去若干结点得到的二叉树称为完全二叉树

特点

最下一层上的结点都集中在该层最左边的若干位置上

满二叉树是完全二叉树，但完全二叉树不一定是满二叉树

完全二叉树中，若某个结点没有左孩子，则一定没有右孩子

深度为k的完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2^(k-1)-1个结点

二叉树的顺序存储

完全二叉树的顺序存储：从树根起，自上层到下层，每层从左至右给所有结点编号，开始结点的编号为1，这样得到的一个反映整个二叉树结构的线性序列。

一般二叉树的顺序存储

将一般二叉树添上一些“虚结点”，使其成为完全二叉树，并从树根起，自上层到下层，每层从左至右给所有结点编号，开始结点的编号为1，“虚结点”用/0表示

二叉树的链式存储

结点的结构：指针域、数据域、指针域

二叉链表

带双亲指针的二叉链表（多一个指针域指向双亲）

二叉树的遍历

先序遍历：根——左——右

中序遍历：左——根——右

后序遍历：左——右——根

确定二叉树：已知中序遍历序列和先序遍历序列或后序遍历序列可以确定一棵二叉树

二叉链表的建立

基于先序和中序遍历序列建立二叉链表

基于带虚结点先序遍历序列建立二叉链表

二叉链表的基本操作

遍历二叉树

计算二叉树深度

计算所有结点总数

计算叶子结点数

计算双孩子结点数

计算单孩子结点数

树和森林

树、森林到二叉树的转换

将树转换为二叉树

加线：在所有兄弟结点之间加一条线

去线：对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线

调整按树的层次进行调整，将原来的右兄弟变成其右孩子，原来的无兄弟结点变成左孩子

说明：由于树根没有兄弟，故数转换为二叉树后，二叉树的根结点的右子树必为空

将一个森林转换为二叉树

转换为二叉树：将森林中的每棵树转换为二叉树

连接根节点：再将个二叉树的根节点视为兄弟从左至右连在一起

调整：按树的层次进行调整，将原来的右兄弟变成其右孩子，原来的无兄弟结点变成左孩子

二叉树到树、森林的转换

加线：在左孩子结点的双亲与左孩子结点的右孩子、右孩子的右孩子等等之间加一条线

去线：去掉所有双亲与右孩子之间的连线

调整：按树的层次结构进行调整，将原来根结点的右孩子、右孩子的右孩子等变成森林中树的根，其他结点的右孩子、右孩子的右孩子等变为兄弟

树的存储结构

双亲链表表示法：所有亲兄弟链接一个双亲

孩子链表表示法：一个双亲串链接所有孩子

孩子兄弟链表示：左指针域指向孩子，右指针域指向兄弟

哈夫曼树及哈夫曼编码

哈夫曼树有关概念

哈夫曼树：带权路径最小的二叉树称为哈夫曼树或最优二叉树

树的路径长度：从根结点到树中每一结点的路径长度之和称为树的路径长度

树的带权路径长度

结点的权：赋予树中某结点的一个有某种意义的实数

结点的带权路径长度：结点到树根之间路径长度与该结点上权的乘积

树的带权路径长度：树中所有叶结点的带权路径长度之和，也叫树的代价。

哈夫曼树的构造：在森林中选出两颗根结点权值最小的数，将这两棵树合并成一棵新的树，重复操作，当只剩下一棵树时，它就是哈夫曼树

哈夫曼树结点的结构：权值域、左孩子指针域、右孩子指针域、双亲指针域

哈夫曼编码

编码：数据压缩的过程称为编码，即将字符转换为对应的二进制位串

解码：数据解压的过程称为解码，即将二进制位串转换为对应的字符

编码方案

等长编码方案：将给定字符集中的每个字符码长固定

变长编码方案：将频率高的字符编码设置较短，将频率低的字符编码设置较长

前缀码方案：对字符集进行编码时，要求字符集中任一字符的编码都不是其他字符编码的前缀

最优前缀码：平均码长或文件总长最小的前缀码称为最优前缀码

根据最优二叉树构造哈夫曼编码

图

图的概念

无向图和有向图

无向图（Vi,Vj)

有向图<Vi,Vj>

图的边和顶点的关系

若(Vi,Vj)是一条无向边，则称顶点Vi和Vj互为邻接顶点，或称Vi和Vj相邻接，并称（Vi，Vj）依附或关联于顶点Vi和Vj，或称（Vi，Vj）与顶点Vi和Vj相关联

若<Vi,Vj>是一条有向边，则称顶点Vi邻接到顶点Vj，顶点Vj邻接于顶点Vi，并称（Vi，Vj）关联于顶点Vi和Vj，或称（Vi，Vj）与顶点Vi和Vj相关联

子图：被包含点包含边的图

路径

无向图的路径

有向图的路径

路径长度

简单路径

简单回路或简单环

有根图和图的根

连通图和连通分量

顶点间的连通性：两点间有路径，则称该两点是连通的

连通图（无向图）：无向图中任意两个不同的点都连通，称图为连通图

连通分量：无向图的极大连通子图称为连通图的连通分量（与其他子图不相连的子图）

强连通图和强连通分量

强连通图（有向图）：在有向图中，若对于V(G)中任意两个不同的顶点V和Vj，都存在从Vi到Vj以及Vj到Vi的路径，则称G是强连通图

强连通分量：有向图的极大强连通子图称为G的强连通分量

说明1：强连通图只有一个强连通分量，既是其自身

说明2：非强连通图的有向图有多个强连分量

网络：若将图的每条边都附上一个权，则称这种带权图为网络

图的存储结构

图的邻接矩阵表示（数组）

无向图的邻接矩阵

有向图的邻接矩阵

网络的邻接矩阵

邻接矩阵的特点

对称性：无向图的邻接矩阵一定是对称矩阵，而有向图的邻接矩阵不一定对称，邻接矩阵主对角元素全为0

顶点的个数：邻接矩阵的阶数表示该图顶点的个数，邻接矩阵含元素的个数与点数有关，与边数无关

边的个数：无向图邻接矩阵中非零元个数的一半或上三角矩阵非零元个数或下三角矩阵非零元个数是该无向图边的个数；有向图邻接矩阵中非零元的个数是该有向图的个数为第i个顶点的入度，第i行与第i列非零元素个数之和是第i个顶点的度

两点的邻接性：无向图邻接矩阵中第i行第i列（或第j行第i列）元素非零表示对应的第i个顶点与第j个顶点相邻接，为零表示对应的两个顶点不邻接；有向图邻接矩阵中第i行第i列元素非零表示对应的第i个顶点邻接到第j个顶点

图的邻接表表示（链式）

邻接表的结点结构：邻接点域、指针域

无向图的邻接表

有向图的邻接表

有向图的逆邻接表

邻接表的特点

存储唯一性:邻接表的存储表示不唯一，边表结点的次序不同得到不同的存储

顶点的个数:顶点表含元素的个数表示该图顶点的个数

边的个数:无向图每个顶点边表结点个数的和的一半表示该无向图边的个数；有向图每个顶点边表结点个数的和表示该有向图边的个数。

顶点的度:无向图顶点v边表结点的个数表示顶点v的度。有向图顶点vi边表结点的个数表示顶点vi的出度，其他顶点边表中值为i的结点个数的和表示顶点的入度

两顶点的邻接性:无向图第i个(第j个)顶点的边表有值为j(i)的结点表示顶点vi与顶点相邻接;有向图第i个顶点的边表有值为j的结点表示顶点邻接到顶点Vj

图的遍历

深度优先遍历

广度优先遍历

生成树

生成树概念

生成树：如果连通图G的一个子图是一颗包含G所有顶点的树，则该子图称为G的生成树（包含所有顶点，不一定包含所有边）

深度优先生成树

广度优先生成树

最小生成树：权值最小的生成树称为最小生成树

最小生成树算法

普里姆算法：时间复杂度为O(n^2)，适合对边数较多的稠密图求最小生成树

克鲁斯科尔算法：每次选最小的，但不能是同一条边；时间复杂度为O(elge)，适合对边数较少的稀疏图求最小生成树

最短路径

最短路径问题

带权图的最短路径：从一个顶点到另一个顶点所经过边的权值之和称为该路径的权值，从一个顶点到另一个顶点之间路径权值最小的路径，称为最短路径

源点和终点：路的开始顶点称为源点，路的最后一个顶点称为终点

最短路径问题

单源最短路径问题

单目标最短路径问题

单顶点对间最短路径问题

所有顶点对间最短路径问题

迪杰斯特拉算法

拓扑排序

定义：将有向无环图中所有顶点排成一个线性序列

拓扑排序方法

无前驱顶点优先

1、在有向图中选一个没有前驱的顶点并输出

2、从图中删除该顶点并删除与该顶点有关的所有边

3、重复上述两步，直至全部顶点均已输出，或者图中不存在无前驱的顶点为止后一种情况则说明有向图中存在环

无后继顶点优先

1、在有向图中选一个没有后继的顶点并输出

2、从图中删除该顶点并删除与该顶点有关的所有边

3、重复上述两步，直至全部顶点均已输出，或者图中不存在无后继的顶点为止。
后一种情况则说明有向图中存在环

排序和查找

排序

基本概念

排序：将数据元素(或记录)的任意序列,通过某种方法重新排列成一个按关键字有序(递PPT排序的麦增或递减)序列的过程称为排序

排序的两种基本操作：① 比较两个关键字值的大小 ② 移动记录或交换记录。

排序的稳定性：某种排序方法，如果对任意一组含相同关键字的记录，按此方法排序后，相同关键字记录的相对位置保持不变，则称此排序方法是稳定的，否则称为是不稳定的

内排序和外排序

内排序:整个排序过程都在内存进行的排序方法称为内排序

外排序:如果待排序的数据量较大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序方法称为外排序

排序方法的分类

插入类排序

选择类排序

交换类排序

归并排序

分配排序

就绪排序

直接插入排序

希尔排序

折半插入排序

表插入排序

冒泡排序

快速排序

直接选择排序

堆排序

不稳定排序

希尔排序

快速排序

直接选择排序

堆排序

评价排序算法好坏的标准

主要是算法执行时间和所需的辅助空间

其次是算法本身的复杂程度

就地排序：若排序算法所需的辅助空间不依赖于问题的规模n，即辅助空间是 O(1)则称此排序方法为就地排序

约定：本单元中的排序均是按关键字递增排序，且以顺序表作为文件的存储结构

插入排序

直接插入排序

基本思想：边插入边排序，就像打扑克抓牌一样，边抓边排序

平均时间复杂度O(n^2)

适合于排序记录基本有序或记录较少的情况

就地排序：空间复杂度O(1)

稳定

希尔排序

基本思想：将序列内记录间隔分组，两两一组，然后组内排序交换，重复以上操作，但记录间间隔递减，当间隔递减到一并完成组内排序后，对所有元素进行直接插入排序

平均时间复杂度O(n^(5/4))

就地排序（用一个空间暂存数据进行比较）

不稳定（相同元素不在同一组的话，有可能相对位置会改变）

折半插入排序

首和当前折半比较，左部分还是右部分，再折半比较，左还是右，只剩下一个比较后插入。

平均时间复杂度O(n^2)

就地排序

稳定

表插入排序

就地排序

稳定

交换排序

冒泡排序

具体思想：通过重复地遍历待排序的序列，一次比较两个元素，并按照升序或者降序来决定是否交换它们的位置，直到没有需要交换的元素时，排序完成。

平均时间复杂度O(n^2)

就地排序

稳定

快速排序

具体实现：选择一个中心数（任意）作为参考，将所有元素与之比较，并形成中心数左右两边两个子表，小的放在左边的子表，大的放在右边的子表，子表内做相同的操作，以此类推

平均时间复杂度O(nlgn)

就地排序

不稳定

选择排序

直接选择排序

基本思路：通过比较，每一趟从待排序的记录中选出关键字值最小（大）的记录，顺序放在已经排好的子文件的最前（后），直到全部记录排序完毕

平均时间复杂度O(n^2)

就地排序

不稳定

堆排序

大根堆：一棵树中，双亲永远比孩子大的叫大根堆

小根堆：一棵树中，双亲永远比孩子小的叫小根堆

具体实现：每次取堆顶元素，然后再将堆的堆顶删除并重新做堆

平均时间复杂度O(nlog2n)

就地排序

不稳定

归并排序

两路归并排序

具体实现：两个指针分别指向两路关键字有序表的开头关键字，比较两个关键字的大小并且取最小的（或最大的）值放入排序列表，并将被取走关键字的列表的指针向后移动一位，继续比较，以此类推。

平均时间复杂度O(nlog2n)

空间复杂度O(n)

稳定

自底向上归并排序

具体实现：两个元素归并成一个组合并在组内排序过后，两个组合归并成一个新的组合，以此类推

时间复杂度O(nlgn)

空间复杂度O(n)

稳定

自顶向下归并排序

具体实现：将待排序的文件分解成两个子文件（子序列），再对两个子文件依次用同样的方法进行排序，待两个文件均有序时，将两个文件归并为一个文件

时间复杂度O(nlgn)

空间复杂度O(n)

稳定

分配排序

箱排序

基本思想:设置若干个箱子，依次扫描待排序的记录R[0]R[1]、…、R[n-1]，把关键字等于k的记录全都装入到第k个箱子里(称为分配)，然后按序号依次将各非空的箱子首尾连接起来(称为收集)

子主题

是否稳定：与桶内排序方法有关

桶排序

排序方法：在箱排序的基础上进行了变种，将关键字的取值范围变成了一个区间[0,1)，而不是等于某个固定的数。如果在一个桶中有多个记录，使用直接插入排序由从小到大的顺序排序

平均时间复杂度O(n^2/m)

空间复杂度：顺序存储O(m*n)；链式存储O(n)

是否稳定：与桶内排序方法有关

基数排序

排序方法：将整数按位数切割成不同的数字，然后每个位数分别比较并按大小放入箱子，待所有位数比较完成，按顺序回收箱子内的元素。

平均时间复杂度：O(n)

空间复杂度O(n+r)

稳定

查找

基本概念

动态查找表：允许插入和删除操作

静态查找表：允许查找和检索操作

内查找：查找过程再内存中进行

外查找：查找过程中需要访问外存

平均查找长度

线性表查找

顺序查找

基本思路：从表的一端开始，顺序扫描线性表，依次按给定值K与关键字Key 进行比较,若相等，则查找成功，并给出数据元素在表中的位置;若整个表查找完毕，仍未找到与K相同的关键字，则查找失败，给出失败信息

平均查找长度：(n+1)/2

优点：算法简单，对表结构无要求

缺点：查找效率低

二分查找（折半查找）

具体思路

平均查找长度

优点：效率高

缺点：只适用于顺序存储结构，不能用于链式存储结构；要求线性表是有序的。

分块查找

基本思路：先在索引表中采用二分查找，以确定待查的元素在哪一块；然后在已确定的块中进行顺序查找

分块有序：每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字

平均查找长度：略

优点：灵活性较好，只要每个块内元素是无序的，而块与块之间是有序的，就可以实现分块中查找；在块内插入和删除操作操作，不需要移动大量元素

缺点：需要维护额外的一个索引表，造成了一定的空间开销；最坏情况下，其查找效率会降低到与顺序查找相同

树查找

二叉排序树查找

特点：二叉排序树中任一结点的关键字，必须大于其左子树所有结点的关键字，小于等于右子树所有结点的关键字

平均查找长度O(lgn)

平衡二叉搜索树(AVL树) P(329)

概念：是一种二叉排序树，其中每一个节点
的左子树和右子树的高度差绝对值不超过1

优缺点：

维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，
更多的地方是用追求局部而不是非常严格整体平衡的红黑树。
当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树。

多路查找树(B树)

概念：每一个结点的孩子树可以多余俩个，且每一个结点处可以存储多个元素

4种形式

2-3树

每一个结点都具有俩个孩子(称为2结点)，或三个孩子(称为3结点)

2-3-4树

2-3树的扩展，最多四个孩子

B树

一种平衡的多路查找树

所有叶子结点都位于同一层次

B+树

应文件系统那个所需而出的一种B树的变形树

出现在分支节点中的元素会在叶子结点中再次列出，每一个叶子结点都会保存一个指向后一叶子结点的指针

红黑树

概念：一种自平衡二叉查找树，和AVL树类似(并不是真正的平衡二叉树)，
都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

适合：适合搜索，插入，删除较多的情况

性质：

每个结点要么是红色，要么是黑色

根结点永远是黑色

所有的叶节点都是空结点(即null)，并且是黑色的

每个红色结点的俩个子结点都是黑色(从每个叶子到跟的路径上不会有俩个连续的红色结点)

从任一结点到其子树中每个叶子结点的路径都包含相同数量的黑色结点

关键性质：

这些性质强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。主要原因在于，性质4导致了路径不能有两个毗连的红色节点，最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点，根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长

散列表查找(哈希查找)

概念：散列技术是在记录的存储位置和它的关键字之间建立一个稳定的对映关系f，
使得每个关键字key对于一个存储位置f(key)，f称为散列函数，又称为哈希(Hash)函数

特点