简单写一下Map对象的底层实现原来,包括常用的几个方法:
size,set(),get(),delete(),clear()
Map底层数据结构是,hashMap,即哈希表或者散列表
哈希表冲突解决方案采用拉链法
function MyMap(){
this.init();
}
MyMap.prototype.init = function(){
this.size = 0;
this.bucket = new Array(8);
for(let i = 0; i < 8; i++){
this.bucket[i] = {};
this.bucket[i].next = null;
}
}
MyMap.prototype.hash = function(key){
let index = 0;
// 根据key的不同的数据类型,返回不同的index,其实就是决定放到bucket的那个链表上
if(typeof key === 'object'){
index = 0;
}else if(typeof key === 'number'){
index = key % this.bucket.length;
}else if(typeof key === 'undefined'){
index = 1;
}else if(typeof key === 'null'){
index = 2;
}else if(typeof key === 'string'){
for(let i = 0; i < 10; i++){
index += isNaN(key.charCodeAt(i)) ? 0 : key.charCodeAt(i);
}
}
index = index % this.bucket.length;
return index;
}
MyMap.prototype.get = function(key){
const i = this.hash(key);
let target = this.bucket[i];
// 找到在链表上哪个位置
while(target.next){
if(target.next.key === key){
return target.next.value;
}
target = target.next;
}
return undefined;
}
MyMap.prototype.set = function(key, value){
// 1、决定key,value放到哪个链表上
const i = this.hash(key);
// 2、获取当前要存放的链表
let target = this.bucket[i];
// 放到链表上哪个位置
while(target.next){
// key已经存在,直接修改
if(target.next.key === key){
target.next.value = value;
return this;
}
target = target.next;
}
target.next = {key, value, next : null}
this.size++;
return this;
}
MyMap.prototype.has = function(key){
const i = this.hash(key);
let target = this.bucket[i];
while(target.next){
if(target.next.key === key){
return true;
}
target = target.next;
}
return false;
}
MyMap.prototype.clear = function(){
this.init();
}
MyMap.prototype.delete = function(key){
const i = this.hash(key);
let target = this.bucket[i];
// 防止删除第一个,设置虚拟头
let front = {
next: target
};
let cur = front;
while(cur.next){
if(cur.next.key === key){
cur.next = cur.next.next;
return true;
}
cur = cur.next;
}
return false
}
网友评论