How to Uses Hashes, Maps, and Sets in JavaScript

One of the first thing new JavaScript programmers learn is hashes.  Hashes are useful for saving data, nesting data, and in general having a faster Big-O lookup time than arrays*.

*Do you know the reason that hashes have O(1) lookup time?  IT'S BECAUSE A HASH IS A FUNCTION!  You take in your hash keys, do a bunch of fancy math, and out pops a singular result for each key input.  It still sort of blows my mind that a hash is essentially the sort of thing we studied in Algebra 1, only you can input strings, numbers, whatever you want into a hash and it'll still spit out an answer.  Of course, all those strings and s and whatnot are of course binary numbers, so it makes a fair amount of sense when you think about it.

If you had Aleph-One amount of memory, you could make a hash table for these functions.

Hashes are useful for all sorts of things as well - the sorts of things you might encounter in code challenges in particular, like counting up how many of a thing there are in an array, or doing something every time something happens in an array, or...basically making an array cooler.

let array = [1,1,3,2,0,2,3,3]
let hash = {}

for (let i=0; i < array.length; i++) {
if (!hash[array[i]]) {
hash[array[i]] = 1
} else {
hash[array[i]]++
}
}

console.log(hash)
//this code counts up how many of each number there are in the array. See the result below:


Hashes are certainly useful, but they have some limitations.  The numbers in the hash above, for instance, are listed in numerical order.  Not because they're actually ordered, but because that's how the console prints them out.  This can be really frustrating if, for instance, you want to find out what key was the first one made for your hash, or you wanted to order your keys and take them out later.

Enter hashmaps.

A hashmap is exactly like a hash, except that it is ordered.  It's a bit like a hash plus an array.  So you can do things like spit out your ordered pairs in the order they were entered:

let array = ["c","c","1","b","z","b","a",'a']
let map = new Map

for (let i=0; i < array.length; i++) {
if (!map.has(array[i])) {
map.set(array[i], 1);
} else {
map.set(array[i], map.get(array[i]) + 1);
}
}

console.log(map)

for (const [key, value] of map.entries()) {
console.log(key, value);
}

console.log("map size:", map.size)

What do we get when we run the above code?


Not only does JavaScript not re-order the hashmap entries when printing them out, it also actually keeps that order in its internal structure.  And, very importantly, that ordering allows them to be iterable - you can do a for-loop with a hashmap, or a .forEach, or whatever iterable you want.  Not only that, but you can check the size of the hashmap!  So very useful, for instance, if you want to know how many keys you have, cap the number of keys you're storing, only iterate up to a certain key, etc.

There's also one other type of object in JavaScript that can be used similarly to hashes: sets.

let array = ["c","c","1","b","z","b","a",'a']
let set = new Set(array)

console.log(set)

Sets are objects that keep only unique values.  So the set above simply keeps the unique objects in the array:


And, as you can see in that single line where we define the set, sets are pretty slick - it doesn't take a lot of code to make one.  So instead of using setting up a hash like this:

let hash = {}

for (let i=0; i < array.length; i++) {
if (!hash[array[i]]) {
hash[array[i]] = true
}
}


to do things like be able to check if your data is new, you can simply make a set and be done with it.

Sets, like maps, also have a size.  So you can do things like find out how many unique elements are in an array very quickly:

let array = ["c","c","1","b","z","b","a",'a']
let set = new Set(array)

console.log("The number of unique values in the array is:", set.size)


Doing this with a hash is much more involved:

let array = ["c","c","1","b","z","b","a",'a']
let hash = {}
let count = 0

for (let i=0; i < array.length; i++) {
if (!hash[array[i]]) {
hash[array[i]] = true
count++
}
}

console.log("The number of unique values in the array is:", count)


So, there you go: the world is much bigger than just hashes and arrays.

Comments

Post a Comment

Popular posts from this blog

Making Logic Gates in JavaScript

Image
Everyone knows that computer programs are made of bits - the ones and zeros that hold all the information that keeps our modern life running. But how do you get from numbers to programs - how simple ones and zeros do  anything? The answer is logic gates (as well as a whole bunch of stuff about how electronics are built - you need to actually make these logic gates on out of circuits in order for our logic structures to be enacted; but I'm a programmer, not an electrical engineer, so let's not go there).  A logic gate is what's known as a  Boolean function , a mathematical operation that takes in bits and spits out more bits. Each logic gate takes in two bits of information (as mentioned before, generally denoted as a 1 (also sometimes represented as true ) or a zero (also sometimes represented as false )), so there are four possible inputs to a logic gate: {0, 0}, {0, 1}, {1, 0}, and {1, 1}.  For each of these inputs, a logic gate can spit out either a 1 or a 0, so t...
Read more

Bitwise Operations

Image
 When I was in 9th grade, I once spent the day going to school with my cousin.  At lunchtime, one of her friends was showing off a newfound skill: "I can count to ten in German! Eins, zwei, drei, vier, funf, sechs, sieben, acht, neun, zehn!" "That's nothing," I said, "I can count to ten in binary.  1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010!" No one got it.  And unfortunately, it seems like binary is also foreign to a lot of software developers as well. What is Binary? Binary is the two-digit radix (or base) system.  In the decimal system - what most people use on a daily basis - we use ten different digits (the Arabic numerals 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) to represent number values.  Numbers in the rightmost position before the decimal point represent that digit's value multiplied by ten to the zeroth power, and each position to the right increases the power of ten by one.  So 12 is actually another way of saying 1*10^1 + 2*10^0; 433 is equi...
Read more

The Sorting Hat

Image
Here's a lesson about the difference between theory and practical applications. Everyone knows about  bubble Sort  and  merge Sort  - they're probably the first two sorting algorithms you learned.  Everyone also knows that (1) bubble sort sucks and (2) this is due to the fact that its average time complexity is O(n^2), aka the worst time complexity.  It even generally performs worse than things like insertion sort and  selection sort , the "a D- is still a passing grade" of sorting algorithms. While all these things are true, there's a more important truth: always test your code. While reading  The Imposter's Handbook by Rob Conery  the other day and flipping through the comparison sort algorithms he provides, I decided, Why not actually test out this code?   And, the  speed test demon  that I am, my test involved sorting out his [23,4,42,15,16,8] array one million times with bubble sort and with merge sort, and I got this res...
Read more