如何构建棋类程序hash表(200分)

B

blacwet

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-11

• #1

一般的文章都说构建hash表的方法是：产生一个随机board然后和已有的board异或产生哈西键值。
但是这样产生的结果并不是hash的呀，就是说以前的board有x种情况，
产生的哈西键值还是x种情况。并没有压缩。再者，压缩后必然涉及冲突问题，
如何解决呢？产生了hash表以后又如何进行查找呢？希望能给于详细的解答，
最好有示例代码：）

 

吴

吴剑明

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-11

• #2

THashedStringlist

 

B

blacwet

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-11

• #3

我说的不是用什么类实现，而是构造和查找方法

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-15

• #4

看看这样做是否可行：将XOR之后的棋盘看成一个内存中的文件，对其进行CRC演算，得到一个16位
或32位的CRC校验码，用它即可作为棋盘的HASH值。
>>冲突如何解决
对于棋类游戏，可以通过很多种方法减少冲突的发生——
1.在Hsah值之外，将棋盘上双方的棋子数量也保存起来，作为比较依据（很实用哟）
2.将棋盘分为几个对称的区域，对每个区域都计算Hash值
3.将Hash的值域扩大到64Bit——可以保证几亿种盘面情况中，出现冲突的概率小于1/10^n(n=3..6)
这意味着——现在有好几亿个棋局，你可以对其采用数千种Hash算法（64bit）而不会发生一个冲突！

 

B

blacwet

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-17

• #5

因为我是看到很多文章都说采用XOR的方法，但是，如果XOR之后还要采用其它方法的话，
那为什么不直接采用该方法呢？因为实际上得到压缩的hash键值的方法是很多的。另外，
只要存在冲突的概率，就意味着程序思考会出错。再者，更重要的是，如何查找hash表？

 

张

张剑波

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-10-03

• #6

多人接受答案了。