技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> JavaScript --> JavaScript中真正的哈希映射(译)

JavaScript中真正的哈希映射(译)

浏览:1458次  出处信息

   在JavaScript中存储键值对的一个简单常见的方法是使用对象字面量。然而,对象字面量不是真正意义上的哈希映射,如果使用不当可能会构成潜在的隐患。虽然目前JavaScript可能没有提供原生的hashmap(至少不能跨浏览器),对象字面量如果没有隐患就能达到所需的功能也许是一个更好的选择。

对象字面量存在的问题

   对象字面的问题在于其原型链继承自Object原型上的对象和方法会破坏其维持键值的机制。以toString方法为例,使用in操作符检查同名属性会导致错误的结果:

var map = {};  
`toString` in map; // true

   上面的错误之所以会发生,是因为in操作符会从对象的原型链上查找继承属性。为了解决该问题,我们可以用hasOwnProperty方法来确定键值的存在性,因为该方法只检查对象本身的属性:

var map = {};  
map.hasOwnProperty('toString'); // false  

   上面的方法能够良好的工作,除非你遇到一个名为hasOwnProperty键。重写此方法将会因为尝试调用hasOwnProperty方法而导致意外的行为,根据新的值最有可能导致错误:

var map = {};  
map.hasOwnProperty = 'foo';  
map.hasOwnProperty('hasOwnProperty'); // TypeError  

   一个快速的修正方法是利用一个通用且没有被篡改的对象字面量,并在你指定的hashmap上下文中执行hasOwnProperty方法:

var map = {};  
map.hasOwnProperty = 'foo';  
{}.hasOwnProperty.call(map, 'hasOwnProperty'); // true

   尽管实际工作时没有任何问题,但对象字面量还是限制了它的使用。举个例子,每次你在for...in循环里面遍历一个对象的属性,你都要过滤其原型链中的属性:

var map = {};  
var has = {}.hasOwnProperty;

for (var key in map) {  
    if(has.call(map, key)) {
        // ...
    }
}

   一段时间后,可能会变得有点乏味。值得庆幸的是,有一个更好的办法。

空对象

   创建一个真正的哈希映射的秘诀就是避免原型,及其带来的包袱。我们可以利用ES5中引入的Object.create方法达到该目的。该方法的特别之处在于你可以给一个新对象明确定义原型。举个例子,用一个较复杂的方式定义一个简单对象字面量:

var obj = {};  
// 等价于
var obj = Object.create(Object.prototype);  

   除了能够定义一个你选择的原型,你也能够通过传入一个null放弃传入原型:

var map = Object.create(null);

map instanceof Object; // false  
Object.prototype.isPrototypeOf(map); // false  
Object.getPrototypeOf(map); // null  

   这些空对象对于哈希映射是理想的,因为缺少[[Prototype]]避免了命名冲突。由于该对象完全是空的,它会抵制任何形式的强制转换,试图这样做将导致一个错误:

var map = Object.create(null);  
map + ""; // TypeError: Cannot convert object to primitive value  

   空对象没有任何初始值或者字符串表现形式,因为空对象除了作为键值对的存储空间没有为任何其他事情做打算,简单又普通。

   注意hasOwnProperty方法在空对象中也消失了,这无关紧要,因为in操作符可以无异常的工作了:

var map = Object.create(null);  
'toString' in map; // false  

   更好的是,乏味的for...in循环变得更加简单。我们最终可以按其本身的意思写一个循环:

var map = Object.create(null);  
for (var key in map) {  
    // ...
}

   虽然存在差异,但对所有的意图和目的,它仍然表现得就像一个对象字面量。属性可以利用.或则[]访问,对象可以被序列化,且对象仍然可以使用上下文对象的原型方法:

var map = Object.create(null);

Object.defineProperties(map, {  
    'foo': {
        value: 1,
        enumerable: true
    },
    'bar': {
        value: 2,
        enumerable: false
    }
});

map.foo; // 1  
map['bar']; // 2

JSON.stringify(map); // {"foo": 1}

{}.hasOwnProperty.call(map, 'foo'); // true
{}.propertyIsEnumerable.call(map, 'bar'); // false

   甚至不同检查类型的方法将会告诉你从对象字面中期望得到什么:

var map = Object.create(null);  
typeof map; // object  
{}.toString.call(map); // [object Object]
{}.valueOf.call(map); // Object {}

   这一切使得空对象代替对象字面量变得简单,让他们很好地集成到一个现有的应用程序,而不会引起大范围的变化。

总结

   在简单的键值存储的背景下,使用空对象是对象字面量的有效替代方案,用明确的定义消除对象字面量的怪癖。对于更全面的数据结构,ES6将以Map和Set形式引入原生的hashmap。在此之前,甚至之后,你应该使用空对象满足你所有的基本哈希映射需求。

参考

建议继续学习:

  1. 一致性哈希算法及其在分布式系统中的应用    (阅读:7911)
  2. 分布式哈希和一致性哈希    (阅读:7634)
  3. 关于哈希map奇慢无比的原因定位    (阅读:3917)
  4. PHP哈希表碰撞攻击原理    (阅读:3981)
  5. 数据映射–平衡二叉有序树    (阅读:3409)
  6. 浅析Linux Kernel 哈希路由表实现(一)    (阅读:3171)
  7. Java Hash Algorithm Collision Practice (JAVA哈希算法冲突实践)    (阅读:3038)
  8. MySQL B+树索引和哈希索引的区别    (阅读:3045)
  9. Cuckoo Filter:设计与实现    (阅读:3036)
  10. 一致性哈希算法(consistent hashing)    (阅读:2937)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:iframe大小自适应
后一篇:正则表达式基础 >>
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1