哈希去重算法说一下算法思想,最好有伪代码

浓情巧克力FZ 1年前 已收到1个回答 举报

sbiwwk 幼苗

共回答了17个问题采纳率:82.4% 举报

你说的是在广搜中的去重吧,那就是弄一个哈希表,把每步搜出来的结果hash一下,然后存在hash表中,如果发现要存的地方已经有了,如果相同,就不存,不同,就用链表法把他们链起来.
具体不好表达,或是说我表达能力有限,举个简单例子.
我有几个数,{1,2,3,4,5,6,7,8,9,10,1,12,13}
定义一个hash函数 f(x) = x (如果x范围很小,可以直接这么弄,这样不会引起冲突,否则需要弄取模之类的hash函数了,具体你还是要去看看书之类的)
那么定义个hash表
hash=array[1..n]of boolean , n为最大范围
那么每次加入的时候直接判断hash[x]是不是真就可以了,是真的话,就是重了
否则,记录hash[x]为真

1年前 追问

1

浓情巧克力FZ 举报

感觉用哈希去重效率好像有点低,请问还有什么算法专门用来去重的?

举报 sbiwwk

hash可以说是效率最高的集合处理方式了,去重一般首选他,一般来说,一个好的hash函数的去重操作复杂度是常数级的. 其他去重方式也有,比较常用的还有 康托展开
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 4.886 s. - webmaster@yulucn.com