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

琪露诺

映射……？

琪露诺

双射……还是不懂是啥 = =
不玩了不玩了

不过……不明真相呢……
class Point
  attr_accessor:x
  attr_accessor:y
  def direct(x,y)
    @x = x
    @y = y
    return [x,y]
  end  
end
po = Point.new
hash = {}
hash[po.direct(1,1)] = 1
hash[po.direct(1,1)] = 2
hash[po.direct(1,1)] = 3
hash[po.direct(1,1)] = 4

貌似不是这么玩 = =？
OTZ……我没读懂题目 - -|||

紫苏

回复 琪露诺 的帖子

class Point
    def initialize(x, y)
        @x, @y = x, y
    end
end

hash = {}
hash[Point.new(1, 1)] = 1
hash[Point.new(1, 1)] = 2
hash[Point.new(1, 1)] = 3
hash[Point.new(1, 1)] = 4

此时，实现 hash 完成题目要求之前表中有 4 个键值对；实现 hash 完成题目要求之后只有 1 个 Point.new(1, 1) => 4

六祈

回复 紫苏 的帖子
紫苏大人的意思是否如此：
对于x和y皆取最大值时，hash使用30位，然而x、y并没有那么大时，则应当节约内存？

DeathKing

回复 六祈 的帖子


    也就是让我们去找一个线性的函数，函数值与元的长度成正比。我一直受MD5的影响，老是想让值对齐 O_O

紫苏

回复 六祈 的帖子

30 位是方便在 Ruby 中测试，因为 Ruby Fixnum 只能容纳 31 位，再大了就自动转换为 Bignum，不被 Ruby 的散列表接受，但抛开语言设计限制不谈，就这个题目而言是存在能泛用于任意大小的 x、y 的解的
题目要求仅仅是完美散列 + 泛用于任意大小 x、y，你说的节约内存应该是最小完美散列的概念，即尽可能分配量值小的、分散度小（比如 1、2、3、……、9 这样的连续整数串就是分散度最小的 9 个散列码）的散列码，我手头的一种解法就是最小完美散列，但题目没有要求必须“最小” ^^

DeathKing

1. irb(main):001:0> {1=>2}.hash
   
2. => 13
   
3. irb(main):002:0> {1=>3}.hash
   
4. => 9
   
5. irb(main):003:0> {19999999999999999999999999999999999999=>-11111111111111111111
   
6. 111111111111111111111111111111111111}.hash
   
7. => 944961355
   
8. irb(main):004:0>

复制代码

so:

1. def hash
   
2. return {@a => @b}.hash
   
3. end

复制代码

这和八云的借用md5是一个道理吧？

小幽的马甲

回复 紫苏 的帖子
举个例子，如果用4位记录长度，不考虑负数，得到的Hash串为
1001011101
最开始的那个1是起始符没有意义不用管它
后面的0010这4位记录a的长度（2），因此后两位就是a的值（11=3）
然后从这儿一直到最后就是b的值（101=5）
最后得到a=3,b=5
加入符号也是一样的，这样应该能保证双向映射
   

DeathKing

回复 小幽的马甲 的帖子


    其实我之前也是用了几位数来记录长度，但是后来老板说了，如果在题目给定的域下，当然可以这样做。

但是当给定x、y∈R以后，记录长度马上就灰了。

紫苏

回复 小幽的马甲 的帖子

明白了，的确可行，果然思想无疆 o.o

又有个问题：假设需要更多的个“4位”来记录位数的位数，位数的位数的位数，……，那么如何才能知道应该在何时停止，即已经获取到了真实的 a 的位数呢？