蛋疼数学程序帝！散列算法

小幽的马甲

回复 紫苏 的帖子


    {:nm_1:}果然还得再记录一下这个值
Hash=50669=(1 10 0010 11 110 1101)2
同样的，1是起始符
10=2表示要往下找两次
0010表示”下一个“位数的位数是2位
后两位“11=3”表示“下一个”位数（其实是原值）的位数是3
后三位110=6表示a=6
然后从这儿一直到最后的1101=13表示b=13
最后得出a=6，b=13

david50407

我也来提供个想法(笑
先想想数学的二元一次方程组
ax + by = c
dx +ey = f
且a / b != d / e时 必有一组解

也就是说当x + y = k, x - y = h 时必能求出(x, y)之唯一解

class Point
  def hash
    return "#{x+y}@#{x-y}"
  end
end

也就是说当Point的x, y为固定值时Point.hash的值也会固定(不过这儿是字符串
也能从hash反推x, y

david50407

这样好了 咱来学学RUBY的Marshal方法
先分成这样 :
X 的位数| X的正负值( : 1, - : 2) | abs(X) | Y的正负值( : 1, - : 2) | abs(Y)
解释一下...
首先会读取 X 的位数(不考虑正负)
这部分仿照Marshal :
这里用点小技巧 (不过挺占空间的@@
假设(X的位数) <==这也是一个数, 有y位
且 y <= 2^h (1 <= (h 1) <= 9)
也就是说(X的位数) 这个数可以是1 ~ 2^8 位数
也就是说X的位数可以是1 ~ 10^(2^8 1) - 1 (表示此数庞大XD)
也就是说X 可以是1 ~ 10^(10^(2^8 1)) - 1 (更庞大了= =)
接下来依照以下顺序写入
(h 1) --> X 的位数(不足者在前补0) #=> 这当作是第一部分(X 的位数)

再来是第二部分: X的正负值( : 1, - : 2) 这很简单
第3部分依然简单abs后写入
第四第五部分直接写入
不必先写入Y的位数了

LZ应该知道为啥
不知道的再补 (笑

以上都是整数 所以能符合要求
不过x, y值越大 hash值也会越大= =
可能不会是30位 可能大可能小

紫苏

两天过去了，公布一个最小完美散列的解法：



Cheers,
一群邪恶、疯狂的计算机科学家（>v<）

chaochao

两天过去了，公布一个最小完美散列的解法：



Cheers,
一群邪恶、疯狂的计算机科学家（>v ...
紫苏 发表于 2010-8-29 11:28

1.         public static string xxxxxxx(long[] l)
   
2.         {
   
3.             string ret = "";
   
4.             long[] temp = new long[l.Length];
   
5.             for (int i = 0; i < temp.Length; i++)
   
6.             {
   
7.                 temp[i] = l[i];
   
8.             }
   
9.             for (int i = 0; i < 64; i++)
   
10.             {
    
11.                 for (int j = temp.Length - 1; j >= 0; j--)
    
12.                 {
    
13.                     ulong t = (ulong)temp[j];
    
14.                     t = t % 2;
    
15.                     temp[j] = temp[j] >> 1;
    
16.                     ret = t + ret;
    
17.                 }
    
18.             }
    
19.             ret = ret.TrimStart('0');
    
20.             return ret;
    
21.         }

复制代码

紫苏

回复 chaochao 的帖子

呵呵，通用于 N 个域了
其实用纯粹的整数应该也行，.NET 4.0 里面支持 BigInteger

轮回者

一个例子
对于P中的元素q
q.x = 0b11111(2进制)
q.y = 0b10011(2进制)

那么,
F(Q) = 0b1101011111(2进制)

位数不相同的话,少的那个用0补上

至于负数的情况,把负当做1，正当做0
对于某个二进制数(0bX...X),如果是正数的话,就看做0bX...X0,反之,则是0bX...X1
就是说,对于z
双射 f: z -> n
z -> abs(z)*2+1/0(z>0/z<=0)
其实吧,反正N2,N,Z,Z2都是同构的,做个双射对应过去呗

轮回者

回复 紫苏 的帖子


    = = 刚看到.呃,当我没说

逸豫

看到之前的大大们的解法，忽然想到一种解法
首先，既然要用一个数表示唯一的一对数，那么最简单的就是直接把两个数放在一起，中间加上分隔符即可……但是数字中添加分隔符比较麻烦啊……然后就从进制入手，8进制里面是无法出现8这个数字的，那么，我们可以用10进制来表示8进制，同时中间加上8作为分隔符即可
代码如下：

1. tempa = sprintf("%#o", a)
   
2. tempa[0] = a >= 0 ? "1" : "2"
   
3. tempb = sprintf("%#o", b)
   
4. tempb[0] = b >= 0 ? "1" : "2"
   
5. hash = (tempa+"8"+tempb).to_i

复制代码

紫苏

回复 逸豫 的帖子

Orz……|||
想起一个笑话：
世界上有 10 种人：
不懂二进制的、懂二进制的以及懂格雷码的……||