diff options
| -rw-r--r-- | library/alloc/src/collections/btree/map.rs | 1 | ||||
| -rw-r--r-- | library/alloc/tests/btree_set_hash.rs | 14 |
2 files changed, 13 insertions, 2 deletions
diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index 11b0ca4b421..d6032372168 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -1968,6 +1968,7 @@ impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> { #[stable(feature = "rust1", since = "1.0.0")] impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> { fn hash<H: Hasher>(&self, state: &mut H) { + self.len().hash(state); for elt in self { elt.hash(state); } diff --git a/library/alloc/tests/btree_set_hash.rs b/library/alloc/tests/btree_set_hash.rs index e06a95ded94..ab275ac4353 100644 --- a/library/alloc/tests/btree_set_hash.rs +++ b/library/alloc/tests/btree_set_hash.rs @@ -1,9 +1,8 @@ +use crate::hash; use std::collections::BTreeSet; #[test] fn test_hash() { - use crate::hash; - let mut x = BTreeSet::new(); let mut y = BTreeSet::new(); @@ -17,3 +16,14 @@ fn test_hash() { assert_eq!(hash(&x), hash(&y)); } + +#[test] +fn test_prefix_free() { + let x = BTreeSet::from([1, 2, 3]); + let y = BTreeSet::<i32>::new(); + + // If hashed by iteration alone, `(x, y)` and `(y, x)` would visit the same + // order of elements, resulting in the same hash. But now that we also hash + // the length, they get distinct sequences of hashed data. + assert_ne!(hash(&(&x, &y)), hash(&(&y, &x))); +} |