0

我试图确定一个哈希函数，它接受输入 (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 <double, double> hash_table

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

到目前为止，我只能提出线性函数，例如： double Hash_function(int i, int k)

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

但是，我无法确定具有某个（i，k）的唯一键。我可以使用哪些功能来帮助我这样做？

4

3 回答 3

2

从数学上讲，您正在寻求双射。这不是计算机科学意义上的散列函数，因为散列函数有时会产生冲突（除非它是完美的散列函数）。

您标记hash_table的不是哈希表。std::map是一种不同的数据结构，称为有序映射，它能够使用小于运算符<为其提供严格弱排序的任何键类型。实际上，您可以std::pair从utility标题中使用：

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

要插入表中，您将使用：

table[std::make_pair(i, j)] = value;
于 2012-12-09T22:47:59.967 回答
1

@Grizzly 是正确的，使用 double 作为键是有问题的。也许使用基于字符串的散列技术会更好？

于 2012-12-09T22:18:45.593 回答
0

如果 i & k 是 0-100，那么您的密钥可以是一个简单的短（甚至签名），并且是唯一生成的，例如short key = i | k << 8.

于 2012-12-09T23:01:20.610 回答