0

在我看来， boost::unordered_map 始终检查您正在查找的密钥与存储桶中的密钥之间的相等性，即使存储桶中只有一个项目与您的密钥散列到。这是安全的，表可能是用不同的键构建的，然后是您正在查找的键，并且您正在查找的键可能与用于构建表的先前键之一发生冲突。

但是，假设我知道要查找哪些键，并且如果存储桶中只有一个键，我想跳过相等性检查。那就是我可以保证我只会查找我之前插入到地图中的键。有没有一种方法可以跳过相等性检查，或者是否有其他一些哈希表实现可以做到这一点？

这是我编写的示例代码，表明 boost::unordered_map 正在检查是否只有一项：

#include <iostream>
#include <boost/unordered_map.hpp>

typedef void (*dispatchFunction)();

void dispatchA() { std::cout << "A" << std::endl; }
void dispatchB() { std::cout << "B" << std::endl; }

template<class T> 
struct myequal_to {
  bool operator()(const T &a, const T &b) const {
    std::cout << "myequal_to: " << a << " " << b << std::endl;
    return a==b;
  }
};

void unordered_map_example() {
  typedef boost::unordered_map<std::string, dispatchFunction,
                       boost::hash<std::string>,
                       myequal_to<std::string> > mymap_t;
  mymap_t mymap;
  mymap["eventA"]=dispatchA; 
  mymap["eventB"]=dispatchB;

  mymap_t::size_type max_elements_in_a_bucket = 0;
  for (mymap_t::size_type bucket = 0; bucket < mymap.bucket_count(); ++bucket) {
    max_elements_in_a_bucket = std::max(max_elements_in_a_bucket,
                                        mymap.bucket_size(bucket));
  }
  std::cout << "number of buckets: " << mymap.bucket_count() 
            << " max per bucket: " << max_elements_in_a_bucket << std::endl;

  dispatchFunction foo = mymap["eventA"];
  foo();
}

int main() {
  unordered_map_example();
  return 0;
}

我的输出显示 myequal 被称为：

桶数：每个桶最多 11 个：1 myequal_to: eventA eventA A

4

1 回答 1

1

如果可能存在冲突（因此需要存储桶中的多个元素），那么您必须检查哈希键，因为您找到的唯一元素可能与目标发生冲突而不是目标。我想如果您正在搜索已知在表中的键并且只是进行搜索以找到它，您可以跳过比较。

于 2013-06-26T23:47:34.467 回答