本篇文章给大家带来了关于javascript中的相关知识，其中主要介绍了关于JavaScript怎么实现哈希表的相关问题，对最终数据插入的数组进行整个结构的封装，得到的就是哈希表，希望对大家有帮助。
相关推荐：javascript学习教程
哈希表通常是基于数组进行实现的，但是相对于数组，它有很多优势：
- 它可以提供非常快速的插入-删除-查找操作
- 无论多少数据，插入和删除需要接近常量的时间：即O(1)的时间级。实际上，只需要几个机器指令即可完成。
- 哈希表的速度比树还要快，基本可以瞬间查找到想要的元素
- 哈希表相对于树来说编码要容易很多
哈希表相对于数组的一些不足：
- 哈希表中的数据是没有顺序的，所以不能以一种固定的方式来遍历其中的元素
- 通常情况下，哈希表中的key是不允许重复的，不能放置相同的key，用于保存不同的元素
- 空间利用率不高，底层使用的是数组，并且某些单元格没有被利用
哈希表是什么？
- 哈希表并不好理解，不像数组、链表和树等可通过图形的形式表示其结构和原理。
- 哈希表的结构就是数组，但它神奇之处在于对下标值的一种变换，这种变换我们可以称之为哈希函数，通过哈希函数可以获取HashCode。
哈希表的一些概念
- 哈希化：将大数字转化成数组范围内下标的过程，称之为哈希化；
- 哈希函数：我们通常会将单词转化成大数字，把大数字进行哈希化的代码实现放在一个函数中，该函数就称为哈希函数；
- 哈希表：对最终数据插入的数组进行整个结构的封装，得到的就是哈希表。
仍然需要解决的问题：
- 哈希化过后的下标依然可能重复，如何解决这个问题呢？这种情况称为冲突，冲突是不可避免的，我们只能解决冲突。
解决冲突的方法
解决冲突常见的两种方案：
- 方案一：链地址法（拉链法）；
如下图所示，我们将每一个数字都对10进行取余操作，则余数的范围0~9作为数组的下标值。并且，数组每一个下标值对应的位置存储的不再是一个数字了，而是存储由经过取余操作后得到相同余数的数字组成的数组或链表。
总结：链地址法解决冲突的办法是每个数组单元中存储的不再是单个数据，而是一条链条，这条链条常使用的数据结构为数组或链表，两种数据结构查找的效率相当（因为链条的元素一般不会太多）。
- 方案二：开放地址法；
开放地址法的主要工作方式是寻找空白的单元格来放置冲突的数据项。
据探测空白单元格位置方式的不同，可分为三种方法：
- 线性探测
- 二次探测
- 再哈希法
可以看到随着装填因子的增加，平均探测长度呈线性增长，较为平缓。在开发中使用链地址法较多，比如Java中的HashMap中使用的就是链地址法。
优秀的哈希函数
哈希表的优势在于它的速度，所以哈希函数不能采用消耗性能较高的复杂算法。提高速度的一个方法是在哈希函数中尽量减少乘法和除法。
性能高的哈希函数应具备以下两个优点：
- 快速的计算；
- 均匀的分布；
快速计算
霍纳法则：在中国霍纳法则也叫做秦九韶算法，具体算法为：
求多项式的值时，首先计算最内层括号内一次多项式的值，然后由内向外逐层计算一次多项式的值。这种算法把求n次多项式f(x)的值就转化为求n个一次多项式的值。
变换之前：
- 乘法次数：n（n+1）/2次；
- 加法次数：n次；
变换之后：
- 乘法次数：n次；
- 加法次数：n次；
如果使用大O表示时间复杂度的话，直接从变换前的O(N2)降到了O(N)。
均匀分布
为了保证数据在哈希表中均匀分布，当我们需要使用常量的地方，尽量使用质数；比如：哈希表的长度、N次幂的底数等。
Java中的HashMap采用的是链地址法，哈希化采用的是公式为：index = HashCode（key）&（Length-1）
即将数据化为二进制进行与运算，而不是取余运算。这样计算机直接运算二进制数据，效率更高。但是JavaScript在进行叫大数据的与运算时会出现问题，所以以下使用JavaScript实现哈希化时还是采用取余运算。
function HashTable() {
// 存放相关的元素
this.storage = [];
// 存了多少数据
this.count = 0;
// 用于标记数组中一共存放了多少个元素
this.limit = 7;
/*
设计哈希函数
①将字符串转成比较大的数字
②将大的数字hashCode压缩到数组范围之内
*/
HashTable.prototype.hashFunction = function (str, size) {
var hashCode = 0;
//秦九韶算法（霍纳算法）
// 哈希表的长度、N次幂的底数等尽量选取质数
for (var i = 0; i < str.length; i++) {
// 34 43 43 都是常用的底数
hashCode = 37 * hashCode + str.charCodeAt(i);
}
return hashCode % size;
};
// 插入和修改方法
HashTable.prototype.put = function (key, value) {
// 根据key获取对应的index
var index = this.hashFunction(key, this.limit);
// 根据index取出对应的bucket
var bucket = this.storage[index];
if (bucket == null) {
bucket = [];
this.storage[index] = bucket;
}
// 判断是否是修改数据
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i];
if (tuple[0] === key) {
tuple[1] == value;
return;
}
}
// 不是修改数据就添加数据
bucket.push([key, value]);
this.count++;
// 扩容
if (this.count > this.limit * 0.75) {
var newLimit = this.limit * 2;
var prime = this.getPrime(newLimit);
this.resize(prime);
}
};
// 获取
HashTable.prototype.get = function (key) {
var index = this.hashFunction(key, this.limit);
var bucket = this.storage[index];
if (bucket == null) return null;
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i];
if (tuple[0] === key) {
value == tuple[1];
return value;
}
}
return null;
};
// 删除
HashTable.prototype.remove = function (key) {
var index = this.hashFunction(key, this.limit);
var bucket = this.storage[index];
if (bucket == null) return null;
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i];
if (tuple[0] === key) {
// 从i开始删除一个
bucket.splice(i, 1);
this.count--;
// 缩容
if (this.limit > 7 && this.count < this.limit * 0.25) {
var newLimit = Math.floor(this.limit / 2);
var prime = this.getPrime(newLimit);
this.resize(prime);
}
return tuple[1];
}
}
return null;
};
// 扩容
HashTable.prototype.resize = function (newLimit) {
var oldStorage = this.storage;
// 充值所有的属性
this.storage = [];
this.count = 0;
this.limit = newLimit;
for (var i = 0; i < this.limit; i++) {
var bucket = oldStorage[i];
if (bucket == null) {
continue;
}
for (var j = 0; j < bucket.length; j++) {
var tuple = bucket[j];
this.put(tuple[0], tuple[1]);
}
}
};
// 为空？
HashTable.prototype.isEmpty = function () {
return this.count > 0 ? false : true;
};
// size
HashTable.prototype.size = function () {
return this.count;
};
// toString
HashTable.prototype.toString = function () {
var str = '';
for (var i = 0; i < this.limit; i++) {
var arr = this.storage[i];
if (arr != undefined) {
str += '[';
for (var j = 0; j < arr.length; j++) {
var bucket = arr[j];
str += '[' + bucket[0] + ',' + bucket[1] + ']';
if (j != arr.length - 1) {
str += ',';
}
}
str += ']';
if (i != this.limit - 1) {
str += ',';
}
} else {
str += '[]';
if (i != this.limit - 1) {
str += ',';
}
}
}
return str;
};
HashTable.prototype.isPrime = function (num) {
if (num <= 1) {
return false;
}
//1.获取num的平方根:Math.sqrt(num)
//2.循环判断
for (var i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
};
//获取质数的方法
HashTable.prototype.getPrime = function (num) {
//7*2=14,+1=15,+1=16,+1=17(质数)
while (!this.isPrime(num)) {
num++;
}
console.log(num);
return num;
};
}
var hashTable = new HashTable();
hashTable.put('q', 1);
hashTable.put('w', 1);
hashTable.put('e', 1);
hashTable.put('r', 1);
hashTable.put('t', 1);
hashTable.put('y', 1);
hashTable.put('z', 1);
hashTable.put('x', 1);
hashTable.put('c', 1);
hashTable.put('v', 1);
hashTable.put('b', 1);
hashTable.put('n', 1);
hashTable.remove('q');
console.log(hashTable.toString());//[[w,1]],[[x,1]],[[y,1]],[[z,1]],[],[],[],[],[[n,1]],[],[],[],[[r,1]],[[b,1]],[[t,1],[c,1]],[],[[e,1],[v,1]]
相关推荐：javascript学习教程
以上是详细介绍JavaScript怎么实现哈希表的详细内容。更多信息请关注PHP中文网其他相关文章！
Python vs. JavaScript：开发环境和工具Apr 26, 2025 am 12:09 AMPython和JavaScript在开发环境上的选择都很重要。1)Python的开发环境包括PyCharm、JupyterNotebook和Anaconda，适合数据科学和快速原型开发。2)JavaScript的开发环境包括Node.js、VSCode和Webpack，适用于前端和后端开发。根据项目需求选择合适的工具可以提高开发效率和项目成功率。
JavaScript是用C编写的吗？检查证据Apr 25, 2025 am 12:15 AM是的，JavaScript的引擎核心是用C语言编写的。1）C语言提供了高效性能和底层控制，适合JavaScript引擎的开发。2）以V8引擎为例，其核心用C 编写，结合了C的效率和面向对象特性。3）JavaScript引擎的工作原理包括解析、编译和执行，C语言在这些过程中发挥关键作用。
JavaScript的角色：使网络交互和动态Apr 24, 2025 am 12:12 AMJavaScript是现代网站的核心，因为它增强了网页的交互性和动态性。1)它允许在不刷新页面的情况下改变内容，2)通过DOMAPI操作网页，3)支持复杂的交互效果如动画和拖放，4)优化性能和最佳实践提高用户体验。
C和JavaScript：连接解释Apr 23, 2025 am 12:07 AMC 和JavaScript通过WebAssembly实现互操作性。1）C 代码编译成WebAssembly模块，引入到JavaScript环境中，增强计算能力。2）在游戏开发中，C 处理物理引擎和图形渲染，JavaScript负责游戏逻辑和用户界面。
从网站到应用程序：JavaScript的不同应用Apr 22, 2025 am 12:02 AMJavaScript在网站、移动应用、桌面应用和服务器端编程中均有广泛应用。1)在网站开发中，JavaScript与HTML、CSS一起操作DOM，实现动态效果，并支持如jQuery、React等框架。2)通过ReactNative和Ionic，JavaScript用于开发跨平台移动应用。3)Electron框架使JavaScript能构建桌面应用。4)Node.js让JavaScript在服务器端运行，支持高并发请求。
Python vs. JavaScript：比较用例和应用程序Apr 21, 2025 am 12:01 AMPython更适合数据科学和自动化，JavaScript更适合前端和全栈开发。1.Python在数据科学和机器学习中表现出色，使用NumPy、Pandas等库进行数据处理和建模。2.Python在自动化和脚本编写方面简洁高效。3.JavaScript在前端开发中不可或缺，用于构建动态网页和单页面应用。4.JavaScript通过Node.js在后端开发中发挥作用，支持全栈开发。
C/C在JavaScript口译员和编译器中的作用Apr 20, 2025 am 12:01 AMC和C 在JavaScript引擎中扮演了至关重要的角色，主要用于实现解释器和JIT编译器。 1）C 用于解析JavaScript源码并生成抽象语法树。 2）C 负责生成和执行字节码。 3）C 实现JIT编译器，在运行时优化和编译热点代码，显着提高JavaScript的执行效率。
JavaScript在行动中：现实世界中的示例和项目Apr 19, 2025 am 12:13 AMJavaScript在现实世界中的应用包括前端和后端开发。1)通过构建TODO列表应用展示前端应用，涉及DOM操作和事件处理。2)通过Node.js和Express构建RESTfulAPI展示后端应用。
热AI工具
Undresser.AI Undress
人工智能驱动的应用程序，用于创建逼真的裸体照片
AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。
Undress AI Tool
免费脱衣服图片
Clothoff.io
AI脱衣机
Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸！
热门文章
热工具
DVWA
Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序，非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具，帮助Web开发人员更好地理解保护Web应用程序的过程，并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞，难度各不相同。请注意，该软件中
WebStorm Mac版
好用的JavaScript开发工具
Atom编辑器mac版下载
最流行的的开源编辑器
EditPlus 中文破解版
体积小，语法高亮，不支持代码提示功能
MinGW - 适用于 Windows 的极简 GNU
这个项目正在迁移到osdn.net/projects/mingw的过程中，你可以继续在那里关注我们。MinGW：GNU编译器集合（GCC）的本地Windows移植版本，可自由分发的导入库和用于构建本地Windows应用程序的头文件；包括对MSVC运行时的扩展，以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。
