Хеширование и доступ

Question

Я хочу использовать хешированное хранилище для моих объектов. Это действительно быстрее, чем std::map<std::string, Object>? Я имею в виду поиск. Как я знаю, ускорить процесс оптимизации много.

И я не уверен, что мой код правильный. Действительно ли он использует хешированные ключи при поиске / вставке и т. Д.

using boost::multi_index_container;
using namespace boost::multi_index;

struct Object
{
  std::string name;

  Object(std::string name_): name(name_) {}
};

typedef multi_index_container<
  Object,
  indexed_by<
    hashed_unique<
      BOOST_MULTI_INDEX_MEMBER(Object, std::string, name)
    >
  >
> ObjectSet;

ObjectSet objects;
objects.insert(Object("test1"));
objects.insert(Object("test2"));
objects.insert(Object("test3"));

// And testing:
objects.find("test2");

Answer 1

Почему вы используете Boost Multi-Index Container, когда у вас есть только один ключ? Если вы не планируете добавлять дополнительные ключи в ближайшее время, вам следует просто использовать std::unordered_map или std::map.

Что касается хеш-таблиц и деревьев:

GCC-реализация unordered_map, например, никогда не сжимает свою таблицу, поэтому, если вы добавите много элементов, а затем удалите большинство из них, у вас останется что-то, что имеет довольно ужасную локальность данных (и, следовательно, низкую производительность с кэшированием. Алгоритмически хеш-таблицы могут быть привлекательными, но в реальных работающих системах они могут демонстрировать худшую производительность, чем деревья, особенно когда число элементов исчисляется сотнями или менее.

Answer 2

Нахождение точного совпадения при любых, кроме самых экстремальных обстоятельствах, быстрее, чем использование хешированного ключа в unordered_map (hash_map), чем в базовом красно-черном дереве std :: map.

И да, ваш код должен быть верным, предполагая, что есть хеш-функция, которая принимает std :: string и возвращает хэш своего содержимого.