JavaScript
搜索
分类

JS模拟实现哈希表及应用详解

作者：Wayne-Zhu 时间：2024-04-23 09:25:52　

本文实例讲述了JS模拟实现哈希表及应用。分享给大家供大家参考，具体如下：

在算法中，尤其是有关数组的算法中，哈希表的使用可以很好的解决问题，所以这篇文章会记录一些有关js实现哈希表并给出解决实际问题的例子。

说明： 这篇文章所写并不是真正意义的哈希表，只是与哈希表的使用有相似之处。

第一部分：相关知识点

属性的枚举:


var person = {
 name: "zzw",
 sex: "Male",
 age: 21
};
for (var prop in person) {
 console.log(prop + " ",person[prop]);
}

输出：

JS模拟实现哈希表及应用详解

即对于对象而言，我们可以使用for in来枚举对象的属性。

属性的删除：


var person = {
 name: "zzw",
 sex: "Male",
 age: 21
};
var ifRemove = delete person.name;
for (var prop in person) {
 console.log(prop + " ",person[prop]);
}
console.log(ifRemove);

对象的属性可以通过 delete 来删除，并且会有一个返回值。 如下：

JS模拟实现哈希表及应用详解

注意： 一般只有对象的属性才可以删除，而变量是不能删除的，如：


var x = 1;
console.log(delete x);

这时打印台输出false，因为变量是不可被删除的。

检测属性是否存在：


var person = {
 name: "zzw",
 sex: "Male",
 age: 21
};
console.log("age" in person);
console.log("someOther" in person);

前者返回true，后者返回false。 即我们可以使用in来确定一个对象是否含有该属性。

属性的添加：


var person = {
 name: "zzw",
 sex: "Male",
 age: 21
};
person["school"] = "XJTU";
console.log(person);

属性的添加非常简单，如上所示，最终打印出来的对象是包含 school 属性的。

第二部分: 使用js实现哈希表

下面是通过构造函数得到一个哈希表，在使用时只需实例化即可，且下面的功能较为丰富，在实际问题中，我们可以选择性的使用 。


// 创建构造函数HashTable
function HashTable() {
   // 初始化哈希表的记录条数size
   var size = 0;
   // 创建对象用于接受键值对
   var res = {};
   // 添加关键字，无返回值
   this.add = function (key, value) {
     //判断哈希表中是否存在key，若不存在，则size加1，且赋值
     if (!this.containKey(key)) {
       size++;
     }
     // 如果之前不存在，赋值； 如果之前存在，覆盖。
     res[key] = value;
   };
   // 删除关键字, 如果哈希表中包含key，并且delete返回true则删除，并使得size减1
   this.remove = function (key) {
     if (this.containKey(key) && (delete res[key])) {
       size--;
     }
   };
   // 哈希表中是否包含key，返回一个布尔值
   this.containKey = function (key) {
     return (key in res);
   };
   // 哈希表中是否包含value，返回一个布尔值
   this.containValue = function (value) {
     // 遍历对象中的属性值，判断是否和给定value相等
     for (var prop in res) {
       if (res[prop] === value) {
         return true;
       }
     }
     return false;
   };
   // 根据键获取value,如果不存在就返回null
   this.getValue = function (key) {
     return this.containKey(key) ? res[key] : null;
   };
   // 获取哈希表中的所有value, 返回一个数组
   this.getAllValues = function () {
     var values = [];
     for (var prop in res) {
       values.push(res[prop]);
     }
     return values;
   };
   // 根据值获取哈希表中的key，如果不存在就返回null
   this.getKey = function (value) {
     for (var prop in res) {
       if (res[prop] === value) {
         return prop;
       }
     }
     // 遍历结束没有return，就返回null
     return null;
   };
   // 获取哈希表中所有的key,返回一个数组
   this.getAllKeys = function () {
     var keys = [];
     for (var prop in res) {
       keys.push(prop);
     }
     return keys;
   };
   // 获取哈希表中记录的条数，返回一个数值
   this.getSize = function () {
     return size;
   };
   // 清空哈希表，无返回值
   this.clear = function () {
     size = 0;
     res = {};
   };
}

第三部分： 应用实例

问题：给定一个整型的数组（无序），找出其中的两个数使得其和为某个指定的值，并返回这两个数的下标（数组下标从0开始），假设数组元素的值各不相同。

实现如下：


<!DOCTYPE html>
<html lang="en">
<head>
 <meta charset="UTF-8">
 <title>哈希表的使用</title>
