From f6c234fb45327c3e96b4fe8902dd7416e0f61dde Mon Sep 17 00:00:00 2001 From: Steve Klabnik Date: Sat, 28 Mar 2015 16:06:37 -0400 Subject: Document properties for Eq + Hash Fixes #23320 --- src/libstd/collections/hash/map.rs | 9 ++++++++- src/libstd/collections/hash/set.rs | 11 ++++++++++- 2 files changed, 18 insertions(+), 2 deletions(-) (limited to 'src/libstd') diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs index 91225891338..30ccb05cdf0 100644 --- a/src/libstd/collections/hash/map.rs +++ b/src/libstd/collections/hash/map.rs @@ -214,7 +214,14 @@ fn test_resize_policy() { /// overridden with one of the constructors. /// /// It is required that the keys implement the `Eq` and `Hash` traits, although -/// this can frequently be achieved by using `#[derive(Eq, Hash)]`. +/// this can frequently be achieved by using `#[derive(Eq, Hash)]`. If you +/// implement these yourself, it is important that the following property holds: +/// +/// ```text +/// k1 == k2 -> hash(k1) == hash(k2) +/// ``` +/// +/// In other words, if two keys are equal, their hashes must be equal. /// /// It is a logic error for a key to be modified in such a way that the key's /// hash, as determined by the `Hash` trait, or its equality, as determined by diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs index 0933b4f662a..9bb969c4042 100644 --- a/src/libstd/collections/hash/set.rs +++ b/src/libstd/collections/hash/set.rs @@ -36,7 +36,16 @@ use super::state::HashState; /// An implementation of a hash set using the underlying representation of a /// HashMap where the value is (). As with the `HashMap` type, a `HashSet` -/// requires that the elements implement the `Eq` and `Hash` traits. +/// requires that the elements implement the `Eq` and `Hash` traits. This can +/// frequently be achieved by using `#[derive(Eq, Hash)]`. If you implement +/// these yourself, it is important that the following property holds: +/// +/// ```text +/// k1 == k2 -> hash(k1) == hash(k2) +/// ``` +/// +/// In other words, if two keys are equal, their hashes must be equal. +/// /// /// It is a logic error for an item to be modified in such a way that the /// item's hash, as determined by the `Hash` trait, or its equality, as -- cgit 1.4.1-3-g733a5