Lesson 13-Data Structures – Hash Tables

A hash table is an efficient data storage and retrieval structure that uses a hash function to map keys to positions in the table for accessing records, enabling fast data access. Hash tables have wide applications in computer science, such as database indexing, cache implementation, dictionaries, etc.

Basic Concepts of Hash Tables

  1. Key-Value Pair: The basic unit stored in a hash table, where each key corresponds to a value
  2. Hash Function: A function that maps keys to array indices
  3. Collision: The situation where different keys are mapped to the same index by the hash function
  4. Load Factor: The proportion of filled positions in the hash table, which affects performance

Hash Table Implementations

Array-Based Hash Table Implementation

class HashTable {
  constructor(size = 32) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []);
  }

  // Hash function
  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.size;
    }
    return hash;
  }

  // Set key-value pair
  set(key, value) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    
    // Check if the same key already exists
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][1] = value; // Update value
        return;
      }
    }
    
    // Add new key-value pair
    bucket.push([key, value]);
  }

  // Get value
  get(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        return bucket[i][1];
      }
    }
    
    return undefined; // Key does not exist
  }

  // Delete key-value pair
  remove(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket.splice(i, 1);
        return true;
      }
    }
    
    return false; // Key does not exist
  }

  // Check if key exists
  has(key) {
    return this.get(key) !== undefined;
  }

  // Get all keys
  keys() {
    const keys = [];
    for (const bucket of this.buckets) {
      for (const [key, value] of bucket) {
        keys.push(key);
      }
    }
    return keys;
  }

  // Get all values
  values() {
    const values = [];
    for (const bucket of this.buckets) {
      for (const [key, value] of bucket) {
        values.push(value);
      }
    }
    return values;
  }

  // Get the number of key-value pairs
  size() {
    let count = 0;
    for (const bucket of this.buckets) {
      count += bucket.length;
    }
    return count;
  }
}

// Usage example
const hashTable = new HashTable();
hashTable.set('name', 'Alice');
hashTable.set('age', 25);
hashTable.set('job', 'Developer');

console.log(hashTable.get('name')); // Alice
console.log(hashTable.has('age')); // true
console.log(hashTable.keys()); // ['name', 'age', 'job'] (order may vary)
console.log(hashTable.size()); // 3
hashTable.remove('age');
console.log(hashTable.size()); // 2

Linked List-Based Hash Table Implementation (Separate Chaining)

class HashNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.next = null;
  }
}

class LinkedHashTable {
  constructor(size = 32) {
    this.size = size;
    this.buckets = new Array(size).fill(null);
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.size;
    }
    return hash;
  }

  set(key, value) {
    const index = this.hash(key);
    let head = this.buckets[index];
    
    if (!head) {
      this.buckets[index] = new HashNode(key, value);
      return;
    }
    
    let current = head;
    while (current) {
      if (current.key === key) {
        current.value = value;
        return;
      }
      if (!current.next) {
        current.next = new HashNode(key, value);
        return;
      }
      current = current.next;
    }
  }

  get(key) {
    const index = this.hash(key);
    let current = this.buckets[index];
    
    while (current) {
      if (current.key === key) {
        return current.value;
      }
      current = current.next;
    }
    
    return undefined;
  }

  remove(key) {
    const index = this.hash(key);
    let current = this.buckets[index];
    let previous = null;
    
    while (current) {
      if (current.key === key) {
        if (previous) {
          previous.next = current.next;
        } else {
          this.buckets[index] = current.next;
        }
        return true;
      }
      previous = current;
      current = current.next;
    }
    
    return false;
  }

  has(key) {
    return this.get(key) !== undefined;
  }
}

// Usage example
const linkedHash = new LinkedHashTable();
linkedHash.set('key1', 'value1');
linkedHash.set('key2', 'value2');
console.log(linkedHash.get('key1')); // value1
linkedHash.remove('key1');
console.log(linkedHash.has('key1')); // false

Open Addressing Hash Table Implementation (Linear Probing)

class OpenHashTable {
  constructor(size = 32) {
    this.size = size;
    this.buckets = new Array(size).fill(null);
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.size;
    }
    return hash;
  }

  set(key, value) {
    let index = this.hash(key);
    while (this.buckets[index] !== null && this.buckets[index].key !== key) {
      index = (index + 1) % this.size; // Linear probing
    }
    
    if (this.buckets[index] === null) {
      this.buckets[index] = { key, value };
    } else {
      this.buckets[index].value = value;
    }
  }

  get(key) {
    let index = this.hash(key);
    let startIndex = index;
    
    while (this.buckets[index] !== null) {
      if (this.buckets[index].key === key) {
        return this.buckets[index].value;
      }
      index = (index + 1) % this.size;
      if (index === startIndex) break; // Avoid infinite loop
    }
    
    return undefined;
  }

  remove(key) {
    let index = this.hash(key);
    let startIndex = index;
    
    while (this.buckets[index] !== null) {
      if (this.buckets[index].key === key) {
        this.buckets[index] = null;
        return true;
      }
      index = (index + 1) % this.size;
      if (index === startIndex) break;
    }
    
    return false;
  }

  has(key) {
    return this.get(key) !== undefined;
  }
}

// Usage example
const openHash = new OpenHashTable();
openHash.set('a', 1);
openHash.set('b', 2);
console.log(openHash.get('a')); // 1
openHash.remove('a');
console.log(openHash.has('a')); // false

Collision Resolution Strategies

Separate Chaining

  • Use linked lists or arrays at each bucket to store multiple key-value pairs
  • Advantages: Simple, easy to handle large numbers of collisions
  • Disadvantages: Additional memory for links, potential cache misses

