Implementing a Hash Table in JavaScript

Hash tables are fundamental data structures used for efficient key-value storage and retrieval. This challenge asks you to implement a basic hash table in JavaScript, focusing on core functionalities like insertion, retrieval, deletion, and handling collisions. Building a hash table will solidify your understanding of data structures and algorithms, and is a crucial skill for many programming tasks.

Problem Description

You are tasked with creating a HashTable class in JavaScript. This class should provide the following functionalities:

• constructor(): Initializes an empty hash table. It should include a table property (an array) and a size property (initially 0).
• hash(key): A function that takes a key as input and returns a numerical hash code. For simplicity, you can use a basic hashing function like summing the character codes of the key string. Ensure the hash code is within the bounds of the table array.
• set(key, value): Inserts a key-value pair into the hash table. If the key already exists, update its value. Handle collisions using separate chaining (each index in the table array will hold a linked list of key-value pairs).
• get(key): Retrieves the value associated with a given key. Return undefined if the key is not found.
• delete(key): Removes the key-value pair associated with a given key.
• size(): Returns the number of key-value pairs currently stored in the hash table.

Key Requirements:

• Implement separate chaining for collision resolution. You can use JavaScript arrays to represent the linked lists at each index.
• The hash function should distribute keys reasonably well to minimize collisions.
• The set, get, and delete methods should have an average time complexity of O(1).
• Handle edge cases such as empty keys and values.

Expected Behavior:

The hash table should behave as expected for insertion, retrieval, and deletion of key-value pairs. Collisions should be handled gracefully, and the size property should accurately reflect the number of elements in the table.

Examples

Example 1:

Input:
const hashTable = new HashTable();
hashTable.set('name', 'Alice');
hashTable.set('age', 30);
hashTable.set('city', 'New York');

Output:
hashTable.get('name'); // 'Alice'
hashTable.get('age');  // 30
hashTable.get('city'); // 'New York'
hashTable.get('country'); // undefined

Explanation: The hash table successfully stores and retrieves the key-value pairs. Retrieving a non-existent key returns undefined.

Example 2:

Input:
const hashTable = new HashTable();
hashTable.set('a', 1);
hashTable.set('b', 2);
hashTable.set('c', 3);
hashTable.set('a', 4); // Update existing key

Output:
hashTable.get('a'); // 4
hashTable.get('b'); // 2
hashTable.get('c'); // 3
hashTable.size(); // 3

Explanation: Updating an existing key correctly overwrites the previous value. The size remains unchanged as we only updated a value, not added a new key.

Example 3: (Collision Scenario)

Input:
const hashTable = new HashTable();
hashTable.set('key1', 'value1');
hashTable.set('key2', 'value2'); // Assume 'key1' and 'key2' hash to the same index
hashTable.get('key1'); // 'value1'
hashTable.get('key2'); // 'value2'
hashTable.delete('key1');
hashTable.get('key1'); // undefined
hashTable.get('key2'); // 'value2'

Explanation: Demonstrates collision handling. Both keys hash to the same index, but retrieval and deletion work correctly due to separate chaining.

Constraints

• Keys can be strings.
• Values can be any JavaScript data type.
• The maximum number of key-value pairs the hash table can store is 1000. (This is to prevent excessive memory usage during testing).
• The hash function should produce a non-negative integer.
• The average time complexity for set, get, and delete operations should be O(1). Worst-case complexity (due to collisions) can be O(n), where n is the number of elements in a chain.

Notes

• Consider the trade-offs between different hashing functions. A good hashing function minimizes collisions.
• Think about how to handle resizing the hash table if it becomes too full. (This is not required for this challenge, but it's a good consideration for a production-ready hash table).
• Focus on the core functionalities of a hash table. Error handling and edge cases are important, but prioritize implementing the basic operations correctly.
• Remember that separate chaining involves using linked lists (represented by JavaScript arrays in this case) to store multiple key-value pairs that hash to the same index.