Hash collisions and SymEngine

[saleh jamali]

Hi there,

I hope you guys are having a wonderful day.

I am fairly new to SymEngine and I was wondering what should be expected on a hash collision of the derived classes of SymEngine::Basic?

I am working on a project that uses SymEngine to handle very long expressions and do partial CSE on them. My project uses the value returned by Basic::hash() as unique keys to map various attributes to symbols and expressions.

The terms in the expressions and the symbols themselves could easily hit 200M unique required hashes. 

I noticed the main hashing function in `basic-inl.h` and the 64-bit data type of the hash.

Since a simple sequential counter would not work with the architecture of SymEngine (symbol("a") should have the same hash as another symbol("a)), I guess I have to modify the hash type to something like `long long` (?).

But I am not familiar with the logic behind the hashing function `hash_combine_impl<>()`. Link

Could you please give me some advice on how to approach this issue? Am I missing something obvious? 

[Isuru Fernando]

Hi Saleh,

Welcome to the symengine mailing list.

Hash collisions are unavoidable and modifying the hash type to have more bits will not help

in the long run.

In SymEngine, for std::unordered_map, we use both the Hash and KeyEqual template types

which handle hash collisions. Would that work for you?

Isuru

--
You received this message because you are subscribed to the Google Groups "symengine" group.
To unsubscribe from this group and stop receiving emails from it, send an email to symengine+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/symengine/1c173938-d433-47a5-97df-18b8dc9a5c62n%40googlegroups.com.