Implementing a Hash Table in JavaScript

This challenge asks you to build a fundamental data structure: a hash table. Hash tables are incredibly useful for efficient data storage and retrieval, forming the backbone of many algorithms and applications, from dictionaries to caches. Your task is to implement the core functionalities of a hash table, including insertion, retrieval, and deletion of key-value pairs.

Problem Description

You need to create a HashTable class in JavaScript that stores key-value pairs. The hash table should handle collisions gracefully, meaning that when two different keys hash to the same index, the data associated with both keys can still be stored and retrieved correctly.

Key Requirements:

• Constructor: The HashTable constructor should accept an optional size parameter, representing the initial number of "buckets" or slots in the hash table. If no size is provided, a default size should be used.
• hash(key) method: This method will take a string key and return an integer index within the bounds of the hash table's size. This is your hashing function.
• set(key, value) method: Inserts a key-value pair into the hash table.
  • If the key already exists, its corresponding value should be updated.
  • This method should handle collisions.
• get(key) method: Retrieves the value associated with a given key.
  • If the key is not found, it should return undefined.
• remove(key) method: Removes a key-value pair from the hash table.
  • If the key is not found, it should do nothing.
• Internal Storage: You can choose how to implement the internal storage for the hash table (e.g., an array of arrays for separate chaining, or an array for open addressing).

Expected Behavior:

• The hash table should store and retrieve data efficiently.
• Collisions should not lead to data loss or incorrect retrieval.

Edge Cases to Consider:

• Empty hash table.
• Keys that hash to the same index (collisions).
• Retrieving a non-existent key.
• Removing a non-existent key.
• Updating the value of an existing key.

Examples

Example 1:

// Assume a HashTable class is defined with size 10 and a simple hash function

const myHashTable = new HashTable(10);

myHashTable.set("name", "Alice");
myHashTable.set("age", 30);
myHashTable.set("city", "New York");

console.log(myHashTable.get("name")); // Output: "Alice"
console.log(myHashTable.get("age"));  // Output: 30
console.log(myHashTable.get("country")); // Output: undefined

Explanation: The set operations insert key-value pairs. get successfully retrieves existing values. get for "country" returns undefined as it was never set.

Example 2:

// Assume a HashTable class is defined with size 5 and a hash function that might cause collisions

const myHashTable = new HashTable(5);

// Let's assume "apple" and "banana" hash to the same index (e.g., index 2)
myHashTable.set("apple", "red");
myHashTable.set("banana", "yellow");
myHashTable.set("grape", "purple");

console.log(myHashTable.get("apple"));  // Output: "red"
console.log(myHashTable.get("banana")); // Output: "yellow"
console.log(myHashTable.get("grape"));  // Output: "purple"

Explanation: Even if "apple" and "banana" hash to the same index, the collision resolution strategy ensures both can be stored and retrieved correctly.

Example 3:

const myHashTable = new HashTable(7);

myHashTable.set("key1", "value1");
myHashTable.set("key2", "value2");
console.log(myHashTable.get("key1")); // Output: "value1"

myHashTable.remove("key1");
console.log(myHashTable.get("key1")); // Output: undefined

myHashTable.remove("nonexistent"); // No error, does nothing

Explanation: Demonstrates successful insertion, retrieval, and removal of an item. Attempting to remove a non-existent item has no adverse effect.

Constraints

• The key parameter for set, get, and remove will always be a string.
• The value parameter for set can be any JavaScript data type.
• The size parameter for the constructor will be a positive integer.
• The hashing function should distribute keys reasonably well to minimize collisions, although perfect distribution is not expected. Aim for an average time complexity of O(1) for set, get, and remove operations in the best and average cases. Worst-case complexity (due to many collisions) can be O(n), where n is the number of elements in the hash table.

Notes

• The choice of hashing function is up to you, but a simple one involving character codes and modulo arithmetic is a good starting point.
• Consider using Separate Chaining (e.g., an array of linked lists or arrays) or Open Addressing (e.g., linear probing) to handle collisions. Separate chaining is generally simpler to implement for this challenge.
• Think about how you will store the key along with the value, especially if you are using separate chaining, so you can correctly identify which value to return or remove when a collision occurs.