Data Structures: Hash Tables — from a Javascript perspective.

Building those Data Structure muscles!

Hash Function

First things, first, we will build the Hash function that all {key: value} pairs will be sent through to be hashed. Two things to know about the Hash function: #1. Once you put anything through to be hashed, you can never put that hashed return value through the function to obtain your original value, hence why hashing is so incredible for security uses (reminds of Ruby gem: bcrypt and hashing passwords to get password_digests). Hashing is irreversible. #2. No matter how many times you put the same input into a Hash function, the function will return the same hashed value every single time. Hashing is deterministic.

The return of the Hash function is determinate on the size of the bucket, but the same key given to the hash function will always return the same hashed output, no matter how many times its input.

Hash Table

The next step, after we have defined our Hash function is to build our Hash Table class. There is a way to build this functionality without constructing a class, and an example of this can be seen in Beau Carnes’ video here⁴.

Hash Table class constructor

INSERT

SEARCH

REMOVE

COLLISIONS

Two different inputs CAN return the same hash result, and this is called a collision. This can be seen in the image above, where tomatoes and squash both live at index 1 in our Array. In our code, specifically, JavaScripts Map function takes care of these instances for us. It makes sure not to over-write the value of key of tomato, but instead add squash, so that two objects can live simultaneously at index 1. There are other ways of achieving this using other data structures (for more info feel free to look into Separate Chaining), but Map is pretty amazing for this.

TIME COMPLEXITY OF HASH TABLES

Hash Tables, are incredibly fast for adding, finding and deleting objects in our data, as you can see in the functions of insertion, searching and removing (above). All 3 of these functions give us an average Big O(1) for time complexity. Obviously, our space complexity will be O(n) because the more elements in our data, the more space we take up in a linear degree. On the other hand, Hash Tables aren’t the useful for searching when you don’t know the key and especially are not to be used for sorting.

Beau Carnes⁴
  1. Hash Tables — Data Structures in JavaScript | beiatrix | ‘https://www.youtube.com/watch?v=QuFPIZj55hU
  2. String.prototype.charCodeAt()| ‘https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/charCodeAt
  3. Hash Tables — Beau teaches JavaScript | Beau Carnes — Free Code Camp | ‘https://www.youtube.com/watch?v=F95z5Wxd9ks
  4. Map | ‘https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

Software Engineer. A new addict of ReactJS & Javascript, CSS & APIs, with a little dabbling in Ruby, Ruby On Rails…