</head>
<body>
 <script>
 function queryIndex(arr, result) {
   var hashTable = new HashTable();
   var arrLength = arr.length;
   var sub = [];
   for (var i = 0; i < arrLength; i++) {
     // 扫描一遍，存储下标和值
     hashTable.add(i, arr[i]);
   }
   for (var j = 0; j < arrLength; j++) {
     if (hashTable.containValue(result - arr[j]) && result !== 2*arr[j]) {
       // 获取两个下标，跳出循环
       sub.push(j);
       var antherIndex = Number(hashTable.getKey(result - arr[j]));
       sub.push(antherIndex);
       break;
     }
   }
   if (sub.length !== 0) {
     return sub;
   } else {
     return -1;
   }
 }
 console.log(queryIndex([1,5,7,3,8], 15)); // 2, 4
 console.log(queryIndex([8,18,28,12,29,17], 46)); // 2, 4
 console.log(queryIndex([8,18,28,12,29,17], 2)); // -1
  // 创建构造函数HashTable
 function HashTable() {
   // 初始化哈希表的记录条数size
   var size = 0;
   // 创建对象用于接受键值对
   var res = {};
   // 添加关键字，无返回值
   this.add = function (key, value) {
     //判断哈希表中是否存在key，若不存在，则size加1，且赋值
     if (!this.containKey(key)) {
       size++;
     }
     // 如果之前不存在，赋值； 如果之前存在，覆盖。
     res[key] = value;
   };
   // 删除关键字, 如果哈希表中包含key，并且delete返回true则删除，并使得size减1
   this.remove = function (key) {
     if (this.containKey(key) && (delete res[key])) {
       size--;
     }
   };
   // 哈希表中是否包含key，返回一个布尔值
   this.containKey = function (key) {
     return (key in res);
   };
   // 哈希表中是否包含value，返回一个布尔值
   this.containValue = function (value) {
     // 遍历对象中的属性值，判断是否和给定value相等
     for (var prop in res) {
       if (res[prop] === value) {
         return true;
       }
     }
     return false;
   };
   // 根据键获取value,如果不存在就返回null
   this.getValue = function (key) {
     return this.containKey(key) ? res[key] : null;
   };
   // 获取哈希表中的所有value, 返回一个数组
   this.getAllValues = function () {
     var values = [];
     for (var prop in res) {
       values.push(res[prop]);
     }
     return values;
   };
   // 根据值获取哈希表中的key，如果不存在就返回null
   this.getKey = function (value) {
     for (var prop in res) {
       if (res[prop] === value) {
         return prop;
       }
     }
     // 遍历结束没有return，就返回null
     return null;
   };
   // 获取哈希表中所有的key,返回一个数组
   this.getAllKeys = function () {
     var keys = [];
     for (var prop in res) {
       keys.push(prop);
     }
     return keys;
   };
   // 获取哈希表中记录的条数，返回一个数值
   this.getSize = function () {
     return size;
   };
   // 清空哈希表，无返回值
   this.clear = function () {
     size = 0;
     res = {};
   };
 }
 </script>
</body>
</html>

在实际的使用过程中，我们可以先写出主要的功能，然后有需要再添加。

希望本文所述对大家JavaScript程序设计有所帮助。

来源：http://www.cnblogs.com/zhuzhenwei918/p/6658260.html

标签：JS,哈希表
0
投稿

猜你喜欢

  • Python 读取千万级数据自动写入 MySQL 数据库

    2023-11-08 09:25:47

  • Python中处理时间的几种方法小结

    2021-03-15 17:58:33

  • python遍历文件目录、批量处理同类文件

    2021-10-19 14:58:12

  • 微信小程序有旋转动画效果的音乐组件实例代码

    2024-05-02 16:11:35

  • 用DW8制作网页中常用的过度效果

    2007-10-16 12:56:00

  • Golang中互斥锁和读写互斥锁原理及示例代码

    2024-05-29 22:06:52

  • TensorFlow中tf.batch_matmul()的用法

    2022-06-06 10:33:37

  • Python实现常见的回文字符串算法

    2022-07-10 10:32:29

  • 浅析webpack-bundle-analyzer在vue-cli3中的使用

    2024-05-28 16:09:50

  • Python实现备份MySQL数据库的方法示例

    2024-01-27 18:20:04

  • python实现求最长回文子串长度

    2022-09-29 13:56:32

  • MySQL使用外键实现级联删除与更新的方法

    2024-01-25 19:52:12

  • “您无权查看该网页”的原因和解决方法

    2008-03-24 16:57:00

  • 可编辑下拉框的2种实现方式

    2024-04-22 13:08:08

  • 从ASP过渡到ASP.net遗留的二十个积习

    2024-06-05 09:26:33

  • Python读取指定日期邮件的实例

    2023-05-28 17:20:01

  • 如何解决django配置settings时遇到Could not import settings 'conf.local'

    2021-07-23 13:31:57

  • asp 实现的冒泡排序程序

    2011-03-25 11:13:00

  • JavaScript的2008[译]

    2009-02-20 13:49:00

  • python实现DNS正向查询、反向查询的例子

    2022-10-29 07:18:55
    • asp之家 网络编程 m.aspxhome.com