Skip to content

impl Hash for Value#1127

Merged
dtolnay merged 1 commit intoserde-rs:masterfrom
edwardycl:hash
Jun 25, 2024
Merged

impl Hash for Value#1127
dtolnay merged 1 commit intoserde-rs:masterfrom
edwardycl:hash

Conversation

@edwardycl
Copy link
Copy Markdown
Contributor

IndexMap is the only type that is used within Value that does not implement Hash, and it is by design: indexmap-rs/indexmap#288 (comment)

If "preserve_order" feature is not set, Value::Object uses BTreeMap instead of IndexMap so it is possible to auto-impl Hash for Value.

Copy link
Copy Markdown
Member

@dtolnay dtolnay left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Cargo features are required to be additive, so enabling a feature cannot result in an impl being removed.

@edwardycl
Copy link
Copy Markdown
Contributor Author

edwardycl commented Apr 25, 2024

Now that I think about it, since the type of key is fixed to String, IndexMap can also be hashed by sorting its key-value in a consistent order. It doesn't break the Eq-Hash relationship, and we can implement Hash regardless of the "preserve_order" feature. What do you think?

@edwardycl edwardycl requested a review from dtolnay May 13, 2024 04:12
@edwardycl edwardycl changed the title impl Hash for Value when "preserve_order" feature is not set impl Hash for Value May 23, 2024
Copy link
Copy Markdown
Member

@dtolnay dtolnay left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks!

For the cfg(feature = "preserve_order") case, maybe a better performing implementation would be to hash each entry individually and xor them together. This would make the hash insensitive to order.

use std::hash::{BuildHasher, RandomState};
use std::sync::OnceLock;

static RANDOM_STATE: OnceLock<RandomState> = OnceLock::new();
let random_state = RANDOM_STATE.get_or_init(RandomState::new);
self.map
    .iter()
    .map(|entry| random_state.hash_one(entry))
    .fold(0, |xor, next| xor ^ next)
    .hash(state);

I would be interested to see a benchmark comparing this approach.

@dtolnay dtolnay merged commit eb0330a into serde-rs:master Jun 25, 2024
takumi-earth pushed a commit to earthlings-dev/json that referenced this pull request Jan 27, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Development

Successfully merging this pull request may close these issues.

2 participants