CODEWITHSUNDEEP
javascriptduplicates
Swink
Swink

Reputation: 457

Javascript - Clarification on HashTable

I was watching a video on how to create a function to replace all duplicates in an array. For example, if an array consists of [1,1,2], the function will output simply [1,2].

After watching the video , the final code was : 

let removeDuplicates = (a)=>{

let input = {};
let output = [];

for (let i = 0; i < a.length; i++){
    let el = a[i];

    if (!(el in input)){
        input[el] = true;
        output.push(el)
    }
  };
  return output;
}

I understand majority of the function, but I'm having trouble understanding how the HashTable Input is used during the if statement.My questions are 1) how can we check if el isn't in input we input is never used previously in the function. 2) why do we set input[el] = true .

I'm sorry if this is not the clearest question in the world. I just can't get this question out of my head. Thanks in advance for the help.

Upvotes: 1

Views: 163

Answers (4)

DJDaveMark
DJDaveMark

Reputation: 2855

input starts off empty {}, then after the 1st loop looks like {"1": true} then after the second loop, nothing has changed, after the 3rd loop looks like {"1": true, "2": true}

The code would still work even if we changed it to any of the following:

input[el] = undefined;
input[el] = null;
input[el] = el;
input[el] = "blah";
input[el] = "";
input[el] = false;
input[el] = 0;

because input contains a key "1" then the value 1 will never be added to the output array more than once. The test which handles this could also be changed from:

if (!(el in input)){

to:

if( !input.hasOwnProperty(el) ) {

See: Object.prototype.hasOwnProperty

You could also log the content of input at the end of the for loop to see what's going on like this:

console.log(JSON.stringify(input));

I've used JSON.stringify to avoid any 'helpful' browser consoles updating the content of previously logged objects.

Basically, play with the code to see what happens. If you only ever read how to code, you'll never be able to code.

Here's a snippet of the code you can run/modify to see how it works:

let a = [1, 1, 2];

let input = {};
let output = [];

console.log(JSON.stringify(input));

for (let i = 0; i < a.length; i++){
    let el = a[i];

    if (!(el in input)){
    //if (input.hasOwnProperty(el))){
        input[el] = true;
        //input[el] = undefined;
        //input[el] = null;
        //input[el] = el;
        //input[el] = "blah";
        //input[el] = "";
        //input[el] = false;
        //input[el] = 0;
        output.push(el)
    }
    
    console.log(JSON.stringify(input));
}

console.log(output);

and just for completeness you could also do away with the pseudo-hash input object by simply doing the following (although performance wise is probably much slower for big arrays):

let a = [1, 1, 2];
let output = [];

for (let i = 0; i < a.length; i++){
    if (output.indexOf(a[i]) === -1 ){
        output.push(a[i])
    }
}

console.log(JSON.stringify(output)); // [1,2]

Upvotes: 1

Tamir Kfir
Tamir Kfir

Reputation: 398

  1. input is declared outside of the for loop, therefore it existed before the function and still exists inside the for loop scope throughout its course. More info about the let keyword and its scoping.
  2. We could set it any value we want, just so there's an el key in input

Upvotes: 1

javaBean007
javaBean007

Reputation: 565

Good question, other people may be asking the same thing. Actually your second question answers your first question once you understand how it works, so lets start there.

2) The first thing to understand is what we are concerned about is having the output array returned without any duplicates, so we set input[el] = true, because we want this to occur. Any value that makes it through the if check, is added to input object, then to our desired output. The input behaves similar to a HashTable or Set in this case:

1)With that understanding, we can see that input object is being declared outside of the loop but within the function, so it's entire purpose is just a container(Set) to check against, via the if check, before we add an item to our output.

This can be tested out by:

let input = {};
input["One"] = true;
console.log(input); //outputs {One: true}

Upvotes: 0

cptwonton
cptwonton

Reputation: 468

  1. Basically, the code is using the input variable as a way to hold all the values already seen as we iterate over the passed in a array. Input starts off as empty, and gets populated as we iterate thru a. It is in scope from the perspective of the for loop.

  2. The code sets input[el] = true, but actually you could set input[el] to anything and have the code still work. All the conditional !(el in input) is checking is that input has an object with a key of el. The value of that key does not matter in this case.

Using your example where a is [1,1,2]...

You begin with having the input object as empty.

Then, you take in the first element of a, 1, and set el = 1.

if 1 is not in input (it's not), you set input[1] = true, and push 1 onto the output array.

Next, you take in the second element 1 and set el = 1.

!(el in input) at this point is false since 1 is already in the input object. you ignore this and continue to the next element in a.

finally, you check 2 and set el = 2. if 2 is not in input (it's not), you set input[2] = true, and push 2 onto the output array.

A more straightforward way to do this is to convert the array to a set.

Or alternatively, you could just use the output array and use the indexOf method on each element of your passed in a variable to see if it already exists in output - if not, add it. otherwise continue.

Upvotes: 0

Related Questions