C++ unordered_map 存在自定义哈希问题

Question

我正在尝试编写用于 unordered_map 的自定义哈希函数。我能够插入项目并遍历它们，但无法使用 at()、find() 或 operator[] 函数查找项目。

#include <cstddef>
#include <iostream>
#include <functional>
#include <random>
#include <unordered_map>

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define JHASH_GOLDEN_RATIO  0x9e3779b9

using namespace std;

#define __jhash_mix(a, b, c) \
{ \
  a -= b; a -= c; a ^= (c>>13); \
  b -= c; b -= a; b ^= (a<<8); \
  c -= a; c -= b; c ^= (b>>13); \
  a -= b; a -= c; a ^= (c>>12);  \
  b -= c; b -= a; b ^= (a<<16); \
  c -= a; c -= b; c ^= (b>>5); \
  a -= b; a -= c; a ^= (c>>3);  \
  b -= c; b -= a; b ^= (a<<10); \
  c -= a; c -= b; c ^= (b>>15); \
}

uint32_t
jhash_3words (uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
{
  a += JHASH_GOLDEN_RATIO;
  b += JHASH_GOLDEN_RATIO;
  c += initval;

  __jhash_mix (a, b, c);

  return c;
}

size_t jenkins_hash(const uint32_t &num){
    return (size_t) jhash_3words (num, 0, 0, rand());
}

int main(){

    std::unordered_map<uint32_t, char, std::function<decltype(jenkins_hash)>> ids(0, jenkins_hash );

        ids[(uint32_t) 42341] = 'g';
        ids[(uint32_t) 2232] = 'b';
        ids[(uint32_t) 7556] = 'q';

    for ( auto it = ids.begin(); it != ids.end(); ++it ){
        std::cout << "Element " << it->first << " " << it->second << std::endl;
    }
    std::cout << ids.size() << std::endl;

    printf("%c\n", ids.find(7556)->second);


    return 0;
}

以上代码的输出如下：

Element 2232 b
Element 7556 q
Element 42341 g
3
Segmentation fault (core dumped)

我的问题是...

为什么会产生段错误？
为什么 at() 和 operator[] 只是 return 什么都不做，而 find() 段错误？

有什么想法吗？

Answer 1

size_t jenkins_hash(const uint32_t &num){
    return (size_t) jhash_3words (num, 0, 0, rand());
}

由于您的散列函数包含一个随机元素，两次 7556 散列将产生不同的散列值。这意味着 find 完成的查找无法找到任何内容，实际上 returns ids.end()，您不应该取消引用。

以下是您应该如何使用 find():

auto found = ids.find(7556);
if(found != ids.end()) {
  printf("%c\n", found->second);
}

C++ unordered_map 存在自定义哈希问题

C++ unordered_map with custom hash issues

c++

hash

unordered-map