想象一下两个正整数A和B.我想将这两个整数组合成一个整数C.
可能没有其他整数D和E组合为C.因此将它们与加法运算符组合不起作用.例如30 + 10 = 40 = 40 + 0 = 39 + 1连接也不起作用.例如"31"+"2"= 312 ="3"+"12"
这种组合操作也应该是确定性的(总是在相同的输入下产生相同的结果)并且应该总是在整数的正侧或负侧产生整数.
问题一般: 我有一个很大的2d点空间,人口稀少的点.可以把它想象成一个涂有黑点的大白色帆布.我必须迭代并搜索这些点很多.Canvas(点空间)可能很大,接近int的限制,并且在设置点之前它的大小是未知的.
这让我想到了哈希:
理想: 我需要一个带2D点的哈希函数,返回一个唯一的uint32.这样就不会发生碰撞.您可以假设uint32可以轻松计算Canvas上的点数.
重要提示:事先不可能知道画布的大小(甚至可能会改变),所以就像这样
canvaswidth*y + x
遗憾的是,这是不可能的.
我也试过很天真
abs(x)+ abs(y)
但这会产生太多的碰撞.
妥协: 一种散列函数,它提供非常低的碰撞概率.
任何人的想法？谢谢你的帮助.
此致,Andreas T.
编辑:我不得不改变问题文本中的内容:我改变了"能够用uint32计算画布点数"的假设"能够计算画布上的点数(或者要存储的坐标对的数量")通过uint32.我原来的问题没有多大意义,因为我有一个sqrt(max(uint32))xsqrt(max(uint32))大小的画布,它可以通过16位移位和OR进行唯一表示.
我希望这是可以的,因为所有答案仍然对更新的假设最有意义
对不起.
我的课:
public class myClass
{
public int A { get; set; }
public int B { get; set; }
public int C { get; set; }
public int D { get; set; }
}
和主要的例子:
Dictionary<myClass, List<string>> dict = new Dictionary<myClass, List<string>>();
myClass first = new myClass();
first.A = 2;
first.B = 3;
myClass second = new myClass();
second.A = 2;
second.B = 3;
second.C = 5;
second.D = 6;
dict.Add(first, new List<string>());
if (dict.ContainsKey(second))
{
//
//should come here …请考虑以下代码:
struct Vec2 : IEquatable<Vec2>
{
double X,Y;
public bool Equals(Vec2 other)
{
return X.Equals(other.X) && Y.Equals(other.Y);
}
public override bool Equals(object obj)
{
if (obj is Vec2)
{
return Equals((Vec2)obj);
}
return false;
}
// this will return the same value when X, Y are swapped
public override int GetHashCode()
{
return X.GetHashCode() ^ Y.GetHashCode();
}
}
除了比较双精度的平等对话(这只是演示代码)之外,我关注的是当X,Y值被交换时存在哈希冲突.例如:
Vec2 A = new Vec2() { X=1, Y=5 };
Vec2 B = new Vec2() { X=5, Y=1 };
bool test1 = …我有一系列对象,其唯一不同的内部状态是2-d位置(2个整数)的固定长度列表(或其他).也就是说,它们都具有相同数量的元素,具有(可能)不同的2-d值.
我将不断地将新实例与之前存在的所有实例进行比较,因此我编写一个良好的散列函数以最大限度地减少比较次数非常重要.
你会怎么推荐我哈希呢？