js dictionary Dictionary stores elements in the form of [key, value]. Dictionaries are also called mappings. This article mainly shares with you detailed examples of js dictionaries and hash tables. I hope it can help you.
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 table
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}
}
}
};
}There is a conflict when the hash values are the same
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 link
The separated link method involves creating a link for each position in the hash table Linked list and store elements in it. It is the easiest way to resolve conflicts, but it requires additional storage outside of the HashTable instance. Override put get remove print' method
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 + ']';
}
};
}Another way to resolve conflicts is linear probing. When you want to add a new element to a certain position in the table, if the position with index
is already occupied, try the position with index+1. If the position of index+1 is also occupied, try the position of
index+2, and so on
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 + ']';
}
};
}The "lose lose" hash function we implemented is not a well-performing hash function because it creates too many collisions. If we use this function, various conflicts will occur. A well-performing hash function is made up of several aspects: the time to insert and retrieve elements (i.e. performance), and of course a low likelihood of collisions. We can find some different implementation methods on the Internet
, or we can also implement our own hash functionfunction 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('[' + this.key + ' - ' + this.value + ']');
this.toString = function() {
return '[' + this.key + ' - ' + this.value + ']';
}
};
}The above is the detailed content of Detailed explanation of js dictionary and hash table examples. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
