DEV Community: draczihper

Set Implementation In JavaScript

draczihper — Sat, 28 Sep 2024 10:44:22 +0000

Introduction

Do you know the popular data structure Set in Javascript? Or you might have seen the below snippet in some of Javascript codes.

const mySet = new Set();
mySet.add("apple");
console.log(mySet.has("apple")); // OUTPUT: True
mySet.delete("apple");
console.log(mySet.has(apple)); // OUTPUT: False

Set is a built-in data structure that allows you to store unique values of any type, whether they are primitive values of object references. Unlike arrays, which allow duplicate values, a Set guarantees that all elements are unique.

Key Characteristics of a Javascript Set

Uniqueness: A Set has no duplicates and if you try to add a duplicate value it is ignored.
Order: A Set maintains insertion order, so values are iterated in the order they were inserted.
Data types: A Set can hold any type, including objects, primitives and even other set.
No Key-Value pairs: A Set only has values unlike key-value pairs in Map.

Advantages of using a Javascript Set

Automatic uniqueness: Every element in the set is unique.
Fast lookups: Checking if an element exists is faster than in array due to it's constant time complexity O(1).

It is worth noting that, there are many advantages of using Set such as in mathematics and complex database systems but let's stick with these two for now.

Implementation

Normally a Set in Javascript is implemented by hashing the value(due to absence of key-value pairs, we just regard it to key) passed as an argument in a hashing function. The hashing implementation is not explicity described in Javascript documentation, so we will implement our own hashing function (🤞-fingers crossed, it outperforms our considerations which we will talk about later). It's also worth noting that, we will implement a sort of Linked List through chaining to avoid collisions if two different keys have them same hash code after hashing. If you don't know what is hashing? what does it do? and how it's done?, please check out this article.

Node class

We will create a class called Node to store/add our keys. This class will create an object that has key and next property.

class Node {
    constructor(key){
        this.key = key;
        this.next = next;
    }
}

HashSet class

We will create a HashSet class that implements our hashing function and other useful Set methods. In our constructor we declare a variable initialCapacity equal to 1, to store the initial length of buckets array.
Buckets are useful storage location of keys which will be hashed. We will use these buckets to do operations (like delete, insert, lookup) on that key by using the hash generated.
Size property is initialized to track the size of our hash set and load factor of 0.75 is set in order to expand our buckets when 75% of elements fill up the buckets.

class HashSet {
    constructor(initialCapacity = 1) {
        this.buckets = new Array(initialCapacity);
        this.size = 0;
        this.loadFactor = 0.75;

    }
}

Hash function

We define a method (object function) that takes as a parameter the key that is supposed to be hashed and return the hash code which will be used as index for the bucket to store the key.

// Define hash function inside the HashSet class

