散列表定义-百度百科
我的理解是:我有一条数据要存 name:xxx,如果直接存，以后数据越来越多的时候，可能要遍历查找，现在我按照一定规则（散列函数）转换成地址，下次读取时，只要按照这个这个散列函数直接访问地址，快速返回我要的key-value.不需要遍历了。
比如 a:1 => 变身=>[dajdhkadhk]:1=>读取=>a:1
1 创建散列表
function HashTable() {
var table = []
// 散列函数
var loseloseHashCode = function(key){
var hash = 0
for(var i =0 ;i<key.length;i++){
hash+=key.charCodeAt(i)
}
return hash % 37
}
// 向散列表中增加一个新的项
this.put = function (key,value){
var position = loseloseHashCode(key)
console.log(position+'-'+key)
table[position]=value
}
// 读取某项
this.get=function(key){
return table[loseloseHashCode(key)]
}
//删除某项
this.remove=function(key){
table[loseloseHashCode(key)] =undefind
}
this.print=function(){
for(let i=0;i<table.length;i++){
if(table[i]!==undefined){
console.log(i+':'+table[i])
}
}
}
}
运行能读，能存，能删
但是当key转换成的散列值与之前的相同时，值将会被覆盖。
image.png
print一下
image.png
2 解决冲突
2.1分离链接
思路，table[position]变成一个链表
function HashTable() {
var table = []
// 散列函数
var loseloseHashCode = function(key){
var hash = 0
for(var i =0 ;i<key.length;i++){
hash+=key.charCodeAt(i)
}
return hash % 37
}
var ValuePair = function(key,value){
this.key = key
this.value = value
this.toString = function(){
return '['+this.key+'-'+this.value+']'
}
}
// 向散列表中增加一个新的项
this.put = function (key,value){
var position = loseloseHashCode(key)
console.log(position+':'+key)
if(table[position] ==undefined){
table[position]=new LinkedList()
}
table[position].append(new ValuePair(key,value))
}
// 读取某项
this.get=function(key){
var position = loseloseHashCode(key)
if(table[position]!==undefined){
let current = table[position].getHead();
while(current.next){
if(current.element.key === key){
return current.element.value
}
current = current.next
}
// 检查元素在第一个或最后一个节点的情况
if(current.element.key === key){
return current.element.value
}
}
return undefined
}
//删除某项
this.remove=function(key){
var position = loseloseHashCode(key)
if (table[position] !== undefined) {
let current = table[position].getHead()
while(current.next){
if(current.element.key === key){
table[position].remove(current.element)
if(table[position].isEmpty()){
table[position]=undefined
}
return true
}
current = current.next
}
if (current.element.key === key) {
table[position].remove(current.element)
if (table[position].isEmpty()) {
table[position] = undefined
}
return true
}
}
return false
}
this.print=function(){
for(let i=0;i<table.length;i++){
if(table[i]!==undefined){
console.log(i+':'+table[i])
}
}
}
}
2.2线性探查
table[position]存在=>table[position+1]={key,value}
模拟过程:
h= new HashTable()
1,插入
考虑一个情况1,2,4,5坑位都占好了，
现在position假设为3，table[3]此时为undefined,table[3]={key:'name',value:zlj}
插入成功
现在我又要插数据了，position还是为3，3号坑位已经被占了，我要向后寻找坑位，6号坑位是空的，tablep[6]={key:'age',value:26}
插入成功
2，查找:
我要h.get('age')
根据我散列转换函数position就是3呀，
现在来核对一下是否正确
table[3].key ：name 不是age,
向下一个坑位寻找，下一个坑位有两种情况，要么被占领了，要么没有被占，只要下一个坑位的不是{key:age}就一直向后寻找，直到找到。
如果一直找不到怎么办，所以要在初始的时候判断一下table[position]===undefind
思考：h.get('age')只会是两种结果，要么存在值，要么为undefind
,存在值要么在position的某个位置，要么在999999+的位置，反正肯定能找到的，因为我们插值就是这样插得，这个坑位被占，一直向后寻找空的坑位，要么这个坑位根本没有占。
function HashTable() {
var table = []
// 散列函数
var loseloseHashCode = function(key){
var hash = 0
for(var i =0 ;i<key.length;i++){
hash+=key.charCodeAt(i)
}
return hash % 37
}
var ValuePair = function(key,value){
this.key = key
this.value = value
this.toString = function(){
return '['+this.key+'-'+this.value+']'
}
}
// 向散列表中增加一个新的项
this.put = function (key,value){
var position = loseloseHashCode(key)
// 当前index没用被占用
if (table[position] == undefined) {
table[position] = new ValuePair(key,value)
} else {
// 当前index 已经被占用了
var index = ++position
while (table[index]!=undefined){
index++
}
table[index] = new ValuePair(key,value)
}
}
// 读取某项
this.get=function(key){
var position = loseloseHashCode(key)
if(table[position]!=undefined){
if(table[position].key === key){
return table[position].value
} else {
let index = ++position
// 找到
while(table[index] ==undefined ||table[index].key !== key) {
index++
}
if(table[index].key === key){
return table[index].value
}
}
}
return undefined
}
//删除某项
this.remove=function(key){
var position = loseloseHashCode(key)
if(table[position]!=undefined){
if(table[position].key === key){
table[position] = undefined
return true
} else {
let index = ++position
// 找到
while(table[index] ==undefined ||table[index].key !== key) {
index++
}
if(table[index].key === key){
table[index] = undefined
return true
}
}
}
return false
}
this.print=function(){
for(let i=0;i<table.length;i++){
if(table[i]!==undefined){
console.log(i+':'+table[i])
}
}
}
}
h = new HashTable()
h.put('Mindy','aa')
h.put('Paul','bb')
console.log(h.get('Paul'),h.get('Mindy'))
console.log(h.remove('Paul'),h.remove('Mindy'))
console.log(h.get('Paul'),h.get('Mindy'))
网友评论