Tìm nhóm trong unordered_map từ băm mà không cần khóa

Question

Tôi đang sử dụng tiêu chuẩn :: unordered_map. Tôi có một giá trị băm và một cách để xác định xem một khóa ứng viên cụ thể là chìa khóa mà tôi đang tìm kiếm, nhưng tôi không có một khóa thực sự. Tôi muốn tìm kiếm các thùng tương ứng với giá trị băm và đi qua mỗi yếu tố trong xô đó để xem nếu nó là yếu tố mà tôi đang tìm kiếm. Thật không may, hàm std :: unordered_map :: bucket (x) yêu cầu x là một khóa. Có thực sự không có cách nào để có được một xô từ một giá trị băm mà không đầu tiên xây dựng một chìa khóa?

Chi tiết bạn không cần trả lời câu hỏi: Tôi có thể tạo khóa nhưng trong trường hợp thông thường không có xung đột sẽ mất nhiều thời gian hơn chỉ kiểm tra xem ứng cử viên duy nhất tôi tìm thấy trong thùng chứa đúng một. Tôi có một yếu tố tải thấp vì vậy có rất ít va chạm và thậm chí cho một va chạm giá trị băm đầy đủ là không phù hợp, vì vậy không phù hợp được nhanh chóng xác định không phù hợp. Tôi quan tâm đến điều này bởi vì tôi đã xác định với một hồ sơ mà xây dựng quan trọng là dành một số lượng đáng kể thời gian - có rất nhiều tra cứu và mỗi tra cứu đòi hỏi phải xây dựng một chìa khóa.

Thậm chí thêm chi tiết mà bạn thực sự không cần trả lời câu hỏi: Các khóa là vectơ của số nguyên và truy vấn của tôi là tổng của hai vectơ. Sẽ nhanh hơn nếu kiểm tra xem vectơ V có phải là tổng của hai vectơ A và B hơn là tổng hai vectơ thành một vector thứ ba C = A + B và sau đó so sánh C với V. Tôi có thể xác định giá trị băm của A + B mà không tính toán vector thực tế A + B vì tôi lưu trữ giá trị băm của các vectơ này và hàm băm của tôi f có thuộc tính f (A + B) = f (A) + f (B). Vì vậy, tôi chỉ cần thêm hai giá trị băm được lưu trữ để có được giá trị băm của tổng. Tôi đã đảm bảo giữ một vector dự phòng xung quanh để xây dựng một khóa không yêu cầu cấp phát bộ nhớ nhưng mã để thêm các vectơ vẫn chiếm một lượng đáng kể thời gian.

Answer 1

Bạn không thể tránh việc xây dựng một khóa, nhưng bạn có thể tránh việc xây dựng toàn bộ khóa.

Ví dụ: giả sử bạn có lớp khóa VectorKey gói gọn std::vector và lưu trữ mã băm được tính. Ngoài ra, giả sử bạn cung cấp các triển khai của Hash và KeyEqual truy cập mã băm được lưu trong bộ nhớ cache trên số VectorKey và so sánh các vectơ đóng gói cho sự bình đẳng. Bạn có thể định nghĩa một constructor của VectorKey luôn xây dựng một sản phẩm nào std::vector, và thiết lập mã băm lưu trữ một giá trị truyền cho constructor:

class VectorKey{ 
    int cached_hash; 
    std::vector<int> key; 
public: 
    VectorKey(const std::vector<int>& _key) 
    : key(_key) 
    , cached_hash(calc_hash(_key)) { 
    } 
    // *** This is the centerpiece of the solution: *** 
    // *** this constructor effectively lets you access *** 
    // *** a bucket with nothing more than a hash code. *** 
    VectorKey(int hash) 
    : cached_hash(hash) { 
    } 
    // More code goes here for getting cached_hash 
    // and also for checking equality 
private: 
    int calc_hash(const std::vector<int>& _key) { 
     // calculate the hash code based on the vector 
    } 
}; 

Với một lớp học quan trọng như vậy, bạn có thể nhanh chóng tìm thấy xô bằng cách xây dựng một khóa giả:

size_type bucketIndex = myHashMap.bucket(VectorKey(precalculated_hash));