Data Structures & Algorithms in JavaScript(Dictionary)

Hello Everyone, this is part 10 in the series of blogs about data structures and algorithms in JavaScript. In this blog, I will cover the Dictionary Data Structure.

What is a Dictionary?

A dictionary is a general-purpose data structure for storing a group of objects. A dictionary has a set of keys and each key has a single associated value. - Wikibooks

List Of Operations Available

• set: insert a new key-value pair in the dictionary.
• get: return the value if the key is present.
• remove: remove key-value pair from the dictionary if present.
• hasKey: check if the key exists for not.
• keys: return all the keys in the dictionary.
• values: return all the values in the dictionary.
• keyValues : return an array containing all the pairs.
• forEach: takes callback function to perform an operation on each pair.

A dictionary is also known as a map,symbol table, and an associative array

Implementation of Dictionary in JavaScript

So, Let's start with defining ES6 class Dictionary with a property table; it will hold all the elements.
In a dictionary, the ideal would be to store keys of type string and any type of value (from primitive type such as numbers, a string, to complex objects). However, because JavaScript is not strongly typed, we cannot guarantee the key will be a string .i.e,

We first transform the key whatever object is passed as the key into a string to make it easier to search and retrieve values from the Dictionary class.

Values will be Stored as table[stringify(Key)] = new KeyValues(key,value);

    class Dictionary {
    constructor(toStrFn = toStringFunc) {
        this.table = {};
        this.toStrFn = toStrFn;
        }
    }

Default String Stringify function

function toStringFunc(key) {
    if (key == null) {
        return 'NULL'
    }
    if (key == undefined) {
        return 'UNDEFINED'
    }
    if ((typeof key == "string") || key instanceof String) {
        return `${key}`;
    }
    return key.toString();
}

Set

When inserting a key-value pair, we will check if the key & value is not null.

Else :

• Stringify the key using the default string method
• Create a new instance of KeyPair.
• Add the stringify value as the key and value as the instance of Keypair.

Dictionary Keys are unique.You can't have two or more keys to the same value . if present then it will just override the old value with the new one.

    set(key, value) {
        if (key != null & value != null) {
            const stringKey = this.toStrFn(key);
            this.table[stringKey] = new KeyValue(key, value);
            return true;
        }
        return false;
    }

KeyValue Class

     class KeyValue{
     constructor(key, value){
         this.key = key;
         this.value = value;
     }
     toString(){
         return `[#${this.key} , ${this.value}]`
     }
 }

HasKey

To check if the key is present or not, We will Stringify the key and check if its present or not.

    hasKey(key) {
        return this.table[this.toStrFn(key)] !== null;
    }

Remove

When removing a key-value pair, We first need to check if the key is present in the Dictionary using the HasKey method. If present then deletes the key-value pair.

    remove(key) {
        if (this.hasKey(key)) {
            delete this.table[this.toStrFn(key)];
            return true;
        }
        return false;
    }

get

If a key-value pair, with a key, exists then return value or else null.
As we know that we first we stringify the key and set that as the Object key and value as the instance of KeyValue. ie.

• Stringify the key.
• Return the stringify key's KeyValue value.

    get(key) {
        const keyValuesPair = this.table[this.toStrFn(key)];
        return keyValuesPair != null ? keyValuesPair.value : null;
    }

KeyValues

This method will return all the stored key-value pair in the Dictionary class,

• Initialize an array keyValuePairs
• Iterate table property, if the key exists then push to keyValuePairs array
• Return the keyValuePairs.

    keyValues() {
        const keyValuePairs = [];
        for (const key in this.table) {
            if (this.table.hasOwnProperty(key)) {
                keyValuePairs.push(this.table[key])
            }
        }
        return keyValuePairs;
    }

Keys

This method returns all the key-value pairs keys. We will evoke the KeyValues extract the keys using Array.prototype.map. Alternative use can also do the same thing using for loop.

    keys() {
        return this.keyValues().map(element => element.key);
    }

Values

This method returns all the key-value pairs values. We will evoke the KeyValues extract the values using Array.prototype.map

    values() {
        return this.keyValues().map(element => element.value);
    }

ForEach

ForEach is an iterator function, Which allows us to loop the all key-value pair present in the Dictionary class. But, the same can be applied for other data structures too.

• We evoke the KeyValues and get all the key-value pairs.
• We will iterate over the individual pairs and execute the callback until the condition is true.

    forEach(callback) {
        let keyValuePairs = this.keyValues();
        for (let index = 0; index < keyValuePairs.length; index++) {
            const result = callback(keyValuePairs[index].key, keyValuePairs[index].value);
            if (result == false) {
                break;
            }

        }
    }

you get the full source here

Map ES6 ,Is similar to Dictionary .

Conclusion :

Methods	Complexity
set	O(n)
get	O(1)
remove	O(1)
keys	O(n)
values	O(n)
KeyValues	O(n)
forEach	O(n)

So, stay tuned for the next blog, in which I will cover another DS Hash table.