Hash tables

A hash table is a data structure that uses a hash function to map keys to values. Hash tables provide fast insertion, deletion, and lookup of key-value pairs, with an average time complexity of O(1) for each operation. In JavaScript, objects can be used as hash tables, where the keys are strings and the values can be any type.

Here is an example of creating a hash table in JavaScript using an object:

const hashTable = {};
function hashFunction(key) {
 let hash = 0;
 for (let i = 0; i < key.length; i++) {
   const char = key.charCodeAt(i);
   hash = ((hash << 5) - hash) + char;
   hash |= 0;
 }
 return hash;
}
function insert(key, value) {
 const hashedKey = hashFunction(key);
 hashTable[hashedKey] = value;
}
function get(key) {
 const hashedKey = hashFunction(key);
 return hashTable[hashedKey];
}
function remove(key) {
 const hashedKey = hashFunction(key);
 delete hashTable[hashedKey];
}

In this example, the hashTable object is used to store the key-value pairs. The hashFunction() function is used to convert a string key into a numerical index that can be used to access the corresponding value in the hash table. The insert(), get(), and remove() functions are used to insert, retrieve, and remove key-value pairs from the hash table.

Here are some examples of how to use the hash table:

insert('John', 42);
insert('Jane', 'hello');
insert('Bob', { foo: 'bar' });
console.log(get('John')); // Output: 42
console.log(get('Jane')); // Output: 'hello'
console.log(get('Bob')); // Output: { foo: 'bar' }
remove('Jane');
console.log(get('Jane')); // Output: undefined

In this example, we insert several key-value pairs into the hash table using the insert() function. We then use the get() function to retrieve the values associated with the keys, and the remove() function to remove a key-value pair from the hash table.

Hash tables are used in many applications, such as caching, symbol tables, and database indexing. The efficiency of hash tables makes them a popular choice for many software systems.