在Javascript哈希表构建Javascript的一个哈希表的实现

Javascript是一种基于原型的面向对象语言。在JavaScript中，所有非标量对象表现为关联数组，即从属性键到值的映射。键和值可以是标量，对象或函数。本教程演示如何在这些本机对象周围提供哈希表封装，避免踩入JavaScript对象的内置属性，从而使其更加一致。

介绍

哈希表是一个的置换关联数组（即名称=>值对）。如果你使用PHP，那么你已经非常熟悉这种类型的数据结构，因为所有的PHP数组都是关联的。（这就是我变得熟悉他们）。

在JavaScript中，所有非标量对象表现为关联数组。对象可以使用其他对象作为键。但是，不跟踪关联数组的长度（如基于索引的数组），并且存在键可能与内置成员（例如添加到对象原型的那些）冲突的可能性以及自定义成员，例如长度属性或方便方法。我们将探索一种可以避免这些缺点的方法。

JavaScript中的关联数组（哈希表）的一个简单示例如下：

var h = new Object（）; // or just {}
h ['one'] = 1;
h ['two'] = 2;
h ['three'] = 3;//显示存储的值
for（var k in h）{//使用hasOwnProperty过滤掉Object.prototype中的键if（h.hasOwnProperty（k））{alert（'key is：'+ k +'，value is：'+ h [k]）;}}
}}

提示： 随意更换的console.log（），如果它是由您的浏览器（Chrome，火狐与萤火虫等）支持的警报（）。

正如在PHP中，'foreach'构造用于运行数组，为每个key => value对做一些事情。但是如果我们想知道大小怎么办？

alert（'hash table'size + h.length）;

嗯。对length属性的引用给出了“未定义”的某种意想不到的值。这是因为在Javascript中，当添加新属性（键）时，对象的length属性不会增加（这意味着它的行为不像哈希表）。

基础

在简要讨论基本面之后，我们将开始关注核心问题。在JavaScript中，每个非标量变量都是一个对象。好吧，这是什么意思？基本上，这意味着它有一个构造函数，方法和属性。属性只是一个变量，由对象拥有，因此是该对象的本地变量。使用以下语法访问属性：

h.one

其中一个是财产和'。'。符号表示我们正在谈论对象obj的属性。它也可以以相同的方式分配：

h.one = 1;

上述示例可以替代地执行为：

for（var k in h）{if（h.hasOwnProperty（k））{alert（'key is：'+ k +'，value is：'+ eval（'h。'+ k））;}}
}}

警告： 我们正在使用的eval（）这里只是为了演示表明，直接财产引用（obj.one）产生相同的结果在括号标记（OBJ ['一']）。

还可以向类型为数组的对象添加属性，该对象将分配与数组的索引值和对象的成员混合。

var a = new Array（）; // or just []
a [0] = 0
a ['one'] = 1;
a ['two'] = 2;
a ['three'] = 3;for（var k in a）{if（a.hasOwnProperty（k））{alert（'key is：'+ k +'，value is：'+ a [k]）;}}
}}
alert（a.length）;

奇怪的是，长度报告为1，但是打印了四个键。这是因为我们正在处理数组元素和底层对象。这只是JavaScript闪烁的灵活性（并使我们困惑）。方括号符号（即，[]）被重载。当键是数字时，我们将元素分配给数组。否则，我们将向对象分配成员。

由于每个对象都有使用这种非常相同的语法（例如长度和构造函数）访问的默认属性，因此请考虑散列中的键与这些属性之一相同的情况。这种情况突出了JavaScript中关联数组的基本问题。现在应该清楚为什么当我们创建一个关联数组数据结构时，length属性没有设置。通过添加非整数键来处理对象作为关联数组，您将操作底层JavaScript对象，该对象不会被长度跟踪（长度仅适用于索引的键值）。

构造一个HashTable类

在Javascript中，我们可以创建自己的类。因此，我们要做的是创建一个可以维护关联数组的HashTable（）类，但是从数据键中分离API方法（没有冲突）。

