Hash collisions and SymEngine

Skip to first unread message

saleh jamali

May 16, 2023, 4:09:16 PM5/16/23
to symengine
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

May 16, 2023, 4:21:14 PM5/16/23
to syme...@googlegroups.com
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?


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.
Reply all
Reply to author
0 new messages