簡單寫一下Map對象的底層實(shí)現(xiàn)原來庵朝,包括常用的幾個(gè)方法:
size吗冤,set(),get()九府,delete()椎瘟,clear()
Map底層數(shù)據(jù)結(jié)構(gòu)是,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;
// 根據(jù)key的不同的數(shù)據(jù)類型肺蔚,返回不同的index,其實(shí)就是決定放到bucket的那個(gè)鏈表上
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];
// 找到在鏈表上哪個(gè)位置
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放到哪個(gè)鏈表上
const i = this.hash(key);
// 2儡羔、獲取當(dāng)前要存放的鏈表
let target = this.bucket[i];
// 放到鏈表上哪個(gè)位置
while(target.next){
// key已經(jīng)存在宣羊,直接修改
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];
// 防止刪除第一個(gè),設(shè)置虛擬頭
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
}