Hash table and hash map same ?
Tags: javascript, algorithms, datastructures, sort
Published: 2024-03-25 05:04:54

A [hash table](https://github.com/ajithr116/Data-Structures/blob/main/10-Hash/hashTable.js), also known as a hash map, is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

### Key Components:

1. **Hash Function**: This function takes a key as input and computes a hash code, which is typically an integer. The hash code is used to determine the index or position in the underlying array where the value associated with the key will be stored.

2. **Array of Buckets**: A hash table typically consists of an array of buckets or slots, where each bucket can hold one or more key-value pairs. The size of the array is usually chosen based on the expected number of elements to be stored in the hash table.

3. **Collision Handling**: Since multiple keys may hash to the same index (known as a collision), hash tables need a mechanism to handle collisions. Common collision resolution techniques include chaining (each bucket stores a linked list of key-value pairs) and open addressing (probing to find an empty bucket).

### Operations:

1. **Insertion**: To insert a key-value pair into the hash table, the hash function is applied to the key to determine the index, and the pair is then stored in the corresponding bucket.

2. **Lookup/Search**: To retrieve the value associated with a given key, the hash function is applied to the key to determine the index, and the value is then retrieved from the corresponding bucket.

3. **Deletion**: To remove a key-value pair from the hash table, the hash function is applied to the key to determine the index, and the pair is then removed from the corresponding bucket.

### JavaScript Implementation (Using Chaining):

```javascript
class HashTable{
  constructor(size=10){
    this.table = new Array(size).fill(null).map(()=>[]);
    this.size = size;
    this.count = 0;
  }
  _hash(key){
    let hash = 0;
    for(let i=0;i<key.length;i++){
      hash +=key.charCodeAt(i);
    }
    return hash%this.size;
  }
  set(key,value){
    if(this.count/this.size>0.7){
      this.resize(this.size*2);
    }
    const index = this._hash(key);
    const exist = this.table[index].find((pair)=>pair[0]===key);
    if(exist){
      exist[1]=value;
    }else{
      this.table[index].push([key,value]);
      this.count++;
    }
  }
  get(key){
    const index = this._hash(key);
    const pair = this.table[index].find((pair)=>pair[0]===key);
    return pair ? pair[1] : "not found";
  }
  remove(key){
    const index = this._hash(key);
    const pairIndex = this.table[index].findIndex(pair=>pair[0]===key);
    if(pairIndex!==-1){
      this.table[index].splice(pairIndex,1);
      this.count--;
      if(this.count-this.size>0.3){
        this.resize(Math.floor(this.size/2));
      }
    }
  }
  print(){
    for(let i=0;i<this.size;i++){
      console.log(this.table[i]);
    }
  }
  resize(newSize){
    const oldTable = this.table;
    this.size = newSize;
    this.count=0;
    this.table = new Array(newSize).fill(null).map(()=>[]);
    for(const bucket of oldTable){
      for(const [key,value] of bucket){
        this.set(key,value);
      }
    }
  }
}


const ht = new HashTable();
ht.set("a","aaa");
ht.set("b","bbb");
ht.set("c","ccc");
ht.set("d","ddd");
ht.set("e","eee");
ht.set("f","fff");
ht.set("g","aaa");
ht.set("h","aaa");
ht.set("i","aaa");
ht.set("ijk","aaa");
ht.get("e");
ht.remove('c')
ht.print();
```

### Advantages of [Hash Tables](https://github.com/ajithr116/Data-Structures/blob/main/10-Hash/hashTable.js):

1. **Fast Lookup**: Hash tables provide fast average-case time complexity for insertion, lookup, and deletion operations, typically O(1), making them efficient for storing and retrieving data.

2. **Versatility**: Hash tables can be used to implement various data structures and algorithms, including dictionaries, sets, caches, and more.

3. **Dynamic Sizing**: Many hash table implementations support dynamic resizing, allowing the hash table to grow or shrink as needed to accommodate changes in the number of elements stored.

### Disadvantages of [Hash Tables](https://github.com/ajithr116/Data-Structures/blob/main/10-Hash/hashTable.js):

1. **Hash Collisions**: Hash collisions can occur when multiple keys hash to the same index, potentially degrading performance. Collision resolution techniques like chaining or probing are needed to handle collisions effectively.

2. **Space Overhead**: Hash tables may consume more memory than other data structures due to the need for additional space to store hash codes and manage collisions.

3. **Deterministic Hashing**: The effectiveness of a hash table depends heavily on the quality of the hash function used. A poor hash function may result in more collisions and reduced performance.

### Conclusion:

https://github.com/ajithr116/Data-Structures/blob/main/10-Hash/hashTable.js are versatile and efficient data structures used in a wide range of applications. By using an appropriate hash function and collision resolution strategy, hash tables can provide fast and effective storage and retrieval of key-value pairs, making them a valuable tool in computer science and software engineering.

---