在无序映射中计算重新哈希的次数

Question

如何评估unordered_map在IT技术中的性能？[C++14]

在我的代码中，我使用std :: unordered_map处理亿万个键。为了优化性能，我希望了解unordered_map的行为，例如重新哈希的次数及其他参数（有多少桶？在重新哈希之前有多少空桶？）。我知道STL提供了桶的数量，但是还需要哪些信息才能进行分析？

- letsBeePolite

---

我知道STL提供了桶的数量？这很遗憾，但是却是事实。桶接口本来就不应该存在。:( - Baum mit Augen

Answer 1

像许多标准容器一样，unordered_map被要求呈指数增长。具体速率由实现定义；您可以检查实现或其源代码的规格。

它的调整大小是确定性的。如果您将其包装在shim中，您可以通过在允许扩展容器的每个操作之前和之后检查bucket_count来检测这些调整大小。

您可以遍历桶：

template<class UnorderedMeow>
std::size_t empty_buckets( UnorderedMeow&& meow ) {
  std::size_t r = 0;
  auto buckets = meow.buckets_count();
  for (decltype(buckets) i = 0; i < buckets; ++i)
    if (meow.bucket_size(i)==0)
      ++r;
  return r;
}

查找有多少个是空的。

如果您使用基于继承的组合并仅覆盖您知道可以添加/删除内容的部分...

template<class Base>
struct instrumented_unordered_map:Base {
  using Self = instrumented_unordered_map;
  using Base::Base;
  using key_type = Base::key_type; // etc
  struct instrument {
    Self* self;
    instrument( Self* s ):self(s) {
      self->start_instrument();
    }
    ~instrument() {
      self->end_instrument();
    }
  };
  struct instrument_state {
    // blah
  };
  instrument_state state;
  void start_instrument() {
    // populate state
  }
  void end_instrument() {
    // extract from state, generate report
  }
  decltype(auto) operator[]( key_type const& key ) {
    instrument _(this);
    return Base::operator[](key);
  }
  // etc  
};

- Yakk - Adam Nevraumont