Предоставление хорошей хэш-функции

Question

В моем первоначальном вопросе (подробное экспериментальное исследование): Appropriate container for the fast insertion and lookup of n-dimensional real vectors (initial benchmarking provided) У меня действительно странное поведение с использованием несортированного набора для управления случайными 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; 
} 

Две самые странные вещи:

1. Запуск экспериментов без каких-либо флагов оптимизации, даже с распущенными толерантности (1е-1) почти все случайные векторы (реализованы в виде N-мерных массивов) были идентифицированы как уникальные. Я не наблюдал этого, используя vectors и sets.
2. При включении флага оптимизации -O3 количество уникальных элементов значительно отличается от чисел без оптимизации, и это, безусловно, означает, что с моим подходом что-то не так.

Edit: проблема 2-й решается с учетом @WhozCraig замечания.

Итак, мой вопрос:: Это странное поведение, потому что моя хэш-функция плохо разработана? Если да, можете ли вы предложить, как сделать лучшую хэш-функцию для моего дела?

Answer 1

Ваша программа имеет неопределенное поведение (неинициализировано std::size_t ret).

Во-первых, ArrayEqual не вызывает отношения эквивалентности. Это не транзитивно - существуют три массива a, b и c таким образом, что a является «достаточно близко» к b и b является «достаточно близко» к c, но a не «достаточно близко» к c.

Во-вторых, ArrayHash может не возвращать одно и то же значение хэша для двух массивов, которое ArrayEqual объявляет равным.

Оба эти условия являются обязательными для аргументов шаблона std::unordered_set.