十一、数据结构基础——线性表和散列表

本章主要介绍线性表的链式存储、散列表的压缩映射建立量数据类型间关系的作用。

一般条件下散列查找的性能可以媲美顺序表的查找，即时间复杂度O(1)。

动态链表

（一）单链表结点的定义

单链表中每个节点都是一个节点，不仅要存储元素值，还要存储指向下一个元素的指针。可用如下类来表示这样的节点：

（二）单链表的基本操作（插入、删除、遍历、查找）

①插入结点：

插入时需要先找到第p个节点的位置（0<=p<=n），因此最坏的时间复杂度为O(n)。

②删除结点：

删除时需要先找到第p个节点的位置（0<=p<=n），因此最坏的时间复杂度为O(n)。

③遍历链表：

遍历的时间复杂度为O(n)。

④查找结点：

查找第p个结点的时间复杂度为O(n)。

静态链表

静态链表中的指针不是通常意义的指针类型变量，而是存储一个数组下标的整型变量，通过它可以找到后继节点在数组中的位置，其功能类似于真实的指针。

其结点定义如下：

但实际上为了简便，编程上一般使用array<int,2>来作为一个结点的类型，其中下标为0的元素存储节点的值，下标为1的元素存储结点的下一个结点地址。

在工程项目中，动态链表是最常见的链表的实现方法。但是在程序设计竞赛或考试中，由于一般数据量是已知的，因此用静态链表会易于编码和查找。

双向链表

双向链表既可以向后遍历，也可以向前遍历。因此在单链表结点的基础上增添一个指针域pre即可。双向链表结点的定义如下：

C++标准库中list就是双向链表，因此当你获取list中一个元素的迭代器时，可以快速找到其前驱和后继。通常情况下，当需要使用链表时，都可以用list容器实现相关功能。

散列表

散列表提供一个数组，为每个可能的关键字保留一个位置，通过一个转换函数将关键字转换为一个它在数组中的下标，这个转换函数称为散列函数（或哈希函数）。理想情况下，也能够以O(1)的时间访问散列表中的任意元素。

（一）散列函数

散列是一种压缩映射，其核心思想是将一种类型的关键字通过一个函数转换成一个整数，使得这个整数能够尽可能地表示这个关键字本身。这个函数称为散列函数或哈希函数，转换成的整数称为该关键字的散列值或哈希值。

常见的散列函数设计方法为

⭐除留余数法，即将key对一个指定的数字m（通常取散列表表长）取余数作为散列值，即：

（二）冲突

当对于不同key得到同样的哈希值时，称之为冲突或碰撞。设计的散列函数应当尽可能避免冲突，为此散列表的表长通常设置为一个素数（例如1e9+7）。

补充：1e9+7是最小的10位素数，对其取模后可以保证值在int（大概-2e9~2e9）范围内。

⭐常见的冲突解决方法有：

①开放定址法：，其中hash(key)是散列函数，m是散列表长,d_i是增量序列，i是已经发生冲突的次数。增量序列可以有以下取法：

1）当时，称为线性探测法。

2）当时，称为平方探测法。

②再散列法：定义多个散列函数，若一个散列函数发生冲突，则逐一利用其他散列函数产生新的散列值，直到冲突不再发生。

③链地址法：将散列到同一位置得到所有元素保存在一个链表中。当访问一个元素时，先计算该元素的散列值，然后遍历其对应的单链表，查找相应元素。当需要使用散列表时，通常可以直接C++标准库中的无序关联容器（unordered_map、unordered_set），此时一般不需要实现这些解决冲突的办法。

（三）自定义无序关联容器的关键字哈希函数

无序关联容器的关键字是限制类型的，当需要将其他类型作为其关键字时，则要另外定义其哈希函数。无序容器在创建对象时，可以向它传递函数对象作为额外的参数，这个函数对象定义了针对关键字类型对象的哈希函数，它应该返回一个整数值，建议返回long long类型。

例如：自定义关键字是array<int,2>的unordered_map的哈希函数代码模板

选用容器实现哈希表的原则

①关键字能作为数组下标且数据规模较小，使用数组（vector、array、bitset、C++内置数组）；

②关键字不能作为数组下标，但可以直接作为无序关联容器的键，用无序关联容器；

③关键字不能作为无序关联容器的键，但能直接作为有序关联容器的键，用有序关联容器；

④关键字不能直接做数组下标、有/无序关联容器的键，应当自定义该类型的默认哈希函数并使用无序关联容器。