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;
}
}Nach dem Login kopieren
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 + ' - ' + 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}
}
}
};
}Nach dem Login kopieren
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
Nach dem Login kopieren
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('[' + this.key + ' - ' + this.value + ']');
this.toString = function() {
return '[' + this.key + ' - ' + this.value + ']';
}
};
}Nach dem Login kopieren
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('[' + this.key + ' - ' + this.value + ']');
this.toString = function() {
return '[' + this.key + ' - ' + this.value + ']';
}
};
}Nach dem Login kopieren
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!
