c++ - Map C++ 的哈希函数

Question

我正在尝试确定一个哈希函数，该函数接受输入 (i, k) 并确定一个唯一的解决方案。

(i, k) 的可能输入范围从 0 到 100。将每个 (i, k) 视为三叉树中节点的位置。

Ex: (0, 0) can diverge to (1, 1) (1, 0) (1, -1). 
    (1, 1) can diverge to (2, 2) (2, 1) (2, 0).

此处给出示例:

http://www.google.com/imgres?imgurl=http://sfb649.wiwi.hu-berlin.de/fedc_homepage/xplore/tutorials/stfhtmlimg1156.gif&imgrefurl=http://sfb649.wiwi.hu-berlin.de/fedc_homepage/xplore/tutorials/stfhtmlnode41.html&h=413&w=416&sz=4&tbnid=OegDZu-yeVitZM:&tbnh=90&tbnw=91&zoom=1&usg=__9uQWDNYNLV14YioWWbrqPgfa3DQ=&docid=2hhitNyRWjI_DM&hl=en&sa=X&ei=xAfFUIbyG8nzyAHv2YDICg&ved=0CDsQ9QEwAQ

我正在使用 map

map <double, double> hash_table

我需要从对 (i, k) 中确定一个键值以散列为该 (i, k) 的值

到目前为止，我只能提出线性函数，例如: 双哈希函数(int i, int k)

{
    //double val = pow(i, k) + i;
    //return (val % 4294967296);
    return (i*3.1415 + k*i*9.12341); 
}

但是，我无法确定具有特定 (i, k) 的唯一键。我可以使用什么样的功能来帮助我这样做？

Answer 1

从数学上讲，您正在寻找一个 bijection .这不是计算机科学意义上的哈希函数，因为哈希函数有时会产生冲突(除非它是 perfect hash function )。

您标记的内容 hash_table不是哈希表。 std::map是一种称为有序映射的不同数据结构，它能够使用小于运算符 < 的任何键类型。提供一个 strict weak ordering .事实上，您可以使用 std::pair 来自 utility header :

std::map<std::pair<int, int>, double> table;

要插入表中，您可以使用:

table[std::make_pair(i, j)] = value;