To continue my exploration of data structures, I wanted to write this article on creating our own dictionary class in JavaScript.
A dictionary, also known as a map, is used to store [key, value] pairs, where the key can be used to look up a particular element. Dictionaries are often used to store the reference address of objects or for a project like an actual dictionary or an address book, for example.
Creating the Dictionary class
The base structure of our Dictionary
class will look like this:
import { defaultToString } from '../util';
export default class Dictionary {
constructor(toStrFn = defaultToString) { // defaultToString below
this.toStrFn = toStrFn;
this.table = {};
}
}
As you can see, we are storing the elements of the Dictionary
class in an Object
instance and the [key, value] pairs are being stored as table[key] = {key, value}
.
Ideally, we would be storing keys of type string and any type of value
but because JavaScript is not strongly typed, we cannot guarantee the key
will be a string. Thus, we will have to transform whatever object is passed as the key
into a string to make it easier to search and retrieve values. For this reason, we are passing in a function which will look something like this:
export function defaultToString(item) {
if (item === null) {
return 'NULL';
} else if (item === undefined) {
return 'UNDEFINED';
} else if (typeof item === 'string' || item instanceof String) {
return `${item}`;
}
return item.toString();
}
Over the course of this article, we will cover the following methods for our dictionary:
-
hasKey(key)
: returntrue
if thekey
exists in the dictionary. -
set(key, value)
: add a new element to the dictionary. If thekey
already exists, the existingvalue
will be overwritten with the new one. -
remove(key)
: remove thevalue
from the dictionary. -
get(key)
: return thevalue
associated with the passedkey
. -
keys()
: return an array of all the keys the dictionary contains. -
values()
: return an array of all the values of the dictionary. -
keyValues()
: return an array of all [key, value] pairs of the dictionary. -
size()
: return the number of values the dictionary contains. -
isEmpty()
: returntrue
if thesize
equals zero. -
clear()
: remove all values from the dictionary. -
forEach(callBackFn)
: iterate everyvalue
pair in the dictionary and perform the call back function.
Verify a key exists in the dictionary
The first method we will cover is the hasKey(key)
method since we will need it for other methods.
hasKey(key) {
return this.table[this.toStrFn(key)] != null;
}
Set a key and value in the dictionary
Next up, the set(key, value)
method which can be used to add a new value or update an existing one:
set(key, value) {
if (key != null && value != null) {
const tableKey = this.toStrFn(key);
this.table[tableKey] = new ValuePair(key, value);
return true;
}
return false;
}
As you can see, we instantiated the class ValuePair
which we define as follows:
class ValuePair(key, value) {
constructor(key, value) {
this.key = key;
this.value = value;
}
toString() {
return `[${this.key}: ${this.value}]`;
}
}
Remove a value from the dictionary
The remove
method is pretty straight forward at this point, especially with the help of the JavaScript delete
operator:
remove(key) {
if (this.hasKey(key)) {
delete this.table[this.toStrFn((key))];
return true;
}
return false;
}
Retrieve a value from the dictionary
Next, we will write the get
method in order to search for a particular key
and retrieve its value
:
get(key) {
const valuePair = this.table[this.toStrFn(key)];
return valuePair == null ? undefined : valuePair.value;
}
keyValues, keys, and values methods
Now we will create some more supplementary but nevertheless useful methods. The valuePairs
method will return an array with all ValuePair
objects in the dictionary, using the built-in values
method from the JavaScript Object
class:
keyValues() {
return Object.values(this.table);
}
Next, we will write the keys
method which returns all the original keys used to identify a value in the Dictionary
class:
keys() {
return this.keyValues().map(valuePair => valuePair.key);
}
The values
method will look similar to the keys
method, returning an array of all values stored in the dictionary:
values() {
return this.keyValues().map(valuePair => valuePair.value);
}
Iterating each ValuePair of the dictionary
Let's write a forEach
method that will iterate each ValuePair in the dictionary and evoke a callback function for each iteration:
forEach(callbackFn) {
const valuePairs = this.keyValues();
for (let i = 0; i < valuePairs.length; i++) {
const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
if (result === false) {
break;
}
}
}
size, isEmpty, clear, and toString methods
size() {
return this.keyValues().length;
}
Note we could have evoked the Object.keys
method instead (return Object.keys(this.table).length
).
Now we can use our size
method for isEmpty
:
isEmpty() {
return this.size() === 0;
}
As expected, clear
is very simple:
clear() {
this.table = {};
}
Finally, the toString
method:
toString() {
if (this.isEmpty()) {
return '';
}
const valuePairs = this.keyValues();
let objString = `${valuePairs[0].toString()}`;
for (let i = 1; i < valuePairs.length; i++) {
objString = `${objString}, ${valuePairs[i].toString()}`;
}
return objString;
}
Conclusion
I hope this article helped you gain a better understanding of dictionaries and the common methods associated with it. I sort of considered this to be a warm up for a later article I plan to write soon on Hash Tables so stay tuned for more!
- Creating Dictionary using Object by Ismail Baydan of Poftut
Top comments (0)