首页 > 代码库 > 算法练习--二分搜索哈希表-JS 实现
算法练习--二分搜索哈希表-JS 实现
1. 以哈希KEY的值建立二叉哈希表
2. 根据传入的哈希值使用二分法搜索
具体实现如下:
function binarySearchTable(comp){ this.comp = comp; this.kv = new Array(); } binarySearchTable.prototype.add = function(k,v){ if(this.kv.length == 0 || this.comp(this.kv[0].key,k) >= 0){ this.kv.splice(0,0,{key:k,value:v}); return this; } else if(this.comp(this.kv[this.kv.length - 1].key,k) <= 0){ this.kv.push({key:k,value:v}); return this; } else{ for(var i = 1,j = i+1;j < this.kv.length; i ++, j++){ if((this.comp(this.kv[i].key) < 0 || this.comp(this.kv[i].key) == 0) && (this.comp(this.kv[j].key) > 0 || this.comp(this.kv[j].key) == 0)){ this.kv.splice(i,0,new {key:k,value:v}); return this; } } } }; binarySearchTable.prototype.getIndexByKey = function(k){ var lo = 0; var hi = this.kv.length - 1; var mid = (lo + hi) / 2 | 0; var c = 0; while(lo < hi && (++c) < 10){ if(this.comp(k,this.kv[mid].key) == 0){return mid;} else if(this.comp(k,this.kv[lo].key) == 0){return lo;} else if(this.comp(k,this.kv[hi].key) == 0){return hi;} else if(this.comp(this.kv[mid].key,k) < 0){lo = mid;mid = (hi+lo) / 2 | 0;} else {hi=mid;mid = (lo+hi)/2 | 0;} } return null; }; binarySearchTable.prototype.removeByKey = function(k){ var index = this.getIndexByKey(k); if(index != null){this.kv.splice(index,1);} } var comp = function(k1,k2){return k1 < k2 ? -1 : k1 == k2 ? 0 : 1;}; var tbl = new binarySearchTable(comp); tbl.add("bec",1); tbl.add("acd",1); tbl.add("abc",1); tbl.add("dec",1); console.log(tbl.getIndexByKey("abc")); tbl.removeByKey("abc"); console.log(tbl.getIndexByKey("abc"));
算法练习--二分搜索哈希表-JS 实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。