使用哈希表搜索

在搜索操作方面，散列表是一种非常高效的数据结构。由于哈希表以关联方式存储数据，如果我们知道在哪里查找数据，就能轻松快速地获取数据。在哈希表中，每个数据都有一个与之关联的唯一索引。如果我们知道要查看哪个索引，就能非常容易地找到键。通常，在其他编程语言中，我们必须使用单独的哈希函数来计算哈希索引，以存储值。散列函数的目的是为同一个键生成相同的索引，同时避免碰撞。然而，PHP 的一大特点是 PHP 数组本身就是一个哈希表，它的底层是 C 语言实现的。由于数组是动态的，因此我们不必担心数组的大小或数组中数值过多的问题。我们需要将值存储在关联数组中，这样就可以将值与键关联起来。如果值是字符串或整数，则键可以是值本身。让我们运行一个示例来了解使用哈希表进行搜索：

我们刚刚建立了一个简单的随机关联数组，其中值和键是相同的。由于我们使用的是 PHP 数组，虽然值的范围是 1 到 500，但实际数组的大小从 10 到 30 不等。如果使用其他语言，我们就会构造一个大小为 501 的数组来容纳这个值作为键。这就是使用哈希函数计算索引的原因。如果我们愿意，也可以使用 PHP 内置的散列函数：

第一个参数是我们希望使用的哈希算法类型。我们可以选择 md5、sha1、sha256、crc32 等。每种算法都会产生固定长度的散列输出，我们可以用它作为散列表的密钥。

如果我们看一下搜索部分，就会发现我们实际上是在直接检查相关索引。这使得我们的搜索复杂度为 \$O(1)\$。在 PHP 中，即使不使用哈希函数，使用哈希表进行快速搜索也是有益的。不过，如果需要，我们可以随时使用哈希函数。

到目前为止，我们已经介绍了基于数组和线性结构的搜索。现在，我们将把重点转移到分层数据结构搜索，如搜索树和图。虽然我们还没有讨论图（我们将在下一章讨论），但我们将继续关注树搜索，它也可以应用于图搜索。