简体中文(ZH-CN) English(EN) 繁体中文(ZH-TW) 日本語(JA) 한국어(KO) Melayu(MS) Français(FR) Deutsch(DE)
首頁 > web前端 > js教程 > 主體

js字典和散列表實例詳解

小云云
發布： 2018-03-15 17:54:37
原創
1720 人瀏覽過


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 + &#39; - &#39; + 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(&#39;[&#39; + this.key + &#39; - &#39; + this.value + &#39;]&#39;);
			
		this.toString = function() {
			return &#39;[&#39; + this.key + &#39; - &#39; + this.value + &#39;]&#39;;
		}
	};
}
登入後複製

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(&#39;[&#39; + this.key + &#39; - &#39; + this.value + &#39;]&#39;);
			
		this.toString = function() {
			return &#39;[&#39; + this.key + &#39; - &#39; + this.value + &#39;]&#39;;
		}
	};
}
登入後複製

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(&#39;[&#39; + this.key + &#39; - &#39; + this.value + &#39;]&#39;);
this.toString = function() {
return &#39;[&#39; + this.key + &#39; - &#39; + this.value + &#39;]&#39;;
}
};
}
登入後複製

以上是js字典和散列表實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！

相關標籤：
javascript 實例 詳解
來源：php.cn
上一篇：DataTable插件可以實現非同步載入嗎？ 下一篇：checkbox在jQuery的使用
本網站聲明
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn
作者最新文章
最新問題
僅 CSS 方法可在單擊時動態修改圖片 src，無需使用 JavaScript 我需要僅使用css更改滑鼠單擊時圖像的src喜歡img:active{}
來自於 2024-04-06 19:25:49
0
1
505
放大 d3.js 時散佈圖點不會保持值 這是我第一次使用d3.js，所以請耐心等待。我在vue.js檔案中將其作為純JavaScript實作。我正在嘗試製作具有縮放功能的散點圖。到目前為止，我幾乎一切正常，但當我縮放時，...
來自於 2024-04-06 18:16:26
0
1
403
供應商特定偽元素上的 JavaScript 懸停事件 我有以下htmlinput標籤。 $("input[type='range']::-webkit-slider-thumb").on('hover',funct...
來自於 2024-04-06 15:35:24
0
1
274
使用 Javascript / Jquery 提交表單且不含按鈕 我試圖透過呼叫JavaScript函數並使用JQUERY/PHP執行表單來提交沒有按鈕的表單。我希望表單在後端靜默執行，而無需重新載入頁面。不幸的是，它不斷傳回JavaScript...
來自於 2024-04-06 14:54:03
0
2
421
使用「折疊顯示器」類別自訂 Bootstrap 手風琴標題的外觀 我想設定具有類別collapseshow的面板的卡片標題樣式。在此範例中，它是第一個面板。我嘗試使用CSS來使用.accordion.card.card-headerbutton....
來自於 2024-04-06 12:53:11
0
1
376
相關專題
更多>
熱門推薦
熱門教學
更多>
相關教學
熱門推薦
最新課程
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網：公益線上PHP培訓，幫助PHP學習者快速成長！