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

DeathKing

看得不是很明白，说的不知道是不是这个意思：

1、映射GET_HASH：P->Z是一个1对1的函数
2、对于e∈P，GET_HASH(e)是e的唯一标识符？（也就是唯一的全局识别id？）

也就是Point.new(1,0)就像1、2那样，是个固定数，也不像Float那样，每次生成的虽然值一样，但是对象却不一样？

DeathKing

1. class Point
   
2.   def hash
   
3.     return "#{@x}.#{@y.to_s.resive}".to_f
   
4.   end
   
5. end
   

复制代码

hash只能接受Integer（Fixnum）么{:nm_3:}
正在考虑返回Fixnum的方法。

---

好吧，仔细看看这道题并不难，我认为应该这样理解。

1、p ∈ Point； x,y∈Fixnum； h∈Hash（Fixnum）
2、求映射函数GET_HASH：p -> h，且是一个1对1的函数

也就是让我们构建一个二元函数，GET_HASH(x,y)，返回一个Fixnum，那么就要找到一个类似与MD5一样的算法就行了。

其他思路整理中。

DeathKing

于是，考虑到了一种新的Hash生成方法，这个生成的Hash除了特殊值（Point0，0）以外是【对齐】的。特殊的，Point.new(0,0)返回0。并且在这个函数中，0被认为是正数。去掉了关于x和y长度的字段，因为之前算错了。{:nm_3:}

这个Hash有下面的结构
____________
ABJKLMNOPQRS
A => x的正负，可选值（1、2），特殊的，0视为正数
B => y的正负，可选值（1、2），特殊的，0视为正数
J、K、L、M、N、O、P 、Q、R、S=> 描述符，可选值（0、1、2、3、4、5、6、7、8、9）

算法：
1、求取A、B
2、求取abs_x、abs_y，并转化为字符串
3、填充abs_x、abs_y，直到取得字符串长度为5
4、使用嵌入表达式组合，并使用to_i方法转换

代码：

1. def hash
   
2.   return 0 if @x == 0 and @y == 0
   
3.   str = ""
   
4.   abs_x = @x.abs.to_s
   
5.   abs_y = @y.abs.to_s
   
6.   str << (@x >= 0 ? "1" : "2" )
   
7.   str << (@y >= 0 ? "1" : "2" )
   
8.   while abs_x.size < 5
   
9.     abs_x = "0" + abs_x
   
10.   end
    
11.   while abs_y.size < 5
    
12.     abs_y = "0" + abs_y
    
13.   end
    
14.   return "#{str}#{abs_x}#{abs_y}".to_i
    
15. end

复制代码

毛hash个数： 2 * 2 * 2 * 2 * 10 ^ 8 = 1600000000
理论值应该和 2 ^ ( 15 * 2 ) 一样

DeathKing

回复 六祈 的帖子


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

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是一个道理吧？

DeathKing

回复 小幽的马甲 的帖子


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

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