Tóm tắt¶

Điểm lại trọng tâm¶

Cho một đầu vào key, bảng băm có thể truy xuất value tương ứng trong thời gian \(O(1)\), vốn là hiệu suất rất cao.
Các thao tác bảng băm phổ biến bao gồm truy vấn, thêm các cặp khóa-giá trị, xóa các cặp khóa-giá trị và duyệt bảng băm.
Hàm băm ánh xạ một key tới một chỉ số mảng, cho phép truy cập vào ngăn tương ứng và lấy ra value.
Hai khóa khác nhau có thể dẫn đến cùng một chỉ số mảng sau khi băm, dẫn đến kết quả truy vấn sai. Hiện tượng này được gọi là đụng độ mã băm.
Dung lượng của bảng băm càng lớn thì xác suất xảy ra đụng độ mã băm càng thấp. Do đó, việc mở rộng bảng băm có thể giảm thiểu đụng độ mã băm. Tương tự như mở rộng mảng, việc mở rộng bảng băm rất tốn kém.
Hệ số tải, được định nghĩa là số lượng phần tử chia cho số lượng ngăn, phản ánh mức độ nghiêm trọng của đụng độ mã băm và thường được sử dụng làm điều kiện để kích hoạt việc mở rộng bảng băm.
Chuỗi kề giải quyết đụng độ mã băm bằng cách lưu trữ tất cả các phần tử bị đụng độ trong cùng một danh sách liên kết. Tuy nhiên, các danh sách liên kết quá dài có thể làm giảm hiệu suất truy vấn, điều này có thể được cải thiện bằng cách chuyển đổi tiếp các danh sách liên kết thành cây đỏ-đen.
Địa chỉ mở xử lý đụng độ mã băm thông qua việc dò nhiều lần. Dò tuyến tính sử dụng một bước dò cố định nhưng không thể xóa phần tử trực tiếp và dễ bị kết cụm. Băm kép sử dụng nhiều hàm băm để dò, giúp giảm hiện tượng kết cụm so với dò tuyến tính nhưng làm tăng chi phí tính toán.
Các ngôn ngữ lập trình khác nhau áp dụng các triển khai bảng băm khác nhau. Ví dụ: HashMap của Java sử dụng chuỗi kề, trong khi dict của Python sử dụng địa chỉ mở.
Trong bảng băm, chúng ta mong muốn các thuật toán băm có tính xác định, hiệu suất cao và phân phối đều. Trong mật mã học, các thuật toán băm cũng cần có tính chống đụng độ và hiệu ứng lở tuyết.
Các thuật toán băm thường sử dụng số nguyên tố lớn làm số chia (modulo) để tối đa hóa tính phân phối đều của các giá trị băm và giảm thiểu đụng độ mã băm.
Các thuật toán băm phổ biến bao gồm MD5, SHA-1, SHA-2 và SHA-3. MD5 thường được sử dụng để kiểm tra tính toàn vẹn của tệp tin, trong khi SHA-2 thường được sử dụng trong các giao thức và ứng dụng bảo mật.
Các ngôn ngữ lập trình thường cung cấp các thuật toán băm tích hợp sẵn cho các kiểu dữ liệu để tính toán chỉ số ngăn trong bảng băm. Nói chung, chỉ các đối tượng bất biến mới có thể băm được.

Câu hỏi thường gặp¶

Hỏi: Khi nào độ phức tạp thời gian của bảng băm giảm xuống còn \(O(n)\)?

Khi đụng độ mã băm xảy ra nghiêm trọng, độ phức tạp thời gian của bảng băm có thể giảm xuống còn \(O(n)\). Khi hàm băm được thiết kế tốt, dung lượng được thiết lập phù hợp và các đụng độ được phân bổ đều thì độ phức tạp thời gian sẽ là \(O(1)\). Chúng ta thường coi độ phức tạp thời gian là \(O(1)\) khi sử dụng các bảng băm tích hợp sẵn trong các ngôn ngữ lập trình.

Hỏi: Tại sao không sử dụng hàm băm \(f(x) = x\)? Điều này sẽ loại bỏ đụng độ băm.