Open Addressing

  • Linear Probing: Search sequentially for the next available slot
  • Quadratic Probing: Use quadratic function to probe
  • Double Hashing: Use a second hash function for probing
  • Advantages: Better cache performance, no extra memory for links
  • Disadvantages: Clustering issues, more complex deletion

Hash Function Design

A good hash function should:

  1. Be fast to compute
  2. Produce uniform distribution
  3. Minimize collisions
  4. Be deterministic

Common hash functions in JavaScript:

  1. Simple string hash:
function simpleHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % size;
}
  1. djb2 hash function:
function djb2(key) {
  let hash = 5381;
  for (let i = 0; i < key.length; i++) {
    hash = ((hash << 5) + hash) + key.charCodeAt(i);
  }
  return hash >>> 0; // Convert to unsigned 32-bit integer
}
  1. MurmurHash (advanced, requires implementation)

Dynamic Resizing

When load factor exceeds a threshold (e.g., 0.75), resize the hash table:

class ResizableHashTable extends HashTable {
  constructor(size = 32, loadFactor = 0.75) {
    super(size);
    this.loadFactor = loadFactor;
  }

  set(key, value) {
    super.set(key, value);
    if (this.size() / this.size > this.loadFactor) {
      this.resize();
    }
  }

  resize() {
    const oldBuckets = this.buckets;
    this.size *= 2;
    this.buckets = new Array(this.size).fill(null).map(() => []);
    
    for (const bucket of oldBuckets) {
      for (const [key, value] of bucket) {
        this.set(key, value);
      }
    }
  }
}

Hash Table Applications

Caching (LRU Cache)

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new HashTable(); // For O(1) access
    this.order = []; // To track access order
  }

  get(key) {
    if (!this.cache.has(key)) return -1;
    
    // Update access order
    this.order.splice(this.order.indexOf(key), 1);
    this.order.push(key);
    
    return this.cache.get(key);
  }

  put(key, value) {
    if (this.cache.has(key)) {
      // Update value and order
      this.cache.set(key, value);
      this.order.splice(this.order.indexOf(key), 1);
      this.order.push(key);
    } else {
      if (this.order.length >= this.capacity) {
        // Remove least recently used
        const lruKey = this.order.shift();
        this.cache.remove(lruKey);
      }
      
      this.cache.set(key, value);
      this.order.push(key);
    }
  }
}

// Usage example
const cache = new LRUCache(2);
cache.put('a', 1);
cache.put('b', 2);
console.log(cache.get('a')); // 1
cache.put('c', 3); // Removes 'b'
console.log(cache.get('b')); // -1

Frequency Statistics

function countWordFrequency(text) {
  const words = text.split(/\s+/);
  const frequency = new Dictionary();
  
  for (const word of words) {
    if (frequency.has(word)) {
      frequency.set(word, frequency.get(word) + 1);
    } else {
      frequency.set(word, 1);
    }
  }
  
  return frequency;
}

// Usage example
const text = "hello world hello javascript";
const freq = countWordFrequency(text);
console.log(freq.keys()); // ["hello", "world", "javascript"]
console.log(freq.get("hello")); // 2

Fast Lookup of Object Properties

function createFastLookup(obj) {
  const lookup = new Dictionary();
  
  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      lookup.set(key, obj[key]);
    }
  }
  
  return {
    get: (key) => lookup.get(key),
    has: (key) => lookup.has(key)
  };
}

// Usage example
const person = { name: 'Alice', age: 25, job: 'Developer' };
const fastLookup = createFastLookup(person);
console.log(fastLookup.get('name')); // Alice
console.log(fastLookup.has('age')); // true

Comparison of Hash Tables with Other Data Structures

FeatureHash TableArrayLinked ListBinary Search Tree
InsertionO(1) averageO(n)O(1)O(log n) average
LookupO(1) averageO(log n) after sortingO(n)O(log n) average
DeletionO(1) averageO(n)O(1)O(log n) average
Sequential AccessNot supportedO(1)O(n)In-order traversal O(n)
Key-Value StorageSupportedNot supportedPossible but inefficientPossible but inefficient

Optimization Techniques for Hash Tables

  1. Good Hash Function:
    • Uniform distribution
    • Fast computation
    • Reduce collisions
  2. Dynamic Resizing:
    • Resize when load factor exceeds threshold
    • Usually double the size
  3. Collision Resolution Strategy Selection:
    • Separate chaining suitable for most cases
    • Open addressing suitable for memory-constrained scenarios
  4. Cache Friendliness:
    • Consider data locality
    • Reduce pointer jumps
  5. Concurrency Control:
    • For multi-threaded environments, consider locking or using concurrent hash tables

Practical Application Scenarios

  1. Database Indexing: Fast record lookup
  2. Caching Systems: Such as Redis, Memcached
  3. Compiler Symbol Tables: Store variable and function information
  4. Routing Tables: Store IP to MAC address mappings in network devices
  5. Object Property Storage: Internal implementation in JavaScript engines
  6. Counters: Count element frequencies
  7. Sets Implementation: Fast lookup and deduplication

Summary

Hash tables are an extremely efficient data structure, particularly suitable for scenarios requiring fast lookup, insertion, and deletion. Understanding the working principles of hash tables, collision resolution strategies, and performance optimization techniques is crucial for developing high-performance applications. In practical development, although we usually use language-built-in Maps or objects to implement similar functionality, a deep understanding of the underlying implementation of hash tables helps us better use these tools and implement customized hash table structures when necessary.

Share your love