DEV Community: AvishkarDalvi

Your own HashTable/Dictionary/Map in JavaScript

AvishkarDalvi — Thu, 19 Aug 2021 18:39:32 +0000

We often use Hashtables/Maps/Dictionaries to store data as they provide fast lookups at O(1). Even arrays provide O(1) lookups but only if you are aware of the index of the element that you are trying to access, otherwise you have to loop through the array and check every element to finally find a match thereby making the time complexity O(n).
In JavaScript, even objects are like maps as even they store data in key-value pairs but the only difference is objects can only have strings as keys whereas maps can have any data type as a key.
Let's implement our very own HashTable.For this, we will declare a JavaScript class with a constructor with just one property that will be an array(an array of arrays to be fair).

class HashTable {
  constructor(size){
    this.data = new Array(size);
  }

As we know for O(1) lookup we need to store the key-value pair at a particular index in this array so that we can access the same using that index. Thus whenever we insert a key-value pair in the HashTable, the key is passed to a hash function that generates an array index location where the key will be stored. This particular hash function has to be an idempotent hash function, which means that a given input will always generate the same output. (example: if it generates 104 for 'mango' then it will always generate 104 for 'mango', the output will not change over time).
Let's implement the hash function, I am using the below logic you can use any hashing logic you wish.

hash(key) {
    let hash = 0;
    for (let i =0; i < key.length; i++){
        hash = (hash + key.charCodeAt(i) * i) % this.data.length
    }
    return hash;
  }

Java guys can make this hash function private, as it will only be used internally. Notice that we use % this.data.length so that the hash value which will be used as the array index of the list this.data does exceed the length of this.data.
Now, let's use this hash function to insert key-value pairs in our HashTable by implementing the set method. This method takes two parameters namely the key and value, in which the key is passed to the hash function which generates a number that is the index position of the this.data array and we will store this key-value pair as an array at the index location i.e [key, value] at this.data[hashValueOfKey].

set(key, value) {
    let address = this.hash(key);
    if (!this.data[address]) {
      this.data[address] = [];
    }
    this.data[address].push([key, value]);
    return this.data;
  }

Here we calculate the hash for the key, check if something exists at that calculated hash index of that array, if not then we create an array at that index place the key-value pair inside it. If the array index already holds an array of key-value pairs then we push the new array of key-value pairs inside the array present at that index of this.data.
Lastly, let's implement the get function that accepts the key as a parameter and retrieves the value that we inserted alongside that key. In this function first, we calculate the hash for key passed as our hash function is an idempotent function thus it will generate the same value(index of this.data) that was generated at the time of insertion of the key-value pair in case of set method. Then if we find an array present that at the generated index location of this.data then we iterate over that array(this array contains arrays that have two elements key and value i.e [key, value]) and check if the key passed to our get function matches with the first element of any of the subarrays, as the first element is the key and the second element is the value. If we find a match then we return the second element i.e value of that array else we return undefined.

get(key){
    const address = this.hash(key);
    const currentBucket = this.data[address]
    if (currentBucket) {
      for(let i = 0; i < currentBucket.length; i++){
        if(currentBucket[i][0] === key) {
          return currentBucket[i][1]
        }
      }
    }
    return undefined;
  }

In this way, we have implemented the HashTable with O(1) insertion and lookup, below is the full code

class HashTable {
  constructor(size){
    this.data = new Array(size);
  }

  hash(key) {
    let hash = 0;
    for (let i =0; i < key.length; i++){
        hash = (hash + key.charCodeAt(i) * i) % this.data.length
    }
    return hash;
  }

  set(key, value) {
    let address = this.hash(key);
    if (!this.data[address]) {
      this.data[address] = [];
    }
    this.data[address].push([key, value]);
    return this.data;
  }

  get(key){
    const address = this.hash(key);
    const currentBucket = this.data[address]
    if (currentBucket) {
      for(let i = 0; i < currentBucket.length; i++){
        if(currentBucket[i][0] === key) {
          return currentBucket[i][1]
        }
      }
    }
    return undefined;
  }
}

const myHashTable = new HashTable(50);
myHashTable.set('grapes', 10000)
myHashTable.get('grapes')
myHashTable.set('apples', 9)
myHashTable.get('apples')

Your own array in JavaScript

AvishkarDalvi — Fri, 13 Aug 2021 06:29:24 +0000

We know that data structures are built on top of other basic data structures. One of the very basic or the first data structure that we across are arrays. But have you ever wondered how an array is built? If yes then let's try implementing an array from scratch in JavaScript.

For this, you need to have some basic knowledge of objects and classes. Even if you don't I would still insist you continue reading. Let's start, we know that every array holds a list of data and has length. So let's create a class whose constructor has data and length as properties.

class MyArray{