你可能会想，“好吧，所以我们做一个类，但是我们如何摆脱冲突的属性问题？很容易，我们做一个属性，它本身是一个关联数组，称为项目。然后，我们可以使用任何我们想要的键，并将数组的数据存储在其他属性中。诀窍是将关联数组的数据部分移到类的属性内部。以下列表是HashTable（）对象定义：

function HashTable（obj）
{this.length = 0;this.items = {};for（var p in obj）{if（obj.hasOwnProperty（p））{this.items [p] = obj [p];this.length ++;}}}}
}}

注： 如果您使用的是已经定义了这个功能的JavaScript库，您应该对此类选择另一名称。

让我们分解一下。右击蝙蝠，我们创建一个length属性，它将从0开始。此外，我们在构造函数中接受一个对象。接下来，我们使用传递给构造函数的对象的key => value对来填充内部项，并相应地增加长度。创建HashTable（）对象的典型调用将使用以下语法：

var h = new HashTable（{one：1，two：2，three：3，“i'm no 4”：4}）;

已经必须很高兴看到一个结构...这么容易添加数据到结构！

现在，正如你可能还记得，我们不能在关联数组中有任何属性或方法（因为它们可能与数据的键冲突），所以除了一个“foreach”结构之外，我们不能做我们的关联数组。现在他们是分开的，我们有能力添加方法和属性，让我们开始吧！

function HashTable（obj）
{this.length = 0;this.items = {};for（var p in obj）{if（obj.hasOwnProperty（p））{this.items [p] = obj [p];this.length ++;}}}}this.setItem = function（key，value）{var previous = undefined;if（this.hasItem（key））{previous = this.items [key];}}else {this.length ++;}}this.items [key] = value;return previous;}}this.getItem = function（key）{return this.hasItem（key）？this.items [key]：undefined;}}this.hasItem = function（key）{return this.items.hasOwnProperty（key）;}}this.removeItem = function（key）{if（this.hasItem（key））{previous = this.items [key];this.length--;删除this.items [key];return previous;}}else {return undefined;}}}}this.keys = function（）{var keys = [];for（var k in this.items）{if（this.hasItem（k））{keys.push（k）;}}}}返回键;}}this.values = function（）{var values = [];for（var k in this.items）{if（this.hasItem（k））{values.push（this.items [k]）;}}}}返回值;}}this.each = function（fn）{for（var k in this.items）{if（this.hasItem（k））{fn（k，this.items [k]）;}}}}}}this.clear = function（）{this.items = {}this.length = 0;}}
}}

注： 另外，您也可以直接引用构造函数参数，OBJ，而不是将其复制到成员属性，物品。随你便。

让我们通过一些练习来放置HashTable（）。

var h = new HashTable（{one：1，two：2，three：3，“i'm no 4”：4}）;alert（'original length：'+ h.length）;
alert（'key of key“one”：'+ h.getItem（'one'））;
alert（'has key“foo”？'+ h.hasItem（'foo'））;
alert（'key'foo'：'+ h.setItem（'foo'，'bar'）的上一个值）;
alert（'length after setItem：'+ h.length）;
alert（'key of key“foo”：'+ h.getItem（'foo'））;
alert（'key of key“i'm no 4”：'+ h.getItem（“i'm no 4”））;
h.clear（）;
alert（'length after clear：'+ h.length）;

这些调用应该产生以下输出：

• 原长：4
• 键“1”的值：1
• 有键“foo”？假
• 键的前一个值“foo”：未定义
• setItem之后的长度：5
• 键值“foo”：bar
• 键“i'm no 4”的值：4
• 清除后长度：0

让我们来看看这一切是如何工作的。

了解实现

我们现在有很多有用的方法！在JavaScript中，任何变量都可以是对函数的引用，所以要向类中添加方法，最简单的方法是只需编写函数，然后将其分配给类中的属性。好吧，所以你可能会想，“但我不能有相同的属性名称作为方法名称。没错，JavaScript对象的另一个限制是方法是属性。但是，在大多数情况下，它不会是一个问题，因为方法名称应该是'行为'名称，属性应该是'状态'名称。

为了访问底层项目，我们添加了方法'setItem'，'getItem'，'hasItem'，'keys'，'values'来设置和检索数据以及'remoteItem'和'clear'方法来刷新数据。现在我们将每个键=>值对作为一个项目。不是为了完整性添加'getItem'。你可以直接访问items属性直接通过键检索值（这将稍快）。'hasItem'方法使用'hasOwnProperty'方法来检查一个键是否属于items对象，而不是已经添加到Object原型（这是由诸如prototype.js这样的库完成的）的函数。

我们的方法的最重要的作用是保持length属性是最新的。我们可以看到，它需要大量的工作，我们的工作，我们可以使用这些好的方法，以轻松工作与我们的哈希。就像Java中的HashTable一样，返回值是对被替换的HashTable（）中的项的引用：

alert（“Previous value：”+ h.setItem（'foobar'，'hey'））;

如果你现在想像HashTable（）一样重复遍历对象，你可以使用几种不同的方法：

迭代项，过滤掉从Object.prototype继承的成员：

for（var k in h.items）{if（h.hasItem（k））{alert（'key is：'+ k +'，value is：'+ h.items [k]）;}}
}}

