Каков наилучший способ использовать HashMap в C ++?

Question

Я знаю, что у STL есть HashMap API, но я не могу найти хорошую и исчерпывающую документацию с хорошими примерами по этому поводу.

Любые хорошие примеры приветствуются.

Answer 1

Стандартная библиотека включает в себя контейнеры с упорядоченной и неупорядоченной картой (std::map и std::unordered_map). В упорядоченной карте элементы отсортированы по ключу, вставка и доступ в O (log n) . Обычно стандартная библиотека внутренне использует красно-чёрные деревья для упорядоченных карт. Но это только деталь реализации. В неупорядоченную карту вставьте и получите доступ в O (1). Это просто другое название хеш-таблицы.

Пример с (заказанным) std::map:

#include <map>
#include <iostream>
#include <cassert>

int main(int argc, char **argv)
{
  std::map<std::string, int> m;
  m["hello"] = 23;
  // check if key is present
  if (m.find("world") != m.end())
    std::cout << "map contains key world!\n";
  // retrieve
  std::cout << m["hello"] << '\n';
  std::map<std::string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  std::cout << "Key: " << i->first << " Value: " << i->second << '\n';
  return 0;
}

Выход:

23
Key: hello Value: 23

Если вам нужен порядок в вашем контейнере и вам подходит время выполнения O (log n), просто используйте std::map.

В противном случае, если вам действительно нужна хеш-таблица (O (1) вставка / доступ), проверьте std::unordered_map, который имеет аналогичный std::map API (например, в приведенном выше примере вам просто нужно найти и замените map на unordered_map).

Контейнер unordered_map был представлен с версией C ++ 11 стандарта . Таким образом, в зависимости от вашего компилятора вы должны включить функции C ++ 11 (например, при использовании GCC 4.8 вы должны добавить -std=c++11 к CXXFLAGS).

Еще до выпуска C ++ 11 GCC поддерживал unordered_map - в пространстве имен std::tr1. Таким образом, для старых компиляторов GCC вы можете попробовать использовать его так:

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

Это также часть boost, т. Е. Вы можете использовать соответствующий boost-header для лучшей переносимости.

Answer 2

A hash_map является более старой, нестандартной версией того, что для целей стандартизации называется unordered_map (первоначально в TR1 и включено в стандарт начиная с C ++ 11). Как следует из названия, он отличается от std::map в основном неупорядоченным - если, например, вы перебираете карту с begin() до end(), вы получаете элементы в порядке по ключу ¹, но если вы перебираете unordered_map с begin() до end(), вы получаете элементы в более или менее произвольном порядке.

Обычно unordered_map обычно имеет постоянную сложность. То есть вставка, поиск и т. Д. Обычно занимают фиксированное количество времени, независимо от того, сколько элементов в таблице. std::map имеет сложность, которая логарифмируется по количеству сохраняемых элементов - что означает, что время для вставки или извлечения элемента увеличивается, но довольно медленно , когда карта увеличивается. Например, если для поиска одного из 1 миллиона элементов требуется 1 микросекунда, то можно ожидать, что для поиска одного из 2 миллионов элементов потребуется около 2 микросекунд, 3 микросекунды для одного из 4 миллионов элементов, 4 микросекунды для одного из 8 миллионов. предметы и т. д.

С практической точки зрения, это еще не вся история. По своей природе простая хеш-таблица имеет фиксированный размер. Адаптировать его к требованиям переменного размера для контейнера общего назначения несколько нетривиально. В результате операции, которые (потенциально) увеличивают таблицу (например, вставка), потенциально относительно медленны (то есть большинство являются довольно быстрыми, но периодически одна будет намного медленнее). Поиск, который не может изменить размер таблицы, как правило, намного быстрее. В результате большинство таблиц на основе хеш-функции имеют тенденцию работать лучше, когда вы выполняете много поисков по сравнению с количеством вставок. В ситуациях, когда вы вставляете много данных, затем просматриваете таблицу один раз, чтобы получить результаты (например, подсчитав количество уникальных слов в файле), есть вероятность, что std::map будет таким же быстрым и, возможно, даже более быстрым (но, опять же, сложность вычислений различна, поэтому она также может зависеть от количества уникальных слов в файле).

---

^{1 Где порядок определяется третьим параметром шаблона при создании карты, std::less<T> по умолчанию.}

Answer 3

Вот более полный и гибкий пример, который не пропускает необходимые включения для генерации ошибок компиляции:

#include <iostream>
#include <unordered_map>

class Hashtable {
    std::unordered_map<const void *, const void *> htmap;

public:
    void put(const void *key, const void *value) {
            htmap[key] = value;
    }

    const void *get(const void *key) {
            return htmap[key];
    }

};

int main() {
    Hashtable ht;
    ht.put("Bob", "Dylan");
    int one = 1;
    ht.put("one", &one);
    std::cout << (char *)ht.get("Bob") << "; " << *(int *)ht.get("one");
}

По-прежнему не особенно полезно для ключей, если только они не предопределены как указатели, потому что соответствующее значение не подойдет! (Однако, поскольку я обычно использую строки для ключей, замена «string» вместо «const void *» в объявлении ключа должна решить эту проблему.)

Answer 4

Доказательство того, что std::unordered_map использует хеш-карту в GCC stdlibc ++ 6.4 *

Это было упомянуто по адресу: https://stackoverflow.com/a/3578247/895245, но в следующем ответе: Какая структура данных находится внутри std :: map в C ++? Я привел дополнительные доказательства этого для GCC stdlibc ++ 6.4. реализация:

• Отладка шага GDB в класс
• анализ характеристик производительности

Вот предварительный просмотр графика характеристик производительности, описанного в этом ответе:

Как использовать пользовательский класс и хэш-функцию с unordered_map

Этот ответ гласит: C ++ unordered_map с использованием пользовательского типа класса в качестве ключа

Выдержка: равенство:

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

Функция хеширования:

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}