  constructor(){
    this.length=0;
    this.data={};
  }

Next, we should get an item from the array at any index, so let's implement the get method that accepts the index as a parameter and returns the item or data at that particular index.

get(index){
  return this.data[index];
}

The above method returns the item present at the key which is an index in this case from the data object(Remember object["keyname"] syntax).
Next, let's add elements to our array by implementing the push method.

push(item){
  this.data[this.length]=item;
  this.length++;
  return this.data;
}

In this method, we add a new key to the data object and assign a value that is the new item we are inserting against it(as good as object["keyname"]:value). And then we update the length by 1 as we have added a new item.
What comes after the push? Obviously pop. Let's implement pop, so pop basically means to remove the last added item from the array. This means we have to remove the last added key-value pair from the data object, one way to do this in JavaScript is by using the delete keyword and we also have to decrement the length property by 1.

pop(){
  const lastItem=this.data[this.length-1];
  delete this.data[this.length-1];
  this.length--;
  return lastItem;
}

The last method that we implement is deleting the element at a particular index. This method accepts the index as input and deletes the element present at that index

deleteAtIndex(index){
  const item=this.data[index];
  this.shiftItems(index);
  return item;
}

shiftItems(index){
  for(let i=index;i<this.length-1;i++){
    this.data[i]=this.data[i+1];
  }
  delete this.data[this.length-1];
  this.length--;
}

Here we are internally calling the shiftItems method that does a left rotation on the keys of our data object. Thus this operation is of O(n) complexity. In the for loop we iterate from the index passed as a parameter to our method to the second last item of our array(second last key of our data object) and we assign the value of the next element or key to the current key. (left rotation). So {1:val1,2:val2,ind:val3,4:val4,5:val5} becomes {1:val1,2:val2,ind:val4,4:val5,5:val5}. Now we can see that the value at our passed index is replaced or removed but since we did not iterate till the last element we have a duplicate value in the last index and since we are performing a delete operation the array size should also decrease by 1. Thus we use the delete this.data[this.length-1] to delete the last key-value pair of the data object and also decrement the length by 1 in the next step.

So this completes our array implementation. Try this code on your local or console and have your very own implementation of the array. I hope you find this helpful. Thanks and goodbye.
Here is the full code.

// implementing array of our own

class MyArray{

