Rehashing là gì?

Băm lại (rehashing) là một kỹ thuật trong đó bảng băm (hash table) được thay đổi kích thước, tức là kích thước của bảng băm được nhân đôi bằng cách tạo một bảng băm mới.

Về cơ bản, khi hệ số tải (load factor) tăng lên nhiều hơn giá trị được xác định trước của nó (ví dụ: 0,75), thì độ phức tạp thời gian (time complexity) cho tìm kiếm và chèn sẽ tăng lên. Vì vậy, để khắc phục điều này, kích thước của mảng (array) được tăng lên (thường là gấp đôi) và tất cả các giá trị được băm lại và lưu trữ trong mảng có kích thước gấp đôi mới để duy trì hệ số tải thấp và độ phức tạp (complexity) thấp. Điều này có nghĩa là nếu chúng ta đã có mảng có kích thước 100 trước đó và một khi chúng ta đã lưu trữ 75 phần tử (element) vào đó (vì nó có hệ số tải = 75), thì khi chúng ta cần lưu trữ phần tử thứ 76, chúng ta nhân đôi kích thước của nó lên 200.