Với hàm băm \(f(x) = x\), mỗi phần tử tương ứng với một chỉ số ngăn duy nhất, tương đương với một mảng. Tuy nhiên, không gian đầu vào thường lớn hơn nhiều so với không gian đầu ra (độ dài mảng), do đó bước cuối cùng của hàm băm thường là chia lấy dư cho độ dài mảng. Nói cách khác, mục tiêu của bảng băm là ánh xạ một không gian trạng thái lớn hơn vào một không gian nhỏ hơn trong khi vẫn cung cấp hiệu suất truy vấn \(O(1)\).

Hỏi: Tại sao bảng băm có thể hiệu quả hơn mảng, danh sách liên kết hoặc cây nhị phân, mặc dù bảng băm được triển khai bằng các cấu trúc này?

Thứ nhất, bảng băm có hiệu suất thời gian cao hơn nhưng hiệu suất không gian thấp hơn. Một phần đáng kể bộ nhớ trong bảng băm vẫn không được sử dụng.

Thứ hai, bảng băm chỉ hiệu quả hơn về mặt thời gian trong các trường hợp sử dụng cụ thể. Nếu một chức năng có thể được triển khai với cùng độ phức tạp thời gian bằng mảng hoặc danh sách liên kết, nó thường chạy nhanh hơn so với bảng băm. Điều này là do việc tính toán hàm băm phát sinh chi phí, làm cho hệ số hằng số trong độ phức tạp thời gian lớn hơn.

Cuối cùng, độ phức tạp thời gian của bảng băm có thể bị giảm sút. Ví dụ, trong chuỗi kề, chúng ta thực hiện các thao tác tìm kiếm trong danh sách liên kết hoặc cây đỏ-đen, vốn vẫn có nguy cơ bị giảm hiệu suất về mức thời gian \(O(n)\).

Hỏi: Băm kép cũng có khuyết điểm là không thể xóa trực tiếp phần tử đúng không? Không gian được đánh dấu là đã xóa có thể được tái sử dụng không?

Băm kép là một dạng địa chỉ mở, và tất cả các phương pháp địa chỉ mở đều có khuyết điểm là không thể xóa trực tiếp các phần tử; chúng yêu cầu đánh dấu các phần tử đã bị xóa. Không gian được đánh dấu có thể được tái sử dụng. Khi chèn các phần tử mới vào bảng băm và hàm băm trỏ đến một vị trí được đánh dấu là đã xóa, vị trí đó có thể được sử dụng cho phần tử mới. Điều này duy trì chuỗi dò của bảng băm trong khi đảm bảo sử dụng không gian hiệu quả.

Hỏi: Tại sao đụng độ mã băm lại xảy ra trong quá trình tìm kiếm của dò tuyến tính?

Trong quá trình tìm kiếm, hàm băm trỏ đến ngăn và cặp khóa-giá trị tương ứng. Nếu key không khớp, điều đó cho thấy có đụng độ mã băm. Do đó, dò tuyến tính sẽ tìm kiếm xuống dưới theo một bước dò định sẵn cho đến khi tìm thấy cặp khóa-giá trị chính xác hoặc tìm kiếm thất bại.

Hỏi: Tại sao việc mở rộng bảng băm có thể giảm thiểu đụng độ mã băm?

Bước cuối cùng của một hàm băm thường bao gồm việc chia lấy dư cho độ dài mảng \(n\), để giữ cho đầu ra nằm trong phạm vi chỉ số mảng. Khi mở rộng, độ dài mảng \(n\) thay đổi, và các chỉ số tương ứng với các khóa cũng có thể thay đổi. Các khóa trước đây được ánh xạ tới cùng một ngăn có thể được phân bổ trên nhiều ngăn sau khi mở rộng, từ đó giảm thiểu đụng độ mã băm.

Hỏi: Nếu mục tiêu là truy cập hiệu quả, tại sao không sử dụng trực tiếp một mảng?

Khi các giá trị key là các số nguyên liên tục trong một phạm vi nhỏ, mảng quả thực là một lựa chọn đơn giản và hiệu quả. Nhưng khi key thuộc kiểu dữ liệu khác, chẳng hạn như chuỗi ký tự, chúng ta cần một hàm băm để ánh xạ key tới một chỉ số mảng và sau đó lưu trữ phần tử đó trong một mảng các ngăn. Cấu trúc đó chính xác là bảng băm.