php 哈希表 VS 关联数组

Hash tables VS associative arrays

提问by Bakhtiyor

Recently I have read about hash-tablesin a very famous book "Introduction to Algorithms". I haven't used them in any real applications yet, but want to. But I don't know how to start.
Can anyone give me some samples of using it, for example, how to realize a dictionary application (like ABBYY Lingvo) using hash-tables?
And finally I would like to know what is the difference between hash-tables and associative arrays in PHP, I mean which technology should I use and in which situations?
If I am wrong (I beg pardon) please correct me, because actually I am starting with hash-tables and I have just basic (theoretical) knowledge about them.
Thanks a lot.

最近我在一本非常著名的书《算法导论》中读到了哈希表。我还没有在任何实际应用程序中使用它们，但想使用它们。但我不知道如何开始。 谁能给我一些使用它的示例，例如，如何使用哈希表实现字典应用程序（如 ABBYY Lingvo）？ 最后我想知道 PHP 中的哈希表和关联数组有什么区别，我的意思是我应该使用哪种技术以及在哪些情况下？ 如果我错了（请原谅）请纠正我，因为实际上我是从哈希表开始的，而且我对它们只有基本的（理论）知识。 非常感谢。

回答by Cam

In PHP, associative arrays are implemented as hashtables, with a bit of extra functionality.

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

However technically speaking, an associative array is not identical to a hashtable - it's simply implementedin part with a hashtable behind the scenes. Because most of its implementation is a hashtable, it can do everything a hashtable can - but it can do more, too.

然而，从技术上讲，关联数组与哈希表并不相同——它只是在幕后部分用哈希表实现。因为它的大部分实现是一个哈希表，它可以做哈希表可以做的所有事情——但它也可以做更多的事情。

For example, you can loop through an associative array using a for loop, which you can't do with a hashtable.

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

So while they're similar, an associative array can actually do a supersetof what a hashtable can do - so they're not exactly the same thing. Think of it as hashtables plus extra functionality.

因此，虽然它们很相似，但关联数组实际上可以做哈希表可以做的事情的超集——所以它们并不完全相同。把它想象成哈希表加上额外的功能。

Code examples:

代码示例：

Using an associative array as a hashtable:

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

$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

Looping through an associative array:

循环遍历关联数组：

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

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

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

Note especially how in the second example, the order of each element is maintained (Tyler, Bill Marc) based on the order in which they were entered into the array. This is a major difference between associative arrays and hashtables. A hashtable maintains no connection between the items it holds, whereas a PHP associative array does (you can even sort a PHP associative array).

请特别注意在第二个示例中，每个元素的顺序（Tyler、Bill Marc）是如何根据它们进入数组的顺序来维护的。这是关联数组和哈希表之间的主要区别。哈希表在它所持有的项目之间没有任何联系，而 PHP 关联数组却可以（您甚至可以对 PHP 关联数组进行排序）。

回答by Sergey Eremin

php arrays ARE basically hash tables

php数组基本上是哈希表

回答by Greg Kuperberg

The difference between an associative array and a hash table is that an associative array is a data type, while a hash table is a data implementation. Obviously the associative array type is very important in many current programming languages: Perl, Python, PHP, etc. A hash table is the main way to implement an associative array, but not quite the only way. And associative arrays are the main use of hash tables, but not quite the only use. So it's not that they are the same, but if you already have associative arrays, then you usually shouldn't worry about the difference.

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

For performance reasons, it can be important to know that your associative arrays in your favorite language are implemented as hashes. And it can be important to have some idea of the overhead cost of that implementation. Hash tables are slower and use more memory than linear arrays as you see them in C.

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

Perl lumps the two concepts together by calling associative arrays "hashes". Like a number of features of Perl, it isn't quite wrong, but it's sloppy.

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

回答by WoZ

An array in PHP is actually an ordered map, not hashtable. Main difference between map and hashtable consists in inability to remember the order in wich elements have been added. On the other hand, hashtables are much faster than maps. Complexity of fetching an element from map is O(nlogn) and from hashtable is O(1).

PHP 中的数组实际上是一个有序映射，而不是哈希表。map 和 hashtable 之间的主要区别在于无法记住添加元素的顺序。另一方面，哈希表比映射快得多。从映射中获取元素的复杂度为 O(nlogn)，从哈希表中获取元素的复杂度为 O(1)。

回答by Mecki

An associative array is an array where you don't access elements by an index, but by a key. How this works internally is implementation specific (there is no rule how it must work). An associative array could be implemented by a hash table (most implementations will do that), but it could also be implemented by some sort of tree structure or a skip list or the algorithm just iterates over all elements in the array and looks for a key that matches (this would be awfully slow, but it works).

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

A hash table is a way how to store data where values are associated to keys and where you intend to find values for keys within a (usually almost) constant time. This sounds exactly like what you expect of an associative array, that's why most of the time hash tables are used for implementing those arrays, but that is not mandatory.

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