js版本基于链表法的散列表

  • 时间:
  • 来源:互联网
let getWords=require("./1.js").getWords			//导入1.js,代码见字符串部分的文章
let char2int=require("./1.js").char2int

words=getWords(maxcount=555,minlen=1,maxlen=5,R=26)
words=Array.from(new Set(words))				//去重
console.log(words)
let M=31
var map=[]

for(let i in words){
    let k=words[i]
    let v=k+"val"
    put(k,v,map)
}

testGetAll(words,map)


for(let i=0;i<5;i++){
    let k=words[Math.round(Math.random()*words.length)]
    delete_(k,map)
    console.log("delete "+k)
}
testGetAll(words,map)
console.log(1+"-->"+get(1,map))



function testGetAll(words,map){
    for(let i in words){
        let k=words[i]
        let obj=get(k,map)
        let v=obj==undefined?undefined:obj.v
        if(k+"val"!=v){
            console.log("get test ERROR-->"+k)
        }
    }
}


//node:{k:asd,v:asdval,next:node}
function hash(k,size=M){
    var code=0
    for(let i=0;i<k.length;i++){
        code=(code*R+char2int(k[i]))%M
    }
    return code
}


function get(k,map){
    let code=hash(k)
    var node=map[code]
    while(node!=undefined){
        if(node.k==k){
            return node
        }
        node=node.next
    }
}


function put(k,v,map){
    let code=hash(k)
    var node=map[code]
    var prev=node
    if(node==undefined){
        map[code]={k:k,v:v}
        return
    }
    while(node!=undefined){
        if(node.k==k){
            node.v=v
            return 
        }
        prev=node
        node=node.next
    }
    prev.next={k:k,v:v}
}


function delete_(k,map){
    let code=hash(k)
    var node=map[code]
    var prev=node
    if(node==undefined){
        return
    }
    if(node.k==k){
        map[code]=node.next
        return
    }
    while(node!=undefined){
        if(node.k==k){
            prev.next=node.next
            return 
        }
        prev=node
        node=node.next
    }
}
Hoto Kokoa
发布了355 篇原创文章 · 获赞 20 · 访问量 1万+
私信 关注

本文链接http://element-ui.cn/news/show-1002.aspx