使用每个迭代条目：（注意，在这种情况下我们不必使用hasOwnProperty）

h.each（function（k，v）{alert（'key is：'+ k +'，value is：'+ v）;
}）;

迭代键集合：

for（var i = 0，keys = h.keys（），len = keys.length; i <len; i ++）{alert（'key is：'+ keys [i] +'，value is：'+ h.getItem（keys [i]））;
}}

迭代值的集合：

for（var i = 0，v = h.values（），len = v.length; i <len; i ++）{alert（'value is：'+ v [i]）;
}}

你还可以找到哈希表的大小：

alert（'hash table的大小：'+ h.length）;

摘要

现在你应该回??家，开始在你写的每个JavaScript代码中使用它，因为它最终使得JavaScript中的关联数组很有用。它非常适合存储配置数据，从函数返回多个值，列表继续。

虽然这篇文章仍然作为背景材料是有用的，我强烈建议采用更加成熟的JavaScript库，如jQuery的，它提供了更多的良好测试方便的API，包括jQuery.each（） ，这是一个通用的迭代函数，可用于以无缝地迭代对象和数组。

归因

感谢彼得·贝利这个原来的文章中指出了错误，并建议如何改进它。我已经包括他的反馈下面逐字。我已经尽了最大努力将他推荐的更改整合到文章中。他是正确的，但是，这篇文章实际上只是在JavaScript中向关联数组添加一个length属性，并允许您添加不与键名称冲突的其他方法，简单和简单。

• 你在第一个例子中误导了读者，从一个新的Array（）开始，好像对下一步有什么意义。第一行也可以读取“var myArray = new Boolean（）;” 关于多少不相关的数组有例子。< - 我改变了使用Object（）的例子。
• 你得到的对象迭代都错了。for..in循环需要检查obj.hasOwnProperty（）。有关摘要http://javascript.crockford.com/survey.html，请参阅这里的“对象”部分。< - 我已经包括使用hasOwnProperty（）和解释为什么它是必要的。
• 此外，eval（）的用法是完全不合理的，因为javascript对象支持括号符号。myArray [i]会正常工作。我发现这是特别麻烦，因为你在页面上的注释建议读者，他们“有”使用eval（），可能是最危险的功能在javascript核心。更何况你在前面的例子中使用这个确切的语法！（myArray ['one'] = 1与myArray.one = 1相同）。< - 我添加了一个注意，这纯粹是为了演示的目的。
• 不是所有的变量都是对象！有实际的标量类型。它只是觉得他们都是对象，因为它们基本上实现为泛型。< - 我澄清，我在谈论非标量对象。
• 也许我最大的问题是，文章几乎不需要存在。JavaScript对象*是*哈希表！Hash类提供的唯一真正的实用程序是大小确定。其他（设置，获取，有，删除）是本机可用。

感谢彼得！

---