js字典和散列表實例詳解
- 小云云原創
- 2018-03-15 17:54:371763瀏覽
js字典 字典則是以[鍵，值]的形式來儲存元素。字典也稱作映射，本文主要和大家分享js字典和散列表實例詳解，希望能幫助大家。
function Dictionary() {
var items = {};
this.has = function(key) {
return key in items;
}
this.set = function(key,value){
items[key] = value;
}
this.remove = function(Key){
if(this.has(Key)){
delete items[Key];
return true;
}
return false;
}
this.get = function(key){
return this.has(Key)?items[Key]:undefined;
}
this.values = function() {
var values = {};
for (var k in items) { //{1}
if (this.has(k)) {
values.push(items[k]); //{2}
}
}
return values;
};
this.size = function(){
return Object.keys(items).length; //{4}
};
this.sizeLegacy = function(){
var count = 0;
for(var prop in items) { //{5}
if(items.hasOwnProperty(prop)) //{6}
++count; //{7}
}
return count;
};
this.getItems = function() {
return items;
}
}散列表
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 = this.loseloseHashCode(key);
console.log(position + ' - ' + key);
table[position] = value;
}
this.get = function(key){
return table[this.loseloseHashCode(key)];
}
this.remove = function(key) {
table[loseloseHashCode(key)] = undefined;
};
this.print = function() {
for (var i = 0; i < table.length; ++i) { //{1}
if (table[i] !== undefined) { //{2}
console.log(i + ": " + table[i]);//{3}
}
}
};
}hash值相同的時候有衝突
19 - Gandalf HashTable.js:12 29 - John HashTable.js:12 16 - Tyrion HashTable.js:12 16 - Aaron HashTable.js:12 13 - Donnie HashTable.js:12 13 - Ana HashTable.js:12 5 - Jonathan HashTable.js:12 5 - Jamie HashTable.js:12 5 - Sue HashTable.js:12 32 - Mindy HashTable.js:12 32 - Paul HashTable.js:12 10 - Nathan HashTable.js:24 5: sue@email.com HashTable.js:24 10: nathan@email.com HashTable.js:24 13: ana@email.com HashTable.js:24 16: aaron@email.com HashTable.js:24 19: gandalf@email.com HashTable.js:24 29: johnsnow@email.com HashTable.js:24 32: paul@email.com
1. 分離連結
分離連結法包括為散列表的每一個位置創建一個鍊錶並將元素儲存在裡面。它是解決衝突的
最簡單的方法，但是它在 HashTable 實例之外還需要額外的儲存空間。重寫put get remove print'方法
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);
//undefined创建链表
if(table[position] == undefined)
table[position] = new LinkedList();
//undefined不为空 链表后面加元素
table[position].append(new ValuePair(key,value));
}
this.get = function(key){
var position = loseloseHashCode(key);
if(table[position] !== undefined ){
var 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){
var 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 true;
}
return fasle;
};
this.print = function() {
for (var i = 0; i < table.length; ++i) { //{1}
if (table[i] !== undefined) { //{2}
var current = table[i].getHead();
while(current.next){
console.info("output",current.element.toString());
current = current.next;
}
console.info("output",current.element.toString());//{3}
}
}
};
//新增的方法 创建node元素 将key，value放入这个对象
var ValuePair = function(key, value){
this.key = key;
this.value = value;
console.info('[' + this.key + ' - ' + this.value + ']');
this.toString = function() {
return '[' + this.key + ' - ' + this.value + ']';
}
};
}2. 線性探查
另一種解決衝突的方法是線性探查。當想要在表中某個位置加入新元素的時候，如果索引
為index的位置已經被佔據了，就嘗試index+1的位置。如果index+1的位置也被佔據了，就嘗試
index+2的位置，以此類推
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);
if(table[position] == undefined){
table[position] = new ValuePair(key,value);
}esle{
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{
var 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{
var index =++position;
while(table[index]===undefined||table[index].key!==key){
index++
}
if(table[index].key===key){
table[position] = undefined;
return true;
}
}
}
return false;
};
this.print = function() {
for (var i = 0; i < table.length; ++i) { //{1}
if (table[i] !== undefined) { //{2}
console.info("output",table[i].toString());
}
}
};
//新增的方法 创建node元素 将key，value放入这个对象
var ValuePair = function(key, value){
this.key = key;
this.value = value;
console.info('[' + this.key + ' - ' + this.value + ']');
this.toString = function() {
return '[' + this.key + ' - ' + this.value + ']';
}
};
}3.創建更好的雜湊函數
我們實現的「lose lose」雜湊函數並不是表現良好的雜湊函數，因為它會產生太多的衝
突。如果我們使用這個函數的話，會產生各種各樣的衝突。一個表現良好的雜湊函數是由幾個方
面構成的：插入和檢索元素的時間（即性能），當然也包括較低的衝突可能性。我們可以在網路上
找到一些不同的實作方法，或者也可以實作自己的雜湊函數
function HashTable() {
var table = [];
var loseloseHashCode = function (key) {
var hash = 5381;
for(var i = 0;i<key.length;i++){
hash += hash*33+key.charCodeAt(i);
}
return hash % 1013;
}
this.put = function(key,value){
var position = loseloseHashCode(key);
table[position] = new ValuePair(key,value);
}
this.get = function(key){
var position = loseloseHashCode(key);
if(table[position] !== undefined )
return table[position].value;
return undefined;
}
this.remove = function(key) {
var position = loseloseHashCode(key);
if(table[position] !== undefined ){
table[position] = undefined;
return true;
}
return false;
};
this.print = function() {
for (var i = 0; i < table.length; ++i) { //{1}
if (table[i] !== undefined) { //{2}
console.info("output",table[i].toString());
}
}
};
//新增的方法 创建node元素 将key，value放入这个对象
var ValuePair = function(key, value){
this.key = key;
this.value = value;
console.info('[' + this.key + ' - ' + this.value + ']');
this.toString = function() {
return '[' + this.key + ' - ' + this.value + ']';
}
};
}以上是js字典和散列表實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！
陳述：
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn