当存储在表中时，直接寻址运用值和键之间的一对一映射。 但是，当存在少量键值对时，此办法存在成绩。 该表将具有很多记载，并且十分庞大，思索到典型计算机上的可用内存，该表能够不实在践甚至无法存储。 为避免此成绩，我们运用哈希表。
哈希函数
名为哈希函数(h)的特殊函数用于克制直接寻址中的上述成绩。
在直接拜访中，带有密钥k的值存储在插槽k中。 运用哈希函数，我们可以计算出每个值都指向的表(插槽)的索引。 运用给定键的哈希函数计算的值称为哈希值，它表示该值映射到的表的索引。
h：哈希函数
k：应确定其哈希值的键
m：哈希表的大小(可用插槽数)。 一个不接近2的准确乘方的素数是m的一个不错的选择。
Fig 5. Representation of a Hash Function
1→1→1
5→5→5
23→23→3
63→63→3
从下面给出的最后两个示例中，我们可以看到，当哈希函数为多个键生成相反的索引时，就会发作抵触。 我们可以经过选择适宜的哈希函数h并运用链接和开放式寻址等技术来处置抵触。
哈希表的运用
用于完成数据库索引。
用于完成关联数组。
用于完成"设置"数据结构。
6.树
树是一种层次结构，其中数据按层次停止组织并链接在一同。 此结构与链接列表不同，而在链接列表中，项目以线性顺序链接。
在过去的几十年中，曾经开收回各种类型的树木，以适宜某些运用并满足某些限制。 一些示例是二叉搜索树，B树，红黑树，展开树，AVL树和n元树。
二叉搜索树
望文生义，二进制搜索树(BST)是一种二进制树，其中数据以分层结构停止组织。 此数据结构按排序顺序存储值，我们将在本课程中详细研讨这些值。
二叉搜索树中的每个节点都包含以下属性。
key：存储在节点中的值。
left：指向左孩子的指针。
右：指向正确孩子的指针。
p：指向父节点的指针。
二叉搜索树具有共同的属性，可将其与其他树区分开。 此属性称为binary-search-tree属性。
令x为二叉搜索树中的一个节点。
假设y是x左子树中的一个节点，则y.key≤x.key
假设y是x的右子树中的节点，则y.key≥x.key
Fig 6. Visualization of Basic Terminology of Trees.
树的运用
二叉树：用于完成表达式解析器和表达式求解器。
二进制搜索树：用于许多不断输入和输入数据的搜索运用顺序中。
堆：由JVM(Java虚拟机)用来存储Java对象。
Trap：用于无线网络。
7.堆
堆是二叉树的一种特殊状况，其中将父节点与其子节点的值停止比较，并对其停止相应陈列。
让我们看看如何表示堆。 堆可以运用树和数组表示。 图7和8显示了我们如何运用二叉树和数组来表示二叉堆。
Fig 7. Binary Tree Representation of a Heap
Fig 8. Array Representation of a Heap
堆可以有2种类型。
最小堆-父项的密钥小于或等于子项的密钥。 这称为min-heap属性。 根将包含堆的最小值。
最大堆数-父项的密钥大于或等于子项的密钥。 这称为max-heap属性。 根将包含堆的最大值。
堆的运用
用于完成优先级队列，由于可以依据堆属性对优先级值停止排序。
可以在O(log n)时间内运用堆来完成队列功用。
用于查找给定数组中k个最小(或最大)的值。
用于堆排序算法。
8.图
一个图由一组有限的顶点或节点以及一组衔接这些顶点的边组成。
图的顺序是图中的顶点数。 图的大小是图中的边数。
假设两个节点经过同一边彼此衔接，则称它们为相邻节点。
有向图
假设图形G的一切边缘都具有指示什么是起始顶点和什么是终止顶点的方向，则称该图形为有向图。
我们说(u，v)从顶点u入射或分开顶点u，然后入射到或进入顶点v。
自环：从顶点到本身的边。
无向图
假设图G的一切边缘均有方向，则称其为无向图。 它可以在两个顶点之间以两种方式传达。
假设顶点未衔接到图中的任何其他节点，则称该顶点为孤立的。
Fig 9. Visualization of Terminology of Graphs
图的运用
用于表示社交媒体网络。 每个用户都是一个顶点，并且在用户衔接时会创立一条边。
用于表示搜索引擎的网页和链接。 互联网上的网页经过超链接相互链接。 每页是一个顶点，两页之间的超链接是一条边。 用于Google中的页面排名。
用于表示GPS中的位置和路途。 位置是顶点，衔接位置的路途是边。 用于计算两个位置之间的最长途径。
【编辑引荐】
顺序员的外包阅历：印度、中国和菲律宾
假设新冠病毒是在亚美尼亚迸发会发作什么？顺序员用Python停止模拟
(责任编辑：admin)