Giới thiệu

Hash table được sử dụng để lưu cặp key-value, giống như array nhưng key không được sắp xếp. Cho phép truy xuất giá trị nhanh O(1)

Hash table sẽ dùng 1 hàm băm để chuyển đổi key thành một chỉ số trong mảng

Cấu trúc của hash table:

• Hash function: chuyển key thành một số nguyên index .
• Array (bucket array): Lưu trữ giá trị tại bị trí được hash.
• Collision handling: Xử lý trường hợp nhiều key trả về một index :
  • Chaining: nếu hash bị trùng index thì ghi đè lên vị trí index đó, tại vị trí index đó lưu nhiều cặp [key, value]
  • Linear probing: nếu index bị trùng sẽ ghi ở vị trí trống kế tiếp.

Khởi tạo

class HashTable {
  buckets;
  size: number;

  constructor(size = 4) {
    this.buckets = new Array(size);
    this.size = size;
  }
  
   _hash(key) {
    let total = 0;
    const PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      const char = key[i];
      const value = char.charCodeAt(0) - 96;
      total = (total * PRIME + value) % this.size;
    }
    return total;
  }
}

Khởi tạo các method

set

  set(key, value) {
    const index = this._hash(key);
    if (!this.buckets[index]) {
      this.buckets[index] = [];
    }

    this.buckets[index].push([key, value]);
  }

get

get(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    if (bucket) {
      for (let pair of bucket) {
        if (pair[0] === key) {
          return pair[1];
        }
      }
    }
    return undefined;
  }

keys

  keys() {
    const keys = [];
    for (let bucket of this.buckets) {
      if (bucket) {
        for (let pair of bucket) {
          keys.push(pair[0]);
        }
      }
    }
    return keys;
  }

values

 values() {
    const values = [];
    for (let bucket of this.buckets) {
      if (bucket) {
        for (let pair of bucket) {
          values.push(pair[1]);
        }
      }
    }
    return values;
  }

Độ phức tạp