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

六祈

内个，16384刚好可以用14位表示，@a和@b组成28位，剩下2位用来表示4个象限，紫苏大人这个问题的条件刚好是临界值，几乎是没有额外的算法了

然后做法就支持下小幽的吧   ——→其实手头没有参考资料

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 ) 一样

八云紫

1. module ReisenRSA
   
2.   class Reisen_RSA
   
3.     def initialize(p, q)
   
4.       @p = p
   
5.       @q = q
   
6.       get_data
   
7.     end
   
8.    
   
9.     def get_data
   
10.       @n = @p * @q
    
11.       @t =(@p - 1) * (@q - 1)
    
12.     end
    
13.    
    
14.     def get_d(e)
    
15.       (1..99999).each do |i|
    
16.         return i if i * e % @t == 1
    
17.       end
    
18.     end
    
19.    
    
20.     def pack(e, number)
    
21.       @d = get_d(e)
    
22.       @e = e
    
23.       return number ** @d % @n
    
24.     end
    
25.    
    
26.     def unpack(e, number)
    
27.       if @e != e
    
28.          @d = get_d(e)
    
29.          @e = e
    
30.        end
    
31.       return number ** e % @n
    
32.     end
    
33.    
    
34.   end
    
35. end

复制代码

好吧,整数简单的 RSA 算法. 要求苛刻. 需要 q p 是质数,  e 要小于 t =(p- 1) * (q - 1). 先判断正负,取绝对值来计算.

雷欧纳德

如果是临时数据那直接用内存地址吧

紫苏

回复 贝伦卡 的帖子

稀疏散列结构应该可以用链表实现（Google 的那个 sparsehash 似乎就是？），但确实有空时折衷的问题 o.o

IamI

一个糟糕的想法，一段糟糕的代码= =b 二进制变换摘要然后叠加

1. # f:Defined Fixnum
   
2. # return : 0b Array
   
3. def turn(f)
   
4.   #s = []
   
5.   #begin
   
6.   #  s.push f % 2
   
7.   #  f = f / 2
   
8.   #end until f == 0
   
9.   #return s
   
10.   s = sprintf("%#b", f)
    
11.   a = s.scan(/./)
    
12.   a.delete_at 0
    
13.   a.delete_at 0
    
14.   b = []
    
15.   for i in a
    
16.     b.push(i.to_i)
    
17.   end
    
18.   return b
    
19. end
    
20. # s:defined Array
    
21. # return: zipped Fixnum
    
22. def zip(s)
    
23.   num = 0
    
24.   begin
    
25.       count = 1
    
26.       l = s.pop
    
27.       n = 0
    
28.       loop do
    
29.         break if count == 5
    
30.         n = s.pop
    
31.         break if n == nil
    
32.         if l == n
    
33.           count += 1
    
34.         else
    
35.           s.push(n)
    
36.           break
    
37.         end
    
38.       end
    
39.       num += (l * 5 + count - 1)
    
40.       num *= 10
    
41.   end until s == []
    
42.   return num
    
43. end
    
44. 
    
45. x = 4001
    
46. y = 2007
    
47. hash = zip(turn(x)).to_s
    
48. hash2 = zip(turn(y)).to_s
    
49. puts (hash + “00” + hash2).to_i
    
50.   

复制代码

另外，如果遇到0b101010101010101代码会超过Fixnum限定。下次想办法把01算成一位……= =b

小幽的马甲

"是按照数的位数来位移么……粗略一想，位移量是变量的话，似乎难免碰撞吧？固定量 X 的位移可以保证高 X 位独立于低 X 位，而变量位移则无法保证"
那如果把位数记录下来呢？保留8位记录位数就能保证2^256范围内不会碰撞了。如果还不过那再用8位记录位数的位数，那么可以保证2^(2^256)位不会碰撞了= =这样可以无限逼近无限

紫苏

回复 小幽的马甲 的帖子

没理解为什么要保留位来记录位数？