关联数组执行起来像散列表吗?

Do associative arrays perform like a hash table?

本文关键字：列表 数组 执行 起来 关联      更新时间：2023-09-26

假设JavaScript中有一个关联数组

var hashTable = {};
hashTable["red"] = "ff0000";
hashTable["green"] = "00ff00";
hashTable["blue"] = "0000ff";

当您像这样检索值时会发生什么:

var blue = hashTable["blue"];

性能是否与其他语言的哈希表相似?我的意思是，是否有一个实际的哈希函数用于确定属性的位置，或者是否有一个循环搜索，如:

for (var color in hashTable) {
    if (hashTable.hasOwnProperty(color)) {
        //look for matching key
    }
}

实现是否因浏览器而异?我找不到任何与这个特定主题相关的东西。谢谢。

它在不同的javascript引擎中实现不同，现在，似乎对象不支持' dictionary-like ';数据结构。

从https://developers.google.com/v8/design

:

JavaScript是一种动态编程语言:可以动态地向对象添加和删除属性。这意味着对象的属性可能会改变。大多数JavaScript引擎使用类似字典的数据结构作为对象属性的存储——每个属性访问都需要动态查找来解析属性在内存中的位置。这种方法使得在JavaScript中访问属性通常比在Java和Smalltalk等编程语言中访问实例变量要慢得多。在这些语言中，由于对象类定义的固定对象布局，实例变量位于由编译器确定的固定偏移位置。访问仅仅是内存加载或存储的问题，通常只需要一条指令。

为了减少访问JavaScript属性所需的时间，V8不使用动态查找来访问属性。相反，V8在幕后动态创建隐藏类。这个基本想法并不新鲜——基于原型的编程语言Self使用地图做了类似的事情。在V8中，当添加新属性时，对象会更改其隐藏类。

Firefox的IonMonkey也有类似的功能。摘自对Mozilla开发人员的采访(http://www.infoq.com/news/2011/05/ionmonkey):

)

动态语言可能没有任何内在的优化优势，但它们确实具有静态语言没有的有趣的优化。例如，在编写JavaScript时，对象以散列表的形式显示给用户，将属性名映射到值。如果它们真的是那样实现的，它们会很慢，而且会占用很多内存。

一个好的引擎能够在内部对看起来相同的对象进行分组，从中提取出类似java的内部类。然后JIT可以将对象视为具有实际类型，生成超级快速的代码，从而避免昂贵的属性查找。

Javascript没有真正的"关联数组"。{}返回一个JavaScript 对象，它可以有命名属性，也可以有一个原型，它允许对象从其他对象继承属性。

因此性能将不太像哈希表，因为属性可能从它们的原型对象继承，并且根据名称搜索给定属性可能需要在找到它之前遍历原型树。

这篇博文也可能提供一些见解:

http://www.devthought.com/2012/01/18/an-object-is-not-a-hash/

术语associative array描述了它的用法:它是一个键值容器，用于将一个事物关联到另一个事物。但是术语hash table描述了它的实现:它使用哈希函数来定位底层数组中的元素。在一些使用红黑树或其他数据结构而不是哈希表的实现中可能存在associative array

相关文章：