散列表VS关联数组

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 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

特别注意在第二个例子中,每个元素的顺序是根据它们输入数组的顺序而保持的(Tyler,Bill Marc).这是关联数组和哈希表之间的主要区别.哈希表在它保存的项之间不保持连接,而PHP关联数组则保持连接(你甚至可以对PHP关联数组进行排序).

Answer 2

php数组基本上是哈希表

Answer 3

关联数组和散列表之间的区别在于关联数组是数据类型,而散列表是数据实现.显然,关联数组类型在许多当前的编程语言中非常重要:Perl,Python,PHP等.哈希表是实现关联数组的主要方式,但不是唯一的方法.关联数组是哈希表的主要用途,但并不是唯一的用途.所以并不是它们是相同的,但如果你已经有了关联数组,那么你通常不应该担心这些差异.

出于性能原因,了解您喜欢的语言中的关联数组是否实现为哈希值非常重要.了解该实现的开销成本非常重要.散列表比线性数组更慢并且使用更多内存,如在C中看到的那样.

Perl通过调用关联数组"哈希"将这两个概念结合在一起.就像Perl的许多功能一样,它并没有错,但它很邋..

Answer 4

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