JS模拟实现哈希表及应用详解
作者：Wayne-Zhu 发布时间：2024-04-23 09:25:52
标签：JS,哈希表
本文实例讲述了JS模拟实现哈希表及应用。分享给大家供大家参考，具体如下：
在算法中，尤其是有关数组的算法中，哈希表的使用可以很好的解决问题，所以这篇文章会记录一些有关js实现哈希表并给出解决实际问题的例子。
说明： 这篇文章所写并不是真正意义的哈希表，只是与哈希表的使用有相似之处。
第一部分：相关知识点
属性的枚举:
var person = {
name: "zzw",
sex: "Male",
age: 21
};
for (var prop in person) {
console.log(prop + " ",person[prop]);
}
输出：
即对于对象而言，我们可以使用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 来删除，并且会有一个返回值。 如下：
注意： 一般只有对象的属性才可以删除，而变量是不能删除的，如：
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
0
投稿猜你喜欢
- 场景：按照github文档上启动一个flask的app，默认是用5000端口，如果5000端口被占用，启动失败。样例代码：from flas
- 一个网站程序，在添加新闻时出现错误以下是错误提示： Microsoft OLE DB Provide
- 前言:看似简单的任务，往往隐藏陷阱！一个常见的任务是在一个列表上迭代，并根据条件删除一些元素。本文将展示如何完成该任务的不同方法，同时展示一
前言工作中经常会使用到将宽表变成窄表，例如这样的形式编号编码单位1单位2单位3单位4.................. &nbs- 本文实例讲述了Laravel框架实现定时发布任务的方法。分享给大家供大家参考，具体如下：背景：需要每隔一小时新建一个任务http://lar
- Mysql常用显示命令1、显示当前数据库服务器中的数据库列表：mysql> SHOW DATABASES;注意：mysql库里面有MY
- 本文实例讲述了Python实现堆排序的方法。分享给大家供大家参考，具体如下：堆排序作是基本排序方法的一种，类似于合并排序而不像插入排序，它的
- 用下列代码可在控制弹出NTLM验证窗口：<％ Response.Status = "401 Unauthorized&quo
- 数据结构和算法算法：解决问题的方法和步骤评价算法的好坏：渐近时间复杂度和渐近空间复杂度。渐近时间复杂度的大O标记：- 常量时间复杂度 - 布
- 首先我们需要几个包：requests, lxml, bs4, pymongo, redis1. 创建爬虫对象，具有的几个行为：抓取页面，解析
- 本文实例讲述了Python单向链表和双向链表原理与用法。分享给大家供大家参考，具体如下：链表是一种数据结构，链表在循环遍历的时候效率不高，但
- 本篇文章将介绍：xlwt 常用功能xlrd 常用功能xlutils 常用功能xlwt写Excel时公式的应用xlwt写入特定目录（路径设置）
- 一、下载MySQL登录MySQL官网下载MSI Installer：点击“Dnownload”点击“No thanks, just star
- python读取Excel表格文件，例如获取这个文件的数据python读取Excel表格文件，需要如下步骤：1、安装Excel读取数据的库-
- 需求：用户输入运算表达式，终端显示计算结果代码：# ！/usr/bin/env/ python3# -*- coding: utf-8 -*
- MySQL 8.0.27 下载、安装与配置 超详细教程（Windows64位），供大家参考，具体内容如下1.官网下载1.下载地址：MySQL
- 起因引发原因：门店需求新增自提门店，自提门店需要加自提点图片，在渠道店上引入了图片地址img_url 的字段，字段值定义为text not
- 在mysql安装目录的bin下, 运行mysql --install MYSQL5查看服务中, 会多一个MYSQL5的服务XAMPP的控制面
- 一个写给别人的小代码顺便也贴上来这是一个滑动展示用的小容器通过鼠标移动和离开触发滑动效果<!DOCTYPE html PUBLIC &
- 本文实例讲述了Python时间的精准正则匹配方法。分享给大家供大家参考，具体如下：要用正则表达式精准匹配时间，其实并不容易方式一:>&
