哈希表与关联数组

Question

最近，我在一本非常有名的书《算法简介中读到了哈希表一个>”。我还没有在任何实际的应用程序中使用它们，但我想这样做。但我不知道如何开始。
有哪些使用示例，例如如何使用哈希表实现字典应用程序（如 ABBYY Lingvo）？

最后我想知道 PHP 中的哈希表和关联数组有什么区别，我的意思是我应该使用哪种技术以及在什么情况下？

如果我错了（请原谅），请纠正我，因为实际上我是从哈希表开始的，我只有关于它们的基本（理论）知识。

Answer 1

在 PHP 中，关联数组被实现为哈希表，并具有一些额外的功能。

然而，从技术上讲，关联数组与哈希表并不相同。它只是在幕后通过哈希表部分实现。因为它的大部分实现都是哈希表，所以它可以完成哈希表可以做的所有事情，而且还可以做更多的事情。

例如，您可以使用 for 循环遍历关联数组，而哈希表则无法做到这一点。

因此，虽然它们很相似，但关联数组实际上可以执行哈希表功能的超集，因此它们并不完全相同。将其视为哈希表加上额外的功能。

代码示例：

使用关联数组作为哈希表：

$favoriteColor = array();
$favoriteColor['bob'] = 'blue';
$favoriteColor['Peter'] = 'red';
$favoriteColor['Sally'] = 'pink';
echo 'bob likes: ' . $favoriteColor['bob'] . "\n";
echo 'Sally likes: ' . $favoriteColor['Sally'] . "\n";
// Output: bob likes blue
//         Sally likes pink

循环关联数组：

$idTable = array();
$idTable['Tyler'] = 1;
$idTable['Bill'] = 20;
$idTable['Marc'] = 4;
// Up until here, we're using the array as a hash table.

// Now we loop through the array - you can't do this with a hash table:
foreach($idTable as $person => $id)
    echo 'id: ' . $id . ' | person: ' . $person . "\n";

// Output: id: 1 | person: Tyler
//         id: 20 | person: Bill
//         id: 4 | person: Marc

特别注意在第二个示例中如何维护每个元素的顺序（Tyler、Bill 和 Marc）基于他们进入数组的顺序。这是关联数组和哈希表之间的主要区别。哈希表不维护其所保存的项之间的任何连接，而 PHP 关联数组则保留（您甚至可以对 PHP 关联数组进行排序）。

Answer 2

PHP 数组基本上是哈希表。

Answer 3

关联数组和哈希表之间的区别在于，关联数组是一种数据类型，而哈希表是一种数据实现。显然，关联数组类型在当前的许多编程语言中非常重要：Perl、Python、PHP 等。哈希表是实现关联数组的主要方式，但不是唯一的方式。关联数组是哈希表的主要用途，但并不是唯一的用途。所以这并不是说它们是相同的，但是如果您已经有关联数组，那么您通常不必担心差异。

出于性能原因，了解您最喜欢的语言中的关联数组是作为哈希实现的非常重要。了解该实施的间接费用也很重要。正如您在 C 中看到的那样，散列表比线性数组更慢并且使用更多的内存。Perl

通过将关联数组称为“散列”将这两个概念混为一谈。就像 Perl 的许多功能一样，它并没有完全错误，但它很草率。

Answer 4

PHP 中的数组实际上是一个有序映射，而不是哈希表。

映射和哈希表之间的主要区别在于无法记住添加元素的顺序。另一方面，哈希表比映射快得多。从映射中获取元素的复杂度为 O(n·log_n)，从哈希表中获取元素的复杂度为 O(1)。

Answer 5

关联数组是一种不通过索引而是通过键访问元素的数组。它的内部工作原理是特定于实现的（没有规则它必须如何工作）。关联数组可以通过哈希表来实现（大多数实现都会这样做），但它也可以通过某种树结构或跳跃列表来实现，或者算法只是迭代数组中的所有元素并查找键匹配（这会非常慢，但它有效）。

哈希表是一种存储数据的方法，其中值与键相关联，并且您打算在（通常几乎）恒定时间内查找键的值。这听起来与您对关联数组的期望完全一样，这就是为什么大多数时候使用哈希表来实现这些数组，但这不是强制性的。