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

紫苏

继 chaochao 之后（http://rpg.blue/forum.php?mod=viewthread&tid=140141）的第二波蛋疼，欢迎各位踊跃参加，参与就有奖励！这次的主题是散列函数！

散列结构是一种十分高效的数据结构，在设计良好的散列函数驱动下，散列结构的各种基本操作都只需要平摊的常量时间内完成。散列元素由其唯一的散列码标识，散列码相同的元素被视为相等元素，不可同时存在于结构中。我们这次的任务就是设计一个计算散列码的散列函数

给你一个包含了两个整数域 x、y 的 Point 结构（设 Point 结构集合为 P），找到一个计算完美散列码（Z 中的一个元素）的散列函数 F:P->Z，使得 F(a) = F(b) 当且仅当 a.x = b.x AND a.y = b.y
所谓完美，是指永远不会出现散列碰撞，即出现两个不同的点（x 不相等或 y 不相等）却生成了相同散列码的情况。该散列函数必须一次性生成无冲突散列码
（注：这里的 = 关系是整数集合 Z 中的 =，相等关系）

Ruby 程序框架：

1. 
   
2. class S
   
3.   def initialize(a, b)
   
4.     @a, @b = a, b
   
5.   end
   
6.   def eql?(obj)
   
7.     return self.hash == obj.hash
   
8.   end
   
9.   def hash
   
10.     #...
    
11.   end
    
12. end
    

复制代码

这里的 hash 方法就是 Point 类的散列函数（方法），我们的目的就是要实现 hash 方法，使得 x 和 y 都相同的 Point 对象在 Ruby 的散列表中被视为相同的键，而不会重复生成元素
演示——
覆盖继承自 Object 的 hash 方法前：

1. 
   
2. ret = {}
   
3. ret[Point.new(1, 0)] = 1
   
4. ret[Point.new(2, 3)] = 2
   
5. ret[Point.new(1, 0)] = 3
   
6. ret[Point.new(1, 0)] = 4
   
7. p ret[Point.new(1, 0)]  # => nil
   
8. p ret                   # => 四个点的对象都存在与散列表中，但其实第1、3、4个点是相同的

复制代码

完美实现 hash 方法后：

1. 
   
2. ret = {}
   
3. ret[Point.new(1, 0)] = 1
   
4. ret[Point.new(2, 3)] = 2
   
5. ret[Point.new(1, 0)] = 3
   
6. ret[Point.new(1, 0)] = 4
   
7. p ret[Point.new(1, 0)]  # => 4
   
8. p ret                   # => 只包含两个不同的点 (1,0) 和 (2, 3)

复制代码

为了方便在 Ruby 中测试，你可以做如下假设：x 和 y 的值在 15 位整数的表示范围内，即 -16384 到 +16383，这样生成的散列码就是一个 30 位整数，能够被 Fixnum 表示

要求：给出能说明算法的伪代码，或者详细代码
语言不限，重在参与，欢迎提问和讨论

忍也忍

完全看不懂的表示很有压力。

八云紫

就是说给定一组 (x, y) ，在 x y 都相等的情况下，值才相等，对么？？

小幽的马甲

一向是以模一个大质数为Hash值，碰撞时做成一个链表
完美哈希还真没想过……

八云紫

1. #include "md5.h"
   
2. #include <iostream>
   
3. 
   
4. using namespace std;
   
5. 
   
6. void PrintMD5(const char* &str, MD5& md5) {
   
7.   cout << "MD5(\"" << str << "\") = " << md5.toString() << endl;
   
8. }
   
9. 
   
10. int main(int argc, char* argv[]) {
    
11. 
    
12.         MD5 md5;
    
13.         md5.update("12");
    
14.         PrintMD5("", md5);
    
15. 
    
16.         md5.update("21");
    
17.         PrintMD5("21", md5);
    
18. 
    
19.         return 0;
    
20.        
    
21. }

复制代码

按照 MD5 的定义应该可以，只是可能结果的长度太长了点~~~

-------------------------

Wndows 下无编译器，测试不能，Linux 下不会输出，悲剧~~~~

DeathKing

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

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

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

雷欧纳德

实际只要重载Point的等于、小于比较符就能直接用Point对象做key值完成了吧

小幽的马甲

1. hash = (@a << 14) + @b
   
2. return hash

复制代码

= =这样行么……
-------------------------------------------
忘记有符号了……

1. 
   
2.     aa = @a >= 0 ? 1 : 0
   
3.     bb = @b >= 0 ? 1 : 0
   
4.     @a = (aa << 14) | @a.abs
   
5.     @b = @b.abs
   
6.     hash = (@a << 14) + @b
   
7.     hash = - hash if aa ^ bb == 1
   
8.     return hash
   

复制代码

= =

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一样的算法就行了。

其他思路整理中。

逸豫

恩……最大15位么……
那就用一个100000000000000进制的数……
恩……第一位位放x，第二位位放y,转成10进制
什么效率什么的不关我事……

晕……原来是2进制15位……果然我做题不读题的优良传统依然保持么- -|||