在Javascript中实现伪哈希表

简介: 了解数据结构的人应该都听说过哈希表这种数据结构,它是一种典型的利用键值对存储并检索数据的一种非线性结构,又称散列表或杂凑法。在一般的线性表结构中,数据的相对位置是随机的,即数据和用于检索的关键字之间不存在确定的关系,检索数据时往往需要进行一系列的比较,最终找到要检索的数据,这种方法往往建立在循环比较的机制上,利用时间的代价节省了空间,实现了数据的存储和检索功能。

了解数据结构的人应该都听说过哈希表这种数据结构,它是一种典型的利用键值对存储并检索数据的一种非线性结构,又称散列表或杂凑法。在一般的线性表结构中,数据的相对位置是随机的,即数据和用于检索的关键字之间不存在确定的关系,检索数据时往往需要进行一系列的比较,最终找到要检索的数据,这种方法往往建立在循环比较的机制上,利用时间的代价节省了空间,实现了数据的存储和检索功能。而哈希表则使用键值对进行数据的存储,在数据的存储位置和它的关键字之间建立了一一对应的关系,从而使每个关键字和结构中的一个唯一的存储位置相对应,所以在检索数据时,只需要根据这个对应关系便可快速定位到要查找的数据。

    事实上,我们通常并不关心数据是如何存储的,而关心的是我们在使用数据的时候是否方便,例如对数据进行排序、查找、替换等操作,由于这种操作是贯穿在整个应用程序始终的,因此对效率的要求也就很高了。一般的高级语言,如C和C的变种,都提供了用于存储哈希表的数据结构,但在弱类型语言中,如javascript等脚本语言,本身并没有直接提供类似于哈希表的这种结构,不过我们可以从数组出发,按照哈希表的原理自己打造一个脚本语言专有的哈希表数据结构。

    我们知道,在数据中,可以通过下标直接定位到相应数据,也就是用于存储数据的空间,数组的这种特性本身就决定了它可以被用来实现哈希算法,不过在C语言中,数组的下标只能是从0开始的整数,而不能为其它类型的数据,但在javascript中,我们可以借用“对象”这个概念,按照数组的特性来模拟哈希算法。因为在javascript中,对象其实就是属性或方法的一个集合,于是我们可以构造一个Hashtable对象,它有key和value两个属性,自己编写代码来模拟一个完整的哈希表。下面是一段在javascript中实现哈希表的代码:

复制代码
1  function  Hashtable()  
2 
3     this ._hash  =  {}; 
4     this ._count  =   0
5     this .add  =   function (key, value)  
6    { 
7         if  ( this ._hash.hasOwnProperty(key))  return   false
8         else  {  this ._hash[key]  =  value;  this ._count ++ return   true ; } 
9    } 
10     this .remove  =   function (key) {  delete   this ._hash[key];  this ._count -- ; } 
11     this .count  =   function () {  return   this ._count; } 
12     this .items  =   function (key) {  if  ( this .contains(key))  return   this ._hash[key]; } 
13     this .contains  =   function (key) {  return   this ._hash.hasOwnProperty(key); } 
14     this .clear  =   function () {  this ._hash  =  {};  this ._count  =   0 ; } 
15  }
复制代码

    实现起来很简单,我们在function中定义了一个_hash对象,该对象有一个属性key,我们可以给这个属性赋值,hasOwnProperty方法是javascript提供的方法,用于返回指定的对象中是否包含某个属性。同时我们在该function中还定义了一个_count对象,用于记录Hashtable中的数据个数,因为我们不想每次获取Hashtable中的数据个数时都要通过一个内置的循环来计数,这样开销就会小一些,前面说了,哈希算法的一个基本特性就是效率高。delete语句在javascript中用于销毁一个对象。

    下面是使用该Hashtable的一些例子:

