вопросы / учебник по hash_map

Question

Я знаю, как работает hashmap в Java. Но я не могу полностью понять в C ++.

Я нашел несколько простых руководств, но там нет хеш-функций и т. Д.

Нужна ли строке хэш-функция?

hash_map<string, string> hm;
hm.insert(make_pair("one", "two"));
hm.insert(make_pair("three", "four"));

как это будет работать без хеш-функций для строки? как добавить хеш-функцию?

Есть ли хороший учебник для hash_map?

Спасибо!

Answer 1

Для начала, hash_map не является стандартной библиотекой C ++;это расширение компилятора, которое поставляется с Visual Studio и g ++.Если вы хотите использовать более стандартизированную хеш-таблицу в C ++, посмотрите на библиотеки Boost.Unordered, хеш-контейнеры TR1 или, если у вас более современный компилятор, новые стандартные типы хеш-контейнеров C ++ 0x.Эти контейнеры с именами unordered_map и unordered_set, а не с более выразительными hash_map или hash_set, имеют более стандартизированную поддержку и более переносимы.

Что касается вашего вопроса о том, как указатьхеш-функция, hash_map имеет встроенные хеш-функции для большинства стандартных типов, включая std::string, поэтому вам не нужно указывать их.Если вы хотите определить свою собственную хеш-функцию, вы должны создать объект функции, который перегружает operator() для предоставления хеш-кода, а затем параметризовать hash_map для этого типа в дополнение к другим типам.Например:

struct MyCustomHash {
    size_t operator() (const string& str) const {
        /* Terrible hash function... for instructional purposes only! */
        return str.empty()? 0 : str[0];
    }
};

hash_map<string, int, MyCustomHash> myHashMap;

Теперь myHashMap будет использовать MyCustomHash вместо хэш-функции по умолчанию.

Надеюсь, это поможет!

Answer 2

Какую реализацию hashmap вы используете? Тот, который добавлен в C ++ 0x, std :: unordered_map, уже определяет хеш-функции для некоторых типов (включая строки). Если вы попытаетесь использовать хэш-карту без хэш-функции, она не будет скомпилирована (ошибка будет возникать при попытке вставить что-либо).