leetcode

Design HashSet solution using TypeScript

This post outlines my TypeScript solution to the "Design HashSet" question on LeetCode.

The solution uses arrays as buckets, which isn't ideal, because the array must be iterated over when searching for a value. However, the hashing function does a pretty good job of distributing the values evenly across the set. In practice, the number of values iterated in a bucket will be very small. For this exercise, the hash set will also not be resized.

/**
 * Design HashSet
 * Design a HashSet without using any 
 * built-in hash table libraries.
 */
class MyHashSet {
    size: number;
    buckets: number[][] = [];

    /**
     * Create a new Hash Set.
     */
    constructor(size = 999) {
        this.size = size;
    }

    /**
     * Add a value to the set.
     */
    add(key: number): void {
        const bucket = this.findBucket(key);
        if (!bucket.includes(key)) {
            bucket.push(key);
        }
        this.buckets[this.findIndex(key)] = bucket;
    }

    /**
     * Remove a value from the set.
     */
    remove(key: number): void {
        const bucket = this.findBucket(key)
        const index = bucket.indexOf(key);
        if (index !== -1) {
            bucket.splice(index, 1);
        }
    }

    /**
     * Check if the set contains a value.
     */
    contains(key: number): boolean {
        const bucket = this.findBucket(key)
        return bucket.includes(key);
    }

    /**
     * Retrieve an entry array index for a given key.
     */
    findIndex(key: number): number {
        return Math.abs(this.createHash(key) % this.size);
    }

    /**
     * Retrieve a bucket for a given key.
     */
    findBucket(key: number): number[] {
        const index = this.findIndex(key);
        return this.buckets[index] || [];
    }

    /**
     * Generate a hash code for a given number
     */
    createHash(key: number): number {
        let result = 0;
        for (let i = 0; i < `${key}`.length; i++) {
            result = (((result << 5) - result) + `${key}`.charCodeAt(i)) & 0xFFFFFFFF;
        }
        return result;
    }
}

more LeetCode posts