1 use crate::raw
::{Bucket, RawDrain, RawIntoIter, RawIter, RawTable}
;
2 use crate::CollectionAllocErr
;
3 use core
::borrow
::Borrow
;
4 use core
::fmt
::{self, Debug}
;
5 use core
::hash
::{BuildHasher, Hash, Hasher}
;
6 use core
::iter
::{FromIterator, FusedIterator}
;
7 use core
::marker
::PhantomData
;
11 pub use crate::fx
::FxHashBuilder
as DefaultHashBuilder
;
13 /// A hash map implemented with quadratic probing and SIMD lookup.
15 /// The default hashing algorithm is currently `fx`, though this is
16 /// subject to change at any point in the future. This hash function is very
17 /// fast for all types of keys, but this algorithm will typically *not* protect
18 /// against attacks such as HashDoS.
20 /// The hashing algorithm can be replaced on a per-`HashMap` basis using the
21 /// [`default`], [`with_hasher`], and [`with_capacity_and_hasher`] methods. Many
22 /// alternative algorithms are available on crates.io, such as the [`fnv`] crate.
24 /// It is required that the keys implement the [`Eq`] and [`Hash`] traits, although
25 /// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
26 /// If you implement these yourself, it is important that the following
30 /// k1 == k2 -> hash(k1) == hash(k2)
33 /// In other words, if two keys are equal, their hashes must be equal.
35 /// It is a logic error for a key to be modified in such a way that the key's
36 /// hash, as determined by the [`Hash`] trait, or its equality, as determined by
37 /// the [`Eq`] trait, changes while it is in the map. This is normally only
38 /// possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
40 /// It is also a logic error for the [`Hash`] implementation of a key to panic.
41 /// This is generally only possible if the trait is implemented manually. If a
42 /// panic does occur then the contents of the `HashMap` may become corrupted and
43 /// some items may be dropped from the table.
48 /// use hashbrown::HashMap;
50 /// // Type inference lets us omit an explicit type signature (which
51 /// // would be `HashMap<String, String>` in this example).
52 /// let mut book_reviews = HashMap::new();
54 /// // Review some books.
55 /// book_reviews.insert(
56 /// "Adventures of Huckleberry Finn".to_string(),
57 /// "My favorite book.".to_string(),
59 /// book_reviews.insert(
60 /// "Grimms' Fairy Tales".to_string(),
61 /// "Masterpiece.".to_string(),
63 /// book_reviews.insert(
64 /// "Pride and Prejudice".to_string(),
65 /// "Very enjoyable.".to_string(),
67 /// book_reviews.insert(
68 /// "The Adventures of Sherlock Holmes".to_string(),
69 /// "Eye lyked it alot.".to_string(),
72 /// // Check for a specific one.
73 /// // When collections store owned values (String), they can still be
74 /// // queried using references (&str).
75 /// if !book_reviews.contains_key("Les Misérables") {
76 /// println!("We've got {} reviews, but Les Misérables ain't one.",
77 /// book_reviews.len());
80 /// // oops, this review has a lot of spelling mistakes, let's delete it.
81 /// book_reviews.remove("The Adventures of Sherlock Holmes");
83 /// // Look up the values associated with some keys.
84 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
85 /// for &book in &to_find {
86 /// match book_reviews.get(book) {
87 /// Some(review) => println!("{}: {}", book, review),
88 /// None => println!("{} is unreviewed.", book)
92 /// // Look up the value for a key (will panic if the key is not found).
93 /// println!("Review for Jane: {}", book_reviews["Pride and Prejudice"]);
95 /// // Iterate over everything.
96 /// for (book, review) in &book_reviews {
97 /// println!("{}: \"{}\"", book, review);
101 /// `HashMap` also implements an [`Entry API`](#method.entry), which allows
102 /// for more complex methods of getting, setting, updating and removing keys and
106 /// use hashbrown::HashMap;
108 /// // type inference lets us omit an explicit type signature (which
109 /// // would be `HashMap<&str, u8>` in this example).
110 /// let mut player_stats = HashMap::new();
112 /// fn random_stat_buff() -> u8 {
113 /// // could actually return some random value here - let's just return
114 /// // some fixed value for now
118 /// // insert a key only if it doesn't already exist
119 /// player_stats.entry("health").or_insert(100);
121 /// // insert a key using a function that provides a new value only if it
122 /// // doesn't already exist
123 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
125 /// // update a key, guarding against the key possibly not being set
126 /// let stat = player_stats.entry("attack").or_insert(100);
127 /// *stat += random_stat_buff();
130 /// The easiest way to use `HashMap` with a custom key type is to derive [`Eq`] and [`Hash`].
131 /// We must also derive [`PartialEq`].
133 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
134 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
135 /// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html
136 /// [`RefCell`]: https://doc.rust-lang.org/std/cell/struct.RefCell.html
137 /// [`Cell`]: https://doc.rust-lang.org/std/cell/struct.Cell.html
138 /// [`default`]: #method.default
139 /// [`with_hasher`]: #method.with_hasher
140 /// [`with_capacity_and_hasher`]: #method.with_capacity_and_hasher
141 /// [`fnv`]: https://crates.io/crates/fnv
144 /// use hashbrown::HashMap;
146 /// #[derive(Hash, Eq, PartialEq, Debug)]
153 /// /// Creates a new Viking.
154 /// fn new(name: &str, country: &str) -> Viking {
155 /// Viking { name: name.to_string(), country: country.to_string() }
159 /// // Use a HashMap to store the vikings' health points.
160 /// let mut vikings = HashMap::new();
162 /// vikings.insert(Viking::new("Einar", "Norway"), 25);
163 /// vikings.insert(Viking::new("Olaf", "Denmark"), 24);
164 /// vikings.insert(Viking::new("Harald", "Iceland"), 12);
166 /// // Use derived implementation to print the status of the vikings.
167 /// for (viking, health) in &vikings {
168 /// println!("{:?} has {} hp", viking, health);
172 /// A `HashMap` with fixed list of elements can be initialized from an array:
175 /// use hashbrown::HashMap;
178 /// let timber_resources: HashMap<&str, i32> =
179 /// [("Norway", 100),
182 /// .iter().cloned().collect();
183 /// // use the values stored in map
188 pub struct HashMap
<K
, V
, S
= DefaultHashBuilder
> {
189 pub(crate) hash_builder
: S
,
190 pub(crate) table
: RawTable
<(K
, V
)>,
194 pub(crate) fn make_hash
<K
: Hash
+ ?Sized
>(hash_builder
: &impl BuildHasher
, val
: &K
) -> u64 {
195 let mut state
= hash_builder
.build_hasher();
196 val
.hash(&mut state
);
200 impl<K
, V
> HashMap
<K
, V
, DefaultHashBuilder
> {
201 /// Creates an empty `HashMap`.
203 /// The hash map is initially created with a capacity of 0, so it will not allocate until it
204 /// is first inserted into.
209 /// use hashbrown::HashMap;
210 /// let mut map: HashMap<&str, i32> = HashMap::new();
213 pub fn new() -> Self {
217 /// Creates an empty `HashMap` with the specified capacity.
219 /// The hash map will be able to hold at least `capacity` elements without
220 /// reallocating. If `capacity` is 0, the hash map will not allocate.
225 /// use hashbrown::HashMap;
226 /// let mut map: HashMap<&str, i32> = HashMap::with_capacity(10);
229 pub fn with_capacity(capacity
: usize) -> Self {
230 Self::with_capacity_and_hasher(capacity
, DefaultHashBuilder
::default())
234 impl<K
, V
, S
> HashMap
<K
, V
, S
> {
235 /// Creates an empty `HashMap` which will use the given hash builder to hash
238 /// The created map has the default initial capacity.
240 /// Warning: `hash_builder` is normally randomly generated, and
241 /// is designed to allow HashMaps to be resistant to attacks that
242 /// cause many collisions and very poor performance. Setting it
243 /// manually using this function can expose a DoS attack vector.
248 /// use hashbrown::HashMap;
249 /// use hashbrown::hash_map::DefaultHashBuilder;
251 /// let s = DefaultHashBuilder::default();
252 /// let mut map = HashMap::with_hasher(s);
253 /// map.insert(1, 2);
256 pub fn with_hasher(hash_builder
: S
) -> Self {
259 table
: RawTable
::new(),
263 /// Creates an empty `HashMap` with the specified capacity, using `hash_builder`
264 /// to hash the keys.
266 /// The hash map will be able to hold at least `capacity` elements without
267 /// reallocating. If `capacity` is 0, the hash map will not allocate.
269 /// Warning: `hash_builder` is normally randomly generated, and
270 /// is designed to allow HashMaps to be resistant to attacks that
271 /// cause many collisions and very poor performance. Setting it
272 /// manually using this function can expose a DoS attack vector.
277 /// use hashbrown::HashMap;
278 /// use hashbrown::hash_map::DefaultHashBuilder;
280 /// let s = DefaultHashBuilder::default();
281 /// let mut map = HashMap::with_capacity_and_hasher(10, s);
282 /// map.insert(1, 2);
285 pub fn with_capacity_and_hasher(capacity
: usize, hash_builder
: S
) -> Self {
288 table
: RawTable
::with_capacity(capacity
),
292 /// Returns a reference to the map's [`BuildHasher`].
294 /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
299 /// use hashbrown::HashMap;
300 /// use hashbrown::hash_map::DefaultHashBuilder;
302 /// let hasher = DefaultHashBuilder::default();
303 /// let map: HashMap<i32, i32> = HashMap::with_hasher(hasher);
304 /// let hasher: &DefaultHashBuilder = map.hasher();
307 pub fn hasher(&self) -> &S
{
311 /// Returns the number of elements the map can hold without reallocating.
313 /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
314 /// more, but is guaranteed to be able to hold at least this many.
319 /// use hashbrown::HashMap;
320 /// let map: HashMap<i32, i32> = HashMap::with_capacity(100);
321 /// assert!(map.capacity() >= 100);
324 pub fn capacity(&self) -> usize {
325 self.table
.capacity()
328 /// An iterator visiting all keys in arbitrary order.
329 /// The iterator element type is `&'a K`.
334 /// use hashbrown::HashMap;
336 /// let mut map = HashMap::new();
337 /// map.insert("a", 1);
338 /// map.insert("b", 2);
339 /// map.insert("c", 3);
341 /// for key in map.keys() {
342 /// println!("{}", key);
346 pub fn keys(&self) -> Keys
<'_
, K
, V
> {
347 Keys { inner: self.iter() }
350 /// An iterator visiting all values in arbitrary order.
351 /// The iterator element type is `&'a V`.
356 /// use hashbrown::HashMap;
358 /// let mut map = HashMap::new();
359 /// map.insert("a", 1);
360 /// map.insert("b", 2);
361 /// map.insert("c", 3);
363 /// for val in map.values() {
364 /// println!("{}", val);
368 pub fn values(&self) -> Values
<'_
, K
, V
> {
369 Values { inner: self.iter() }
372 /// An iterator visiting all values mutably in arbitrary order.
373 /// The iterator element type is `&'a mut V`.
378 /// use hashbrown::HashMap;
380 /// let mut map = HashMap::new();
382 /// map.insert("a", 1);
383 /// map.insert("b", 2);
384 /// map.insert("c", 3);
386 /// for val in map.values_mut() {
387 /// *val = *val + 10;
390 /// for val in map.values() {
391 /// println!("{}", val);
395 pub fn values_mut(&mut self) -> ValuesMut
<'_
, K
, V
> {
397 inner
: self.iter_mut(),
401 /// An iterator visiting all key-value pairs in arbitrary order.
402 /// The iterator element type is `(&'a K, &'a V)`.
407 /// use hashbrown::HashMap;
409 /// let mut map = HashMap::new();
410 /// map.insert("a", 1);
411 /// map.insert("b", 2);
412 /// map.insert("c", 3);
414 /// for (key, val) in map.iter() {
415 /// println!("key: {} val: {}", key, val);
419 pub fn iter(&self) -> Iter
<'_
, K
, V
> {
420 // Here we tie the lifetime of self to the iter.
423 inner
: self.table
.iter(),
429 /// An iterator visiting all key-value pairs in arbitrary order,
430 /// with mutable references to the values.
431 /// The iterator element type is `(&'a K, &'a mut V)`.
436 /// use hashbrown::HashMap;
438 /// let mut map = HashMap::new();
439 /// map.insert("a", 1);
440 /// map.insert("b", 2);
441 /// map.insert("c", 3);
443 /// // Update all values
444 /// for (_, val) in map.iter_mut() {
448 /// for (key, val) in &map {
449 /// println!("key: {} val: {}", key, val);
453 pub fn iter_mut(&mut self) -> IterMut
<'_
, K
, V
> {
454 // Here we tie the lifetime of self to the iter.
457 inner
: self.table
.iter(),
465 fn raw_capacity(&self) -> usize {
469 /// Returns the number of elements in the map.
474 /// use hashbrown::HashMap;
476 /// let mut a = HashMap::new();
477 /// assert_eq!(a.len(), 0);
478 /// a.insert(1, "a");
479 /// assert_eq!(a.len(), 1);
482 pub fn len(&self) -> usize {
486 /// Returns `true` if the map contains no elements.
491 /// use hashbrown::HashMap;
493 /// let mut a = HashMap::new();
494 /// assert!(a.is_empty());
495 /// a.insert(1, "a");
496 /// assert!(!a.is_empty());
499 pub fn is_empty(&self) -> bool
{
503 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
504 /// allocated memory for reuse.
509 /// use hashbrown::HashMap;
511 /// let mut a = HashMap::new();
512 /// a.insert(1, "a");
513 /// a.insert(2, "b");
515 /// for (k, v) in a.drain().take(1) {
516 /// assert!(k == 1 || k == 2);
517 /// assert!(v == "a" || v == "b");
520 /// assert!(a.is_empty());
523 pub fn drain(&mut self) -> Drain
<'_
, K
, V
> {
524 // Here we tie the lifetime of self to the iter.
527 inner
: self.table
.drain(),
532 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
538 /// use hashbrown::HashMap;
540 /// let mut a = HashMap::new();
541 /// a.insert(1, "a");
543 /// assert!(a.is_empty());
546 pub fn clear(&mut self) {
551 impl<K
, V
, S
> HashMap
<K
, V
, S
>
556 /// Reserves capacity for at least `additional` more elements to be inserted
557 /// in the `HashMap`. The collection may reserve more space to avoid
558 /// frequent reallocations.
562 /// Panics if the new allocation size overflows [`usize`].
564 /// [`usize`]: https://doc.rust-lang.org/std/primitive.usize.html
569 /// use hashbrown::HashMap;
570 /// let mut map: HashMap<&str, i32> = HashMap::new();
574 pub fn reserve(&mut self, additional
: usize) {
575 let hash_builder
= &self.hash_builder
;
577 .reserve(additional
, |x
| make_hash(hash_builder
, &x
.0));
580 /// Tries to reserve capacity for at least `additional` more elements to be inserted
581 /// in the given `HashMap<K,V>`. The collection may reserve more space to avoid
582 /// frequent reallocations.
586 /// If the capacity overflows, or the allocator reports a failure, then an error
592 /// use hashbrown::HashMap;
593 /// let mut map: HashMap<&str, isize> = HashMap::new();
594 /// map.try_reserve(10).expect("why is the test harness OOMing on 10 bytes?");
597 pub fn try_reserve(&mut self, additional
: usize) -> Result
<(), CollectionAllocErr
> {
598 let hash_builder
= &self.hash_builder
;
600 .try_reserve(additional
, |x
| make_hash(hash_builder
, &x
.0))
603 /// Shrinks the capacity of the map as much as possible. It will drop
604 /// down as much as possible while maintaining the internal rules
605 /// and possibly leaving some space in accordance with the resize policy.
610 /// use hashbrown::HashMap;
612 /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
613 /// map.insert(1, 2);
614 /// map.insert(3, 4);
615 /// assert!(map.capacity() >= 100);
616 /// map.shrink_to_fit();
617 /// assert!(map.capacity() >= 2);
620 pub fn shrink_to_fit(&mut self) {
621 let hash_builder
= &self.hash_builder
;
622 self.table
.shrink_to(0, |x
| make_hash(hash_builder
, &x
.0));
625 /// Shrinks the capacity of the map with a lower limit. It will drop
626 /// down no lower than the supplied limit while maintaining the internal rules
627 /// and possibly leaving some space in accordance with the resize policy.
629 /// This function does nothing if the current capacity is smaller than the
630 /// supplied minimum capacity.
635 /// use hashbrown::HashMap;
637 /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
638 /// map.insert(1, 2);
639 /// map.insert(3, 4);
640 /// assert!(map.capacity() >= 100);
641 /// map.shrink_to(10);
642 /// assert!(map.capacity() >= 10);
643 /// map.shrink_to(0);
644 /// assert!(map.capacity() >= 2);
645 /// map.shrink_to(10);
646 /// assert!(map.capacity() >= 2);
649 pub fn shrink_to(&mut self, min_capacity
: usize) {
650 let hash_builder
= &self.hash_builder
;
652 .shrink_to(min_capacity
, |x
| make_hash(hash_builder
, &x
.0));
655 /// Gets the given key's corresponding entry in the map for in-place manipulation.
660 /// use hashbrown::HashMap;
662 /// let mut letters = HashMap::new();
664 /// for ch in "a short treatise on fungi".chars() {
665 /// let counter = letters.entry(ch).or_insert(0);
669 /// assert_eq!(letters[&'s'], 2);
670 /// assert_eq!(letters[&'t'], 3);
671 /// assert_eq!(letters[&'u'], 1);
672 /// assert_eq!(letters.get(&'y'), None);
675 pub fn entry(&mut self, key
: K
) -> Entry
<'_
, K
, V
, S
> {
676 let hash
= make_hash(&self.hash_builder
, &key
);
677 if let Some(elem
) = self.table
.find(hash
, |q
| q
.0.eq(&key
)) {
678 Entry
::Occupied(OccupiedEntry
{
684 Entry
::Vacant(VacantEntry
{
692 /// Returns a reference to the value corresponding to the key.
694 /// The key may be any borrowed form of the map's key type, but
695 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
698 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
699 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
704 /// use hashbrown::HashMap;
706 /// let mut map = HashMap::new();
707 /// map.insert(1, "a");
708 /// assert_eq!(map.get(&1), Some(&"a"));
709 /// assert_eq!(map.get(&2), None);
712 pub fn get
<Q
: ?Sized
>(&self, k
: &Q
) -> Option
<&V
>
717 self.get_key_value(k
).map(|(_
, v
)| v
)
720 /// Returns the key-value pair corresponding to the supplied key.
722 /// The supplied key may be any borrowed form of the map's key type, but
723 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
726 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
727 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
732 /// use hashbrown::HashMap;
734 /// let mut map = HashMap::new();
735 /// map.insert(1, "a");
736 /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
737 /// assert_eq!(map.get_key_value(&2), None);
740 pub fn get_key_value
<Q
: ?Sized
>(&self, k
: &Q
) -> Option
<(&K
, &V
)>
745 let hash
= make_hash(&self.hash_builder
, k
);
747 .find(hash
, |x
| k
.eq(x
.0.borrow()))
749 let &(ref key
, ref value
) = item
.as_ref();
754 /// Returns `true` if the map contains a value for the specified key.
756 /// The key may be any borrowed form of the map's key type, but
757 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
760 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
761 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
766 /// use hashbrown::HashMap;
768 /// let mut map = HashMap::new();
769 /// map.insert(1, "a");
770 /// assert_eq!(map.contains_key(&1), true);
771 /// assert_eq!(map.contains_key(&2), false);
774 pub fn contains_key
<Q
: ?Sized
>(&self, k
: &Q
) -> bool
779 self.get(k
).is_some()
782 /// Returns a mutable reference to the value corresponding to the key.
784 /// The key may be any borrowed form of the map's key type, but
785 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
788 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
789 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
794 /// use hashbrown::HashMap;
796 /// let mut map = HashMap::new();
797 /// map.insert(1, "a");
798 /// if let Some(x) = map.get_mut(&1) {
801 /// assert_eq!(map[&1], "b");
804 pub fn get_mut
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<&mut V
>
809 let hash
= make_hash(&self.hash_builder
, k
);
811 .find(hash
, |x
| k
.eq(x
.0.borrow()))
812 .map(|item
| unsafe { &mut item.as_mut().1 }
)
815 /// Inserts a key-value pair into the map.
817 /// If the map did not have this key present, [`None`] is returned.
819 /// If the map did have this key present, the value is updated, and the old
820 /// value is returned. The key is not updated, though; this matters for
821 /// types that can be `==` without being identical. See the [module-level
822 /// documentation] for more.
824 /// [`None`]: https://doc.rust-lang.org/std/option/enum.Option.html#variant.None
825 /// [module-level documentation]: index.html#insert-and-complex-keys
830 /// use hashbrown::HashMap;
832 /// let mut map = HashMap::new();
833 /// assert_eq!(map.insert(37, "a"), None);
834 /// assert_eq!(map.is_empty(), false);
836 /// map.insert(37, "b");
837 /// assert_eq!(map.insert(37, "c"), Some("b"));
838 /// assert_eq!(map[&37], "c");
841 pub fn insert(&mut self, k
: K
, v
: V
) -> Option
<V
> {
843 let hash
= make_hash(&self.hash_builder
, &k
);
844 if let Some(item
) = self.table
.find(hash
, |x
| k
.eq(&x
.0)) {
845 Some(mem
::replace(&mut item
.as_mut().1, v
))
847 let hash_builder
= &self.hash_builder
;
849 .insert(hash
, (k
, v
), |x
| make_hash(hash_builder
, &x
.0));
855 /// Removes a key from the map, returning the value at the key if the key
856 /// was previously in the map.
858 /// The key may be any borrowed form of the map's key type, but
859 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
862 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
863 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
868 /// use hashbrown::HashMap;
870 /// let mut map = HashMap::new();
871 /// map.insert(1, "a");
872 /// assert_eq!(map.remove(&1), Some("a"));
873 /// assert_eq!(map.remove(&1), None);
876 pub fn remove
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<V
>
881 self.remove_entry(k
).map(|(_
, v
)| v
)
884 /// Removes a key from the map, returning the stored key and value if the
885 /// key was previously in the map.
887 /// The key may be any borrowed form of the map's key type, but
888 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
891 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
892 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
897 /// use hashbrown::HashMap;
900 /// let mut map = HashMap::new();
901 /// map.insert(1, "a");
902 /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
903 /// assert_eq!(map.remove(&1), None);
907 pub fn remove_entry
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<(K
, V
)>
913 let hash
= make_hash(&self.hash_builder
, &k
);
914 if let Some(item
) = self.table
.find(hash
, |x
| k
.eq(x
.0.borrow())) {
915 self.table
.erase_no_drop(&item
);
923 /// Retains only the elements specified by the predicate.
925 /// In other words, remove all pairs `(k, v)` such that `f(&k,&mut v)` returns `false`.
930 /// use hashbrown::HashMap;
932 /// let mut map: HashMap<i32, i32> = (0..8).map(|x|(x, x*10)).collect();
933 /// map.retain(|&k, _| k % 2 == 0);
934 /// assert_eq!(map.len(), 4);
936 pub fn retain
<F
>(&mut self, mut f
: F
)
938 F
: FnMut(&K
, &mut V
) -> bool
,
940 // Here we only use `iter` as a temporary, preventing use-after-free
942 for item
in self.table
.iter() {
943 let &mut (ref key
, ref mut value
) = item
.as_mut();
945 // Erase the element from the table first since drop might panic.
946 self.table
.erase_no_drop(&item
);
954 impl<K
, V
, S
> HashMap
<K
, V
, S
>
958 /// Creates a raw entry builder for the HashMap.
960 /// Raw entries provide the lowest level of control for searching and
961 /// manipulating a map. They must be manually initialized with a hash and
962 /// then manually searched. After this, insertions into a vacant entry
963 /// still require an owned key to be provided.
965 /// Raw entries are useful for such exotic situations as:
967 /// * Hash memoization
968 /// * Deferring the creation of an owned key until it is known to be required
969 /// * Using a search key that doesn't work with the Borrow trait
970 /// * Using custom comparison logic without newtype wrappers
972 /// Because raw entries provide much more low-level control, it's much easier
973 /// to put the HashMap into an inconsistent state which, while memory-safe,
974 /// will cause the map to produce seemingly random results. Higher-level and
975 /// more foolproof APIs like `entry` should be preferred when possible.
977 /// In particular, the hash used to initialized the raw entry must still be
978 /// consistent with the hash of the key that is ultimately stored in the entry.
979 /// This is because implementations of HashMap may need to recompute hashes
980 /// when resizing, at which point only the keys are available.
982 /// Raw entries give mutable access to the keys. This must not be used
983 /// to modify how the key would compare or hash, as the map will not re-evaluate
984 /// where the key should go, meaning the keys may become "lost" if their
985 /// location does not reflect their state. For instance, if you change a key
986 /// so that the map now contains keys which compare equal, search may start
987 /// acting erratically, with two keys randomly masking each other. Implementations
988 /// are free to assume this doesn't happen (within the limits of memory-safety).
990 pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut
<'_
, K
, V
, S
> {
991 RawEntryBuilderMut { map: self }
994 /// Creates a raw immutable entry builder for the HashMap.
996 /// Raw entries provide the lowest level of control for searching and
997 /// manipulating a map. They must be manually initialized with a hash and
998 /// then manually searched.
1000 /// This is useful for
1001 /// * Hash memoization
1002 /// * Using a search key that doesn't work with the Borrow trait
1003 /// * Using custom comparison logic without newtype wrappers
1005 /// Unless you are in such a situation, higher-level and more foolproof APIs like
1006 /// `get` should be preferred.
1008 /// Immutable raw entries have very limited use; you might instead want `raw_entry_mut`.
1010 pub fn raw_entry(&self) -> RawEntryBuilder
<'_
, K
, V
, S
> {
1011 RawEntryBuilder { map: self }
1015 impl<K
, V
, S
> PartialEq
for HashMap
<K
, V
, S
>
1021 fn eq(&self, other
: &Self) -> bool
{
1022 if self.len() != other
.len() {
1027 .all(|(key
, value
)| other
.get(key
).map_or(false, |v
| *value
== *v
))
1031 impl<K
, V
, S
> Eq
for HashMap
<K
, V
, S
>
1039 impl<K
, V
, S
> Debug
for HashMap
<K
, V
, S
>
1045 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1046 f
.debug_map().entries(self.iter()).finish()
1050 impl<K
, V
, S
> Default
for HashMap
<K
, V
, S
>
1052 S
: BuildHasher
+ Default
,
1054 /// Creates an empty `HashMap<K, V, S>`, with the `Default` value for the hasher.
1056 fn default() -> Self {
1057 Self::with_hasher(Default
::default())
1061 impl<K
, Q
: ?Sized
, V
, S
> Index
<&Q
> for HashMap
<K
, V
, S
>
1063 K
: Eq
+ Hash
+ Borrow
<Q
>,
1069 /// Returns a reference to the value corresponding to the supplied key.
1073 /// Panics if the key is not present in the `HashMap`.
1075 fn index(&self, key
: &Q
) -> &V
{
1076 self.get(key
).expect("no entry found for key")
1080 /// An iterator over the entries of a `HashMap`.
1082 /// This `struct` is created by the [`iter`] method on [`HashMap`]. See its
1083 /// documentation for more.
1085 /// [`iter`]: struct.HashMap.html#method.iter
1086 /// [`HashMap`]: struct.HashMap.html
1087 pub struct Iter
<'a
, K
, V
> {
1088 inner
: RawIter
<(K
, V
)>,
1089 marker
: PhantomData
<(&'a K
, &'a V
)>,
1092 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1093 impl<K
, V
> Clone
for Iter
<'_
, K
, V
> {
1095 fn clone(&self) -> Self {
1097 inner
: self.inner
.clone(),
1098 marker
: PhantomData
,
1103 impl<K
: Debug
, V
: Debug
> fmt
::Debug
for Iter
<'_
, K
, V
> {
1104 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1105 f
.debug_list().entries(self.clone()).finish()
1109 /// A mutable iterator over the entries of a `HashMap`.
1111 /// This `struct` is created by the [`iter_mut`] method on [`HashMap`]. See its
1112 /// documentation for more.
1114 /// [`iter_mut`]: struct.HashMap.html#method.iter_mut
1115 /// [`HashMap`]: struct.HashMap.html
1116 pub struct IterMut
<'a
, K
, V
> {
1117 inner
: RawIter
<(K
, V
)>,
1118 // To ensure invariance with respect to V
1119 marker
: PhantomData
<(&'a K
, &'a
mut V
)>,
1122 // We override the default Send impl which has K: Sync instead of K: Send. Both
1123 // are correct, but this one is more general since it allows keys which
1124 // implement Send but not Sync.
1125 unsafe impl<K
: Send
, V
: Send
> Send
for IterMut
<'_
, K
, V
> {}
1127 impl<K
, V
> IterMut
<'_
, K
, V
> {
1128 /// Returns a iterator of references over the remaining items.
1130 pub(super) fn iter(&self) -> Iter
<'_
, K
, V
> {
1132 inner
: self.inner
.clone(),
1133 marker
: PhantomData
,
1138 /// An owning iterator over the entries of a `HashMap`.
1140 /// This `struct` is created by the [`into_iter`] method on [`HashMap`][`HashMap`]
1141 /// (provided by the `IntoIterator` trait). See its documentation for more.
1143 /// [`into_iter`]: struct.HashMap.html#method.into_iter
1144 /// [`HashMap`]: struct.HashMap.html
1145 pub struct IntoIter
<K
, V
> {
1146 inner
: RawIntoIter
<(K
, V
)>,
1149 impl<K
, V
> IntoIter
<K
, V
> {
1150 /// Returns a iterator of references over the remaining items.
1152 pub(super) fn iter(&self) -> Iter
<'_
, K
, V
> {
1154 inner
: self.inner
.iter(),
1155 marker
: PhantomData
,
1160 /// An iterator over the keys of a `HashMap`.
1162 /// This `struct` is created by the [`keys`] method on [`HashMap`]. See its
1163 /// documentation for more.
1165 /// [`keys`]: struct.HashMap.html#method.keys
1166 /// [`HashMap`]: struct.HashMap.html
1167 pub struct Keys
<'a
, K
, V
> {
1168 inner
: Iter
<'a
, K
, V
>,
1171 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1172 impl<K
, V
> Clone
for Keys
<'_
, K
, V
> {
1174 fn clone(&self) -> Self {
1176 inner
: self.inner
.clone(),
1181 impl<K
: Debug
, V
> fmt
::Debug
for Keys
<'_
, K
, V
> {
1182 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1183 f
.debug_list().entries(self.clone()).finish()
1187 /// An iterator over the values of a `HashMap`.
1189 /// This `struct` is created by the [`values`] method on [`HashMap`]. See its
1190 /// documentation for more.
1192 /// [`values`]: struct.HashMap.html#method.values
1193 /// [`HashMap`]: struct.HashMap.html
1194 pub struct Values
<'a
, K
, V
> {
1195 inner
: Iter
<'a
, K
, V
>,
1198 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1199 impl<K
, V
> Clone
for Values
<'_
, K
, V
> {
1201 fn clone(&self) -> Self {
1203 inner
: self.inner
.clone(),
1208 impl<K
, V
: Debug
> fmt
::Debug
for Values
<'_
, K
, V
> {
1209 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1210 f
.debug_list().entries(self.clone()).finish()
1214 /// A draining iterator over the entries of a `HashMap`.
1216 /// This `struct` is created by the [`drain`] method on [`HashMap`]. See its
1217 /// documentation for more.
1219 /// [`drain`]: struct.HashMap.html#method.drain
1220 /// [`HashMap`]: struct.HashMap.html
1221 pub struct Drain
<'a
, K
, V
> {
1222 inner
: RawDrain
<'a
, (K
, V
)>,
1225 impl<K
, V
> Drain
<'_
, K
, V
> {
1226 /// Returns a iterator of references over the remaining items.
1228 pub(super) fn iter(&self) -> Iter
<'_
, K
, V
> {
1230 inner
: self.inner
.iter(),
1231 marker
: PhantomData
,
1236 /// A mutable iterator over the values of a `HashMap`.
1238 /// This `struct` is created by the [`values_mut`] method on [`HashMap`]. See its
1239 /// documentation for more.
1241 /// [`values_mut`]: struct.HashMap.html#method.values_mut
1242 /// [`HashMap`]: struct.HashMap.html
1243 pub struct ValuesMut
<'a
, K
, V
> {
1244 inner
: IterMut
<'a
, K
, V
>,
1247 /// A builder for computing where in a [`HashMap`] a key-value pair would be stored.
1249 /// See the [`HashMap::raw_entry_mut`] docs for usage examples.
1251 /// [`HashMap::raw_entry_mut`]: struct.HashMap.html#method.raw_entry_mut
1252 pub struct RawEntryBuilderMut
<'a
, K
, V
, S
> {
1253 map
: &'a
mut HashMap
<K
, V
, S
>,
1256 /// A view into a single entry in a map, which may either be vacant or occupied.
1258 /// This is a lower-level version of [`Entry`].
1260 /// This `enum` is constructed from the [`raw_entry`] method on [`HashMap`].
1262 /// [`HashMap`]: struct.HashMap.html
1263 /// [`Entry`]: enum.Entry.html
1264 /// [`raw_entry`]: struct.HashMap.html#method.raw_entry
1265 pub enum RawEntryMut
<'a
, K
: 'a
, V
: 'a
, S
: 'a
> {
1266 /// An occupied entry.
1267 Occupied(RawOccupiedEntryMut
<'a
, K
, V
>),
1269 Vacant(RawVacantEntryMut
<'a
, K
, V
, S
>),
1272 /// A view into an occupied entry in a `HashMap`.
1273 /// It is part of the [`RawEntryMut`] enum.
1275 /// [`RawEntryMut`]: enum.RawEntryMut.html
1276 pub struct RawOccupiedEntryMut
<'a
, K
, V
> {
1277 elem
: Bucket
<(K
, V
)>,
1278 table
: &'a
mut RawTable
<(K
, V
)>,
1281 /// A view into a vacant entry in a `HashMap`.
1282 /// It is part of the [`RawEntryMut`] enum.
1284 /// [`RawEntryMut`]: enum.RawEntryMut.html
1285 pub struct RawVacantEntryMut
<'a
, K
, V
, S
> {
1286 table
: &'a
mut RawTable
<(K
, V
)>,
1287 hash_builder
: &'a S
,
1290 /// A builder for computing where in a [`HashMap`] a key-value pair would be stored.
1292 /// See the [`HashMap::raw_entry`] docs for usage examples.
1294 /// [`HashMap::raw_entry`]: struct.HashMap.html#method.raw_entry
1295 pub struct RawEntryBuilder
<'a
, K
, V
, S
> {
1296 map
: &'a HashMap
<K
, V
, S
>,
1299 impl<'a
, K
, V
, S
> RawEntryBuilderMut
<'a
, K
, V
, S
>
1303 /// Creates a `RawEntryMut` from the given key.
1305 #[allow(clippy::wrong_self_convention)]
1306 pub fn from_key
<Q
: ?Sized
>(self, k
: &Q
) -> RawEntryMut
<'a
, K
, V
, S
>
1311 let mut hasher
= self.map
.hash_builder
.build_hasher();
1312 k
.hash(&mut hasher
);
1313 self.from_key_hashed_nocheck(hasher
.finish(), k
)
1316 /// Creates a `RawEntryMut` from the given key and its hash.
1318 #[allow(clippy::wrong_self_convention)]
1319 pub fn from_key_hashed_nocheck
<Q
: ?Sized
>(self, hash
: u64, k
: &Q
) -> RawEntryMut
<'a
, K
, V
, S
>
1324 self.from_hash(hash
, |q
| q
.borrow().eq(k
))
1328 impl<'a
, K
, V
, S
> RawEntryBuilderMut
<'a
, K
, V
, S
>
1332 /// Creates a `RawEntryMut` from the given hash.
1334 #[allow(clippy::wrong_self_convention)]
1335 pub fn from_hash
<F
>(self, hash
: u64, is_match
: F
) -> RawEntryMut
<'a
, K
, V
, S
>
1337 for<'b
> F
: FnMut(&'b K
) -> bool
,
1339 self.search(hash
, is_match
)
1343 fn search
<F
>(self, hash
: u64, mut is_match
: F
) -> RawEntryMut
<'a
, K
, V
, S
>
1345 for<'b
> F
: FnMut(&'b K
) -> bool
,
1347 match self.map
.table
.find(hash
, |(k
, _
)| is_match(k
)) {
1348 Some(elem
) => RawEntryMut
::Occupied(RawOccupiedEntryMut
{
1350 table
: &mut self.map
.table
,
1352 None
=> RawEntryMut
::Vacant(RawVacantEntryMut
{
1353 table
: &mut self.map
.table
,
1354 hash_builder
: &self.map
.hash_builder
,
1360 impl<'a
, K
, V
, S
> RawEntryBuilder
<'a
, K
, V
, S
>
1364 /// Access an entry by key.
1366 #[allow(clippy::wrong_self_convention)]
1367 pub fn from_key
<Q
: ?Sized
>(self, k
: &Q
) -> Option
<(&'a K
, &'a V
)>
1372 let mut hasher
= self.map
.hash_builder
.build_hasher();
1373 k
.hash(&mut hasher
);
1374 self.from_key_hashed_nocheck(hasher
.finish(), k
)
1377 /// Access an entry by a key and its hash.
1379 #[allow(clippy::wrong_self_convention)]
1380 pub fn from_key_hashed_nocheck
<Q
: ?Sized
>(self, hash
: u64, k
: &Q
) -> Option
<(&'a K
, &'a V
)>
1385 self.from_hash(hash
, |q
| q
.borrow().eq(k
))
1389 fn search
<F
>(self, hash
: u64, mut is_match
: F
) -> Option
<(&'a K
, &'a V
)>
1391 F
: FnMut(&K
) -> bool
,
1395 .find(hash
, |(k
, _
)| is_match(k
))
1396 .map(|item
| unsafe {
1397 let &(ref key
, ref value
) = item
.as_ref();
1402 /// Access an entry by hash.
1404 #[allow(clippy::wrong_self_convention)]
1405 pub fn from_hash
<F
>(self, hash
: u64, is_match
: F
) -> Option
<(&'a K
, &'a V
)>
1407 F
: FnMut(&K
) -> bool
,
1409 self.search(hash
, is_match
)
1413 impl<'a
, K
, V
, S
> RawEntryMut
<'a
, K
, V
, S
> {
1414 /// Ensures a value is in the entry by inserting the default if empty, and returns
1415 /// mutable references to the key and value in the entry.
1420 /// use hashbrown::HashMap;
1422 /// let mut map: HashMap<&str, u32> = HashMap::new();
1424 /// map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 3);
1425 /// assert_eq!(map["poneyland"], 3);
1427 /// *map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 10).1 *= 2;
1428 /// assert_eq!(map["poneyland"], 6);
1431 pub fn or_insert(self, default_key
: K
, default_val
: V
) -> (&'a
mut K
, &'a
mut V
)
1437 RawEntryMut
::Occupied(entry
) => entry
.into_key_value(),
1438 RawEntryMut
::Vacant(entry
) => entry
.insert(default_key
, default_val
),
1442 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1443 /// and returns mutable references to the key and value in the entry.
1448 /// use hashbrown::HashMap;
1450 /// let mut map: HashMap<&str, String> = HashMap::new();
1452 /// map.raw_entry_mut().from_key("poneyland").or_insert_with(|| {
1453 /// ("poneyland", "hoho".to_string())
1456 /// assert_eq!(map["poneyland"], "hoho".to_string());
1459 pub fn or_insert_with
<F
>(self, default: F
) -> (&'a
mut K
, &'a
mut V
)
1461 F
: FnOnce() -> (K
, V
),
1466 RawEntryMut
::Occupied(entry
) => entry
.into_key_value(),
1467 RawEntryMut
::Vacant(entry
) => {
1468 let (k
, v
) = default();
1474 /// Provides in-place mutable access to an occupied entry before any
1475 /// potential inserts into the map.
1480 /// use hashbrown::HashMap;
1482 /// let mut map: HashMap<&str, u32> = HashMap::new();
1484 /// map.raw_entry_mut()
1485 /// .from_key("poneyland")
1486 /// .and_modify(|_k, v| { *v += 1 })
1487 /// .or_insert("poneyland", 42);
1488 /// assert_eq!(map["poneyland"], 42);
1490 /// map.raw_entry_mut()
1491 /// .from_key("poneyland")
1492 /// .and_modify(|_k, v| { *v += 1 })
1493 /// .or_insert("poneyland", 0);
1494 /// assert_eq!(map["poneyland"], 43);
1497 pub fn and_modify
<F
>(self, f
: F
) -> Self
1499 F
: FnOnce(&mut K
, &mut V
),
1502 RawEntryMut
::Occupied(mut entry
) => {
1504 let (k
, v
) = entry
.get_key_value_mut();
1507 RawEntryMut
::Occupied(entry
)
1509 RawEntryMut
::Vacant(entry
) => RawEntryMut
::Vacant(entry
),
1514 impl<'a
, K
, V
> RawOccupiedEntryMut
<'a
, K
, V
> {
1515 /// Gets a reference to the key in the entry.
1517 pub fn key(&self) -> &K
{
1518 unsafe { &self.elem.as_ref().0 }
1521 /// Gets a mutable reference to the key in the entry.
1523 pub fn key_mut(&mut self) -> &mut K
{
1524 unsafe { &mut self.elem.as_mut().0 }
1527 /// Converts the entry into a mutable reference to the key in the entry
1528 /// with a lifetime bound to the map itself.
1530 pub fn into_key(self) -> &'a
mut K
{
1531 unsafe { &mut self.elem.as_mut().0 }
1534 /// Gets a reference to the value in the entry.
1536 pub fn get(&self) -> &V
{
1537 unsafe { &self.elem.as_ref().1 }
1540 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1541 /// with a lifetime bound to the map itself.
1543 pub fn into_mut(self) -> &'a
mut V
{
1544 unsafe { &mut self.elem.as_mut().1 }
1547 /// Gets a mutable reference to the value in the entry.
1549 pub fn get_mut(&mut self) -> &mut V
{
1550 unsafe { &mut self.elem.as_mut().1 }
1553 /// Gets a reference to the key and value in the entry.
1555 pub fn get_key_value(&mut self) -> (&K
, &V
) {
1557 let &(ref key
, ref value
) = self.elem
.as_ref();
1562 /// Gets a mutable reference to the key and value in the entry.
1564 pub fn get_key_value_mut(&mut self) -> (&mut K
, &mut V
) {
1566 let &mut (ref mut key
, ref mut value
) = self.elem
.as_mut();
1571 /// Converts the OccupiedEntry into a mutable reference to the key and value in the entry
1572 /// with a lifetime bound to the map itself.
1574 pub fn into_key_value(self) -> (&'a
mut K
, &'a
mut V
) {
1576 let &mut (ref mut key
, ref mut value
) = self.elem
.as_mut();
1581 /// Sets the value of the entry, and returns the entry's old value.
1583 pub fn insert(&mut self, value
: V
) -> V
{
1584 mem
::replace(self.get_mut(), value
)
1587 /// Sets the value of the entry, and returns the entry's old value.
1589 pub fn insert_key(&mut self, key
: K
) -> K
{
1590 mem
::replace(self.key_mut(), key
)
1593 /// Takes the value out of the entry, and returns it.
1595 pub fn remove(self) -> V
{
1596 self.remove_entry().1
1599 /// Take the ownership of the key and value from the map.
1601 pub fn remove_entry(self) -> (K
, V
) {
1603 self.table
.erase_no_drop(&self.elem
);
1609 impl<'a
, K
, V
, S
> RawVacantEntryMut
<'a
, K
, V
, S
> {
1610 /// Sets the value of the entry with the VacantEntry's key,
1611 /// and returns a mutable reference to it.
1613 pub fn insert(self, key
: K
, value
: V
) -> (&'a
mut K
, &'a
mut V
)
1618 let mut hasher
= self.hash_builder
.build_hasher();
1619 key
.hash(&mut hasher
);
1620 self.insert_hashed_nocheck(hasher
.finish(), key
, value
)
1623 /// Sets the value of the entry with the VacantEntry's key,
1624 /// and returns a mutable reference to it.
1626 #[allow(clippy::shadow_unrelated)]
1627 pub fn insert_hashed_nocheck(self, hash
: u64, key
: K
, value
: V
) -> (&'a
mut K
, &'a
mut V
)
1632 let hash_builder
= self.hash_builder
;
1633 self.insert_with_hasher(hash
, key
, value
, |k
| make_hash(hash_builder
, k
))
1636 /// Set the value of an entry with a custom hasher function.
1638 pub fn insert_with_hasher
<H
>(
1644 ) -> (&'a
mut K
, &'a
mut V
)
1650 let elem
= self.table
.insert(hash
, (key
, value
), |x
| hasher(&x
.0));
1651 let &mut (ref mut k
, ref mut v
) = elem
.as_mut();
1657 impl<K
, V
, S
> Debug
for RawEntryBuilderMut
<'_
, K
, V
, S
> {
1658 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1659 f
.debug_struct("RawEntryBuilder").finish()
1663 impl<K
: Debug
, V
: Debug
, S
> Debug
for RawEntryMut
<'_
, K
, V
, S
> {
1664 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1666 RawEntryMut
::Vacant(ref v
) => f
.debug_tuple("RawEntry").field(v
).finish(),
1667 RawEntryMut
::Occupied(ref o
) => f
.debug_tuple("RawEntry").field(o
).finish(),
1672 impl<K
: Debug
, V
: Debug
> Debug
for RawOccupiedEntryMut
<'_
, K
, V
> {
1673 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1674 f
.debug_struct("RawOccupiedEntryMut")
1675 .field("key", self.key())
1676 .field("value", self.get())
1681 impl<K
, V
, S
> Debug
for RawVacantEntryMut
<'_
, K
, V
, S
> {
1682 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1683 f
.debug_struct("RawVacantEntryMut").finish()
1687 impl<K
, V
, S
> Debug
for RawEntryBuilder
<'_
, K
, V
, S
> {
1688 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1689 f
.debug_struct("RawEntryBuilder").finish()
1693 /// A view into a single entry in a map, which may either be vacant or occupied.
1695 /// This `enum` is constructed from the [`entry`] method on [`HashMap`].
1697 /// [`HashMap`]: struct.HashMap.html
1698 /// [`entry`]: struct.HashMap.html#method.entry
1699 pub enum Entry
<'a
, K
: 'a
, V
: 'a
, S
: 'a
> {
1700 /// An occupied entry.
1701 Occupied(OccupiedEntry
<'a
, K
, V
, S
>),
1704 Vacant(VacantEntry
<'a
, K
, V
, S
>),
1707 impl<K
: Debug
, V
: Debug
, S
> Debug
for Entry
<'_
, K
, V
, S
> {
1708 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1710 Entry
::Vacant(ref v
) => f
.debug_tuple("Entry").field(v
).finish(),
1711 Entry
::Occupied(ref o
) => f
.debug_tuple("Entry").field(o
).finish(),
1716 /// A view into an occupied entry in a `HashMap`.
1717 /// It is part of the [`Entry`] enum.
1719 /// [`Entry`]: enum.Entry.html
1720 pub struct OccupiedEntry
<'a
, K
, V
, S
> {
1722 elem
: Bucket
<(K
, V
)>,
1723 table
: &'a
mut HashMap
<K
, V
, S
>,
1726 unsafe impl<K
, V
, S
> Send
for OccupiedEntry
<'_
, K
, V
, S
>
1733 unsafe impl<K
, V
, S
> Sync
for OccupiedEntry
<'_
, K
, V
, S
>
1741 impl<K
: Debug
, V
: Debug
, S
> Debug
for OccupiedEntry
<'_
, K
, V
, S
> {
1742 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1743 f
.debug_struct("OccupiedEntry")
1744 .field("key", self.key())
1745 .field("value", self.get())
1750 /// A view into a vacant entry in a `HashMap`.
1751 /// It is part of the [`Entry`] enum.
1753 /// [`Entry`]: enum.Entry.html
1754 pub struct VacantEntry
<'a
, K
, V
, S
> {
1757 table
: &'a
mut HashMap
<K
, V
, S
>,
1760 impl<K
: Debug
, V
, S
> Debug
for VacantEntry
<'_
, K
, V
, S
> {
1761 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1762 f
.debug_tuple("VacantEntry").field(self.key()).finish()
1766 impl<'a
, K
, V
, S
> IntoIterator
for &'a HashMap
<K
, V
, S
> {
1767 type Item
= (&'a K
, &'a V
);
1768 type IntoIter
= Iter
<'a
, K
, V
>;
1771 fn into_iter(self) -> Iter
<'a
, K
, V
> {
1776 impl<'a
, K
, V
, S
> IntoIterator
for &'a
mut HashMap
<K
, V
, S
> {
1777 type Item
= (&'a K
, &'a
mut V
);
1778 type IntoIter
= IterMut
<'a
, K
, V
>;
1781 fn into_iter(self) -> IterMut
<'a
, K
, V
> {
1786 impl<K
, V
, S
> IntoIterator
for HashMap
<K
, V
, S
> {
1788 type IntoIter
= IntoIter
<K
, V
>;
1790 /// Creates a consuming iterator, that is, one that moves each key-value
1791 /// pair out of the map in arbitrary order. The map cannot be used after
1797 /// use hashbrown::HashMap;
1799 /// let mut map = HashMap::new();
1800 /// map.insert("a", 1);
1801 /// map.insert("b", 2);
1802 /// map.insert("c", 3);
1804 /// // Not possible with .iter()
1805 /// let vec: Vec<(&str, i32)> = map.into_iter().collect();
1808 fn into_iter(self) -> IntoIter
<K
, V
> {
1810 inner
: self.table
.into_iter(),
1815 impl<'a
, K
, V
> Iterator
for Iter
<'a
, K
, V
> {
1816 type Item
= (&'a K
, &'a V
);
1819 fn next(&mut self) -> Option
<(&'a K
, &'a V
)> {
1820 self.inner
.next().map(|x
| unsafe {
1826 fn size_hint(&self) -> (usize, Option
<usize>) {
1827 self.inner
.size_hint()
1830 impl<K
, V
> ExactSizeIterator
for Iter
<'_
, K
, V
> {
1832 fn len(&self) -> usize {
1837 impl<K
, V
> FusedIterator
for Iter
<'_
, K
, V
> {}
1839 impl<'a
, K
, V
> Iterator
for IterMut
<'a
, K
, V
> {
1840 type Item
= (&'a K
, &'a
mut V
);
1843 fn next(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1844 self.inner
.next().map(|x
| unsafe {
1850 fn size_hint(&self) -> (usize, Option
<usize>) {
1851 self.inner
.size_hint()
1854 impl<K
, V
> ExactSizeIterator
for IterMut
<'_
, K
, V
> {
1856 fn len(&self) -> usize {
1860 impl<K
, V
> FusedIterator
for IterMut
<'_
, K
, V
> {}
1862 impl<K
, V
> fmt
::Debug
for IterMut
<'_
, K
, V
>
1867 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1868 f
.debug_list().entries(self.iter()).finish()
1872 impl<K
, V
> Iterator
for IntoIter
<K
, V
> {
1876 fn next(&mut self) -> Option
<(K
, V
)> {
1880 fn size_hint(&self) -> (usize, Option
<usize>) {
1881 self.inner
.size_hint()
1884 impl<K
, V
> ExactSizeIterator
for IntoIter
<K
, V
> {
1886 fn len(&self) -> usize {
1890 impl<K
, V
> FusedIterator
for IntoIter
<K
, V
> {}
1892 impl<K
: Debug
, V
: Debug
> fmt
::Debug
for IntoIter
<K
, V
> {
1893 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1894 f
.debug_list().entries(self.iter()).finish()
1898 impl<'a
, K
, V
> Iterator
for Keys
<'a
, K
, V
> {
1902 fn next(&mut self) -> Option
<(&'a K
)> {
1903 self.inner
.next().map(|(k
, _
)| k
)
1906 fn size_hint(&self) -> (usize, Option
<usize>) {
1907 self.inner
.size_hint()
1910 impl<K
, V
> ExactSizeIterator
for Keys
<'_
, K
, V
> {
1912 fn len(&self) -> usize {
1916 impl<K
, V
> FusedIterator
for Keys
<'_
, K
, V
> {}
1918 impl<'a
, K
, V
> Iterator
for Values
<'a
, K
, V
> {
1922 fn next(&mut self) -> Option
<(&'a V
)> {
1923 self.inner
.next().map(|(_
, v
)| v
)
1926 fn size_hint(&self) -> (usize, Option
<usize>) {
1927 self.inner
.size_hint()
1930 impl<K
, V
> ExactSizeIterator
for Values
<'_
, K
, V
> {
1932 fn len(&self) -> usize {
1936 impl<K
, V
> FusedIterator
for Values
<'_
, K
, V
> {}
1938 impl<'a
, K
, V
> Iterator
for ValuesMut
<'a
, K
, V
> {
1939 type Item
= &'a
mut V
;
1942 fn next(&mut self) -> Option
<(&'a
mut V
)> {
1943 self.inner
.next().map(|(_
, v
)| v
)
1946 fn size_hint(&self) -> (usize, Option
<usize>) {
1947 self.inner
.size_hint()
1950 impl<K
, V
> ExactSizeIterator
for ValuesMut
<'_
, K
, V
> {
1952 fn len(&self) -> usize {
1956 impl<K
, V
> FusedIterator
for ValuesMut
<'_
, K
, V
> {}
1958 impl<K
, V
> fmt
::Debug
for ValuesMut
<'_
, K
, V
>
1963 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1964 f
.debug_list().entries(self.inner
.iter()).finish()
1968 impl<'a
, K
, V
> Iterator
for Drain
<'a
, K
, V
> {
1972 fn next(&mut self) -> Option
<(K
, V
)> {
1976 fn size_hint(&self) -> (usize, Option
<usize>) {
1977 self.inner
.size_hint()
1980 impl<K
, V
> ExactSizeIterator
for Drain
<'_
, K
, V
> {
1982 fn len(&self) -> usize {
1986 impl<K
, V
> FusedIterator
for Drain
<'_
, K
, V
> {}
1988 impl<K
, V
> fmt
::Debug
for Drain
<'_
, K
, V
>
1993 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1994 f
.debug_list().entries(self.iter()).finish()
1998 impl<'a
, K
, V
, S
> Entry
<'a
, K
, V
, S
> {
1999 /// Ensures a value is in the entry by inserting the default if empty, and returns
2000 /// a mutable reference to the value in the entry.
2005 /// use hashbrown::HashMap;
2007 /// let mut map: HashMap<&str, u32> = HashMap::new();
2009 /// map.entry("poneyland").or_insert(3);
2010 /// assert_eq!(map["poneyland"], 3);
2012 /// *map.entry("poneyland").or_insert(10) *= 2;
2013 /// assert_eq!(map["poneyland"], 6);
2016 pub fn or_insert(self, default: V
) -> &'a
mut V
2022 Entry
::Occupied(entry
) => entry
.into_mut(),
2023 Entry
::Vacant(entry
) => entry
.insert(default),
2027 /// Ensures a value is in the entry by inserting the result of the default function if empty,
2028 /// and returns a mutable reference to the value in the entry.
2033 /// use hashbrown::HashMap;
2035 /// let mut map: HashMap<&str, String> = HashMap::new();
2036 /// let s = "hoho".to_string();
2038 /// map.entry("poneyland").or_insert_with(|| s);
2040 /// assert_eq!(map["poneyland"], "hoho".to_string());
2043 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
2049 Entry
::Occupied(entry
) => entry
.into_mut(),
2050 Entry
::Vacant(entry
) => entry
.insert(default()),
2054 /// Returns a reference to this entry's key.
2059 /// use hashbrown::HashMap;
2061 /// let mut map: HashMap<&str, u32> = HashMap::new();
2062 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2065 pub fn key(&self) -> &K
{
2067 Entry
::Occupied(ref entry
) => entry
.key(),
2068 Entry
::Vacant(ref entry
) => entry
.key(),
2072 /// Provides in-place mutable access to an occupied entry before any
2073 /// potential inserts into the map.
2078 /// use hashbrown::HashMap;
2080 /// let mut map: HashMap<&str, u32> = HashMap::new();
2082 /// map.entry("poneyland")
2083 /// .and_modify(|e| { *e += 1 })
2085 /// assert_eq!(map["poneyland"], 42);
2087 /// map.entry("poneyland")
2088 /// .and_modify(|e| { *e += 1 })
2090 /// assert_eq!(map["poneyland"], 43);
2093 pub fn and_modify
<F
>(self, f
: F
) -> Self
2098 Entry
::Occupied(mut entry
) => {
2100 Entry
::Occupied(entry
)
2102 Entry
::Vacant(entry
) => Entry
::Vacant(entry
),
2107 impl<'a
, K
, V
: Default
, S
> Entry
<'a
, K
, V
, S
> {
2108 /// Ensures a value is in the entry by inserting the default value if empty,
2109 /// and returns a mutable reference to the value in the entry.
2115 /// use hashbrown::HashMap;
2117 /// let mut map: HashMap<&str, Option<u32>> = HashMap::new();
2118 /// map.entry("poneyland").or_default();
2120 /// assert_eq!(map["poneyland"], None);
2124 pub fn or_default(self) -> &'a
mut V
2130 Entry
::Occupied(entry
) => entry
.into_mut(),
2131 Entry
::Vacant(entry
) => entry
.insert(Default
::default()),
2136 impl<'a
, K
, V
, S
> OccupiedEntry
<'a
, K
, V
, S
> {
2137 /// Gets a reference to the key in the entry.
2142 /// use hashbrown::HashMap;
2144 /// let mut map: HashMap<&str, u32> = HashMap::new();
2145 /// map.entry("poneyland").or_insert(12);
2146 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2149 pub fn key(&self) -> &K
{
2150 unsafe { &self.elem.as_ref().0 }
2153 /// Take the ownership of the key and value from the map.
2158 /// use hashbrown::HashMap;
2159 /// use hashbrown::hash_map::Entry;
2161 /// let mut map: HashMap<&str, u32> = HashMap::new();
2162 /// map.entry("poneyland").or_insert(12);
2164 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2165 /// // We delete the entry from the map.
2166 /// o.remove_entry();
2169 /// assert_eq!(map.contains_key("poneyland"), false);
2172 pub fn remove_entry(self) -> (K
, V
) {
2174 self.table
.table
.erase_no_drop(&self.elem
);
2179 /// Gets a reference to the value in the entry.
2184 /// use hashbrown::HashMap;
2185 /// use hashbrown::hash_map::Entry;
2187 /// let mut map: HashMap<&str, u32> = HashMap::new();
2188 /// map.entry("poneyland").or_insert(12);
2190 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2191 /// assert_eq!(o.get(), &12);
2195 pub fn get(&self) -> &V
{
2196 unsafe { &self.elem.as_ref().1 }
2199 /// Gets a mutable reference to the value in the entry.
2201 /// If you need a reference to the `OccupiedEntry` which may outlive the
2202 /// destruction of the `Entry` value, see [`into_mut`].
2204 /// [`into_mut`]: #method.into_mut
2209 /// use hashbrown::HashMap;
2210 /// use hashbrown::hash_map::Entry;
2212 /// let mut map: HashMap<&str, u32> = HashMap::new();
2213 /// map.entry("poneyland").or_insert(12);
2215 /// assert_eq!(map["poneyland"], 12);
2216 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2217 /// *o.get_mut() += 10;
2218 /// assert_eq!(*o.get(), 22);
2220 /// // We can use the same Entry multiple times.
2221 /// *o.get_mut() += 2;
2224 /// assert_eq!(map["poneyland"], 24);
2227 pub fn get_mut(&mut self) -> &mut V
{
2228 unsafe { &mut self.elem.as_mut().1 }
2231 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
2232 /// with a lifetime bound to the map itself.
2234 /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
2236 /// [`get_mut`]: #method.get_mut
2241 /// use hashbrown::HashMap;
2242 /// use hashbrown::hash_map::Entry;
2244 /// let mut map: HashMap<&str, u32> = HashMap::new();
2245 /// map.entry("poneyland").or_insert(12);
2247 /// assert_eq!(map["poneyland"], 12);
2248 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2249 /// *o.into_mut() += 10;
2252 /// assert_eq!(map["poneyland"], 22);
2255 pub fn into_mut(self) -> &'a
mut V
{
2256 unsafe { &mut self.elem.as_mut().1 }
2259 /// Sets the value of the entry, and returns the entry's old value.
2264 /// use hashbrown::HashMap;
2265 /// use hashbrown::hash_map::Entry;
2267 /// let mut map: HashMap<&str, u32> = HashMap::new();
2268 /// map.entry("poneyland").or_insert(12);
2270 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2271 /// assert_eq!(o.insert(15), 12);
2274 /// assert_eq!(map["poneyland"], 15);
2277 pub fn insert(&mut self, mut value
: V
) -> V
{
2278 let old_value
= self.get_mut();
2279 mem
::swap(&mut value
, old_value
);
2283 /// Takes the value out of the entry, and returns it.
2288 /// use hashbrown::HashMap;
2289 /// use hashbrown::hash_map::Entry;
2291 /// let mut map: HashMap<&str, u32> = HashMap::new();
2292 /// map.entry("poneyland").or_insert(12);
2294 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2295 /// assert_eq!(o.remove(), 12);
2298 /// assert_eq!(map.contains_key("poneyland"), false);
2301 pub fn remove(self) -> V
{
2302 self.remove_entry().1
2305 /// Replaces the entry, returning the old key and value. The new key in the hash map will be
2306 /// the key used to create this entry.
2311 /// use hashbrown::hash_map::{Entry, HashMap};
2312 /// use std::rc::Rc;
2314 /// let mut map: HashMap<Rc<String>, u32> = HashMap::new();
2315 /// map.insert(Rc::new("Stringthing".to_string()), 15);
2317 /// let my_key = Rc::new("Stringthing".to_string());
2319 /// if let Entry::Occupied(entry) = map.entry(my_key) {
2320 /// // Also replace the key with a handle to our other key.
2321 /// let (old_key, old_value): (Rc<String>, u32) = entry.replace_entry(16);
2326 pub fn replace_entry(self, value
: V
) -> (K
, V
) {
2327 let entry
= unsafe { self.elem.as_mut() }
;
2329 let old_key
= mem
::replace(&mut entry
.0, self.key
.unwrap());
2330 let old_value
= mem
::replace(&mut entry
.1, value
);
2332 (old_key
, old_value
)
2335 /// Replaces the key in the hash map with the key used to create this entry.
2340 /// use hashbrown::hash_map::{Entry, HashMap};
2341 /// use std::rc::Rc;
2343 /// let mut map: HashMap<Rc<String>, u32> = HashMap::new();
2344 /// let mut known_strings: Vec<Rc<String>> = Vec::new();
2346 /// // Initialise known strings, run program, etc.
2348 /// reclaim_memory(&mut map, &known_strings);
2350 /// fn reclaim_memory(map: &mut HashMap<Rc<String>, u32>, known_strings: &[Rc<String>] ) {
2351 /// for s in known_strings {
2352 /// if let Entry::Occupied(entry) = map.entry(s.clone()) {
2353 /// // Replaces the entry's key with our version of it in `known_strings`.
2354 /// entry.replace_key();
2360 pub fn replace_key(self) -> K
{
2361 let entry
= unsafe { self.elem.as_mut() }
;
2362 mem
::replace(&mut entry
.0, self.key
.unwrap())
2366 impl<'a
, K
, V
, S
> VacantEntry
<'a
, K
, V
, S
> {
2367 /// Gets a reference to the key that would be used when inserting a value
2368 /// through the `VacantEntry`.
2373 /// use hashbrown::HashMap;
2375 /// let mut map: HashMap<&str, u32> = HashMap::new();
2376 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2379 pub fn key(&self) -> &K
{
2383 /// Take ownership of the key.
2388 /// use hashbrown::HashMap;
2389 /// use hashbrown::hash_map::Entry;
2391 /// let mut map: HashMap<&str, u32> = HashMap::new();
2393 /// if let Entry::Vacant(v) = map.entry("poneyland") {
2398 pub fn into_key(self) -> K
{
2402 /// Sets the value of the entry with the VacantEntry's key,
2403 /// and returns a mutable reference to it.
2408 /// use hashbrown::HashMap;
2409 /// use hashbrown::hash_map::Entry;
2411 /// let mut map: HashMap<&str, u32> = HashMap::new();
2413 /// if let Entry::Vacant(o) = map.entry("poneyland") {
2416 /// assert_eq!(map["poneyland"], 37);
2419 pub fn insert(self, value
: V
) -> &'a
mut V
2424 let hash_builder
= &self.table
.hash_builder
;
2425 let bucket
= self.table
.table
.insert(self.hash
, (self.key
, value
), |x
| {
2426 make_hash(hash_builder
, &x
.0)
2428 unsafe { &mut bucket.as_mut().1 }
2432 impl<K
, V
, S
> FromIterator
<(K
, V
)> for HashMap
<K
, V
, S
>
2435 S
: BuildHasher
+ Default
,
2438 fn from_iter
<T
: IntoIterator
<Item
= (K
, V
)>>(iter
: T
) -> Self {
2439 let iter
= iter
.into_iter();
2440 let mut map
= Self::with_capacity_and_hasher(iter
.size_hint().0, S
::default());
2441 iter
.for_each(|(k
, v
)| {
2448 impl<K
, V
, S
> Extend
<(K
, V
)> for HashMap
<K
, V
, S
>
2454 fn extend
<T
: IntoIterator
<Item
= (K
, V
)>>(&mut self, iter
: T
) {
2455 // Keys may be already present or show multiple times in the iterator.
2456 // Reserve the entire hint lower bound if the map is empty.
2457 // Otherwise reserve half the hint (rounded up), so the map
2458 // will only resize twice in the worst case.
2459 let iter
= iter
.into_iter();
2460 let reserve
= if self.is_empty() {
2463 (iter
.size_hint().0 + 1) / 2
2465 self.reserve(reserve
);
2466 iter
.for_each(move |(k
, v
)| {
2472 impl<'a
, K
, V
, S
> Extend
<(&'a K
, &'a V
)> for HashMap
<K
, V
, S
>
2474 K
: Eq
+ Hash
+ Copy
,
2479 fn extend
<T
: IntoIterator
<Item
= (&'a K
, &'a V
)>>(&mut self, iter
: T
) {
2480 self.extend(iter
.into_iter().map(|(&key
, &value
)| (key
, value
)));
2485 fn assert_covariance() {
2486 fn map_key
<'new
>(v
: HashMap
<&'
static str, u8>) -> HashMap
<&'new
str, u8> {
2489 fn map_val
<'new
>(v
: HashMap
<u8, &'
static str>) -> HashMap
<u8, &'new
str> {
2492 fn iter_key
<'a
, 'new
>(v
: Iter
<'a
, &'
static str, u8>) -> Iter
<'a
, &'new
str, u8> {
2495 fn iter_val
<'a
, 'new
>(v
: Iter
<'a
, u8, &'
static str>) -> Iter
<'a
, u8, &'new
str> {
2498 fn into_iter_key
<'new
>(v
: IntoIter
<&'
static str, u8>) -> IntoIter
<&'new
str, u8> {
2501 fn into_iter_val
<'new
>(v
: IntoIter
<u8, &'
static str>) -> IntoIter
<u8, &'new
str> {
2504 fn keys_key
<'a
, 'new
>(v
: Keys
<'a
, &'
static str, u8>) -> Keys
<'a
, &'new
str, u8> {
2507 fn keys_val
<'a
, 'new
>(v
: Keys
<'a
, u8, &'
static str>) -> Keys
<'a
, u8, &'new
str> {
2510 fn values_key
<'a
, 'new
>(v
: Values
<'a
, &'
static str, u8>) -> Values
<'a
, &'new
str, u8> {
2513 fn values_val
<'a
, 'new
>(v
: Values
<'a
, u8, &'
static str>) -> Values
<'a
, u8, &'new
str> {
2517 d
: Drain
<'
static, &'
static str, &'
static str>,
2518 ) -> Drain
<'new
, &'new
str, &'new
str> {
2525 use super::DefaultHashBuilder
;
2526 use super::Entry
::{Occupied, Vacant}
;
2527 use super::{HashMap, RawEntryMut}
;
2529 use crate::CollectionAllocErr
::*;
2530 use rand
::{rngs::SmallRng, Rng, SeedableRng}
;
2531 use std
::cell
::RefCell
;
2536 fn test_zero_capacities() {
2537 type HM
= HashMap
<i32, i32>;
2540 assert_eq
!(m
.capacity(), 0);
2542 let m
= HM
::default();
2543 assert_eq
!(m
.capacity(), 0);
2545 let m
= HM
::with_hasher(DefaultHashBuilder
::default());
2546 assert_eq
!(m
.capacity(), 0);
2548 let m
= HM
::with_capacity(0);
2549 assert_eq
!(m
.capacity(), 0);
2551 let m
= HM
::with_capacity_and_hasher(0, DefaultHashBuilder
::default());
2552 assert_eq
!(m
.capacity(), 0);
2554 let mut m
= HM
::new();
2560 assert_eq
!(m
.capacity(), 0);
2562 let mut m
= HM
::new();
2564 assert_eq
!(m
.capacity(), 0);
2568 fn test_create_capacity_zero() {
2569 let mut m
= HashMap
::with_capacity(0);
2571 assert
!(m
.insert(1, 1).is_none());
2573 assert
!(m
.contains_key(&1));
2574 assert
!(!m
.contains_key(&0));
2579 let mut m
= HashMap
::new();
2580 assert_eq
!(m
.len(), 0);
2581 assert
!(m
.insert(1, 2).is_none());
2582 assert_eq
!(m
.len(), 1);
2583 assert
!(m
.insert(2, 4).is_none());
2584 assert_eq
!(m
.len(), 2);
2585 assert_eq
!(*m
.get(&1).unwrap(), 2);
2586 assert_eq
!(*m
.get(&2).unwrap(), 4);
2591 let mut m
= HashMap
::new();
2592 assert_eq
!(m
.len(), 0);
2593 assert
!(m
.insert(1, 2).is_none());
2594 assert_eq
!(m
.len(), 1);
2595 assert
!(m
.insert(2, 4).is_none());
2596 assert_eq
!(m
.len(), 2);
2598 assert_eq
!(*m2
.get(&1).unwrap(), 2);
2599 assert_eq
!(*m2
.get(&2).unwrap(), 4);
2600 assert_eq
!(m2
.len(), 2);
2603 thread_local
! { static DROP_VECTOR: RefCell<Vec<i32>> = RefCell::new(Vec::new()) }
2605 #[derive(Hash, PartialEq, Eq)]
2611 fn new(k
: usize) -> Droppable
{
2612 DROP_VECTOR
.with(|slot
| {
2613 slot
.borrow_mut()[k
] += 1;
2620 impl Drop
for Droppable
{
2621 fn drop(&mut self) {
2622 DROP_VECTOR
.with(|slot
| {
2623 slot
.borrow_mut()[self.k
] -= 1;
2628 impl Clone
for Droppable
{
2629 fn clone(&self) -> Self {
2630 Droppable
::new(self.k
)
2636 DROP_VECTOR
.with(|slot
| {
2637 *slot
.borrow_mut() = vec
![0; 200];
2641 let mut m
= HashMap
::new();
2643 DROP_VECTOR
.with(|v
| {
2645 assert_eq
!(v
.borrow()[i
], 0);
2650 let d1
= Droppable
::new(i
);
2651 let d2
= Droppable
::new(i
+ 100);
2655 DROP_VECTOR
.with(|v
| {
2657 assert_eq
!(v
.borrow()[i
], 1);
2662 let k
= Droppable
::new(i
);
2663 let v
= m
.remove(&k
);
2665 assert
!(v
.is_some());
2667 DROP_VECTOR
.with(|v
| {
2668 assert_eq
!(v
.borrow()[i
], 1);
2669 assert_eq
!(v
.borrow()[i
+ 100], 1);
2673 DROP_VECTOR
.with(|v
| {
2675 assert_eq
!(v
.borrow()[i
], 0);
2676 assert_eq
!(v
.borrow()[i
+ 100], 0);
2680 assert_eq
!(v
.borrow()[i
], 1);
2681 assert_eq
!(v
.borrow()[i
+ 100], 1);
2686 DROP_VECTOR
.with(|v
| {
2688 assert_eq
!(v
.borrow()[i
], 0);
2694 fn test_into_iter_drops() {
2695 DROP_VECTOR
.with(|v
| {
2696 *v
.borrow_mut() = vec
![0; 200];
2700 let mut hm
= HashMap
::new();
2702 DROP_VECTOR
.with(|v
| {
2704 assert_eq
!(v
.borrow()[i
], 0);
2709 let d1
= Droppable
::new(i
);
2710 let d2
= Droppable
::new(i
+ 100);
2714 DROP_VECTOR
.with(|v
| {
2716 assert_eq
!(v
.borrow()[i
], 1);
2723 // By the way, ensure that cloning doesn't screw up the dropping.
2727 let mut half
= hm
.into_iter().take(50);
2729 DROP_VECTOR
.with(|v
| {
2731 assert_eq
!(v
.borrow()[i
], 1);
2735 for _
in half
.by_ref() {}
2737 DROP_VECTOR
.with(|v
| {
2738 let nk
= (0..100).filter(|&i
| v
.borrow()[i
] == 1).count();
2740 let nv
= (0..100).filter(|&i
| v
.borrow()[i
+ 100] == 1).count();
2747 DROP_VECTOR
.with(|v
| {
2749 assert_eq
!(v
.borrow()[i
], 0);
2755 fn test_empty_remove() {
2756 let mut m
: HashMap
<i32, bool
> = HashMap
::new();
2757 assert_eq
!(m
.remove(&0), None
);
2761 fn test_empty_entry() {
2762 let mut m
: HashMap
<i32, bool
> = HashMap
::new();
2764 Occupied(_
) => panic
!(),
2767 assert
!(*m
.entry(0).or_insert(true));
2768 assert_eq
!(m
.len(), 1);
2772 fn test_empty_iter() {
2773 let mut m
: HashMap
<i32, bool
> = HashMap
::new();
2774 assert_eq
!(m
.drain().next(), None
);
2775 assert_eq
!(m
.keys().next(), None
);
2776 assert_eq
!(m
.values().next(), None
);
2777 assert_eq
!(m
.values_mut().next(), None
);
2778 assert_eq
!(m
.iter().next(), None
);
2779 assert_eq
!(m
.iter_mut().next(), None
);
2780 assert_eq
!(m
.len(), 0);
2781 assert
!(m
.is_empty());
2782 assert_eq
!(m
.into_iter().next(), None
);
2786 #[cfg(not(miri))] // FIXME: https://github.com/rust-lang/miri/issues/654
2787 fn test_lots_of_insertions() {
2788 let mut m
= HashMap
::new();
2790 // Try this a few times to make sure we never screw up the hashmap's
2793 assert
!(m
.is_empty());
2796 assert
!(m
.insert(i
, i
).is_none());
2800 assert_eq
!(r
, Some(&j
));
2803 for j
in i
+ 1..1001 {
2805 assert_eq
!(r
, None
);
2809 for i
in 1001..2001 {
2810 assert
!(!m
.contains_key(&i
));
2815 assert
!(m
.remove(&i
).is_some());
2818 assert
!(!m
.contains_key(&j
));
2821 for j
in i
+ 1..1001 {
2822 assert
!(m
.contains_key(&j
));
2827 assert
!(!m
.contains_key(&i
));
2831 assert
!(m
.insert(i
, i
).is_none());
2835 for i
in (1..1001).rev() {
2836 assert
!(m
.remove(&i
).is_some());
2839 assert
!(!m
.contains_key(&j
));
2843 assert
!(m
.contains_key(&j
));
2850 fn test_find_mut() {
2851 let mut m
= HashMap
::new();
2852 assert
!(m
.insert(1, 12).is_none());
2853 assert
!(m
.insert(2, 8).is_none());
2854 assert
!(m
.insert(5, 14).is_none());
2856 match m
.get_mut(&5) {
2858 Some(x
) => *x
= new
,
2860 assert_eq
!(m
.get(&5), Some(&new
));
2864 fn test_insert_overwrite() {
2865 let mut m
= HashMap
::new();
2866 assert
!(m
.insert(1, 2).is_none());
2867 assert_eq
!(*m
.get(&1).unwrap(), 2);
2868 assert
!(!m
.insert(1, 3).is_none());
2869 assert_eq
!(*m
.get(&1).unwrap(), 3);
2873 fn test_insert_conflicts() {
2874 let mut m
= HashMap
::with_capacity(4);
2875 assert
!(m
.insert(1, 2).is_none());
2876 assert
!(m
.insert(5, 3).is_none());
2877 assert
!(m
.insert(9, 4).is_none());
2878 assert_eq
!(*m
.get(&9).unwrap(), 4);
2879 assert_eq
!(*m
.get(&5).unwrap(), 3);
2880 assert_eq
!(*m
.get(&1).unwrap(), 2);
2884 fn test_conflict_remove() {
2885 let mut m
= HashMap
::with_capacity(4);
2886 assert
!(m
.insert(1, 2).is_none());
2887 assert_eq
!(*m
.get(&1).unwrap(), 2);
2888 assert
!(m
.insert(5, 3).is_none());
2889 assert_eq
!(*m
.get(&1).unwrap(), 2);
2890 assert_eq
!(*m
.get(&5).unwrap(), 3);
2891 assert
!(m
.insert(9, 4).is_none());
2892 assert_eq
!(*m
.get(&1).unwrap(), 2);
2893 assert_eq
!(*m
.get(&5).unwrap(), 3);
2894 assert_eq
!(*m
.get(&9).unwrap(), 4);
2895 assert
!(m
.remove(&1).is_some());
2896 assert_eq
!(*m
.get(&9).unwrap(), 4);
2897 assert_eq
!(*m
.get(&5).unwrap(), 3);
2901 fn test_is_empty() {
2902 let mut m
= HashMap
::with_capacity(4);
2903 assert
!(m
.insert(1, 2).is_none());
2904 assert
!(!m
.is_empty());
2905 assert
!(m
.remove(&1).is_some());
2906 assert
!(m
.is_empty());
2911 let mut m
= HashMap
::new();
2913 assert_eq
!(m
.remove(&1), Some(2));
2914 assert_eq
!(m
.remove(&1), None
);
2918 fn test_remove_entry() {
2919 let mut m
= HashMap
::new();
2921 assert_eq
!(m
.remove_entry(&1), Some((1, 2)));
2922 assert_eq
!(m
.remove(&1), None
);
2927 let mut m
= HashMap
::with_capacity(4);
2929 assert
!(m
.insert(i
, i
* 2).is_none());
2931 assert_eq
!(m
.len(), 32);
2933 let mut observed
: u32 = 0;
2936 assert_eq
!(*v
, *k
* 2);
2937 observed
|= 1 << *k
;
2939 assert_eq
!(observed
, 0xFFFF_FFFF);
2944 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
2945 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
2946 let keys
: Vec
<_
> = map
.keys().cloned().collect();
2947 assert_eq
!(keys
.len(), 3);
2948 assert
!(keys
.contains(&1));
2949 assert
!(keys
.contains(&2));
2950 assert
!(keys
.contains(&3));
2955 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
2956 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
2957 let values
: Vec
<_
> = map
.values().cloned().collect();
2958 assert_eq
!(values
.len(), 3);
2959 assert
!(values
.contains(&'a'
));
2960 assert
!(values
.contains(&'b'
));
2961 assert
!(values
.contains(&'c'
));
2965 fn test_values_mut() {
2966 let vec
= vec
![(1, 1), (2, 2), (3, 3)];
2967 let mut map
: HashMap
<_
, _
> = vec
.into_iter().collect();
2968 for value
in map
.values_mut() {
2969 *value
= (*value
) * 2
2971 let values
: Vec
<_
> = map
.values().cloned().collect();
2972 assert_eq
!(values
.len(), 3);
2973 assert
!(values
.contains(&2));
2974 assert
!(values
.contains(&4));
2975 assert
!(values
.contains(&6));
2980 let mut m
= HashMap
::new();
2981 assert
!(m
.get(&1).is_none());
2985 Some(v
) => assert_eq
!(*v
, 2),
2991 let mut m1
= HashMap
::new();
2996 let mut m2
= HashMap
::new();
3009 let mut map
= HashMap
::new();
3010 let empty
: HashMap
<i32, i32> = HashMap
::new();
3015 let map_str
= format
!("{:?}", map
);
3017 assert
!(map_str
== "{1: 2, 3: 4}" || map_str
== "{3: 4, 1: 2}");
3018 assert_eq
!(format
!("{:?}", empty
), "{}");
3023 let mut m
= HashMap
::new();
3025 assert_eq
!(m
.len(), 0);
3026 assert
!(m
.is_empty());
3029 let old_raw_cap
= m
.raw_capacity();
3030 while old_raw_cap
== m
.raw_capacity() {
3035 assert_eq
!(m
.len(), i
);
3036 assert
!(!m
.is_empty());
3040 fn test_behavior_resize_policy() {
3041 let mut m
= HashMap
::new();
3043 assert_eq
!(m
.len(), 0);
3044 assert_eq
!(m
.raw_capacity(), 1);
3045 assert
!(m
.is_empty());
3049 assert
!(m
.is_empty());
3050 let initial_raw_cap
= m
.raw_capacity();
3051 m
.reserve(initial_raw_cap
);
3052 let raw_cap
= m
.raw_capacity();
3054 assert_eq
!(raw_cap
, initial_raw_cap
* 2);
3057 for _
in 0..raw_cap
* 3 / 4 {
3061 // three quarters full
3063 assert_eq
!(m
.len(), i
);
3064 assert_eq
!(m
.raw_capacity(), raw_cap
);
3066 for _
in 0..raw_cap
/ 4 {
3072 let new_raw_cap
= m
.raw_capacity();
3073 assert_eq
!(new_raw_cap
, raw_cap
* 2);
3075 for _
in 0..raw_cap
/ 2 - 1 {
3078 assert_eq
!(m
.raw_capacity(), new_raw_cap
);
3080 // A little more than one quarter full.
3082 assert_eq
!(m
.raw_capacity(), raw_cap
);
3083 // again, a little more than half full
3084 for _
in 0..raw_cap
/ 2 {
3090 assert_eq
!(m
.len(), i
);
3091 assert
!(!m
.is_empty());
3092 assert_eq
!(m
.raw_capacity(), initial_raw_cap
);
3096 fn test_reserve_shrink_to_fit() {
3097 let mut m
= HashMap
::new();
3100 assert
!(m
.capacity() >= m
.len());
3106 let usable_cap
= m
.capacity();
3107 for i
in 128..(128 + 256) {
3109 assert_eq
!(m
.capacity(), usable_cap
);
3112 for i
in 100..(128 + 256) {
3113 assert_eq
!(m
.remove(&i
), Some(i
));
3117 assert_eq
!(m
.len(), 100);
3118 assert
!(!m
.is_empty());
3119 assert
!(m
.capacity() >= m
.len());
3122 assert_eq
!(m
.remove(&i
), Some(i
));
3127 assert_eq
!(m
.len(), 1);
3128 assert
!(m
.capacity() >= m
.len());
3129 assert_eq
!(m
.remove(&0), Some(0));
3133 fn test_from_iter() {
3134 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
3136 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
3138 for &(k
, v
) in &xs
{
3139 assert_eq
!(map
.get(&k
), Some(&v
));
3144 fn test_size_hint() {
3145 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
3147 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
3149 let mut iter
= map
.iter();
3151 for _
in iter
.by_ref().take(3) {}
3153 assert_eq
!(iter
.size_hint(), (3, Some(3)));
3157 fn test_iter_len() {
3158 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
3160 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
3162 let mut iter
= map
.iter();
3164 for _
in iter
.by_ref().take(3) {}
3166 assert_eq
!(iter
.len(), 3);
3170 fn test_mut_size_hint() {
3171 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
3173 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
3175 let mut iter
= map
.iter_mut();
3177 for _
in iter
.by_ref().take(3) {}
3179 assert_eq
!(iter
.size_hint(), (3, Some(3)));
3183 fn test_iter_mut_len() {
3184 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
3186 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
3188 let mut iter
= map
.iter_mut();
3190 for _
in iter
.by_ref().take(3) {}
3192 assert_eq
!(iter
.len(), 3);
3197 let mut map
= HashMap
::new();
3203 assert_eq
!(map
[&2], 1);
3208 fn test_index_nonexistent() {
3209 let mut map
= HashMap
::new();
3220 let xs
= [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
3222 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
3224 // Existing key (insert)
3225 match map
.entry(1) {
3226 Vacant(_
) => unreachable
!(),
3227 Occupied(mut view
) => {
3228 assert_eq
!(view
.get(), &10);
3229 assert_eq
!(view
.insert(100), 10);
3232 assert_eq
!(map
.get(&1).unwrap(), &100);
3233 assert_eq
!(map
.len(), 6);
3235 // Existing key (update)
3236 match map
.entry(2) {
3237 Vacant(_
) => unreachable
!(),
3238 Occupied(mut view
) => {
3239 let v
= view
.get_mut();
3240 let new_v
= (*v
) * 10;
3244 assert_eq
!(map
.get(&2).unwrap(), &200);
3245 assert_eq
!(map
.len(), 6);
3247 // Existing key (take)
3248 match map
.entry(3) {
3249 Vacant(_
) => unreachable
!(),
3251 assert_eq
!(view
.remove(), 30);
3254 assert_eq
!(map
.get(&3), None
);
3255 assert_eq
!(map
.len(), 5);
3257 // Inexistent key (insert)
3258 match map
.entry(10) {
3259 Occupied(_
) => unreachable
!(),
3261 assert_eq
!(*view
.insert(1000), 1000);
3264 assert_eq
!(map
.get(&10).unwrap(), &1000);
3265 assert_eq
!(map
.len(), 6);
3269 fn test_entry_take_doesnt_corrupt() {
3270 #![allow(deprecated)] //rand
3272 fn check(m
: &HashMap
<i32, ()>) {
3274 assert
!(m
.contains_key(k
), "{} is in keys() but not in the map?", k
);
3278 let mut m
= HashMap
::new();
3280 // FIXME: https://github.com/rust-lang/miri/issues/653
3282 let seed
= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
3283 SmallRng
::from_seed(seed
)
3286 // Populate the map with some items.
3288 let x
= rng
.gen_range(-10, 10);
3293 let x
= rng
.gen_range(-10, 10);
3306 fn test_extend_ref() {
3307 let mut a
= HashMap
::new();
3309 let mut b
= HashMap
::new();
3311 b
.insert(3, "three");
3315 assert_eq
!(a
.len(), 3);
3316 assert_eq
!(a
[&1], "one");
3317 assert_eq
!(a
[&2], "two");
3318 assert_eq
!(a
[&3], "three");
3322 fn test_capacity_not_less_than_len() {
3323 let mut a
= HashMap
::new();
3331 assert
!(a
.capacity() > a
.len());
3333 let free
= a
.capacity() - a
.len();
3339 assert_eq
!(a
.len(), a
.capacity());
3341 // Insert at capacity should cause allocation.
3343 assert
!(a
.capacity() > a
.len());
3347 fn test_occupied_entry_key() {
3348 let mut a
= HashMap
::new();
3349 let key
= "hello there";
3350 let value
= "value goes here";
3351 assert
!(a
.is_empty());
3352 a
.insert(key
.clone(), value
.clone());
3353 assert_eq
!(a
.len(), 1);
3354 assert_eq
!(a
[key
], value
);
3356 match a
.entry(key
.clone()) {
3357 Vacant(_
) => panic
!(),
3358 Occupied(e
) => assert_eq
!(key
, *e
.key()),
3360 assert_eq
!(a
.len(), 1);
3361 assert_eq
!(a
[key
], value
);
3365 fn test_vacant_entry_key() {
3366 let mut a
= HashMap
::new();
3367 let key
= "hello there";
3368 let value
= "value goes here";
3370 assert
!(a
.is_empty());
3371 match a
.entry(key
.clone()) {
3372 Occupied(_
) => panic
!(),
3374 assert_eq
!(key
, *e
.key());
3375 e
.insert(value
.clone());
3378 assert_eq
!(a
.len(), 1);
3379 assert_eq
!(a
[key
], value
);
3384 let mut map
: HashMap
<i32, i32> = (0..100).map(|x
| (x
, x
* 10)).collect();
3386 map
.retain(|&k
, _
| k
% 2 == 0);
3387 assert_eq
!(map
.len(), 50);
3388 assert_eq
!(map
[&2], 20);
3389 assert_eq
!(map
[&4], 40);
3390 assert_eq
!(map
[&6], 60);
3394 #[cfg(not(miri))] // FIXME: https://github.com/rust-lang/miri/issues/655
3395 fn test_try_reserve() {
3396 let mut empty_bytes
: HashMap
<u8, u8> = HashMap
::new();
3398 const MAX_USIZE
: usize = usize::MAX
;
3400 if let Err(CapacityOverflow
) = empty_bytes
.try_reserve(MAX_USIZE
) {
3402 panic
!("usize::MAX should trigger an overflow!");
3405 if let Err(AllocErr { .. }
) = empty_bytes
.try_reserve(MAX_USIZE
/ 8) {
3407 // This may succeed if there is enough free memory. Attempt to
3408 // allocate a second hashmap to ensure the allocation will fail.
3409 let mut empty_bytes2
: HashMap
<u8, u8> = HashMap
::new();
3410 if let Err(AllocErr { .. }
) = empty_bytes2
.try_reserve(MAX_USIZE
/ 8) {
3412 panic
!("usize::MAX / 8 should trigger an OOM!");
3418 fn test_raw_entry() {
3419 use super::RawEntryMut
::{Occupied, Vacant}
;
3421 let xs
= [(1i32, 10i32), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
3423 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
3425 let compute_hash
= |map
: &HashMap
<i32, i32>, k
: i32| -> u64 {
3426 use core
::hash
::{BuildHasher, Hash, Hasher}
;
3428 let mut hasher
= map
.hasher().build_hasher();
3429 k
.hash(&mut hasher
);
3433 // Existing key (insert)
3434 match map
.raw_entry_mut().from_key(&1) {
3435 Vacant(_
) => unreachable
!(),
3436 Occupied(mut view
) => {
3437 assert_eq
!(view
.get(), &10);
3438 assert_eq
!(view
.insert(100), 10);
3441 let hash1
= compute_hash(&map
, 1);
3442 assert_eq
!(map
.raw_entry().from_key(&1).unwrap(), (&1, &100));
3444 map
.raw_entry().from_hash(hash1
, |k
| *k
== 1).unwrap(),
3448 map
.raw_entry().from_key_hashed_nocheck(hash1
, &1).unwrap(),
3451 assert_eq
!(map
.len(), 6);
3453 // Existing key (update)
3454 match map
.raw_entry_mut().from_key(&2) {
3455 Vacant(_
) => unreachable
!(),
3456 Occupied(mut view
) => {
3457 let v
= view
.get_mut();
3458 let new_v
= (*v
) * 10;
3462 let hash2
= compute_hash(&map
, 2);
3463 assert_eq
!(map
.raw_entry().from_key(&2).unwrap(), (&2, &200));
3465 map
.raw_entry().from_hash(hash2
, |k
| *k
== 2).unwrap(),
3469 map
.raw_entry().from_key_hashed_nocheck(hash2
, &2).unwrap(),
3472 assert_eq
!(map
.len(), 6);
3474 // Existing key (take)
3475 let hash3
= compute_hash(&map
, 3);
3476 match map
.raw_entry_mut().from_key_hashed_nocheck(hash3
, &3) {
3477 Vacant(_
) => unreachable
!(),
3479 assert_eq
!(view
.remove_entry(), (3, 30));
3482 assert_eq
!(map
.raw_entry().from_key(&3), None
);
3483 assert_eq
!(map
.raw_entry().from_hash(hash3
, |k
| *k
== 3), None
);
3484 assert_eq
!(map
.raw_entry().from_key_hashed_nocheck(hash3
, &3), None
);
3485 assert_eq
!(map
.len(), 5);
3487 // Nonexistent key (insert)
3488 match map
.raw_entry_mut().from_key(&10) {
3489 Occupied(_
) => unreachable
!(),
3491 assert_eq
!(view
.insert(10, 1000), (&mut 10, &mut 1000));
3494 assert_eq
!(map
.raw_entry().from_key(&10).unwrap(), (&10, &1000));
3495 assert_eq
!(map
.len(), 6);
3497 // Ensure all lookup methods produce equivalent results.
3499 let hash
= compute_hash(&map
, k
);
3500 let v
= map
.get(&k
).cloned();
3501 let kv
= v
.as_ref().map(|v
| (&k
, v
));
3503 assert_eq
!(map
.raw_entry().from_key(&k
), kv
);
3504 assert_eq
!(map
.raw_entry().from_hash(hash
, |q
| *q
== k
), kv
);
3505 assert_eq
!(map
.raw_entry().from_key_hashed_nocheck(hash
, &k
), kv
);
3507 match map
.raw_entry_mut().from_key(&k
) {
3508 Occupied(mut o
) => assert_eq
!(Some(o
.get_key_value()), kv
),
3509 Vacant(_
) => assert_eq
!(v
, None
),
3511 match map
.raw_entry_mut().from_key_hashed_nocheck(hash
, &k
) {
3512 Occupied(mut o
) => assert_eq
!(Some(o
.get_key_value()), kv
),
3513 Vacant(_
) => assert_eq
!(v
, None
),
3515 match map
.raw_entry_mut().from_hash(hash
, |q
| *q
== k
) {
3516 Occupied(mut o
) => assert_eq
!(Some(o
.get_key_value()), kv
),
3517 Vacant(_
) => assert_eq
!(v
, None
),
3523 fn test_key_without_hash_impl() {
3525 struct IntWrapper(u64);
3527 let mut m
: HashMap
<IntWrapper
, ()> = HashMap
::new();
3529 assert
!(m
.raw_entry().from_hash(0, |k
| k
.0 == 0).is_none());
3532 let vacant_entry
= match m
.raw_entry_mut().from_hash(0, |k
| k
.0 == 0) {
3533 RawEntryMut
::Occupied(..) => panic
!("Found entry for key 0"),
3534 RawEntryMut
::Vacant(e
) => e
,
3536 vacant_entry
.insert_with_hasher(0, IntWrapper(0), (), |k
| k
.0);
3539 assert
!(m
.raw_entry().from_hash(0, |k
| k
.0 == 0).is_some());
3540 assert
!(m
.raw_entry().from_hash(1, |k
| k
.0 == 1).is_none());
3541 assert
!(m
.raw_entry().from_hash(2, |k
| k
.0 == 2).is_none());
3544 let vacant_entry
= match m
.raw_entry_mut().from_hash(1, |k
| k
.0 == 1) {
3545 RawEntryMut
::Occupied(..) => panic
!("Found entry for key 1"),
3546 RawEntryMut
::Vacant(e
) => e
,
3548 vacant_entry
.insert_with_hasher(1, IntWrapper(1), (), |k
| k
.0);
3551 assert
!(m
.raw_entry().from_hash(0, |k
| k
.0 == 0).is_some());
3552 assert
!(m
.raw_entry().from_hash(1, |k
| k
.0 == 1).is_some());
3553 assert
!(m
.raw_entry().from_hash(2, |k
| k
.0 == 2).is_none());
3556 let occupied_entry
= match m
.raw_entry_mut().from_hash(0, |k
| k
.0 == 0) {
3557 RawEntryMut
::Occupied(e
) => e
,
3558 RawEntryMut
::Vacant(..) => panic
!("Couldn't find entry for key 0"),
3560 occupied_entry
.remove();
3562 assert
!(m
.raw_entry().from_hash(0, |k
| k
.0 == 0).is_none());
3563 assert
!(m
.raw_entry().from_hash(1, |k
| k
.0 == 1).is_some());
3564 assert
!(m
.raw_entry().from_hash(2, |k
| k
.0 == 2).is_none());