BTG Coding School

Hash Tables

Last time we learned about arrays, which allow efficient access to a sequence of values that are stored side-by-side. Values are looked up by their index, which starts at 0 and runs up to length-1.

This is nice for data that is stored close together, and can easily be referenced by number. But sometimes that isn’t very useful.

In this lesson we’ll look at Hash Tables, which work when we want to do lookups based on something beside a number. It also helps for numerical data that isn’t close together, where we might have many spaces.

Hash tables are a general concept you’ll see in many programming languages. Javascript calls their hash tables “objects”, and uses them for more than just storing data.

Hash Table example

Lets look at a basic example :

let vals = { 'cat': 5, 'dog': 3 };
console.log(vals['cat']);

We create an object / hash table much like an array. Instead of [ and ], we use { and } to surround the values. Then we have the data. In a hash table, each entry has two parts. The key is what is used for looking up in the table, and the value is the value stored at a given key. You can kind of think about arrays having only numeric keys. And since arrays are sequential, we didnt need to specify the key for each value.

When creating a hash table, we put the key, followed by : then the value. Each entry is comma separated, just as with arrays.

When we want to look up a value, we use the square brackets just like with arrays.

Why are they called “objects” in Javascript?

In many programming languages, hash table keys must have the same type K, and values must have the same type V. We can then say that the table maps values from K to V.

Javascript does not have this limitation. Javascript then uses hash tables to implement “object oriented programming”. Here, each hash table or “object” can be thought of as representing some real world object, and each value within the hash table as some attribute of some object.

For representing players in a 2d game, for example, you could have: 

let player1 = {
    'name': 'p1',
    'x_position': 0,
    'y_position': 5,
    'health': 100
};

let player2 = {
    'name': 'player2',
    'x_position': 15,
    'y_position': 2,
    'health': 80
};

Object oriented programming is just one way of solving problems, and is otherwise outside the scope of this course. I include this here just to give a bit more context to why this structure is called an object in Javascript.

Other object operations

There are several other common operations on hash tables. Here is a table of the most common things you’ll need, as well as how to accomplish them in Javascript.

What Javascript example
checking if a key exists 
 
let a = {};
if ('cat' in a) {
  console.log('a has a key named "cat"');
}
looping over keys in a table 
let vals = { 'cat': 5, 'dog': 3 };
Object.keys(vals).forEach(function(key) {
  console.log('key ' + key + ' equals: ' + vals[key]);
});
removing an entry 
 delete vals['cat'];

Exercises

  1. Given an array, of many values, find the most common value.

    Hint You'll want to use a hash table that tracks the number of times you have seen a value. When you encounter a value, you can update the count if you've seen it before, otherwise insert a 1 count. Then you can go through your hash table to find the most popular one. ( As an improvement, can you implement it without needing to go through the hash table again?)

  2. (Challenge) Suppose you’re playing a game of scrabble, and want to see if you can make a given word from the letters you have so far. Write a function, buildable(letters, tryToMake), that takes two strings. Letters is a list of the letters you have, and tryToMake is a word that you want to check if you can make from what you have.

    Hint For each word, you'll want to create a map that goes from letter->count for that letter. Once you have these two maps, check the letters in tryToMakeMap and ensure they're less than or equal to the count in lettersMap.

Solutions

  1. let counts = {}
let vals = [1, 2, 3, 4, 3, 2, 2, 1];
let mostFrequent = undefined;
for (let i = 0; i < vals.length; i++) {
    let val = vals[i];
    if (val in counts) {
        counts[val] += 1;
        let count = counts[v];
        if (mostFrequent == undefined || counts[mostFrequent] > count) {
            mostFrequent = val;
        }
    }
}

  2. function makeCounts(word) {
    let have = {};
    for (let i = 0; i < word.length; i++) {
        if (word[i] in have) {
            have[word[i]] += 1;
        } else {
            have[word[i]] = 1;
        }
    }
    return have;
}

// Returns true if every letter in candidateMap
// shows up fewer times than it does in haveMap.
// Otherwise it has too many of that letter and
// cannot be built.
function buildable(letters, candidate) {
    let lettersMap = makeCounts(letters);
    let candidateMap = makeCounts(candidate);
    // We 
    for (let i = 0; i < candidate.length; i++) {
        let letter = candidate[i];
        if ((letter in lettersMap) == false) {
            // we dont have that letter at all, return false
            // right now
            return false;
        } else if (lettersMap[letter] < candidateMap[letter]) {
            // it needs too many, stop checking and return false.
            return false;
        }
        // otherwise, the loop continues to check the rest of the letters.
    }
    // If we reach here, then all the checks have passed and
    // the word can be built.
    return true;
}

Next: Wrap up & Reference sheets

This is the last lesson in the programming basics course. On the next page you’ll find a reference sheet for everything covered in this course.