C++ - unordered_map complexity

Question

Tôi cần tạo hàm tra cứu trong đó cặp (X, Y) tương ứng với giá trị Z cụ thể. Một trong những yêu cầu chính cho điều này là tôi cần phải làm điều đó trong càng gần với O (1) phức tạp như tôi có thể. Kế hoạch của tôi là sử dụng unordered_map.

Tôi thường không sử dụng bảng băm để tra cứu, vì thời gian tra cứu chưa bao giờ quan trọng đối với tôi. Tôi có đúng trong suy nghĩ rằng miễn là tôi xây dựng unordered_map không có va chạm, thời gian tra cứu của tôi sẽ là O (1)?

Mối quan tâm của tôi sau đó là những gì phức tạp sẽ trở thành nếu có chìa khóa không có trong bản đồ không có thứ tự. Nếu tôi sử dụng unordered_map :: find() :, ví dụ, để xác định xem một khóa có hiện diện trong bảng băm của tôi hay không, nó sẽ cho tôi biết câu trả lời như thế nào? Nó thực sự lặp qua tất cả các phím?

Tôi đánh giá rất cao sự trợ giúp.

Answer 1

Các tiêu chuẩn nhiều hơn hoặc ít đòi hỏi sử dụng xô cho va chạm độ phân giải, có nghĩa là thực tế tìm kiếm thời gian sẽ lẽ được tuyến tính liên quan đến số phần tử trong xô , bất kể nguyên tố này là hiện tại hay không phải. Có thể làm cho nó O (lg N), nhưng nó thường không được thực hiện, vì số lượng thành phần trong thùng nên là nhỏ, nếu bảng băm đang được sử dụng chính xác.

Để đảm bảo rằng số phần tử trong nhóm nhỏ, bạn phải đảm bảo rằng hàm băm có hiệu quả. Điều gì có nghĩa là phương tiện hiệu quả phụ thuộc vào loại và giá trị được băm. (Việc triển khai MS sử dụng FNV, là một trong những mã băm chung nhất xung quanh, nhưng nếu bạn có kiến ​​thức đặc biệt về dữ liệu thực tế, bạn có thể làm tốt hơn.) Một thứ khác có thể giúp giảm số lượng thành phần trên mỗi nhóm là buộc nhiều nhóm hơn hoặc sử dụng hệ số tải nhỏ hơn. Lần đầu tiên, bạn có thể vượt qua số lượng ban đầu tối thiểu là các nhóm làm đối số cho hàm tạo. Nếu bạn biết số liệu tổng số sẽ nằm trong bản đồ, bạn có thể kiểm soát hệ số tải theo cách này. Bạn cũng có thể cho một số lượng minumum số lượng nhóm sau khi bảng đã được lấp đầy, bằng cách gọi số rehash. Nếu không, có chức năng std::unordered_map<>::max_load_factor mà bạn có thể sử dụng. Nó không được đảm bảo để làm bất cứ điều gì, nhưng trong bất kỳ hợp lý thực hiện, nó sẽ. Lưu ý rằng nếu bạn sử dụng nó trên số đã được điền unordered_map, có thể bạn sẽ phải gọi unordered_map<>::rehash sau đó.

(Có một số điều tôi không hiểu về tiêu chuẩn unordered_map: tại sao hệ số tải là một float, thay vì double; lý do tại sao nó không yêu cầu phải có một hiệu ứng; và tại sao nó không thực hiện tự động gọi rehash cho bạn)

Answer 2

Như với bất kỳ bảng băm, trường hợp xấu nhất luôn là tuyến tính phức tạp (Edit: nếu bạn xây dựng bản đồ mà không cần bất kỳ sự va chạm như bạn đã nêu trong bài viết ban đầu của bạn, sau đó bạn sẽ không bao giờ gặp trường hợp này):

http://www.cplusplus.com/reference/unordered_map/unordered_map/find/

phức tạp trường hợp trung bình: không đổi. Trường hợp xấu nhất: tuyến tính trong kích thước vùng chứa.

Giá trị trả lại Trình lặp cho phần tử, nếu tìm thấy giá trị khóa được chỉ định hoặc unordered_map :: kết thúc nếu không tìm thấy khóa được chỉ định trong vùng chứa.

Tuy nhiên, vì một unordered_map chỉ có thể chứa các khóa duy nhất, bạn sẽ thấy độ phức tạp trung bình của thời gian cố định (container đầu tiên kiểm tra chỉ mục băm và sau đó lặp lại giá trị tại chỉ mục đó).

Tôi nghĩ rằng tài liệu cho unordered_map::count chức năng là thông tin mới hơn:

tìm kiếm container cho các yếu tố mà quan trọng là k và trả về số của các yếu tố được tìm thấy. Vì vùng chứa unordered_map không cho phép các khóa trùng lặp, điều này có nghĩa là hàm thực sự trả về 1 nếu một phần tử có khóa đó tồn tại trong vùng chứa và bằng không.

Answer 3

Để không có xung đột trong cấu trúc dữ liệu băm là vô cùng khó khăn (nếu không thể không cho hàm băm cho sẵn và bất kỳ loại dữ liệu nào). Nó cũng sẽ đòi hỏi một kích thước bảng chính xác bằng số lượng các phím. Không, nó không cần phải nghiêm khắc. Miễn là hàm băm phân phối các giá trị theo cách tương đối đồng nhất, bạn sẽ có độ phức tạp tra cứu O(1).

Bảng băm thường chỉ là mảng có danh sách liên kết để xử lý các xung đột (đây là phương pháp chuỗi - có các phương pháp khác, nhưng đây có thể là cách được sử dụng nhiều nhất để xử lý các xung đột). Do đó, để tìm hiểu xem một giá trị có được chứa trong một nhóm hay không, nó sẽ phải (có khả năng) lặp qua tất cả các giá trị trong nhóm đó. Vì vậy, nếu hàm băm cung cấp cho bạn phân phối đồng nhất và có N nhóm và tổng số giá trị M, thì phải có (trung bình) M/N giá trị cho mỗi nhóm.Miễn là giá trị này không quá lớn, điều này cho phép tra cứu O(1). Vì vậy, như một chút của một câu trả lời dài cho câu hỏi của bạn, miễn là hàm băm là hợp lý, bạn sẽ nhận được O(1) tra cứu, với nó phải lặp qua (trung bình) O(M/N) phím để cung cấp cho bạn một " phủ định "kết quả.