3 ms·
What are the immutable hash maps based on? How do you use functions or other maps as keys in them?
by JonChesterfield 3y ago
What are the immutable hash maps based on? How do you use functions or other maps as keys in them?
- mattparas 3y agoThey're using hash array mapped tries. I don't have my own personal implementation, I have been using https://github.com/bodil/im-rs https://github.com/bodil/im-rs until I can get around to making my own implementation (not that I really need to, but it would be a fun exercise). Functions generate a hash based on a unique id generated for the function, plus the hash of any captured variables, and a hash of the pointer address to the function). That is off the top of my head though so I could be missing some details. Hashing maps is tricky! With a sufficiently deep hash map you can run into problems since that invokes an equality check as well - at least how I handle it, is that you just attempt to naively hash the keys and values of the hash map, to create a hash code for that object. If the equality check ends up with a sufficiently large depth, eq returns false so we don't stack overflow.