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 + ' - ' + 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 Indexfunction 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 + ']';
}
};
}
Index+2-Position usw.
3. Erstellen Sie eine bessere Hash-Funktion
Das „verlieren lose“-Hash-Funktion ist keine leistungsstarke Hash-Funktion, da sie zu vielefunction 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 + ']';
}
};
}, 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!