hash(key) {
    let primeNumber = 31;
    let hashCode = 0;

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

We multiply by prime number 31 because it helps reduce the possibility of hash code being evenly divisible buckets length and avoid collision (though not at 100%). Prime number 31 is a choice in this case as it one of the prime number that does not lead to many collisions. You can read this stackoverflow question to get more context. We also find the UTF-16 code of the key by iterating through every character in the key and later modulo the whole operation by our buckets length to avoid hash codes outside our buckets length.

Add method

Inside the hash set class and below the hash function we add our first method to put keys inside our hash set. Add method takes the key as a parameter. In the first if statement we check if size has reached the load factor in order to resize our hash set.
If the hash set is empty, we then find the index in the buckets array, where our hashed key will stay. Check the bucket at the index if it is empty and then put our key inside else we return that the key already exists, and if it does exist we set the next property equal to the new key.

add(key) {
        if (this.size >= this.buckets * this.loadFactor) {
            this.resize() // Resize our hash set as elements increase
        }

        const index = this.hash(key);
        if (!this.buckets[index]) {
            this.buckets[index] = new Node(key);
            this.size++;
            return true;
        } else {
            let current = this.buckets[index];
            while (current) {
                if (current.key === key) {
                    return false; // Key already exists
                }
                if (!current.next) {
                    current.next = new Node(key);
                    this.size++;
                    return true;
                }
                current = current.next;
            }
        }

}

Has method

The has method return a boolean, if the key is available in the hash set. It takes a key parameter and hashes it to find the index of the key in the buckets array. It then iterates throught the hash set and return true if current index key is equal to the key parameter.

has(key){
    const index = this.hash(key);
    let current = this.buckets[index];
    while(current){
        if(current.key === key){
            return true;
        }
        current = current.next;
    }
    return false;
}

Remove method

The remove method, removes a key passed as a parameter. It hashes the key and gives the index in the bucket array. Keeps track of the previous node by defining let prev = null. After that we iterate the hash set and check if our current key of iteration is equal to the key. If it is equal and it is not the first element because in the first element the previous node is null, we remove that node else we remove the first node. Later we update the previous node equal to current node and current node equal to the next node to ensure our iterations goes through all elements.

remove(key) {
    const index = this.hash(key);
    let current = this.buckets[index];
    let prev = null

    while (current) {
        if (current.key === key){
            if (prev){
                prev.next = current.next;
            }else {
                this.bucket[index] = current.next
            }
            this.size--;
            return true;
        }
        prev = current;
        current = current.next;
    }
    return false;
}

Resize method

Resize methods expands the length of our buckets array when elements in the bucket reach the load factor. In other words when we have three elements(keys) or above and four buckets, we double our buckets array. Resize method also acts as an add method on the new capacity of our hash set. It rehashes previous available elements and put them in buckets array again. This helps to reduce collision and evenly distribute elements.

resize() {
    const newCapacity = this.buckets.length * 2;
    const newBuckets = new Array(newCapacity);

    for(let i = 0; i < this.buckets.length; i++) {
        let current = this.buckets[i];
        while(current){
            const newIndex = this.hash(current.key) % newCapacity;
            if(!newBuckets[newIndex]){
                newBuckets[newIndex] = new Node(current.key);
            } else {
                let newCurrent = newBuckets[newIndex];
                while(newCurrent.next){ 
                    newCurrent = newCurrent.next;
                }
                newCurrent.next = new Node(current.key);
            }
            current = current.next
        }
    }
    this.buckets = newBuckets;
}

Size method

The size method return the size of our hash set.

size(){
    return this.size;
}

Clear method

Clear method, clear our hash set and set the size equal to 0.

clear(){
    this.buckets = new Array(1);
    this.size = 0;
}

Keys method

Keys method create an array and iterates over the hash set to push all available keys one by one including keys that were hashed to the same index.

keys() {
        const allKeys = [];
        for (let i = 0; i < this.buckets.length; i++) {
            let current = this.buckets[i];
            while (current) {
                allKeys.push(current.key);
                current = current.next;
            }
        }
        return allKeys;
    }

There are other useful methods like bucketCount() to see how many buckets are in our hash set and collisions to view all the collisions in our hash set but that's something for later on. If your interested to see how they are implemented, go checkout this github repo.

Common Considerations

Hash Collisions: In practice, hash functions can result in the same index for different keys. This implementation resolves collisions using chaining, where multiple values are stored in an array at the same index.
Performance Considerations: A poorly distributed hash function can cause excessive collisions, making the time complexity closer to O(n) instead of O(1).

Common Use Cases

Filtering Duplicates: For example, when you need to remove duplicates from a list of items.
Membership Testing: Checking if a value exists in a collection.
Efficient Data Lookups: For quick existence checks in algorithms that require this (like graph algorithms or caching).

That's it for this tutorial, I hope you have learned something. If you have any suggestions, corrections, opinions don't hesitate to say something.

AI Era: A Perfect Time for Jack of All Trades, Master of None

draczihper — Mon, 23 Sep 2024 21:14:47 +0000

In today’s rapidly evolving AI landscape, particularly within software development and engineering, I believe we're entering the perfect era for being a "jack of all trades." While this might sound controversial or counterintuitive to some, let me explain why.

AI, especially large language models (LLMs) like GPTs, has become increasingly adept at performing tasks that once required significant time and expertise. From creating elegant, responsive websites to writing compelling content or designing interfaces, these tools can now handle what used to take entire teams of specialists. The time-intensive tasks of the past have become a matter of minutes for AI. This shift is why I argue that focusing on mastering one skill, such as being a specialist in HTML or CSS, may no longer be a sustainable approach for many developers.

Why is this the perfect time for a "jack of all trades"?
Because the nature of AI today allows developers to move beyond strict specialization. AI tools enable us to quickly prototype and build products, reducing the need to dedicate years to mastering just one niche skill. A single developer can now leverage AI to generate code, design interfaces, and handle basic integration, tasks that previously required more manual expertise. As a result, developers who can navigate multiple areas, even at a basic level, will have more flexibility and adaptability in this AI-driven era.

For years, the software development workflow has grown increasingly complex to ensure better user experience and more robust products. This complexity pushed many of us to specialize, often becoming masters of one skill to reduce the friction and speed up development. However, I believe this narrative is changing. AI has the potential to simplify workflows, and a single developer can now do more, especially when dealing with projects involving straightforward, single-language workflows and basic integrations.

Will AI replace developers?
While AI has not yet reached a point where it can replace developers entirely, it’s undeniable that certain roles, particularly those focused on simpler tasks, may one day be automated away. In anticipation of this shift, it’s essential to evolve—to broaden our skill sets and be able to connect the dots across the entire software development lifecycle. This is where being a "jack of all trades" becomes invaluable. By understanding multiple aspects of the development process, you position yourself as an agile problem solver rather than someone who risks being left behind.

In conclusion, the era of AI challenges the old notion that you must be a master of one skill to succeed. The "jack of all trades" approach has never been more relevant, especially as AI continues to democratize access to powerful tools that make development faster and more efficient. Adaptability and broad knowledge are becoming key assets in the modern development landscape.

Understanding JS getters and setters

draczihper — Sun, 26 May 2024 16:26:31 +0000

Let's dive to understand getters and setters from a 10x newbie. You should have a basic knowledge of JavaScript objects and classes to go on with this tutorial.

`get`

What is get in JavaScript?
get is a syntax that binds an object property to function, that will be called when that property is looked up.

Using `get` in objects

//  Object example with a getter
const obj = {
name: 'John',
surname: 'Doe',
age: 32,
get intro() {
return `Hello there, my name is ${this.name} and I am ${this.age} years old`;
  }
}

console.log(obj.intro) 
// OUTPUT: Hello there, my name is John and I am 32 years old

So a get is used to look into a function code and run it. Without the get syntax the output will be the whole function intro() { /* ... */} because calling our obj.intro won't know what to do with our function call and hence it returns the whole function.

get can bind property names of the function. Example;

const obj = {
/* code... */
get prop() { /* code to be executed when calling obj.prop */ }
}

Also get can use computed property names (expression). Example;

const obj = {
/* code... */
get [expression]() { /* code to be executed when calling obj.[expression] */ }
}

Using `get` in classes

In classes get is used the same as in objects but since getter properties are defined on the prototype property of the class unlike in object you need to instantiate the class with the new keyword, otherwise calling raw class will return undefined. Example;

class WithGet {
  text = "Hi there";

  get greeting() {
    return this.text;
  }
}

// Without instantiation
console.log(WithGet.greeeting)
// OUTPUT: undefined

// With instantiation
const greet = new WithGet()
console.log(greet.greeting) 
// OUTPUT: Hi there

That's it on understanding getters. Some advanced concepts on static and private getters, deleting a getter, defining a getter on an existing object are discussed here.

get is useful because it provides encapsulation, allowing you to control access to the internal properties of an object.
get is used for lazy evaluation, where a value is only computed the first time it is accessed.
get provide a clean and readable way to access properties.

`set`

What is set in JavaScript?
set syntax binds an object property to a function to be called when there is an attempt to set that property.

Using `set` in objects

// Object example with a setter

const score = {
  sheet: [],
  set grade(passmark) {
    this.sheet.push(passmark);
  }
}

score.grade = 'A';
score.grade = 'B';

console.log(score.sheet);
// OUTPUT: ["A", "B"]

So a set is used to set put into a property some value defined in the setter eg. in our score object, set is used to put grades in the sheet array property. Without the setter set our code would run but it would return an empty array [] because the grade function method won't know what to do with sheet array property.

set can bind a function method. Example;

const obj = {
/* code... */
set prop(val) { /* code to be executed when calling obj.prop */ }
}

Where the val parameter is the value which you want to set on the object.

Also set can use computed property names (expression). Example;

const obj = {
/* code... */
get [expression](val) { /* code to be executed when calling obj.[expression] */ }
}

Using `set` in classes

In classes set has the same syntax but commas are not needed between methods. Example;

class WithSet {
  text = "Hi there";
  get greeting() {
    return this.text;
  }

  set greeting(name) {
     this.text = `Hello ${name}`;
  }
}

// Without instantiation
console.log(WithSet.greeting)
// OUTPUT: undefined

// With instantiation
const greet = new WithSet()
greet.greeting  = 'John';
console.log(greet.greeting) 
// OUTPUT: Hello John

Note In classes, to return the code which the setter (for this example greeting setter) has done action on, you need a getter otherwise, you need to explicitly define a function method that will return the greeting or use a constructor.

That's it on understanding setters. Some advanced concepts on static and private setters, deleting a setter, defining a setter on an existing object are discussed here.

set allows you to control how properties of an object are modified thus offering control and encapsulation of code.
set help maintain the integrity of the object's data by ensuring that any changes are validated and processed correctly before being applied.
set centralize the logic for updating a property, which makes the code easier to maintain and refactor.

Thanks for reading this tutorial and I hope you understood what are getters and setters. For any queries, corrections or suggestion please comment so we can all level up to 10x newbies😉.