Detaillierte Erläuterung der Beispiele für js-Wörterbuch und Hash-Tabellen

js-Wörterbuch Das Wörterbuch speichert Elemente in der Form [Schlüssel, Wert]. Wörterbücher werden auch Mappings genannt. In diesem Artikel werden hauptsächlich detaillierte Beispiele für js-Wörterbücher und Hash-Tabellen vorgestellt.

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;
}
}

Hash-Tabelle

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}
			}
		}
	};
}

Es liegt ein Konflikt vor, wenn die Hash-Werte gleich sind

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. Separate Verknüpfung
Die Die getrennte Verknüpfungsmethode umfasst eine Hash-Tabelle. Erstellen Sie an jeder Position eine verknüpfte Liste und speichern Sie die Elemente darin. Dies ist die einfachste Möglichkeit, Konflikte zu lösen, erfordert jedoch zusätzlichen Speicher außerhalb der HashTable-Instanz. Überschreiben Sie die Methode „Put Get Remove Print“

2. Lineare Sondierung

Eine weitere Möglichkeit, Konflikte zu lösen, ist die lineare Sondierung. Wenn Sie ein neues Element an einer bestimmten Position in der Tabelle hinzufügen möchten und die Position mit Index

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;;
		}
	};
}

bereits belegt ist, versuchen Sie es mit der Position mit Index+1. Wenn die Index+1-Position ebenfalls belegt ist, versuchen Sie es mit

Index+2-Position usw.

3. Erstellen Sie eine bessere Hash-Funktion

Das „verlieren lose“-Hash-Funktion ist keine leistungsstarke Hash-Funktion, da sie zu viele

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;;
		}
	};
}

Kollisionen erzeugt. Wenn wir diese Funktion verwenden, treten verschiedene Konflikte auf. Eine gut funktionierende Hash-Funktion besteht aus mehreren Aspekten: Zeit zum Einfügen und Abrufen von Elementen (d. h. Leistung) und natürlich einer geringen Wahrscheinlichkeit von Kollisionen. Wir können einige verschiedene Implementierungsmethoden online finden

, oder wir können unsere eigene Hash-Funktion implementieren

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Beispiele für js-Wörterbuch und Hash-Tabellen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!