search

crate-py / rpds

Python bindings to the Rust rpds crate for persistent data structures
https://rpds.readthedocs.io/
MIT License
39 stars 12 forks source link

Implement __hash__ #50

Closed Julian closed 2 months ago

Julian commented 9 months ago
qerub commented 6 months ago

I'm not familiar enough with Rust to provide a PR that implements __hash__ for List but I would really appreciate such an addition. :)

Julian commented 6 months ago

Hey.

I think List should be relatively straightforward and basically match what I did for Queue (as opposed to the other 2 which require a different approach) -- but I haven't made time to do it, and especially so now that there's some work to figure out how to upgrade to PyO3 0.21...

But I can try to put it on the TODO list.

Can I ask out of curiosity what you're using rpds.py for that led you to need it?

qerub commented 6 months ago

Sure! I want an immutable list implementation in an application I'm developing and since rpds-py is already a (currently transitive) dependency via jsonschema it's appealing to use instead of adding yet another dependency like pyrsistent.

FlickerSoul commented 3 months ago

I can open a PR implementing __hash__ for list!

I'm not sure how to implement hash for the HashTrieMap and HashTrieSet since sequence matters when building a hash from a hasher. The simplest on top of my mind was sort the keys (items) in the map (set) based on their hashes. For example, for map, it could be 

hashes = []
FOR key, value IN map:
    hash_tuple = (python_hash(key), python_hash(value))

SORT hashes

FOR k_hash, v_hash IN hashes:
    hasher.write_i128( (k_hash << 64) | v_hash )

RETURN hasher.finish()

I'm not a cryptography expert so I'm not sure if this is a good idea. :(

FlickerSoul commented 3 months ago

I just wrote something for __hash__ here. I'm curious what you think :)

Thanks!

Julian commented 3 months ago

Hey! Help here would also be great.

For the unordered collections I think the best idea so far is we port the CPython hashing code which is used for frozenset -- it can be found here: https://github.com/python/cpython/blob/d69529d31ccd1510843cfac1ab53bb8cb027541f/Objects/setobject.c#L715

FlickerSoul commented 3 months ago

Thanks for the direction! I'll take a look :)

Julian commented 2 months ago

Thanks to @FlickerSoul this should be done. Please give it a try!