Tìm Hiểu Cấu Trúc Dữ Liệu Hash Table và Ứng Dụng Thực Tế

Hash table (bảng băm) là một cấu trúc dữ liệu quan trọng, được sử dụng rộng rãi trong nhiều ngôn ngữ lập trình và ứng dụng thực tế. Bài viết này sẽ đi sâu vào khái niệm, cơ chế hoạt động, và cách giải quyết xung đột trong hash table, giúp bạn hiểu rõ hơn về nền tảng thuật toán này.

Giới thiệu về Hash Table

Trong lĩnh vực khoa học máy tính, hash table (hay còn gọi là hash map) là một cấu trúc dữ liệu dùng để lưu trữ các cặp key-value. Nó sử dụng một hàm băm (hash function) để tính toán vị trí (index) lưu trữ dữ liệu dựa trên key. Mục tiêu chính của hash table là đạt được độ phức tạp thời gian O(1) cho các thao tác tìm kiếm, thêm và xóa phần tử, biến nó thành một lựa chọn hiệu quả cho nhiều ứng dụng.

Minh họa hash table với các bucket và linked list để giải quyết collisionMinh họa hash table với các bucket và linked list để giải quyết collision

Cơ chế hoạt động của Hash Table

Để hiểu rõ hơn về cách hash table hoạt động, hãy xem xét ví dụ về việc tìm kiếm sách trong thư viện. Mỗi cuốn sách có một mã số duy nhất, và các cuốn sách được sắp xếp theo một hệ thống gọi là “call number” trong thư viện. Chúng ta sử dụng call number và mã số duy nhất để xác định vị trí chính xác của cuốn sách.

Tương tự, trong hash table, mỗi key được chuyển đổi thành một giá trị băm (hash code) thông qua một hàm băm. Giá trị băm này sau đó được sử dụng để xác định vị trí lưu trữ (index) của key-value pair trong bảng.

Hàm băm (Hash Function):

Hàm băm là một hàm toán học nhận đầu vào là key và trả về một giá trị băm. Một hàm băm tốt cần phải phân phối các key đều trên bảng băm để tránh tình trạng xung đột (collision), khi nhiều key khác nhau được băm vào cùng một vị trí.

Có nhiều cách để triển khai hàm băm. Một phương pháp phổ biến là dựa trên mã ASCII của các ký tự trong key. Ví dụ, ta có thể sử dụng công thức sau:

s.charAt(0) * 31^(n-1) + s.charAt(1) * 31^(n-2) + ... + s.charAt(n-1)

Trong đó:

  • s là chuỗi cần băm.
  • n là độ dài của chuỗi.

Ví dụ, để băm chuỗi “ABC”, ta có:

“ABC” = ‘A’ 31^2 + ‘B’ 31 + ‘C’ = 65 31^2 + 66 31 + 67 = 64578

Ví dụ minh họa:

Giả sử chúng ta có một bảng các chuỗi: {“abcdef”, “bcdefa”, “cdefab”, “defabc”}. Mã ASCII của a, b, c, d, e, f lần lượt là 97, 98, 99, 100, 101, 102. Chúng ta nhận thấy rằng các chuỗi này có cùng độ dài và chỉ khác nhau về thứ tự các ký tự.

Để tạo index cho mỗi chuỗi, chúng ta có thể tính tổng của (mã ASCII của ký tự * vị trí của ký tự trong chuỗi). Sau đó, chúng ta chia tổng này cho một số (ví dụ: 2069) để tạo ra index:

Chuỗi Hàm băm Index
abcdef (971 + 982 + 993 + 1004 + 1015 + 1026)%2069 38
bcdefa (981 + 992 + 1003 + 1014 + 1025 + 976)%2069 23
cdefab (991 + 1002 + 1013 + 1024 + 975 + 986)%2069 14
defabc (1001 + 1012 + 1023 + 974 + 985 + 996)%2069 11

Ví dụ về việc băm các chuỗi và tạo index trong hash tableVí dụ về việc băm các chuỗi và tạo index trong hash table

Giải quyết xung đột (Collision) trong Hash Table

