# Unveiling the Magic of Hash Tables: Your Ultimate Guide to Efficient Data Lookup PT. 2

Photo belongs to [Ján Jakub Naništa](https://unsplash.com/es/@janjakubnanista?utm_content=creditCopyText&utm_medium=referral&utm_source=unsplash) in [Unsplash](https://unsplash.com/es/fotos/edificio-de-hormigon-blanco-y-azul-de-4-plantas-UHyrjKPsshk?utm_content=creditCopyText&utm_medium=referral&utm_source=unsplash)

Last week, we began [exploring Hash Tables](https://medium.com/@rubenosmaralvarado/unveiling-the-magic-of-hash-tables-your-ultimate-guide-to-efficient-data-lookup-pt-1-800ed3cb8f3f), a crucial data structure for software engineers. Today we’ll continue our review by adding usability features to our custom Hash Table class.

Join me as we dive deeper into the magic of hash tables in this second installment.

### Starting from where we left

Let’s make a quick recap of what we covered in our previous session: We began by constructing a custom `hash table` class that utilizes two generic types - one specifically for the key and another designated for the value. Subsequently, we established a table object designed to function as a container for our various buckets. Following this, we carefully defined a hash function implementing the well-known `DJB2 algorithm` to efficiently process our keys. This foundation provides us with the essential infrastructure to insert new buckets into our table structure and assign them a properly `hashed key`, ensuring optimal performance and data organization. These fundamental components form the backbone of our hash table implementation, allowing us to build more sophisticated features on top of this solid base. This leaves our class in the following state:

```tsx
export class HashTable<K, V> {
  private table: Array<Array<[K, V]>>;

  constructor(private size: number) {
	  this.table = new Array(size).fill(null).map(() => []);
  }
  
  private hash(key: K): number {
    let hash = 5381;
    const strKey = String(key);

    for (let i = 0; i < strKey.length; i++) {
        const char = strKey.charCodeAt(i);
        hash = (hash * 33) + char;
    }

    return Math.abs(hash) % this.size;
  }
}
```

### Adding New Data

Let’s define our `set` function which will insert or update a new key-value pair in our table. It will receive two generic parameters: one of type `K` for the key and another of type `V` for the value. Since it won't return anything, the return type is void.

```typescript
set(key: K, value: V): void {}
```

First, in the function body, we need to get the `index` by hashing the `key`. Once we have the `index`, we'll retrieve the corresponding `bucket` from our table. If no `bucket` exists at that `index`, our table initialization will have already created an empty array there.

```typescript
const index = this.hash(key);
const bucket = this.table[index];
```

Inside the `bucket`, we need to find the `key`. Remember the apartments analogy from the [previous post](https://medium.com/@rubenosmaralvarado/unveiling-the-magic-of-hash-tables-your-ultimate-guide-to-efficient-data-lookup-pt-1-800ed3cb8f3f)? We have the building and the floor, now we need to locate the specific apartment number.

```typescript
const existing = bucket.find(([k]) => k === key);
```

If the apartment already has an occupant (data), we need to update it; if not, we will assign the value.

```typescript
if (existing) {
    existing[1] = value;
} else {
    bucket.push([key, value])
}
```

### Retrieving Data by Key

Next, let’s create our get method. This method accepts a `key` parameter of type `K` and returns a `value` of type `V`, giving us the following method signature:

```typescript
get(key: K): V | undefined {}
```

Notice the return type declaration includes both `V` and `undefined`. This is because the requested `key` might not exist in our hash table.

Similar to our `set` method, we first need to find the `index` and the `bucket` for the given key. Then we check if the `key` exists in that `bucket`. This two-step process is crucial, we first locate the index using our hash function, then search for the specific key within that bucket.

Using our [apartment analogy](https://medium.com/@rubenosmaralvarado/unveiling-the-magic-of-hash-tables-your-ultimate-guide-to-efficient-data-lookup-pt-1-800ed3cb8f3f): we first identify the building, then the floor, and finally check if the specific apartment exists on that floor.

```typescript
const index = this.hash(key);
const bucket = this.table[index];
const entry = bucket.find(([k]) => k === key);
```

Finally, if the `key` exists in the `bucket`, we return the associated value; otherwise, we return `undefined`. We can achieve this using a [ternary operator](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Conditional_operator).

```typescript
return entry ? entry[1] : undefined;
```

### Checking for Key Existence in Our Hash Table

Now let’s implement our `has` method, which checks whether a key exists in our hash table. This method operates similarly to the `get` method, but with one key difference. Let me walk you through it.

Here’s the method signature:

```typescript
has(key: K): boolean {}
```

Similar to the `get` method, this will accept a `key` parameter of type `K`, but will return a `boolean` value that indicates whether the `key` exists in our hash table. Let's follow the same approach as our previous methods by first obtaining the `index` and the `bucket` for the `key`.

```typescript
const index = this.hash(key);
const bucket = this.table[index];
```

Here’s where things get interesting. After obtaining the `bucket`, we need to check if any entry in it contains our `key`. This is a perfect use case for the `JavaScript` [some method](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/some), which tests whether at least one element in an array passes a given condition.

```typescript
return bucket.some(([k]) => k === key);
```

### Eliminating Data by Key from our Hash Table

Finally, let’s implement our `remove` method. This method takes a `key` parameter of type `K` and returns a `boolean` indicating whether the `key` was successfully removed from the table.

```typescript
remove(key: K): boolean {}
```

Next, as you would expect, we’ll retrieve the `index` and the `bucket` using the same logic as our previous methods. Once we have the `bucket`, we need to find the position of the entry with our `key` so we can remove it from the array. To accomplish this, we'll use the [findIndex](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/findIndex) method to locate the entry and the [splice](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/splice) method to remove it.

After finding the `index` for the `key` in the `bucket` (continuing our apartments analogy), we need to check if the entry exists. The `findIndex` method returns `-1` if no match is found or the actual index position if the entry exists.

Let’s add a condition to check before removing the `key`.

```typescript
if (entryIndex !== -1)
```

If it’s not equal to `-1`, it means the `key` was found, so we can `splice` our array and return `true` because our value was successfully removed from the table; otherwise, we simply return `false`.

```typescript
if (entryIndex !== -1) {
    bucket.splice(entryIndex, 1);
    return true;
}
return false;
```

### Optimizing Our Implementation: A DRY Approach

At this point, you might notice we’re repeating ourselves in each method, and a `pragmatic programmer` never repeats themselves. Let's create a private `getBucket` method to eliminate this redundancy, since retrieving the bucket is the first step in every operation we perform.

```typescript
private getBucket(key: K): Array<[K, V]> {
    const index = this.hash(key);
    return this.table[index];
}
```

This is a private method because it’s only for internal use within our class. It receives the `key` as a parameter and returns the corresponding `bucket` from our table.

And there you have it — a complete implementation of a simple `Hash Table` in `TypeScript`.

### Complete Hash Table Implementation with TypeScript

```tsx
export class HashTable<K, V> {
    private table: Array<Array<[K, V]>>;

    constructor(private size: number) {
        this.table = new Array(size).fill(null).map(() => []);
    }

    private hash(key: K): number {
        let hash = 5381;
        const strKey = String(key);

        for (let i = 0; i < strKey.length; i++) {
            const char = strKey.charCodeAt(i);
            hash = (hash * 33) + char;
        }

        return Math.abs(hash) % this.size;
    }

    private getBucket(key: K): Array<[K, V]> {
        const index = this.hash(key);
        return this.table[index];
    }

    set(key: K, value: V): void {
        const bucket = this.getBucket(key);

        const existing = bucket.find(([k]) => k === key);
        if (existing) {
            existing[1] = value;
        } else {
            bucket.push([key, value])
        }
    }

    get(key: K): V | undefined {
        const bucket = this.getBucket(key);

        const entry = bucket.find(([k]) => k === key);
        return entry ? entry[1] : undefined;
    }

    has(key: K): boolean {
        const bucket = this.getBucket(key);

        return bucket.some(([k]) => k === key);
    }

    remove(key: K): boolean {
        const bucket = this.getBucket(key);

        const entryIndex = bucket.findIndex(([k]) => k === key);
        if (entryIndex !== -1) {
            bucket.splice(entryIndex, 1);
            return true;
        }
        return false;
    }
}
```

### Final Thoughts

As you can see, `Data Structures` and `Algorithms` aren't rocket science once you grasp the core concepts. Creating your own implementations helps you understand why and how they work in practical applications.

Keep practicing — the only way to master something is through consistent practice and patience. As usual, you can review this and other `Data Structures` in my `Github` repository: [https://github.com/RubenOAlvarado/data-structures](https://github.com/RubenOAlvarado/data-structures).

See you next week!