Dynamic hashing là gì?

Vấn đề với băm tĩnh (static hashing) là nó không mở rộng hoặc thu nhỏ động khi kích thước của cơ sở dữ liệu (database) lớn lên hoặc thu nhỏ lại. Băm động (dynamic hashing) cung cấp một cơ chế trong đó các bucket được thêm vào và xóa một cách động và theo yêu cầu. Băm động (dynamic hashing) còn được gọi là băm mở rộng (extended hashing).

Hàm băm (hash function) trong băm động được tạo ra để tạo ra một số lượng lớn các giá trị và chỉ một số ít được sử dụng ban đầu.

Tiền tố (prefix) của toàn bộ giá trị băm (hash value) được lấy làm chỉ mục băm (hash index). Chỉ một phần của giá trị băm được sử dụng cho các địa chỉ của bucket. Mỗi chỉ mục băm đều có giá trị độ sâu (depth value) để biểu thị có bao nhiêu bit được sử dụng để tính toán một hàm băm. Các bit này có thể giải quyết 2n bucket. Khi tất cả các bit này được sử dụng nghĩa là khi tất cả các bucket đã đầy thì giá trị độ sâu được tăng tuyến tính và hai lần bucket được phân bổ (allocate).

Các thao tác (operation):

• Truy vấn: Xem giá trị độ sâu của chỉ mục băm và sử dụng các bit đó để tính địa chỉ của bucket.
• Cập nhật: Thực hiện truy vấn như trên và cập nhật dữ liệu.
• Xóa: Thực hiện truy vấn để xác định vị trí dữ liệu mong muốn và xóa dữ liệu tương tự.

• Chèn: Tính địa chỉ của bucket

  • IF bucket đã đầy.
    • Thêm nhiều bucket thêm
    • Thêm các bit bổ sung vào giá trị băm.
    • Tính toán lại hàm băm.
  • ELSE
    • Thêm dữ liệu vào bucket
  • IF tất cả các bucket đã đầy, hãy thực hiện các biện pháp khắc phục sự cố của băm tĩnh (static hashing).