Thực hiện băm đơn giản trong C++

Question

Tôi tương đối mới đối với C++. Trong Java, thật dễ dàng cho tôi để khởi tạo và sử dụng một hashmap. Tôi muốn biết làm thế nào để làm điều đó một cách đơn giản trong C + +, kể từ khi tôi thấy nhiều triển khai khác nhau và không ai trong số họ nhìn đơn giản với tôi.

Answer 1

Hầu hết các trình biên dịch phải xác định std::hash_map cho bạn; trong tiêu chuẩn C++0x sắp tới, nó sẽ là một phần của thư viện chuẩn là std::unordered_map. Các STL Page trên nó là khá chuẩn. Nếu bạn sử dụng Visual Studio, Microsoft có một trang trên đó.

Nếu bạn muốn sử dụng lớp của bạn làm giá trị, không phải là khóa, thì bạn không cần phải làm gì đặc biệt. Tất cả các loại nguyên thủy (những thứ như int, char, bool và thậm chí char *) nên "chỉ hoạt động" làm khóa trong một hash_map. Tuy nhiên, đối với bất cứ điều gì khác, bạn sẽ phải xác định các hàm băm và bình đẳng của riêng bạn và sau đó viết "functors" để bọc chúng trong một lớp.

Giả sử lớp học của bạn được gọi là MyClass và bạn đã xác định:

size_t MyClass::HashValue() const { /* something */ } 
bool MyClass::Equals(const MyClass& other) const { /* something */ } 

Bạn sẽ cần phải xác định hai functors để bọc các phương pháp đó trong đối tượng.

struct MyClassHash { 
    size_t operator()(const MyClass& p) const { 
    return p.HashValue(); 
    } 
}; 

struct MyClassEqual { 
    bool operator()(const MyClass& c1, const MyClass& c2) const { 
    return c1.Equals(c2); 
    } 
}; 

Và nhanh chóng của bạn hash_map/hash_set như:

hash_map<MyClass, DataType, MyClassHash, MyClassEqual> my_hash_map; 
hash_set<MyClass, MyClassHash, MyClassEqual> my_hash_set; 

Tất cả những gì nên làm việc như mong đợi sau đó.

Answer 2

Hãy thử các lớp học unordered tăng cường.

Answer 3

Hãy xem boost.unordered và data structure.

Answer 4

Sử dụng hashmaps trong C++ thật dễ dàng! Nó giống như sử dụng bản đồ C++ chuẩn. Bạn có thể sử dụng trình biên dịch/triển khai thư viện của mình theo số unordered_map hoặc sử dụng mã được cung cấp bởi boost hoặc một số nhà cung cấp khác. Đây là một mẫu nhanh. Bạn sẽ tìm thấy nhiều hơn nếu bạn làm theo các liên kết bạn đã được đưa ra.

#include <unordered_map> 
#include <string> 
#include <iostream> 

int main() 
{ 
    typedef std::tr1::unordered_map< std::string, int > hashmap; 
    hashmap numbers; 

    numbers["one"] = 1; 
    numbers["two"] = 2; 
    numbers["three"] = 3; 

    std::tr1::hash<std::string> hashfunc = numbers.hash_function(); 
    for(hashmap::const_iterator i = numbers.begin(), e = numbers.end() ; i != e ; ++i) { 
     std::cout << i->first << " -> " << i->second << " (hash = " << hashfunc(i->first) << ")" << std::endl; 
    } 
    return 0; 
} 

Answer 5

Simple Hash Map (Hash Table) Implementation in C++ cho bảng băm cơ bản với cặp khóa-giá trị loại chung và chiến lược chuỗi riêng biệt.