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

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

Любые хорошие примеры будут оценены.

Стандартная библиотека включает контейнеры упорядоченной и неупорядоченной карт ( 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
Ключ: привет Значение: 23

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

В противном случае, если вам действительно нужна хеш-таблица (O (1) insert / access), проверьте std::unordered_map, которая имеет аналог std::mapAPI (например, в приведенном выше примере вам просто нужно найти и заменить 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 для лучшей переносимости.

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

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

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

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

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

#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 *» в объявлении ключа должна решить эту проблему.)

Доказательства 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);
    }
  };

}

Для тех из нас, кто пытается выяснить, как хэшировать наши собственные классы, все еще используя стандартный шаблон, есть простое решение:

1. В вашем классе вам нужно определить перегрузку оператора равенства ==. Если вы не знаете, как это сделать, у GeeksforGeeks есть отличный учебник https://www.geeksforgeeks.org/operator-overloading-c/

2. Под стандартным пространством имен объявите структуру шаблона с именем hash с вашим именем класса в качестве типа (см. Ниже). Я нашел отличный блог, который также показывает пример вычисления хэшей с использованием XOR и битового сдвига, но это выходит за рамки этого вопроса, но он также включает подробные инструкции о том, как выполнить использование хэш-функций, а также https://prateekvjoshi.com/ 2014/06/05 / с использованием хеш-функции-в-C-для-определяемых пользователем классов /

namespace std {

  template<>
  struct hash<my_type> {
    size_t operator()(const my_type& k) {
      // Do your hash function here
      ...
    }
  };

}

3. Итак, чтобы реализовать хеш-таблицу с использованием вашей новой хеш-функции, вам просто нужно создать std::mapили, std::unordered_mapкак вы обычно делаете, и использовать my_typeв качестве ключа, стандартная библиотека автоматически использует хеш-функцию, которую вы определили ранее (на шаге 2) для хеширования твои ключи.

#include <unordered_map>

int main() {
  std::unordered_map<my_type, other_type> my_map;
}