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
投稿
猜你喜欢
- 导读排序算法可以称得上是我的盲点, 曾几何时当我知道Chrome的Array.prototype.sort使用了快速排序时, 我的内心是奔溃
- 本文实例讲述了javascript自动生成包含数字与字符的随机字符串的方法。分享给大家供大家参考。具体如下:这里主要用到Math.rando
- 本文实例讲述了Python实现的简单模板引擎功能。分享给大家供大家参考,具体如下:#coding:utf- 8__author__=&quo
- 根据我最近的一些实践以及在和一些读者进行关于HTML表格的使用问题沟通之后,决定写这篇文章。总的来说,我注意到由于误导性信息,他们对于tab
- 1. ORACLE 的解析器按照从右到左的顺序处理 FROM 子句中的表名,因此 FROM 子句中写在最后的表(基础表 driving ta
- 1、保存整个网络结构信息和模型参数信息:torch.save(model_object, './model.pth')直接加
- 前言康威生命游戏设计并不难,我的思路就是借助pygame进行外观的展示,最近一段时间的游戏项目都是使用pygame进行的,做起来比较顺利。内
- 本文实例讲述了php字符串函数 str类常见用法。分享给大家供大家参考,具体如下:str_split(string, leg);//将一个字
- asp之家注:asp中FSO组件的功能很强大,如果没有FSO很难想象ASP会变成什么样。对于学习asp编程的朋友一定会接触到FSO相关的操作
- 一、打开/关闭文件1、对文件操作时首先要打开文件,打开文件用 fopen()函数,语法是:fopen(filename,mode,inclu
- <?php $curDomain = $_SERVER['HTTP_HOST']; $strHTML = file_g
- 选项卡Tabs是Web中一种非常常用的功能。用户点击或悬浮对应的菜单项,能切换出对应的内容Bootstrap框架中的选项卡主要有两部分内容组
- 1、下载安装 python https://www.python.org/downloads/windows/web-based insta
- 数据准备数据集(JetRail高铁的乘客数量)下载.假设要解决一个时序问题:根据过往两年的数据(2012 年 8 月至 2014 年 8月)
- 详细参考:https://gitee.com/copperpeas/uniapp-paymentuniapp-payment介绍uniapp
- 有时候让了解放双手,让电脑来帮我们自动发一些我们想要发的消息,挺省力的,比如说白天写好了演讲稿,晚上要在群里进行文字演讲,那么我们就可以用脚
- 本文研究的主要是python+matplotlib实现动态绘制图片(交互式绘图)的相关内容,具体介绍和实现代码如下所示。最近在研究动态障碍物
- 当元素设置浮动(float)后会被移出文档流,相信大家都会经常遇到这样的问题。这问题的解决办法有N种之多,因为每种浏览器对CSS的解析各异,
- 本文实例为大家分享了python opencv识别图像轮廓的具体代码,供大家参考,具体内容如下要求:用矩形或者圆形框住图片中的云朵(不要求全
- 最近在看廖老师的python教程,在看到关于文件的操作时,廖老师的其中一段关于查找电脑里的python文件,突然想把之前写的python代码