  constructor(){
    this.length=0;
    this.data={};
  }

get(index){
  return this.data[index];
}

push(item){
  this.data[this.length]=item;
  this.length++;
  return this.data;
}

pop(){
  const lastItem=this.data[this.length-1];
  delete this.data[this.length-1];
  this.length--;
  return lastItem;
}

deleteAtIndex(index){
  const item=this.data[index];
  this.shiftItems(index);
  return item;
}

shiftItems(index){
  for(let i=index;i<this.length-1;i++){
    this.data[i]=this.data[i+1];
  }
  delete this.data[this.length-1];
  this.length--;
}
}

const arr=new MyArray();

arr.push("hii");
arr.push("hello");
arr.push("hola");
arr.push("namaste");

// arr.pop();

// arr.get(2);
arr.deleteAtIndex(1);

arr.push("changed")

Migrating from promise chains to async-await and escaping the try catch hell

AvishkarDalvi — Mon, 26 Jul 2021 16:22:55 +0000

async ()=> {
await promise
}

async-await is a life saver when it comes to avoiding callback hell or the pyramid of doom.

function hell(){
step1((a)=>{
  step2((b)=>{
    step3((c)=>{
       // some code ...
         })
       })
     })
}

The above code can be written in a clean line-by-line format using async-await.

async function heaven(){
   const a= await step1();
   const b= await step2(a);
   const c= await step3(b);
   return a + b + c;
}

This is great but when it comes to error handling this simplicity again goes for a toss because you end up with a try-catch tower of terror.

async function towerOfTerror(){
let a;
let b;
let c;

try{
 a=await step1();
} catch(error){
 handle(error);
}

try{
 b=await step2(a);
} catch(error){
 handle(error);
}

try{
 c=await step3(b);
} catch(error){
 handle(error);
}

return a + b + c;
}

All your one-liners have now expanded to at least 5 lines of code.
One easy way out would be to append the catch method to the end of each promise.

await step1().catch(fun);

But that can still get repetitive.

async function getBetter(){
   const a= await step1().catch(err=>handler(err);
   const b= await step2(a).catch(err=>handler(err);
   const c= await step3(b).catch(err=>handler(err);
   return a + b + c;
}

Another option is to create a function that implements one try-catch to replace all the others. It will first resolve the promise and then return an array that has the first element as the data and the second element as an error. But if there is an error then the data is null and the error is defined.

async function awesome(){
 try{
  const data=await promise;
  return [data,null];
 } catch(error){
  console.error(error);
  return [null,error];
 }

Now you can call this function in your code you can de-structure it to get a clean one-liner error handling.

async function main(){
 const[data,error]=await awesome();
 const[data2,error2]=await awesome();
//or use the if statement if you want to handle the error differently
if(error){
   //do something
   }
}

Cross site scripting(XSS) in 10 mins

AvishkarDalvi — Wed, 07 Jul 2021 20:19:27 +0000

What if we have control over the JavaScript of another website? Let your imagination run wild on this one! What could be the possibilities in this case?

We know that JavaScript has access to the HTML documents via the DOM API's which are provided by the browser itself. This means we can manipulate the DOM and make it look different, like changing the styling or the HTML structure of the page or we can read some cookies using document.cookie and send it over to your website via Ajax request or form submission or some other way.

But I think you get the idea that I am trying to convey here, having access to JavaScript on another website in a different user's context can be very problematic.

Now the question is can we really inject some JavaScript into another web page? Well, the answer is yes!!!

And that's exactly what we call XSS or cross-site scripting. In simple words, it is merely a JavaScript injection technique.
Now to explain this with an example let's do a demonstration of an XSS attack. Note that doing an XSS testing is a punishable offense(read cybercrime) so do not do it on an actual website. For learning purposes there are some sites and tools available, we will use: https://xss-game.appspot.com/level1/frame?
Now once you visit this link you will see the following page:
Now what happens here is whenever you enter a query into the search box and click search an HTTP request is sent to the server along with the query that you entered, the server then processes the request and gives a response accordingly which is then displayed on your webpage.(Note this site will always return no results found for any query as the purpose of this site is to make you understand XSS and not serve requests)

Here we type 'hello' and hit search which sends the request to the server with our entered query as a parameter and the server responds with no results.

Notice the query='hello' parameter being sent in the request in the above image.

Notice the response sent back by the server in the above image.

Now let's inject some JavaScript using the script tag and cause an XSS attack, see the image below:

Here we are injecting the JavaScript alert function using the script tag through the input element of the page. And when we hit the search button this code will be executed and we will have an alert box on the page.

Also, check the network tab in the above image, the response is an HTML page and the browser does not know that the input that we sent is being reflected in the response It assumes the whole response is HTML, and thus you can see that our inserted code became a part of that HTML response as script tags are allowed in HTML pages and thus the code gets executed. An attacker can insert his code in this manner and can steal confidential information or user credentials or tokens thus leaving the site vulnerable.(Note: HTML tags or style tags can also be inserted in the above case to deface the page).
There are different types of XSS:

Reflected XSS

We just saw this in the above example where the input was reflected in the response and identified as a script block and then got executed.
Stored XSS

This is the same as the first one but the input is not just reflected but instead, it is persisted or stored in the database and then shown back to the user by pulling it out from the place it was stored. This is an even more powerful attack as the malicious input is stored in the DB and injects everyone who views the page that depended on your input. An example would be the comments section of any website, now if you use the comment section to inject malicious code then the comments containing the malicious code would be stored in the DB and will affect every user that views that comment on the site. Check this video: https://www.youtube.com/watch?v=2GtbY1XWGlQ
DOM XSS

In this the user's input directly lands inside the dangerous part of the JavaScript code, this happens on the client-side.
Mutated XSS

Here the user input is mutated or changed in some way by the browser before inserting it into the DOM which can sometimes lead to cross-site scripting.

Thus Cross-site scripting aka XSS is basically a JS injection. If you are an application developer you will eventually come across this vulnerability and will have to work your way to fix it or mitigate the risk. It is a huge concept and there as some libraries like DOMPurfiy that sanitizes JS and spits out clean HTML.