Explication détaillée des exemples de dictionnaire js et de table de hachage

dictionnaire js Le dictionnaire stocke les éléments sous la forme de [clé, valeur]. Les dictionnaires sont également appelés mappages. Cet article partage principalement avec vous des exemples détaillés de dictionnaires js et de tables de hachage. J'espère qu'il pourra vous aider.

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

Table de hachage

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

Il y a un conflit lorsque les valeurs de hachage sont les mêmes

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

Lien séparé
Le. La méthode de liaison séparée comprend une table de hachage. Créez une liste chaînée à chaque position et stockez-y les éléments. Il s'agit du moyen le plus simple de résoudre les conflits, mais il nécessite un stockage supplémentaire en dehors de l'instance HashTable. Remplacer la méthode put get Remove print

2. Sondage linéaire

Une autre façon de résoudre les conflits est le sondage linéaire. Lorsque vous souhaitez ajouter un nouvel élément à une certaine position du tableau, si la position avec 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;;
		}
	};
}

est déjà occupée, essayez la position avec index+1. Si la position index+1 est également occupée, essayez la

position index+2, et ainsi de suite

Créer une meilleure fonction de hachage

Le "perdre". La fonction de hachage "lose" que nous avons implémentée n'est pas une fonction de hachage performante car elle crée trop de

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

collisions. Si nous utilisons cette fonction, divers conflits se produiront. Une fonction de hachage performante se compose de plusieurs aspects : le temps nécessaire pour insérer et récupérer les éléments (c'est-à-dire les performances), et bien sûr, une faible probabilité de collisions. Nous pouvons trouver différentes méthodes d'implémentation en ligne

, ou nous pouvons implémenter notre propre fonction de hachage

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!