Understanding Hash Tables and Hash Maps in TypeScript

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:

// For integer keys, the hashing function returns the integer modulo the size of the hash table.
function hashFunction(key: number, tableSize: number): number {
  return key % tableSize;
}

// Hashing functions for float keys can convert them to integers.
function hashFloatKey(key: number, tableSize: number): number {
  return Math.floor(key * 1000) % tableSize; // example
}

// Strings can be hashed by converting each character to its character code.
function hashStringKey(key: string, tableSize: number): number {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % tableSize;
}