提供一个好的哈希函数

Question

提供一个好的哈希函数

c++stlperformance-testingunordered-sethash-function

3

在我的初步问题中（详细的实验调查）：适用于快速插入和查找n维实向量的合适容器（提供了初始基准测试），我使用未排序集合来管理随机N维浮点数组时，由于我的初始（可能设计不良的哈希函数），出现了非常奇怪的行为：

#include <iostream>
#include <chrono>
#include <random>
#include <array>
#include <unordered_set>

const int N = 3;  // Dimensionality of the arrays

std::array<double, N> getRandomArray() {
  // Engines and distributions retain state, thus defined as static
  static std::default_random_engine e;                    // engine
  static std::uniform_real_distribution<double> d(0, 1);  // distribution
  std::array<double, N> ret;
  for (size_t i = 0; i < N; ++i) {
    ret[i] = d(e);
  }
  return ret;
}

// Return Squared Euclidean Distance
template <typename InputIt1, typename InputIt2>
double EuclideanDistance2(InputIt1 beg1, InputIt1 end1, InputIt2 beg2) {
  double val = 0.0;
  while (beg1 != end1) {
    double dist = (*beg1++) - (*beg2++);
    val += dist*dist;
  }
  return val;
}

struct ArrayHash {  // Hash Function
  std::size_t operator() (const std::array<double, N>& arr) const {
    std::size_t ret = 0;
    for (const double elem : arr) {
      ret += std::hash<double>()(elem);
    }
    return ret;
  }
};

struct ArrayEqual {  // Equivalence Criterion
  bool operator() (const std::array<double, N>& arr1,
                          const std::array<double, N>& arr2) const {
    return EuclideanDistance2(arr1.begin(), arr1.end(), arr2.begin()) < tol*tol;
  }
 private:
  static constexpr double tol = 1e-6;  // Comparison tolerance
};


int main() {
  // create a unordered set of double arrays (usda)
  std::unordered_set<std::array<double, N>, ArrayHash, ArrayEqual> usda;
  // record start time
  auto start = std::chrono::steady_clock::now();
  // Generate and insert one hundred thousands new double arrays
  for (size_t i = 0; i < 100000; ++i) {
    // Get a new random double array (da)
    std::array<double, N> da = getRandomArray();
    usda.insert(da);
  }
  // record finish time
  auto end = std::chrono::steady_clock::now();
  std::chrono::duration<double> diff = end - start;
  std::cout << "Time to generate and insert unique elements into UNORD. SET: "
            << diff.count() << " s\n";
  std::cout << "unord. set size() = " << usda.size() << std::endl;
  return 0;
}

两个最奇怪的事情是：

即使使用松散容差（1e-1）运行实验时，几乎所有的随机向量（作为N维数组实现）都被识别为唯一，且没有使用 vectors 和 sets 也没有观察到这种情况。
开启 -O3 优化标志后，独特元素的数量与没有进行优化时有显著差异，这肯定说明我的方法有问题。

编辑：根据@WhozCraig的建议解决了第二个问题。

所以，我的问题是：这种奇怪的行为是因为我的哈希函数设计不好吗？如果是这样，请给出如何为我的情况制作更好的哈希函数的建议。

- Remis

你有检查过给定数组的实际哈希值吗？当使用 -O3 构建时，它是否会改变？你有没有查看过一些可管理数量的随机数组的哈希值分布？-O3 是否选择了不同的默认随机引擎？ - Useless

1

你意识到 std::size_t ret; 这个东西是不确定的吗？因此后续循环的 ret += std::hash<double>()(elem); 实际上几乎毫无价值。所以，是的，我认为它设计得很糟糕。 - WhozCraig

@WhozCraig 谢谢，这真的是问题所在（我真丢人）！在初始化 std::size_t ret = 0 后，我摆脱了第二个奇怪的事情。 - Remis

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Igor Tandetnik · Answer 1

您的程序存在未定义行为（除未初始化的std::size_t ret变量之外）。

首先，ArrayEqual不会导致等价关系。它不是传递性的-存在三个数组a、b和c，使得a与b“足够接近”，b与c“足够接近”，但a与c不“足够接近”。

其次，ArrayHash可能会对由ArrayEqual声明相等的两个数组返回不同的哈希值。

这两者都是std::unordered_set的模板参数的前提条件。