6

所以想象一下，你在 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
    }
}

实现是否因浏览器而异？我找不到与此特定主题相关的任何内容。谢谢。

4

3 回答 3

4

它在不同的 javascript 引擎中以不同的方式实现，如今，对象似乎不再由“类字典”数据结构支持。

来自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 可以将对象视为具有实际类型，生成超快速代码，避免昂贵的属性查找。

于 2013-05-29T23:36:43.453 回答
3

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

所以性能不会很像哈希表，因为属性可能是从它们的原型对象继承的，并且按名称搜索给定的属性可能需要在找到原型树之前遍历它。

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

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

于 2013-05-29T23:28:48.530 回答
0

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

于 2013-05-29T23:45:26.423 回答