Một vấn đề thường gặp trong hash table là xung đột, xảy ra khi hai hoặc nhiều key khác nhau được băm vào cùng một vị trí (index). Điều này có thể làm giảm hiệu suất của hash table. Để giải quyết vấn đề này, có một số phương pháp phổ biến:

  1. Separate Chaining (Liên kết riêng rẽ):

    Trong phương pháp này, mỗi vị trí trong bảng băm chứa một danh sách liên kết (linked list) các key-value pair có cùng giá trị băm. Khi xảy ra xung đột, key-value pair mới sẽ được thêm vào danh sách liên kết tại vị trí đó. Khi tìm kiếm một key, chúng ta sẽ duyệt qua danh sách liên kết tại vị trí tương ứng để tìm key cần tìm.

    Minh họa Separate Chaining để giải quyết collision bằng linked listMinh họa Separate Chaining để giải quyết collision bằng linked list

  2. Open Addressing (Định địa chỉ mở):

    Trong phương pháp này, khi xảy ra xung đột, chúng ta sẽ tìm một vị trí trống khác trong bảng băm để lưu trữ key-value pair mới. Có nhiều kỹ thuật khác nhau để tìm vị trí trống, chẳng hạn như linear probing (tìm kiếm tuyến tính), quadratic probing (tìm kiếm bậc hai), và double hashing (băm kép).

Code ví dụ về Hash Table

Dưới đây là một ví dụ code đơn giản về cách triển khai hash table bằng JavaScript, sử dụng separate chaining để giải quyết xung đột:

import LinkedList from '../linked-list/LinkedList';

const defaultHashTableSize = 32;

export default class HashTable {
  constructor(hashTableSize = defaultHashTableSize) {
    this.table = Array(hashTableSize).fill(null).map(() => new LinkedList());
    this.keys = {};
  }

  hash(key) {
    const hash = Array.from(key).reduce(
      (hashAccumulator, keySymbol) => (hashAccumulator + keySymbol.charCodeAt(0)),
      0,
    );

    return hash % this.table.length;
  }

  set(key, value) {
    const keyHash = this.hash(key);
    this.keys[key] = keyHash;
    const bucketLinkedList = this.table[keyHash];
    const node = bucketLinkedList.find({ callback: nodeValue => nodeValue.key === key });

    if (!node) {
      bucketLinkedList.append({ key, value });
    } else {
      node.value.value = value;
    }
  }

  delete(key) {
    const keyHash = this.hash(key);
    delete this.keys[key];
    const bucketLinkedList = this.table[keyHash];
    const node = bucketLinkedList.find({ callback: nodeValue => nodeValue.key === key });

    if (node) {
      return bucketLinkedList.delete(node.value);
    }

    return null;
  }

  get(key) {
    const bucketLinkedList = this.table[this.hash(key)];
    const node = bucketLinkedList.find({ callback: nodeValue => nodeValue.key === key });

    return node ? node.value.value : undefined;
  }

  has(key) {
    return Object.hasOwnProperty.call(this.keys, key);
  }

  getKeys() {
    return Object.keys(this.keys);
  }
}

Ví dụ khác về minh họa cấu trúc Hash TableVí dụ khác về minh họa cấu trúc Hash Table

Giải thích code:

  • HashTable: Class đại diện cho cấu trúc hash table.
  • constructor: Khởi tạo bảng băm với kích thước mặc định là 32 và tạo một linked list rỗng cho mỗi bucket.
  • hash(key): Hàm băm chuyển đổi key thành một số băm.
  • set(key, value): Thêm một key-value pair vào bảng băm.
  • delete(key): Xóa một key-value pair khỏi bảng băm.
  • get(key): Lấy giá trị tương ứng với key.
  • has(key): Kiểm tra xem key có tồn tại trong bảng băm hay không.
  • getKeys(): Lấy danh sách tất cả các key trong bảng băm.

Kết luận

Hash table là một cấu trúc dữ liệu mạnh mẽ và linh hoạt, được sử dụng rộng rãi trong nhiều ứng dụng khác nhau. Việc hiểu rõ về cơ chế hoạt động và cách giải quyết xung đột trong hash table là rất quan trọng đối với bất kỳ lập trình viên nào. Hy vọng bài viết này đã cung cấp cho bạn một cái nhìn tổng quan về hash table và giúp bạn hiểu rõ hơn về cấu trúc dữ liệu này.