Specify the correct statement about hashing algorithm (Select the best answer).

Đáp án đúng: "The expected complexity of hashing algorithm is O(1). However by the collision resolution, sometimes it may take O(n).". Hàm băm tốt rải khoá đều nên trung bình mỗi ô chỉ giữ rất ít phần tử và chi phí chèn hay tìm là hằng số; nhưng khi nhiều khoá cùng rơi một ô, mọi cách giải va chạm đều phải lần theo cụm hoặc theo chuỗi, và trong trường hợp cực đoan mọi khoá đụng nhau thì phép tìm quét qua cả n phần tử. Phương án "No matter how many data items there are, insertion and searching (and sometimes deletion) always take constant time: O(1)." bỏ qua va chạm, nên chữ always không đứng vững. Phương án "If the chaining method is used for collision resolution, insertion and searching (and sometimes deletion) can take constant time: O(1)." chỉ đúng cho phép chèn vào đầu chuỗi; phép tìm vẫn phải đi hết chuỗi, dài tới n nếu mọi khoá cùng ô. Phương án "If the coalesced method is used for collision resolution, insertion and searching (and sometimes deletion) always take constant time: O(1)." cũng vậy, cách gộp chuỗi ngay trong bảng vẫn bắt phải dò theo con trỏ qua nhiều ô.