复制代码
 1  var  hashCompany  =   new  Hashtable();
 2 
 3  // 向Hashtable中添加键值对
 4  function  FillData(arr) {
 5      hashCompany.clear();
 6 
 7       for  ( var  i  =   0 ; i  <  arr.length  -   1 ; i ++ ) {
 8           if  (arr[i]  !=   "" ) {
 9              t  =  arr[i].split( " ` " );
10               if  (t.length  >   2 ) {
11                   if  ( ! hashCompany.contains(t[ 0 ].trim())) {
12                      hashCompany.add(t[ 0 ].trim(), t[ 1 ]);
13                  }
14              }
15          }
16      }
17  }
18 
19  // 遍历Hashtable并取出值
20  function  GetDataFromHash() {
21       var  s;
22       if  (hashCompany.count  >   0 ) {
23           for  ( var  i  in  hashCompany._hash) {
24              s  +=  i  +   " | " ;
25          }
26      }
27 
28       if  (s.length  >   0 ) {
29          s  =  s.substring( 0 , s.length  -   2 );
30      }
31 
32       return  s;
33  }
复制代码
    代码比较简单,这里就不再多加说明了,其中用到了一个trim函数,下面补上。
// 采用正则表达式去除字符串两端的空格,匿名函数用于扩展String对象的方法
String.prototype.trim  =   function () {  return   this .replace( / (^\s*)|(\s*$) / g,  "" ); }

    哈希表在代码中使用频率很高,灵活使用哈希表可以简化代码并提供诸多方便,尤其是在存储类似于数组的数据并且希望之后能够方便检索。将代码保存于此,以备日后使用。


本文转自Jaxu博客园博客,原文链接:http://www.cnblogs.com/jaxu/archive/2009/03/12/1409395.html,如需转载请自行联系原作者


相关文章
|
JavaScript 前端开发
javascript深拷贝和浅拷贝以及实现方法(推荐)
javascript深拷贝和浅拷贝以及实现方法(推荐)
569 0
javascript深拷贝和浅拷贝以及实现方法(推荐)
|
JavaScript 算法 前端开发
【前端算法】JS实现数字千分位格式化
JS实现数字千分位格式化的几种思路,以及它们之间的性能比较
299 1
|
存储 前端开发 算法
一行代码解决LeetCode实现 strStr()使用JavaScript解题|前端学算法
一行代码解决LeetCode实现 strStr()使用JavaScript解题|前端学算法
143 0
一行代码解决LeetCode实现 strStr()使用JavaScript解题|前端学算法
|
存储 机器学习/深度学习 JavaScript
JS 你最少用几行代码实现深拷贝?
JS 你最少用几行代码实现深拷贝?
JS 你最少用几行代码实现深拷贝?
|
JavaScript 前端开发 算法
JavaScript实现一段时间之后关闭广告
简介:通过JavaScript实现在一段时间之后,广告消失。
105 0
JavaScript实现一段时间之后关闭广告
|
JavaScript 前端开发 算法
JS实现鼠标悬停变色
本文实现的是利用JS实现当鼠标悬停在表格上的时候,表格发生变色。 CSS渲染 JS逻辑 `
186 0
JS实现鼠标悬停变色
|
JavaScript 前端开发 数据安全/隐私保护
JS实现关闭图片窗口
通过事件的绑定来实现,关闭二维码的效果。
134 0
JS实现关闭图片窗口
|
前端开发 JavaScript Windows
js实现body背景图自动扩缩 光靠css几乎无法实现这样的效果
js实现body背景图自动扩缩 光靠css几乎无法实现这样的效果
166 0
js实现body背景图自动扩缩 光靠css几乎无法实现这样的效果
|
存储 JavaScript
js实现多选、全选、反选、取消选择(篇一)
js实现多选、全选、反选、取消选择(篇一)
358 0
js实现多选、全选、反选、取消选择(篇一)
|
JavaScript 前端开发
利用JavaScript实现二级联动
利用JavaScript实现二级联动 要实现JavaScript二级联动效果,首先要确定需要哪些技术: 二维数组 for in循环 new Option(text,value,true,true) add(option,null) onchange() 表单事件 HTML代码: &lt;!-- &lt;input type=&quot;text&quot; id=&quot;text&quot;&gt; --&gt; 请选择省份: &lt;select name=&quot;&quot; id=&quot;provinces&quot;&gt; &lt;!-- &lt;option value=&quot;江苏省&quot;&gt;江苏省&lt;/option&gt;