search

aldanor / chappie

Search algorithms in Rust
Apache License 2.0
1 stars 1 forks source link

hashing once keeping unique state ID in the hash set to avoid hash collision #2

Closed jpastuszek closed 9 years ago

jpastuszek commented 9 years ago

I have realised that we actually need to keep values in HashSet. This values are needed to avoid hash collisions. They are compared (Eq) when more than one value has the same hash to make 100% false positive free decision. If we wanted to avoid keeping States (or they unique IDs) in Visited we would need to use Bloom or Cuckoo filter which does not need to keep value but then we would risk skipping some parts of the graph due to false positives.

So here I added another trait that State needs to implement to get it's unique ID which by default is implemented for case when it is the state itself (assuming it is also Hash + Eq + Clone (so it can be stored in the HashSet)). In more "real life" spaces we may have better (smaller) unique state IDs then the state itself.

BTW: try the benchmark :D

aldanor commented 9 years ago

Double hashing fixed in 78333c5c49e0359e5378883fc96c4764e7540858, hashers are unstable so we may want to proceed with some alternative implementation...