Простая реализация хэш-карты на C++

Я относительно новичок в C++. В Java мне легко создать экземпляр и использовать хэш-карту. Я хотел бы знать, как сделать это простым способом на C++, так как я видел много разных реализаций, и ни одна из них не показалась мне простой.


c++ hashmap hashtable
person Paulo Guedes    schedule 05.11.2008    source источник

Ответы (5)


arrow_upward
26
arrow_downward

Большинство компиляторов должны определить std::hash_map для вас; в грядущем стандарте C++0x он станет частью стандартной библиотеки как std::unordered_map. страница STL довольно стандартна. Если вы используете Visual Studio, у Microsoft есть страница в теме.

Если вы хотите использовать свой класс как значение, а не как ключ, вам не нужно делать ничего особенного. Все примитивные типы (например, int, char, bool и даже char *) должны "просто работать" как ключи в hash_map. Однако для чего-либо еще вам придется определить свои собственные функции хэширования и равенства, а затем написать «функторы», которые оборачивают их в класс.

Предположим, что ваш класс называется MyClass и вы уже определили:

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

Вам нужно будет определить два функтора, чтобы обернуть эти методы в объекты.

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);
  }
};

И создайте свой hash_map/hash_set как:

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

После этого все должно работать как положено.

person hazzen    schedule 05.11.2008
comment
Я забыл сказать, что использую Unix. Пример, который вы закодировали, выглядит очень просто, я попробую. Но метод HashValue() я должен создать сам, верно? Спрашивая об этом, поскольку в Java есть метод hashcode() по умолчанию для класса Object, я не знаю, как он работает в C++. - person Paulo Guedes; 05.11.2008
comment
Я добавил еще несколько пояснений к ответу. Кроме того, был рекомендован материал boost - он аналогичен, но изучение (некоторых частей) boost может быть похоже на изучение совершенно нового языка. unordered не плохое место для начала. - person hazzen; 05.11.2008

arrow_upward
16
arrow_downward

Использовать хэш-карты в C++ очень просто! Это похоже на использование стандартной карты С++. Вы можете использовать свою реализацию компилятора/библиотеки unordered_map или использовать ту, что предоставлена ​​boost или другого поставщика. Вот быстрый пример. Вы найдете больше, если перейдете по ссылкам, которые вам дали.

#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;
}
person Kasprzol    schedule 05.11.2008

arrow_upward
7
arrow_downward

Взгляните на boost.unordered и его структура данных.

person dalle    schedule 05.11.2008

arrow_upward
3
arrow_downward

Попробуйте использовать неупорядоченные классы Boost.

person Mark Ransom    schedule 05.11.2008

arrow_upward
2
arrow_downward

Ознакомьтесь с Реализация простой хэш-карты (хэш-таблицы) на C++, чтобы узнать, как базовая хэш-таблица содержит пары ключ-значение универсального типа и отдельная стратегия цепочки.

person aozturk    schedule 19.05.2013