Implementing a Dictionary in TypeScript

Dictionaries are commonly used collections. They provide the benefit of quickly looking up values based on a supplied Key and these lookups are extremely fast as they don't rely on iterating the collection to locate them. In Typescript this is harder to achieve. I have seen several implementations but many of them use separate backing arrays to hold the keys and the values and either iterate or use an indexOf call to locate the indexes. This can be avoided if you're willing to make the sacrifice of limiting yourself to the string data type for your key. Let's explore how this can be accomplished.

Building the KeyedCollection<T>

Our goal is to have a strongly typed keyed collection that allows you to use a string as the key and any other type for the value. We want to have the basic functionality we're used to with Dictionaries in adding, retrieving and removing values, getting the list of keys, getting a collection of all values, checking for the existence of a value and getting a count of all values. This functionality can be described with the following interface:

export interface IKeyedCollection<T> {
    Add(key: string, value: T);
    ContainsKey(key: string): boolean;
    Count(): number;
    Item(key: string): T;
    Keys(): string[];
    Remove(key: string): T;
    Values(): T[];
}

In the above interface, we see that our definition does not container an indexer. This is by design. Technically we could apply an indexer to our interface and final class, but it would then require that all methods defined would return type T. It would also mean that if someone were to add an object with a key of, say "Count", that our Count method would be replaced. Instead, we will use the Item method to act as our indexer and instead of a backing array, we will use a backing object to store our values.

This does come with one tradeoff. Adding and retrieving a single value is fast, however retrieving the list of Keys and the list of Values (which are returned as arrays) carries a bit of a penalty since the backing object will have to be transformed into an array. We could mitigate this by caching those key and value arrays and invalidating those caches when items are added or removed.

So what does our backing object look like? Well, it can be defined in a single line of code. Typescript allows you to use [index: type] to specify an indexer. This means that we can create our backing object by simply declaring it as:

private items: { [index: string]: T } = {};

This tells us that we will have a string based index (the only two allowed types are 'string' and 'number') and we will have a value of type T. On its own, this doesn't make a whole lot of sense, but remember that we defined T as part of our interface above. The base of our collection will look like this:

export class KeyedCollection<T> implements IKeyedCollection<T> {
    private items: { [index: string]: T } = {};
}

Now all that's left is to implement the remainder of our interface methods. Since we've used the structure above, we can use the items[key] notation to retrieve an item in the collection and we can use JavaScript's built in item.hasOwnProperty(key) function to determine of a key exists. Since our backing store is actually an object and not an array, we will also keep a local "count" of how many items we have in our collection.

Here is the initial implementation of our KeyedCollection<T>

export class KeyedCollection<T> implements IKeyedCollection<T> {
    private items: { [index: string]: T } = {};

    private count: number = 0;

    public ContainsKey(key: string): boolean {
        return this.items.hasOwnProperty(key);
    }

    public Count(): number {
        return this.count;
    }

    public Add(key: string, value: T) {
        if(!this.items.hasOwnProperty(key))
             this.count++;

        this.items[key] = value;
    }

    public Remove(key: string): T {
        var val = this.items[key];
        delete this.items[key];
        this.count--;
        return val;
    }

    public Item(key: string): T {
        return this.items[key];
    }

    public Keys(): string[] {
        var keySet: string[] = [];

        for (var prop in this.items) {
            if (this.items.hasOwnProperty(prop)) {
                keySet.push(prop);
            }
        }

        return keySet;
    }

    public Values(): T[] {
        var values: T[] = [];

        for (var prop in this.items) {
            if (this.items.hasOwnProperty(prop)) {
                values.push(this.items[prop]);
            }
        }

        return values;
    }
}

Using the KeyedCollection<T>

Now that we have a keyed collection in place that can quickly lookup items, the last thing to do is use it! Below is a quick example demonstrating how we would implement this collection in our application.

var ages = new Dictionary<Number>();
ages.Add('Dustin', 36);
ages.Add('Amy', 25);
ages.Add('Angie', 35);
ages.Add('Josh', 4);

var hasJosh = ages.ContainsKey('Josh'); //will return true
var hasBen = ages.ContainsKey('Ben'); //will return false
var amyAge = ages.Item('Amy'); //will return 25
var keys = ages.Keys(); //will return ['Dustin', 'Amy', 'Angie', 'Josh'];
var vals = ages.Values(); //will return [36, 25, 35, 4];
var count = ages.Count(); //will return 4;

ages.Remove('Josh'); //removes Josh
count = ages.Count(); //will return 3;

Conclusion

And that's it. With some minor tradeoffs we can achieve a pretty efficient dictionary structure in Typescript. If the majority if your code will be adding and retrieving singular values, this solution makes a lot of sense. However, if you find that you're spending more time enumerating the complete set of values and/or keys it may be more efficient to use one of the solutions that use backing arrays, or even make your own.

Dustin Horne