JavaScript Map实现原理与底层结构详解

前言

比如,有一天,我们去购物店买了一件新的、不熟悉的商品。

张三:这个商品多少钱

收银员:(在键盘上噼啪作响。。。)

收银员:88元,给你凑个整。

(滴。。。付款成功)

成功支付90元。

hash表

收银员如何在数千件商品中如此迅速地找到这件商品的价格。

有人说可以遍历暴力查询,总能找到项目。

如果有一百万种产品,需要多少时间?虽然始终可以从头到尾查询,但我们追求更好的性能,这就是我们的哈希表存储。

我们需要做的就是将商品转化为下标形式的数字,并对应数组的下标,这样下次遇到这个商品,就可以直接根据下标获取我们需要的信息了。

就像我们有一根香蕉? banana(香蕉)

我们想一个办法把它变成一个数字:

function getHash(str) {
 let _hash = 0;
 for (let i = 0; i < str.length; i++) {
 const charCode = str.charCodeAt(i);
 _hash += charCode;
 }
 return _hash;
 }
 console.log(getHash('banana')) //609

这里我们计算出它对应的数字是609。

这里我们只是添加了字母对应的ascii下标。仅供参考和学习。一个好的哈希算法应该尽量避免下标过多和下标分散过大,还要处理和解决哈希冲突。

所以我们可以将数组下标到位置 609 并添加价格,arr[609] = 66,这里设置66元。

下次查询香蕉的价格,还是可以通过 getHash 算出609,直接取数组的下标就可以得到我们的价格,只需要O(1)的时间。

实现 get 功能

function get(key){
 let _hash = getHash(key);
 //这里的 arr 代表我们存储数据的数组
 if(!this.arr[_hash]){
 //如果没查到数据,返回undefined
 return undefined;
 }
 return this.arr[_hash];
 }

实现 set 功能

function set(key,value){
 let _hash = getHash(key);
 //这里的 arr 代表我们存储数据的数组
 this.arr[_hash] = value;
 }

做个测试

class MyHash {
 constructor(){
 this.arr = [];
 }
 get(key) {
 let _hash = getHash(key);
 //这里的 arr 代表我们存储数据的数组
 if (!this.arr[_hash]) {
 //如果没查到数据,返回undefined
 return undefined;
 }
 return this.arr[_hash];
 }
 set(key, value) {
 let _hash = getHash(key);
 //这里的 arr 代表我们存储数据的数组
 this.arr[_hash] = value;
 }
 }
 let myhash = new MyHash();
 myhash.set('banana', '88')
 console.log(myhash.get('banana'))
作者:十九(一拖再拖)原文地址:https://blog.csdn.net/qq_41974199/article/details/125107037

%s 个评论

要回复文章请先登录注册