网站制作：JavaScript 与散列表-桔子科技网站建设设计公司

网站制作：JavaScript 与散列表

发布人：桔子科技发布时间：2015-05-07 07:03:52 分享到：

本来想喷一喷 PHP 的散列冲突的问题的，翻了翻旧文章发现我一直没介绍过关于散列表的东西。使用 JavaScript 这样基于散列存储的编程语言，要是不明白散列表的概念一定会很纠结吧？整天使用字符串拼接来做对象属性名的话是该了解一下了。

内存这种东西可以理解为一个数组，如果我们知道内存地址的话存取是很快的。所以一般数组的存取是很快的，因为可以通过下标直接算出内存地址。即使是 JavaScript 这么散列化的语言也一样，大多数 JavaScript 引擎会将普通的（连续空项在一定范围内的，可以参考 v8 的 kMaxGap）数组在内存中直接以数组的方式存储。所以 JavaScript 的数组访问是很快的。

然而并不是所有数组都是「普通」的，比如可以定义一个很大很大的数组，里面都是空项。这种情况要是引擎也为其申请一块内存势必造成大量内存浪费。于是这种数组会进入「字典模式」，也就是使用散列表存储。

不仅是这种数组，普通的对象由于属性名是字符串，也无法直接计算成一个唯一的内存地址，所以它们都是散列表存储的。所以我才一直说 JavaScript 基本是一种基于散列表的语言。以前刚从其它编程语言转到 JavaScript 的时候觉得简直太爽了，可以随意地给对象添加属性（现在终于领悟到痛了）。

那么 JavaScript 引擎如何以 O(1) 的时间复杂度来访问对象的字符串属性呢？废话，散列表嘛。首先使用散列函数将字符串属性名转换成一个数值。所谓散列函数，就是用于将字符串转换成一个随机值的幂等函数。或者说就是有一个函数，它接收一个字符串参数，返回一个数值。只要给定的字符串相同则函数总是返回同样的值。具体的实现算法很多，各引擎也使用不同的散列函数，我就不具体指明了。有了一个固定的数值后，只要将这个数值计算成内存地址即可。可是散列函数仅仅是确保的幂等性，没有唯一性的保障。而且这个散列函数的计算结果会是很大的数值，而内存大小通常是给定的。通常会将数值通过取余之类的运算后再对应到内存地址中。那么这就意味着存在经过散列函数计算后会得出相同内存地址的情况，这就是散列冲突。

既然存在冲突的情况，那么这一段用于存储散列的内存就不是直接的存储，而是一个个链表（也称为「桶」）。于是即使两个字符串被计算成了同一结果也会先后存入这个指定的链表中。由于是链表，访问的性能当然会随之降低，但由于散列函数本身的随机性以及用于存储散列表的内存空间通常会视存储的数量而动态增加，所以发生冲突的概率并不高（除非人为地制造冲突，这是确实可能存在的情况）。于是最终可以将它的平均复杂度视为 O(1)。

JavaScript 与散列表的关系太太密切了，这其实也是个坑。虽然散列表的时间复杂度 O(1)，但比起直接的内存访问还是远不及的。C++ 之类的类实现都是可以直接 sizeof 出一个类的大小的，每个类用一段固定的内存去存储，无法动态地添加属性。虽然使用起来没 JavaScript 这么灵活，但在性能方面可以优化到极致。而 JavaScript 引擎虽然也能优化，但这个优化成本已经高破天际了。所以我现在觉得，散列是 JavaScript 的命，也是 JavaScript 的痛。虽然后面的规范也引入了 class 之类的东西，不过满满的都是糖啊。

对于 ES6 以及之后的规范，感觉 JavaScript 已经被玩坏。反正 JavaScript 肯定不是最好的编程语言嘛 .
本文来源于成都网站建设公司、成都网站设计制作公司与成都APP开发公司-桔子科技公司！
成都网站建设,成都网站设计,成都网站制作,成都网页设计，成都网站建设公司 ,成都网站设计公司, 成都网站制作公司，成都手机网站建设，手机网站建设，成都APP开发，APP开发，成都建网站，成都做网站，成都微信网站建设，成都微商城网站建设，成都商城网站建设，成都网络公司。

下一篇：网站制作：样式属性代码怎么缩写？上一篇：介绍JS和CSS资源加载标签的放置位置