Welcome to this lesson that introduces Hash Tables and Hash Maps, fundamental concepts in data structures and algorithms. Hash tables, often implemented as Hash Maps, provide an efficient way to maintain a collection of key-value pairs and allow quick access, insertion, and removal operations. In TypeScript, they are particularly effective because of strong static typing, which helps catch errors at compile time, thus promoting robust and predictable code. This lesson will explore the power of hash maps in reducing time complexity while solving certain types of algorithmic problems.

A crucial component of a hash map is the hashing function, which generates a hash value (usually an integer) from a given key. This hash value determines where to store the associated value in the hash table. While integer keys are straightforward, the hashing function returns the integer modulo the size of the hash table; keys can also be immutables like floats or strings.

• Floats: Convert a float to an integer by multiplying it with a large constant and truncating to avoid hashing to the same value as integer counterparts.
• Strings: Convert each character to its character code, combining these codes in various ways to distribute hash values uniformly.

Hash maps have a limited space defined by the size of the hash table. Ideally, the hashing function should be a one-to-one function (injective), but due to limited space and the infinite nature of potential input values, collisions occur. Hash maps handle collisions through methods like chaining or open addressing.

Below are TypeScript code snippets showcasing simple hashing function implementations for integers, floats, and strings:

TypeScript
Copy to clipboard
1// For integer keys, the hashing function returns the integer modulo the size of the hash table.
2function hashFunction(key: number, tableSize: number): number {
3  return key % tableSize;
4}
5
6// Hashing functions for float keys can convert them to integers.
7function hashFloatKey(key: number, tableSize: number): number {
8  return Math.floor(key * 1000) % tableSize; // example
9}
10
11// Strings can be hashed by converting each character to its character code.
12function hashStringKey(key: string, tableSize: number): number {
13  let hash = 0;
14  for (let i = 0; i < key.length; i++) {
15    hash += key.charCodeAt(i);
16  }
17  return hash % tableSize;
18}

In a Hash Map, data is stored based on a generated hash value from a unique key. This enables quick data access using the key. For instance, consider a list of integers and a target number. Finding two numbers that sum to the target using brute force requires comparing each number with all others — an approach with quadratic time complexity. Using a hash map, each number is stored with its index upon arrival, and the complement (target minus the current number) is checked in the hash map, reducing computational overhead and speeding up the solution.

Here is a TypeScript solution:

TypeScript
Copy to clipboard
1function twoSum(nums: number[], target: number): number[] {
2    const hashMap: { [key: number]: number } = {};
3    for (let i = 0; i < nums.length; i++) {
4        const num = nums[i];
5        if (hashMap[target - num] !== undefined) {
6            return [hashMap[target - num], i];
7        }
8        hashMap[num] = i;
9    }
10    return [];
11}
12
13// Test
14console.log(twoSum([2, 7, 11, 15], 9));  // Output: [0, 1]

With a foundational understanding of Hash Tables/Maps, the upcoming exercises will delve deeper into this topic. We'll practice implementing Hash Maps/Tables in TypeScript, leveraging the strong type system to boost reliability in code while solving complex problems more efficiently. Mastering these concepts in TypeScript will significantly enhance your problem-solving skills and add a powerful tool to your algorithmic toolkit.