map.rs source code [crates/hashbrown/src/map.rs]

1	use crate::raw::{
2	Allocator, Bucket, Global, RawDrain, RawExtractIf, RawIntoIter, RawIter, RawTable,
3	};
4	use crate::{DefaultHashBuilder, Equivalent, TryReserveError};
5	use core::borrow::Borrow;
6	use core::fmt::{self, Debug};
7	use core::hash::{BuildHasher, Hash};
8	use core::iter::FusedIterator;
9	use core::marker::PhantomData;
10	use core::mem;
11	use core::ops::Index;
12
13	#[cfg(feature = "raw-entry")]
14	pub use crate::raw_entry::*;
15
16	/// A hash map implemented with quadratic probing and SIMD lookup.
17	///
18	/// The default hashing algorithm is currently [`foldhash`], though this is
19	/// subject to change at any point in the future. This hash function is very
20	/// fast for all types of keys, but this algorithm will typically not* protect*
21	/// against attacks such as HashDoS.
22	///
23	/// The hashing algorithm can be replaced on a per-`HashMap` basis using the
24	/// [`default`], [`with_hasher`], and [`with_capacity_and_hasher`] methods. Many
25	/// alternative algorithms are available on crates.io, such as the [`fnv`] crate.
26	///
27	/// It is required that the keys implement the [`Eq`] and [`Hash`] traits, although
28	/// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
29	/// If you implement these yourself, it is important that the following
30	/// property holds:
31	///
32	/// ```text
33	/// k1 == k2 -> hash(k1) == hash(k2)
34	/// ```
35	///
36	/// In other words, if two keys are equal, their hashes must be equal.
37	///
38	/// It is a logic error for a key to be modified in such a way that the key's
39	/// hash, as determined by the [`Hash`] trait, or its equality, as determined by
40	/// the [`Eq`] trait, changes while it is in the map. This is normally only
41	/// possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
42	///
43	/// It is also a logic error for the [`Hash`] implementation of a key to panic.
44	/// This is generally only possible if the trait is implemented manually. If a
45	/// panic does occur then the contents of the `HashMap` may become corrupted and
46	/// some items may be dropped from the table.
47	///
48	/// # Examples
49	///
50	/// ```
51	/// use hashbrown::HashMap;
52	///
53	/// // Type inference lets us omit an explicit type signature (which
54	/// // would be `HashMap<String, String>` in this example).
55	/// let mut book_reviews = HashMap::new();
56	///
57	/// // Review some books.
58	/// book_reviews.insert(
59	/// "Adventures of Huckleberry Finn".to_string(),
60	/// "My favorite book.".to_string(),
61	/// );
62	/// book_reviews.insert(
63	/// "Grimms' Fairy Tales".to_string(),
64	/// "Masterpiece.".to_string(),
65	/// );
66	/// book_reviews.insert(
67	/// "Pride and Prejudice".to_string(),
68	/// "Very enjoyable.".to_string(),
69	/// );
70	/// book_reviews.insert(
71	/// "The Adventures of Sherlock Holmes".to_string(),
72	/// "Eye lyked it alot.".to_string(),
73	/// );
74	///
75	/// // Check for a specific one.
76	/// // When collections store owned values (String), they can still be
77	/// // queried using references (&str).
78	/// if !book_reviews.contains_key("Les Misérables") {
79	/// println!("We've got {} reviews, but Les Misérables ain't one.",
80	/// book_reviews.len());
81	/// }
82	///
83	/// // oops, this review has a lot of spelling mistakes, let's delete it.
84	/// book_reviews.remove("The Adventures of Sherlock Holmes");
85	///
86	/// // Look up the values associated with some keys.
87	/// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
88	/// for &book in &to_find {
89	/// match book_reviews.get(book) {
90	/// Some(review) => println!("{}: {}", book, review),
91	/// None => println!("{} is unreviewed.", book)
92	/// }
93	/// }
94	///
95	/// // Look up the value for a key (will panic if the key is not found).
96	/// println!("Review for Jane: {}", book_reviews["Pride and Prejudice"]);
97	///
98	/// // Iterate over everything.
99	/// for (book, review) in &book_reviews {
100	/// println!("{}: `\"`{}`\"`", book, review);
101	/// }
102	/// ```
103	///
104	/// `HashMap` also implements an [`Entry API`](#method.entry), which allows
105	/// for more complex methods of getting, setting, updating and removing keys and
106	/// their values:
107	///
108	/// ```
109	/// use hashbrown::HashMap;
110	///
111	/// // type inference lets us omit an explicit type signature (which
112	/// // would be `HashMap<&str, u8>` in this example).
113	/// let mut player_stats = HashMap::new();
114	///
115	/// fn random_stat_buff() -> u8 {
116	/// // could actually return some random value here - let's just return
117	/// // some fixed value for now
118	/// `42`
119	/// }
120	///
121	/// // insert a key only if it doesn't already exist
122	/// player_stats.entry("health").or_insert(`100`);
123	///
124	/// // insert a key using a function that provides a new value only if it
125	/// // doesn't already exist
126	/// player_stats.entry("defence").or_insert_with(random_stat_buff);
127	///
128	/// // update a key, guarding against the key possibly not being set
129	/// let stat = player_stats.entry("attack").or_insert(`100`);
130	/// *stat += random_stat_buff();
131	/// ```
132	///
133	/// The easiest way to use `HashMap` with a custom key type is to derive [`Eq`] and [`Hash`].
134	/// We must also derive [`PartialEq`].
135	///
136	/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
137	/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
138	/// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html
139	/// [`RefCell`]: https://doc.rust-lang.org/std/cell/struct.RefCell.html
140	/// [`Cell`]: https://doc.rust-lang.org/std/cell/struct.Cell.html
141	/// [`default`]: #method.default
142	/// [`with_hasher`]: #method.with_hasher
143	/// [`with_capacity_and_hasher`]: #method.with_capacity_and_hasher
144	/// [`fnv`]: https://crates.io/crates/fnv
145	/// [`foldhash`]: https://crates.io/crates/foldhash
146	///
147	/// ```
148	/// use hashbrown::HashMap;
149	///
150	/// #[derive(Hash, Eq, PartialEq, Debug)]
151	/// struct Viking {
152	/// name: String,
153	/// country: String,
154	/// }
155	///
156	/// impl Viking {
157	/// /// Creates a new Viking.
158	/// fn new(name: &str, country: &str) -> Viking {
159	/// Viking { name: name.to_string(), country: country.to_string() }
160	/// }
161	/// }
162	///
163	/// // Use a HashMap to store the vikings' health points.
164	/// let mut vikings = HashMap::new();
165	///
166	/// vikings.insert(Viking::new("Einar", "Norway"), `25`);
167	/// vikings.insert(Viking::new("Olaf", "Denmark"), `24`);
168	/// vikings.insert(Viking::new("Harald", "Iceland"), `12`);
169	///
170	/// // Use derived implementation to print the status of the vikings.
171	/// for (viking, health) in &vikings {
172	/// println!("{:?} has {} hp", viking, health);
173	/// }
174	/// ```
175	///
176	/// A `HashMap` with fixed list of elements can be initialized from an array:
177	///
178	/// ```
179	/// use hashbrown::HashMap;
180	///
181	/// let timber_resources: HashMap<&str, i32> = [("Norway", `100`), ("Denmark", `50`), ("Iceland", `10`)]
182	/// .into_iter().collect();
183	/// // use the values stored in map
184	/// ```
185	pub struct HashMap<K, V, S = DefaultHashBuilder, A: Allocator = Global> {
186	pub(crate) hash_builder: S,
187	pub(crate) table: RawTable<(K, V), A>,
188	}
189
190	impl<K: Clone, V: Clone, S: Clone, A: Allocator + Clone> Clone for HashMap<K, V, S, A> {
191	fn clone(&self) -> Self {
192	HashMap {
193	hash_builder: self.hash_builder.clone(),
194	table: self.table.clone(),
195	}
196	}
197
198	fn clone_from(&mut self, source: &Self) {
199	self.table.clone_from(&source.table);
200
201	// Update hash_builder only if we successfully cloned all elements.
202	self.hash_builder.clone_from(&source.hash_builder);
203	}
204	}
205
206	/// Ensures that a single closure type across uses of this which, in turn prevents multiple
207	/// instances of any functions like `RawTable::reserve` from being generated
208	#[cfg_attr(feature = "inline-more", inline)]
209	pub(crate) fn make_hasher<Q, V, S>(hash_builder: &S) -> impl Fn(&(Q, V)) -> u64 + '_
210	where
211	Q: Hash,
212	S: BuildHasher,
213	{
214	move \|val: &(Q, V)\| make_hash::<Q, S>(hash_builder, &val.0)
215	}
216
217	/// Ensures that a single closure type across uses of this which, in turn prevents multiple
218	/// instances of any functions like `RawTable::reserve` from being generated
219	#[cfg_attr(feature = "inline-more", inline)]
220	pub(crate) fn equivalent_key<Q, K, V>(k: &Q) -> impl Fn(&(K, V)) -> bool + '_
221	where
222	Q: Equivalent<K> + ?Sized,
223	{
224	move \|x: &(K, V)\| k.equivalent(&x.0)
225	}
226
227	/// Ensures that a single closure type across uses of this which, in turn prevents multiple
228	/// instances of any functions like `RawTable::reserve` from being generated
229	#[cfg_attr(feature = "inline-more", inline)]
230	#[allow(dead_code)]
231	pub(crate) fn equivalent<Q, K>(k: &Q) -> impl Fn(&K) -> bool + '_
232	where
233	Q: Equivalent<K> + ?Sized,
234	{
235	move \|x: &K\| k.equivalent(key:x)
236	}
237
238	#[cfg(not(feature = "nightly"))]
239	#[cfg_attr(feature = "inline-more", inline)]
240	pub(crate) fn make_hash<Q, S>(hash_builder: &S, val: &Q) -> u64
241	where
242	Q: Hash + ?Sized,
243	S: BuildHasher,
244	{
245	use core::hash::Hasher;
246	let mut state = hash_builder.build_hasher();
247	val.hash(&mut state);
248	state.finish()
249	}
250
251	#[cfg(feature = "nightly")]
252	#[cfg_attr(feature = "inline-more", inline)]
253	pub(crate) fn make_hash<Q, S>(hash_builder: &S, val: &Q) -> u64
254	where
255	Q: Hash + ?Sized,
256	S: BuildHasher,
257	{
258	hash_builder.hash_one(val)
259	}
260
261	#[cfg(feature = "default-hasher")]
262	impl<K, V> HashMap<K, V, DefaultHashBuilder> {
263	/// Creates an empty `HashMap`.
264	///
265	/// The hash map is initially created with a capacity of 0, so it will not allocate until it
266	/// is first inserted into.
267	///
268	/// # HashDoS resistance
269	///
270	/// The `hash_builder` normally use a fixed key by default and that does
271	/// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].
272	/// Users who require HashDoS resistance should explicitly use
273	/// [`std::collections::hash_map::RandomState`]
274	/// as the hasher when creating a [`HashMap`], for example with
275	/// [`with_hasher`](HashMap::with_hasher) method.
276	///
277	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
278	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
279	///
280	/// # Examples
281	///
282	/// ```
283	/// use hashbrown::HashMap;
284	/// let mut map: HashMap<&str, i32> = HashMap::new();
285	/// assert_eq!(map.len(), 0);
286	/// assert_eq!(map.capacity(), 0);
287	/// ```
288	#[cfg_attr(feature = "inline-more", inline)]
289	pub fn new() -> Self {
290	Self::default()
291	}
292
293	/// Creates an empty `HashMap` with the specified capacity.
294	///
295	/// The hash map will be able to hold at least `capacity` elements without
296	/// reallocating. If `capacity` is 0, the hash map will not allocate.
297	///
298	/// # HashDoS resistance
299	///
300	/// The `hash_builder` normally use a fixed key by default and that does
301	/// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].
302	/// Users who require HashDoS resistance should explicitly use
303	/// [`std::collections::hash_map::RandomState`]
304	/// as the hasher when creating a [`HashMap`], for example with
305	/// [`with_capacity_and_hasher`](HashMap::with_capacity_and_hasher) method.
306	///
307	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
308	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
309	///
310	/// # Examples
311	///
312	/// ```
313	/// use hashbrown::HashMap;
314	/// let mut map: HashMap<&str, i32> = HashMap::with_capacity(10);
315	/// assert_eq!(map.len(), 0);
316	/// assert!(map.capacity() >= 10);
317	/// ```
318	#[cfg_attr(feature = "inline-more", inline)]
319	pub fn with_capacity(capacity: usize) -> Self {
320	Self::with_capacity_and_hasher(capacity, DefaultHashBuilder::default())
321	}
322	}
323
324	#[cfg(feature = "default-hasher")]
325	impl<K, V, A: Allocator> HashMap<K, V, DefaultHashBuilder, A> {
326	/// Creates an empty `HashMap` using the given allocator.
327	///
328	/// The hash map is initially created with a capacity of 0, so it will not allocate until it
329	/// is first inserted into.
330	///
331	/// # HashDoS resistance
332	///
333	/// The `hash_builder` normally use a fixed key by default and that does
334	/// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].
335	/// Users who require HashDoS resistance should explicitly use
336	/// [`std::collections::hash_map::RandomState`]
337	/// as the hasher when creating a [`HashMap`], for example with
338	/// [`with_hasher_in`](HashMap::with_hasher_in) method.
339	///
340	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
341	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
342	///
343	/// # Examples
344	///
345	/// ```
346	/// use hashbrown::HashMap;
347	/// use bumpalo::Bump;
348	///
349	/// let bump = Bump::new();
350	/// let mut map = HashMap::new_in(&bump);
351	///
352	/// // The created HashMap holds none elements
353	/// assert_eq!(map.len(), 0);
354	///
355	/// // The created HashMap also doesn't allocate memory
356	/// assert_eq!(map.capacity(), 0);
357	///
358	/// // Now we insert element inside created HashMap
359	/// map.insert("One", 1);
360	/// // We can see that the HashMap holds 1 element
361	/// assert_eq!(map.len(), 1);
362	/// // And it also allocates some capacity
363	/// assert!(map.capacity() > 1);
364	/// ```
365	#[cfg_attr(feature = "inline-more", inline)]
366	pub fn new_in(alloc: A) -> Self {
367	Self::with_hasher_in(DefaultHashBuilder::default(), alloc)
368	}
369
370	/// Creates an empty `HashMap` with the specified capacity using the given allocator.
371	///
372	/// The hash map will be able to hold at least `capacity` elements without
373	/// reallocating. If `capacity` is 0, the hash map will not allocate.
374	///
375	/// # HashDoS resistance
376	///
377	/// The `hash_builder` normally use a fixed key by default and that does
378	/// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].
379	/// Users who require HashDoS resistance should explicitly use
380	/// [`std::collections::hash_map::RandomState`]
381	/// as the hasher when creating a [`HashMap`], for example with
382	/// [`with_capacity_and_hasher_in`](HashMap::with_capacity_and_hasher_in) method.
383	///
384	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
385	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
386	///
387	/// # Examples
388	///
389	/// ```
390	/// use hashbrown::HashMap;
391	/// use bumpalo::Bump;
392	///
393	/// let bump = Bump::new();
394	/// let mut map = HashMap::with_capacity_in(5, &bump);
395	///
396	/// // The created HashMap holds none elements
397	/// assert_eq!(map.len(), 0);
398	/// // But it can hold at least 5 elements without reallocating
399	/// let empty_map_capacity = map.capacity();
400	/// assert!(empty_map_capacity >= 5);
401	///
402	/// // Now we insert some 5 elements inside created HashMap
403	/// map.insert("One", 1);
404	/// map.insert("Two", 2);
405	/// map.insert("Three", 3);
406	/// map.insert("Four", 4);
407	/// map.insert("Five", 5);
408	///
409	/// // We can see that the HashMap holds 5 elements
410	/// assert_eq!(map.len(), 5);
411	/// // But its capacity isn't changed
412	/// assert_eq!(map.capacity(), empty_map_capacity)
413	/// ```
414	#[cfg_attr(feature = "inline-more", inline)]
415	pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
416	Self::with_capacity_and_hasher_in(capacity, DefaultHashBuilder::default(), alloc)
417	}
418	}
419
420	impl<K, V, S> HashMap<K, V, S> {
421	/// Creates an empty `HashMap` which will use the given hash builder to hash
422	/// keys.
423	///
424	/// The hash map is initially created with a capacity of 0, so it will not
425	/// allocate until it is first inserted into.
426	///
427	/// # HashDoS resistance
428	///
429	/// The `hash_builder` normally use a fixed key by default and that does
430	/// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].
431	/// Users who require HashDoS resistance should explicitly use
432	/// [`std::collections::hash_map::RandomState`]
433	/// as the hasher when creating a [`HashMap`].
434	///
435	/// The `hash_builder` passed should implement the [`BuildHasher`] trait for
436	/// the `HashMap` to be useful, see its documentation for details.
437	///
438	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
439	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
440	/// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
441	///
442	/// # Examples
443	///
444	/// ```
445	/// use hashbrown::HashMap;
446	/// use hashbrown::DefaultHashBuilder;
447	///
448	/// let s = DefaultHashBuilder::default();
449	/// let mut map = HashMap::with_hasher(s);
450	/// assert_eq!(map.len(), `0`);
451	/// assert_eq!(map.capacity(), `0`);
452	///
453	/// map.insert(`1`, `2`);
454	/// ```
455	#[cfg_attr(feature = "inline-more", inline)]
456	#[cfg_attr(feature = "rustc-dep-of-std", rustc_const_stable_indirect)]
457	pub const fn with_hasher(hash_builder: S) -> Self {
458	Self {
459	hash_builder,
460	table: RawTable::new(),
461	}
462	}
463
464	/// Creates an empty `HashMap` with the specified capacity, using `hash_builder`
465	/// to hash the keys.
466	///
467	/// The hash map will be able to hold at least `capacity` elements without
468	/// reallocating. If `capacity` is 0, the hash map will not allocate.
469	///
470	/// # HashDoS resistance
471	///
472	/// The `hash_builder` normally use a fixed key by default and that does
473	/// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].
474	/// Users who require HashDoS resistance should explicitly use
475	/// [`std::collections::hash_map::RandomState`]
476	/// as the hasher when creating a [`HashMap`].
477	///
478	/// The `hash_builder` passed should implement the [`BuildHasher`] trait for
479	/// the `HashMap` to be useful, see its documentation for details.
480	///
481	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
482	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
483	/// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
484	///
485	/// # Examples
486	///
487	/// ```
488	/// use hashbrown::HashMap;
489	/// use hashbrown::DefaultHashBuilder;
490	///
491	/// let s = DefaultHashBuilder::default();
492	/// let mut map = HashMap::with_capacity_and_hasher(`10`, s);
493	/// assert_eq!(map.len(), `0`);
494	/// assert!(map.capacity() >= `10`);
495	///
496	/// map.insert(`1`, `2`);
497	/// ```
498	#[cfg_attr(feature = "inline-more", inline)]
499	pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
500	Self {
501	hash_builder,
502	table: RawTable::with_capacity(capacity),
503	}
504	}
505	}
506
507	impl<K, V, S, A: Allocator> HashMap<K, V, S, A> {
508	/// Returns a reference to the underlying allocator.
509	#[inline]
510	pub fn allocator(&self) -> &A {
511	self.table.allocator()
512	}
513
514	/// Creates an empty `HashMap` which will use the given hash builder to hash
515	/// keys. It will be allocated with the given allocator.
516	///
517	/// The hash map is initially created with a capacity of 0, so it will not allocate until it
518	/// is first inserted into.
519	///
520	/// # HashDoS resistance
521	///
522	/// The `hash_builder` normally use a fixed key by default and that does
523	/// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].
524	/// Users who require HashDoS resistance should explicitly use
525	/// [`std::collections::hash_map::RandomState`]
526	/// as the hasher when creating a [`HashMap`].
527	///
528	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
529	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
530	///
531	/// # Examples
532	///
533	/// ```
534	/// use hashbrown::HashMap;
535	/// use hashbrown::DefaultHashBuilder;
536	///
537	/// let s = DefaultHashBuilder::default();
538	/// let mut map = HashMap::with_hasher(s);
539	/// map.insert(`1`, `2`);
540	/// ```
541	#[cfg_attr(feature = "inline-more", inline)]
542	#[cfg_attr(feature = "rustc-dep-of-std", rustc_const_stable_indirect)]
543	pub const fn with_hasher_in(hash_builder: S, alloc: A) -> Self {
544	Self {
545	hash_builder,
546	table: RawTable::new_in(alloc),
547	}
548	}
549
550	/// Creates an empty `HashMap` with the specified capacity, using `hash_builder`
551	/// to hash the keys. It will be allocated with the given allocator.
552	///
553	/// The hash map will be able to hold at least `capacity` elements without
554	/// reallocating. If `capacity` is 0, the hash map will not allocate.
555	///
556	/// # HashDoS resistance
557	///
558	/// The `hash_builder` normally use a fixed key by default and that does
559	/// not allow the `HashMap` to be protected against attacks such as [`HashDoS`].
560	/// Users who require HashDoS resistance should explicitly use
561	/// [`std::collections::hash_map::RandomState`]
562	/// as the hasher when creating a [`HashMap`].
563	///
564	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
565	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
566	///
567	/// # Examples
568	///
569	/// ```
570	/// use hashbrown::HashMap;
571	/// use hashbrown::DefaultHashBuilder;
572	///
573	/// let s = DefaultHashBuilder::default();
574	/// let mut map = HashMap::with_capacity_and_hasher(`10`, s);
575	/// map.insert(`1`, `2`);
576	/// ```
577	#[cfg_attr(feature = "inline-more", inline)]
578	pub fn with_capacity_and_hasher_in(capacity: usize, hash_builder: S, alloc: A) -> Self {
579	Self {
580	hash_builder,
581	table: RawTable::with_capacity_in(capacity, alloc),
582	}
583	}
584
585	/// Returns a reference to the map's [`BuildHasher`].
586	///
587	/// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
588	///
589	/// # Examples
590	///
591	/// ```
592	/// use hashbrown::HashMap;
593	/// use hashbrown::DefaultHashBuilder;
594	///
595	/// let hasher = DefaultHashBuilder::default();
596	/// let map: HashMap<i32, i32> = HashMap::with_hasher(hasher);
597	/// let hasher: &DefaultHashBuilder = map.hasher();
598	/// ```
599	#[cfg_attr(feature = "inline-more", inline)]
600	pub fn hasher(&self) -> &S {
601	&self.hash_builder
602	}
603
604	/// Returns the number of elements the map can hold without reallocating.
605	///
606	/// This number is a lower bound; the `HashMap<K, V>` might be able to hold
607	/// more, but is guaranteed to be able to hold at least this many.
608	///
609	/// # Examples
610	///
611	/// ```
612	/// use hashbrown::HashMap;
613	/// let map: HashMap<i32, i32> = HashMap::with_capacity(`100`);
614	/// assert_eq!(map.len(), `0`);
615	/// assert!(map.capacity() >= `100`);
616	/// ```
617	#[cfg_attr(feature = "inline-more", inline)]
618	pub fn capacity(&self) -> usize {
619	self.table.capacity()
620	}
621
622	/// An iterator visiting all keys in arbitrary order.
623	/// The iterator element type is `&'a K`.
624	///
625	/// # Examples
626	///
627	/// ```
628	/// use hashbrown::HashMap;
629	///
630	/// let mut map = HashMap::new();
631	/// map.insert("a", `1`);
632	/// map.insert("b", `2`);
633	/// map.insert("c", `3`);
634	/// assert_eq!(map.len(), `3`);
635	/// let mut vec: Vec<&str> = Vec::new();
636	///
637	/// for key in map.keys() {
638	/// println!("{}", key);
639	/// vec.push(*key);
640	/// }
641	///
642	/// // The `Keys` iterator produces keys in arbitrary order, so the
643	/// // keys must be sorted to test them against a sorted array.
644	/// vec.sort_unstable();
645	/// assert_eq!(vec, ["a", "b", "c"]);
646	///
647	/// assert_eq!(map.len(), `3`);
648	/// ```
649	#[cfg_attr(feature = "inline-more", inline)]
650	pub fn keys(&self) -> Keys<'_, K, V> {
651	Keys { inner: self.iter() }
652	}
653
654	/// An iterator visiting all values in arbitrary order.
655	/// The iterator element type is `&'a V`.
656	///
657	/// # Examples
658	///
659	/// ```
660	/// use hashbrown::HashMap;
661	///
662	/// let mut map = HashMap::new();
663	/// map.insert("a", `1`);
664	/// map.insert("b", `2`);
665	/// map.insert("c", `3`);
666	/// assert_eq!(map.len(), `3`);
667	/// let mut vec: Vec<i32> = Vec::new();
668	///
669	/// for val in map.values() {
670	/// println!("{}", val);
671	/// vec.push(*val);
672	/// }
673	///
674	/// // The `Values` iterator produces values in arbitrary order, so the
675	/// // values must be sorted to test them against a sorted array.
676	/// vec.sort_unstable();
677	/// assert_eq!(vec, [`1`, `2`, `3`]);
678	///
679	/// assert_eq!(map.len(), `3`);
680	/// ```
681	#[cfg_attr(feature = "inline-more", inline)]
682	pub fn values(&self) -> Values<'_, K, V> {
683	Values { inner: self.iter() }
684	}
685
686	/// An iterator visiting all values mutably in arbitrary order.
687	/// The iterator element type is `&'a mut V`.
688	///
689	/// # Examples
690	///
691	/// ```
692	/// use hashbrown::HashMap;
693	///
694	/// let mut map = HashMap::new();
695	///
696	/// map.insert("a", `1`);
697	/// map.insert("b", `2`);
698	/// map.insert("c", `3`);
699	///
700	/// for val in map.values_mut() {
701	/// val = val + `10`;
702	/// }
703	///
704	/// assert_eq!(map.len(), `3`);
705	/// let mut vec: Vec<i32> = Vec::new();
706	///
707	/// for val in map.values() {
708	/// println!("{}", val);
709	/// vec.push(*val);
710	/// }
711	///
712	/// // The `Values` iterator produces values in arbitrary order, so the
713	/// // values must be sorted to test them against a sorted array.
714	/// vec.sort_unstable();
715	/// assert_eq!(vec, [`11`, `12`, `13`]);
716	///
717	/// assert_eq!(map.len(), `3`);
718	/// ```
719	#[cfg_attr(feature = "inline-more", inline)]
720	pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
721	ValuesMut {
722	inner: self.iter_mut(),
723	}
724	}
725
726	/// An iterator visiting all key-value pairs in arbitrary order.
727	/// The iterator element type is `(&'a K, &'a V)`.
728	///
729	/// # Examples
730	///
731	/// ```
732	/// use hashbrown::HashMap;
733	///
734	/// let mut map = HashMap::new();
735	/// map.insert("a", `1`);
736	/// map.insert("b", `2`);
737	/// map.insert("c", `3`);
738	/// assert_eq!(map.len(), `3`);
739	/// let mut vec: Vec<(&str, i32)> = Vec::new();
740	///
741	/// for (key, val) in map.iter() {
742	/// println!("key: {} val: {}", key, val);
743	/// vec.push((key, val));
744	/// }
745	///
746	/// // The `Iter` iterator produces items in arbitrary order, so the
747	/// // items must be sorted to test them against a sorted array.
748	/// vec.sort_unstable();
749	/// assert_eq!(vec, [("a", `1`), ("b", `2`), ("c", `3`)]);
750	///
751	/// assert_eq!(map.len(), `3`);
752	/// ```
753	#[cfg_attr(feature = "inline-more", inline)]
754	pub fn iter(&self) -> Iter<'_, K, V> {
755	// Here we tie the lifetime of self to the iter.
756	unsafe {
757	Iter {
758	inner: self.table.iter(),
759	marker: PhantomData,
760	}
761	}
762	}
763
764	/// An iterator visiting all key-value pairs in arbitrary order,
765	/// with mutable references to the values.
766	/// The iterator element type is `(&'a K, &'a mut V)`.
767	///
768	/// # Examples
769	///
770	/// ```
771	/// use hashbrown::HashMap;
772	///
773	/// let mut map = HashMap::new();
774	/// map.insert("a", `1`);
775	/// map.insert("b", `2`);
776	/// map.insert("c", `3`);
777	///
778	/// // Update all values
779	/// for (_, val) in map.iter_mut() {
780	/// val = `2`;
781	/// }
782	///
783	/// assert_eq!(map.len(), `3`);
784	/// let mut vec: Vec<(&str, i32)> = Vec::new();
785	///
786	/// for (key, val) in &map {
787	/// println!("key: {} val: {}", key, val);
788	/// vec.push((key, val));
789	/// }
790	///
791	/// // The `Iter` iterator produces items in arbitrary order, so the
792	/// // items must be sorted to test them against a sorted array.
793	/// vec.sort_unstable();
794	/// assert_eq!(vec, [("a", `2`), ("b", `4`), ("c", `6`)]);
795	///
796	/// assert_eq!(map.len(), `3`);
797	/// ```
798	#[cfg_attr(feature = "inline-more", inline)]
799	pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
800	// Here we tie the lifetime of self to the iter.
801	unsafe {
802	IterMut {
803	inner: self.table.iter(),
804	marker: PhantomData,
805	}
806	}
807	}
808
809	#[cfg(test)]
810	#[cfg_attr(feature = "inline-more", inline)]
811	fn raw_capacity(&self) -> usize {
812	self.table.buckets()
813	}
814
815	/// Returns the number of elements in the map.
816	///
817	/// # Examples
818	///
819	/// ```
820	/// use hashbrown::HashMap;
821	///
822	/// let mut a = HashMap::new();
823	/// assert_eq!(a.len(), `0`);
824	/// a.insert(`1`, "a");
825	/// assert_eq!(a.len(), `1`);
826	/// ```
827	#[cfg_attr(feature = "inline-more", inline)]
828	pub fn len(&self) -> usize {
829	self.table.len()
830	}
831
832	/// Returns `true` if the map contains no elements.
833	///
834	/// # Examples
835	///
836	/// ```
837	/// use hashbrown::HashMap;
838	///
839	/// let mut a = HashMap::new();
840	/// assert!(a.is_empty());
841	/// a.insert(`1`, "a");
842	/// assert!(!a.is_empty());
843	/// ```
844	#[cfg_attr(feature = "inline-more", inline)]
845	pub fn is_empty(&self) -> bool {
846	self.len() == `0`
847	}
848
849	/// Clears the map, returning all key-value pairs as an iterator. Keeps the
850	/// allocated memory for reuse.
851	///
852	/// If the returned iterator is dropped before being fully consumed, it
853	/// drops the remaining key-value pairs. The returned iterator keeps a
854	/// mutable borrow on the vector to optimize its implementation.
855	///
856	/// # Examples
857	///
858	/// ```
859	/// use hashbrown::HashMap;
860	///
861	/// let mut a = HashMap::new();
862	/// a.insert(`1`, "a");
863	/// a.insert(`2`, "b");
864	/// let capacity_before_drain = a.capacity();
865	///
866	/// for (k, v) in a.drain().take(`1`) {
867	/// assert!(k == `1` \|\| k == `2`);
868	/// assert!(v == "a" \|\| v == "b");
869	/// }
870	///
871	/// // As we can see, the map is empty and contains no element.
872	/// assert!(a.is_empty() && a.len() == `0`);
873	/// // But map capacity is equal to old one.
874	/// assert_eq!(a.capacity(), capacity_before_drain);
875	///
876	/// let mut a = HashMap::new();
877	/// a.insert(`1`, "a");
878	/// a.insert(`2`, "b");
879	///
880	/// { // Iterator is dropped without being consumed.
881	/// let d = a.drain();
882	/// }
883	///
884	/// // But the map is empty even if we do not use Drain iterator.
885	/// assert!(a.is_empty());
886	/// ```
887	#[cfg_attr(feature = "inline-more", inline)]
888	pub fn drain(&mut self) -> Drain<'_, K, V, A> {
889	Drain {
890	inner: self.table.drain(),
891	}
892	}
893
894	/// Retains only the elements specified by the predicate. Keeps the
895	/// allocated memory for reuse.
896	///
897	/// In other words, remove all pairs `(k, v)` such that `f(&k, &mut v)` returns `false`.
898	/// The elements are visited in unsorted (and unspecified) order.
899	///
900	/// # Examples
901	///
902	/// ```
903	/// use hashbrown::HashMap;
904	///
905	/// let mut map: HashMap<i32, i32> = (`0`..`8`).map(\|x\|(x, x*`10`)).collect();
906	/// assert_eq!(map.len(), `8`);
907	///
908	/// map.retain(\|&k, _\| k % `2` == `0`);
909	///
910	/// // We can see, that the number of elements inside map is changed.
911	/// assert_eq!(map.len(), `4`);
912	///
913	/// let mut vec: Vec<(i32, i32)> = map.iter().map(\|(&k, &v)\| (k, v)).collect();
914	/// vec.sort_unstable();
915	/// assert_eq!(vec, [(`0`, `0`), (`2`, `20`), (`4`, `40`), (`6`, `60`)]);
916	/// ```
917	pub fn retain<F>(&mut self, mut f: F)
918	where
919	F: FnMut(&K, &mut V) -> bool,
920	{
921	// Here we only use `iter` as a temporary, preventing use-after-free
922	unsafe {
923	for item in self.table.iter() {
924	let &mut (ref key, ref mut value) = item.as_mut();
925	if !f(key, value) {
926	self.table.erase(item);
927	}
928	}
929	}
930	}
931
932	/// Drains elements which are true under the given predicate,
933	/// and returns an iterator over the removed items.
934	///
935	/// In other words, move all pairs `(k, v)` such that `f(&k, &mut v)` returns `true` out
936	/// into another iterator.
937	///
938	/// Note that `extract_if` lets you mutate every value in the filter closure, regardless of
939	/// whether you choose to keep or remove it.
940	///
941	/// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
942	/// or the iteration short-circuits, then the remaining elements will be retained.
943	/// Use [`retain()`] with a negated predicate if you do not need the returned iterator.
944	///
945	/// Keeps the allocated memory for reuse.
946	///
947	/// [`retain()`]: HashMap::retain
948	///
949	/// # Examples
950	///
951	/// ```
952	/// use hashbrown::HashMap;
953	///
954	/// let mut map: HashMap<i32, i32> = (`0`..`8`).map(\|x\| (x, x)).collect();
955	///
956	/// let drained: HashMap<i32, i32> = map.extract_if(\|k, _v\| k % `2` == `0`).collect();
957	///
958	/// let mut evens = drained.keys().cloned().collect::<Vec<_>>();
959	/// let mut odds = map.keys().cloned().collect::<Vec<_>>();
960	/// evens.sort();
961	/// odds.sort();
962	///
963	/// assert_eq!(evens, vec![`0`, `2`, `4`, `6`]);
964	/// assert_eq!(odds, vec![`1`, `3`, `5`, `7`]);
965	///
966	/// let mut map: HashMap<i32, i32> = (`0`..`8`).map(\|x\| (x, x)).collect();
967	///
968	/// { // Iterator is dropped without being consumed.
969	/// let d = map.extract_if(\|k, _v\| k % `2` != `0`);
970	/// }
971	///
972	/// // ExtractIf was not exhausted, therefore no elements were drained.
973	/// assert_eq!(map.len(), `8`);
974	/// ```
975	#[cfg_attr(feature = "inline-more", inline)]
976	pub fn extract_if<F>(&mut self, f: F) -> ExtractIf<'_, K, V, F, A>
977	where
978	F: FnMut(&K, &mut V) -> bool,
979	{
980	ExtractIf {
981	f,
982	inner: RawExtractIf {
983	iter: unsafe { self.table.iter() },
984	table: &mut self.table,
985	},
986	}
987	}
988
989	/// Clears the map, removing all key-value pairs. Keeps the allocated memory
990	/// for reuse.
991	///
992	/// # Examples
993	///
994	/// ```
995	/// use hashbrown::HashMap;
996	///
997	/// let mut a = HashMap::new();
998	/// a.insert(`1`, "a");
999	/// let capacity_before_clear = a.capacity();
1000	///
1001	/// a.clear();
1002	///
1003	/// // Map is empty.
1004	/// assert!(a.is_empty());
1005	/// // But map capacity is equal to old one.
1006	/// assert_eq!(a.capacity(), capacity_before_clear);
1007	/// ```
1008	#[cfg_attr(feature = "inline-more", inline)]
1009	pub fn clear(&mut self) {
1010	self.table.clear();
1011	}
1012
1013	/// Creates a consuming iterator visiting all the keys in arbitrary order.
1014	/// The map cannot be used after calling this.
1015	/// The iterator element type is `K`.
1016	///
1017	/// # Examples
1018	///
1019	/// ```
1020	/// use hashbrown::HashMap;
1021	///
1022	/// let mut map = HashMap::new();
1023	/// map.insert("a", `1`);
1024	/// map.insert("b", `2`);
1025	/// map.insert("c", `3`);
1026	///
1027	/// let mut vec: Vec<&str> = map.into_keys().collect();
1028	///
1029	/// // The `IntoKeys` iterator produces keys in arbitrary order, so the
1030	/// // keys must be sorted to test them against a sorted array.
1031	/// vec.sort_unstable();
1032	/// assert_eq!(vec, ["a", "b", "c"]);
1033	/// ```
1034	#[inline]
1035	pub fn into_keys(self) -> IntoKeys<K, V, A> {
1036	IntoKeys {
1037	inner: self.into_iter(),
1038	}
1039	}
1040
1041	/// Creates a consuming iterator visiting all the values in arbitrary order.
1042	/// The map cannot be used after calling this.
1043	/// The iterator element type is `V`.
1044	///
1045	/// # Examples
1046	///
1047	/// ```
1048	/// use hashbrown::HashMap;
1049	///
1050	/// let mut map = HashMap::new();
1051	/// map.insert("a", `1`);
1052	/// map.insert("b", `2`);
1053	/// map.insert("c", `3`);
1054	///
1055	/// let mut vec: Vec<i32> = map.into_values().collect();
1056	///
1057	/// // The `IntoValues` iterator produces values in arbitrary order, so
1058	/// // the values must be sorted to test them against a sorted array.
1059	/// vec.sort_unstable();
1060	/// assert_eq!(vec, [`1`, `2`, `3`]);
1061	/// ```
1062	#[inline]
1063	pub fn into_values(self) -> IntoValues<K, V, A> {
1064	IntoValues {
1065	inner: self.into_iter(),
1066	}
1067	}
1068	}
1069
1070	impl<K, V, S, A> HashMap<K, V, S, A>
1071	where
1072	K: Eq + Hash,
1073	S: BuildHasher,
1074	A: Allocator,
1075	{
1076	/// Reserves capacity for at least `additional` more elements to be inserted
1077	/// in the `HashMap`. The collection may reserve more space to avoid
1078	/// frequent reallocations.
1079	///
1080	/// # Panics
1081	///
1082	/// Panics if the new capacity exceeds [`isize::MAX`] bytes and [`abort`] the program
1083	/// in case of allocation error. Use [`try_reserve`](HashMap::try_reserve) instead
1084	/// if you want to handle memory allocation failure.
1085	///
1086	/// [`isize::MAX`]: https://doc.rust-lang.org/std/primitive.isize.html
1087	/// [`abort`]: https://doc.rust-lang.org/alloc/alloc/fn.handle_alloc_error.html
1088	///
1089	/// # Examples
1090	///
1091	/// ```
1092	/// use hashbrown::HashMap;
1093	/// let mut map: HashMap<&str, i32> = HashMap::new();
1094	/// // Map is empty and doesn't allocate memory
1095	/// assert_eq!(map.capacity(), `0`);
1096	///
1097	/// map.reserve(`10`);
1098	///
1099	/// // And now map can hold at least 10 elements
1100	/// assert!(map.capacity() >= `10`);
1101	/// ```
1102	#[cfg_attr(feature = "inline-more", inline)]
1103	pub fn reserve(&mut self, additional: usize) {
1104	self.table
1105	.reserve(additional, make_hasher::<_, V, S>(&self.hash_builder));
1106	}
1107
1108	/// Tries to reserve capacity for at least `additional` more elements to be inserted
1109	/// in the given `HashMap<K,V>`. The collection may reserve more space to avoid
1110	/// frequent reallocations.
1111	///
1112	/// # Errors
1113	///
1114	/// If the capacity overflows, or the allocator reports a failure, then an error
1115	/// is returned.
1116	///
1117	/// # Examples
1118	///
1119	/// ```
1120	/// use hashbrown::HashMap;
1121	///
1122	/// let mut map: HashMap<&str, isize> = HashMap::new();
1123	/// // Map is empty and doesn't allocate memory
1124	/// assert_eq!(map.capacity(), `0`);
1125	///
1126	/// map.try_reserve(`10`).expect("why is the test harness OOMing on 10 bytes?");
1127	///
1128	/// // And now map can hold at least 10 elements
1129	/// assert!(map.capacity() >= `10`);
1130	/// ```
1131	/// If the capacity overflows, or the allocator reports a failure, then an error
1132	/// is returned:
1133	/// ```
1134	/// # fn test() {
1135	/// use hashbrown::HashMap;
1136	/// use hashbrown::TryReserveError;
1137	/// let mut map: HashMap<i32, i32> = HashMap::new();
1138	///
1139	/// match map.try_reserve(usize::MAX) {
1140	/// Err(error) => match error {
1141	/// TryReserveError::CapacityOverflow => {}
1142	/// _ => panic!("TryReserveError::AllocError ?"),
1143	/// },
1144	/// _ => panic!(),
1145	/// }
1146	/// # }
1147	/// # fn main() {
1148	/// # #[cfg(not(miri))]
1149	/// # test()
1150	/// # }
1151	/// ```
1152	#[cfg_attr(feature = "inline-more", inline)]
1153	pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
1154	self.table
1155	.try_reserve(additional, make_hasher::<_, V, S>(&self.hash_builder))
1156	}
1157
1158	/// Shrinks the capacity of the map as much as possible. It will drop
1159	/// down as much as possible while maintaining the internal rules
1160	/// and possibly leaving some space in accordance with the resize policy.
1161	///
1162	/// # Examples
1163	///
1164	/// ```
1165	/// use hashbrown::HashMap;
1166	///
1167	/// let mut map: HashMap<i32, i32> = HashMap::with_capacity(`100`);
1168	/// map.insert(`1`, `2`);
1169	/// map.insert(`3`, `4`);
1170	/// assert!(map.capacity() >= `100`);
1171	/// map.shrink_to_fit();
1172	/// assert!(map.capacity() >= `2`);
1173	/// ```
1174	#[cfg_attr(feature = "inline-more", inline)]
1175	pub fn shrink_to_fit(&mut self) {
1176	self.table
1177	.shrink_to(`0`, make_hasher::<_, V, S>(&self.hash_builder));
1178	}
1179
1180	/// Shrinks the capacity of the map with a lower limit. It will drop
1181	/// down no lower than the supplied limit while maintaining the internal rules
1182	/// and possibly leaving some space in accordance with the resize policy.
1183	///
1184	/// This function does nothing if the current capacity is smaller than the
1185	/// supplied minimum capacity.
1186	///
1187	/// # Examples
1188	///
1189	/// ```
1190	/// use hashbrown::HashMap;
1191	///
1192	/// let mut map: HashMap<i32, i32> = HashMap::with_capacity(`100`);
1193	/// map.insert(`1`, `2`);
1194	/// map.insert(`3`, `4`);
1195	/// assert!(map.capacity() >= `100`);
1196	/// map.shrink_to(`10`);
1197	/// assert!(map.capacity() >= `10`);
1198	/// map.shrink_to(`0`);
1199	/// assert!(map.capacity() >= `2`);
1200	/// map.shrink_to(`10`);
1201	/// assert!(map.capacity() >= `2`);
1202	/// ```
1203	#[cfg_attr(feature = "inline-more", inline)]
1204	pub fn shrink_to(&mut self, min_capacity: usize) {
1205	self.table
1206	.shrink_to(min_capacity, make_hasher::<_, V, S>(&self.hash_builder));
1207	}
1208
1209	/// Gets the given key's corresponding entry in the map for in-place manipulation.
1210	///
1211	/// # Examples
1212	///
1213	/// ```
1214	/// use hashbrown::HashMap;
1215	///
1216	/// let mut letters = HashMap::new();
1217	///
1218	/// for ch in "a short treatise on fungi".chars() {
1219	/// let counter = letters.entry(ch).or_insert(`0`);
1220	/// *counter += `1`;
1221	/// }
1222	///
1223	/// assert_eq!(letters[&'s'], `2`);
1224	/// assert_eq!(letters[&'t'], `3`);
1225	/// assert_eq!(letters[&'u'], `1`);
1226	/// assert_eq!(letters.get(&'y'), None);
1227	/// ```
1228	#[cfg_attr(feature = "inline-more", inline)]
1229	pub fn entry(&mut self, key: K) -> Entry<'_, K, V, S, A> {
1230	let hash = make_hash::<K, S>(&self.hash_builder, &key);
1231	if let Some(elem) = self.table.find(hash, equivalent_key(&key)) {
1232	Entry::Occupied(OccupiedEntry {
1233	hash,
1234	elem,
1235	table: self,
1236	})
1237	} else {
1238	Entry::Vacant(VacantEntry {
1239	hash,
1240	key,
1241	table: self,
1242	})
1243	}
1244	}
1245
1246	/// Gets the given key's corresponding entry by reference in the map for in-place manipulation.
1247	///
1248	/// # Examples
1249	///
1250	/// ```
1251	/// use hashbrown::HashMap;
1252	///
1253	/// let mut words: HashMap<String, usize> = HashMap::new();
1254	/// let source = ["poneyland", "horseyland", "poneyland", "poneyland"];
1255	/// for (i, &s) in source.iter().enumerate() {
1256	/// let counter = words.entry_ref(s).or_insert(`0`);
1257	/// *counter += `1`;
1258	/// }
1259	///
1260	/// assert_eq!(words["poneyland"], `3`);
1261	/// assert_eq!(words["horseyland"], `1`);
1262	/// ```
1263	#[cfg_attr(feature = "inline-more", inline)]
1264	pub fn entry_ref<'a, 'b, Q>(&'a mut self, key: &'b Q) -> EntryRef<'a, 'b, K, Q, V, S, A>
1265	where
1266	Q: Hash + Equivalent<K> + ?Sized,
1267	{
1268	let hash = make_hash::<Q, S>(&self.hash_builder, key);
1269	if let Some(elem) = self.table.find(hash, equivalent_key(key)) {
1270	EntryRef::Occupied(OccupiedEntry {
1271	hash,
1272	elem,
1273	table: self,
1274	})
1275	} else {
1276	EntryRef::Vacant(VacantEntryRef {
1277	hash,
1278	key,
1279	table: self,
1280	})
1281	}
1282	}
1283
1284	/// Returns a reference to the value corresponding to the key.
1285	///
1286	/// The key may be any borrowed form of the map's key type, but
1287	/// [`Hash`] and [`Eq`] on the borrowed form must* match those for*
1288	/// the key type.
1289	///
1290	/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
1291	/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
1292	///
1293	/// # Examples
1294	///
1295	/// ```
1296	/// use hashbrown::HashMap;
1297	///
1298	/// let mut map = HashMap::new();
1299	/// map.insert(`1`, "a");
1300	/// assert_eq!(map.get(&`1`), Some(&"a"));
1301	/// assert_eq!(map.get(&`2`), None);
1302	/// ```
1303	#[inline]
1304	pub fn get<Q>(&self, k: &Q) -> Option<&V>
1305	where
1306	Q: Hash + Equivalent<K> + ?Sized,
1307	{
1308	// Avoid `Option::map` because it bloats LLVM IR.
1309	match self.get_inner(k) {
1310	Some((_, v)) => Some(v),
1311	None => None,
1312	}
1313	}
1314
1315	/// Returns the key-value pair corresponding to the supplied key.
1316	///
1317	/// The supplied key may be any borrowed form of the map's key type, but
1318	/// [`Hash`] and [`Eq`] on the borrowed form must* match those for*
1319	/// the key type.
1320	///
1321	/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
1322	/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
1323	///
1324	/// # Examples
1325	///
1326	/// ```
1327	/// use hashbrown::HashMap;
1328	///
1329	/// let mut map = HashMap::new();
1330	/// map.insert(`1`, "a");
1331	/// assert_eq!(map.get_key_value(&`1`), Some((&`1`, &"a")));
1332	/// assert_eq!(map.get_key_value(&`2`), None);
1333	/// ```
1334	#[inline]
1335	pub fn get_key_value<Q>(&self, k: &Q) -> Option<(&K, &V)>
1336	where
1337	Q: Hash + Equivalent<K> + ?Sized,
1338	{
1339	// Avoid `Option::map` because it bloats LLVM IR.
1340	match self.get_inner(k) {
1341	Some((key, value)) => Some((key, value)),
1342	None => None,
1343	}
1344	}
1345
1346	#[inline]
1347	fn get_inner<Q>(&self, k: &Q) -> Option<&(K, V)>
1348	where
1349	Q: Hash + Equivalent<K> + ?Sized,
1350	{
1351	if self.table.is_empty() {
1352	None
1353	} else {
1354	let hash = make_hash::<Q, S>(&self.hash_builder, k);
1355	self.table.get(hash, equivalent_key(k))
1356	}
1357	}
1358
1359	/// Returns the key-value pair corresponding to the supplied key, with a mutable reference to value.
1360	///
1361	/// The supplied key may be any borrowed form of the map's key type, but
1362	/// [`Hash`] and [`Eq`] on the borrowed form must* match those for*
1363	/// the key type.
1364	///
1365	/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
1366	/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
1367	///
1368	/// # Examples
1369	///
1370	/// ```
1371	/// use hashbrown::HashMap;
1372	///
1373	/// let mut map = HashMap::new();
1374	/// map.insert(`1`, "a");
1375	/// let (k, v) = map.get_key_value_mut(&`1`).unwrap();
1376	/// assert_eq!(k, &`1`);
1377	/// assert_eq!(v, &mut "a");
1378	/// *v = "b";
1379	/// assert_eq!(map.get_key_value_mut(&`1`), Some((&`1`, &mut "b")));
1380	/// assert_eq!(map.get_key_value_mut(&`2`), None);
1381	/// ```
1382	#[inline]
1383	pub fn get_key_value_mut<Q>(&mut self, k: &Q) -> Option<(&K, &mut V)>
1384	where
1385	Q: Hash + Equivalent<K> + ?Sized,
1386	{
1387	// Avoid `Option::map` because it bloats LLVM IR.
1388	match self.get_inner_mut(k) {
1389	Some(&mut (ref key, ref mut value)) => Some((key, value)),
1390	None => None,
1391	}
1392	}
1393
1394	/// Returns `true` if the map contains a value for the specified key.
1395	///
1396	/// The key may be any borrowed form of the map's key type, but
1397	/// [`Hash`] and [`Eq`] on the borrowed form must* match those for*
1398	/// the key type.
1399	///
1400	/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
1401	/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
1402	///
1403	/// # Examples
1404	///
1405	/// ```
1406	/// use hashbrown::HashMap;
1407	///
1408	/// let mut map = HashMap::new();
1409	/// map.insert(`1`, "a");
1410	/// assert_eq!(map.contains_key(&`1`), `true`);
1411	/// assert_eq!(map.contains_key(&`2`), `false`);
1412	/// ```
1413	#[cfg_attr(feature = "inline-more", inline)]
1414	pub fn contains_key<Q>(&self, k: &Q) -> bool
1415	where
1416	Q: Hash + Equivalent<K> + ?Sized,
1417	{
1418	self.get_inner(k).is_some()
1419	}
1420
1421	/// Returns a mutable reference to the value corresponding to the key.
1422	///
1423	/// The key may be any borrowed form of the map's key type, but
1424	/// [`Hash`] and [`Eq`] on the borrowed form must* match those for*
1425	/// the key type.
1426	///
1427	/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
1428	/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
1429	///
1430	/// # Examples
1431	///
1432	/// ```
1433	/// use hashbrown::HashMap;
1434	///
1435	/// let mut map = HashMap::new();
1436	/// map.insert(`1`, "a");
1437	/// if let Some(x) = map.get_mut(&`1`) {
1438	/// *x = "b";
1439	/// }
1440	/// assert_eq!(map[&`1`], "b");
1441	///
1442	/// assert_eq!(map.get_mut(&`2`), None);
1443	/// ```
1444	#[cfg_attr(feature = "inline-more", inline)]
1445	pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
1446	where
1447	Q: Hash + Equivalent<K> + ?Sized,
1448	{
1449	// Avoid `Option::map` because it bloats LLVM IR.
1450	match self.get_inner_mut(k) {
1451	Some(&mut (_, ref mut v)) => Some(v),
1452	None => None,
1453	}
1454	}
1455
1456	#[inline]
1457	fn get_inner_mut<Q>(&mut self, k: &Q) -> Option<&mut (K, V)>
1458	where
1459	Q: Hash + Equivalent<K> + ?Sized,
1460	{
1461	if self.table.is_empty() {
1462	None
1463	} else {
1464	let hash = make_hash::<Q, S>(&self.hash_builder, k);
1465	self.table.get_mut(hash, equivalent_key(k))
1466	}
1467	}
1468
1469	/// Attempts to get mutable references to `N` values in the map at once.
1470	///
1471	/// Returns an array of length `N` with the results of each query. For soundness, at most one
1472	/// mutable reference will be returned to any value. `None` will be used if the key is missing.
1473	///
1474	/// # Panics
1475	///
1476	/// Panics if any keys are overlapping.
1477	///
1478	/// # Examples
1479	///
1480	/// ```
1481	/// use hashbrown::HashMap;
1482	///
1483	/// let mut libraries = HashMap::new();
1484	/// libraries.insert("Bodleian Library".to_string(), `1602`);
1485	/// libraries.insert("Athenæum".to_string(), `1807`);
1486	/// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), `1691`);
1487	/// libraries.insert("Library of Congress".to_string(), `1800`);
1488	///
1489	/// // Get Athenæum and Bodleian Library
1490	/// let [Some(a), Some(b)] = libraries.get_many_mut([
1491	/// "Athenæum",
1492	/// "Bodleian Library",
1493	/// ]) else { panic!() };
1494	///
1495	/// // Assert values of Athenæum and Library of Congress
1496	/// let got = libraries.get_many_mut([
1497	/// "Athenæum",
1498	/// "Library of Congress",
1499	/// ]);
1500	/// assert_eq!(
1501	/// got,
1502	/// [
1503	/// Some(&mut `1807`),
1504	/// Some(&mut `1800`),
1505	/// ],
1506	/// );
1507	///
1508	/// // Missing keys result in None
1509	/// let got = libraries.get_many_mut([
1510	/// "Athenæum",
1511	/// "New York Public Library",
1512	/// ]);
1513	/// assert_eq!(
1514	/// got,
1515	/// [
1516	/// Some(&mut `1807`),
1517	/// None
1518	/// ]
1519	/// );
1520	/// ```
1521	///
1522	/// ```should_panic
1523	/// use hashbrown::HashMap;
1524	///
1525	/// let mut libraries = HashMap::new();
1526	/// libraries.insert("Athenæum".to_string(), `1807`);
1527	///
1528	/// // Duplicate keys panic!
1529	/// let got = libraries.get_many_mut([
1530	/// "Athenæum",
1531	/// "Athenæum",
1532	/// ]);
1533	/// ```
1534	pub fn get_many_mut<Q, const N: usize>(&mut self, ks: [&Q; N]) -> [Option<&'_ mut V>; N]
1535	where
1536	Q: Hash + Equivalent<K> + ?Sized,
1537	{
1538	self.get_many_mut_inner(ks).map(\|res\| res.map(\|(_, v)\| v))
1539	}
1540
1541	/// Attempts to get mutable references to `N` values in the map at once, without validating that
1542	/// the values are unique.
1543	///
1544	/// Returns an array of length `N` with the results of each query. `None` will be used if
1545	/// the key is missing.
1546	///
1547	/// For a safe alternative see [`get_many_mut`](`HashMap::get_many_mut`).
1548	///
1549	/// # Safety
1550	///
1551	/// Calling this method with overlapping keys is [undefined behavior]* even if the resulting*
1552	/// references are not used.
1553	///
1554	/// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
1555	///
1556	/// # Examples
1557	///
1558	/// ```
1559	/// use hashbrown::HashMap;
1560	///
1561	/// let mut libraries = HashMap::new();
1562	/// libraries.insert("Bodleian Library".to_string(), `1602`);
1563	/// libraries.insert("Athenæum".to_string(), `1807`);
1564	/// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), `1691`);
1565	/// libraries.insert("Library of Congress".to_string(), `1800`);
1566	///
1567	/// // SAFETY: The keys do not overlap.
1568	/// let [Some(a), Some(b)] = (unsafe { libraries.get_many_unchecked_mut([
1569	/// "Athenæum",
1570	/// "Bodleian Library",
1571	/// ]) }) else { panic!() };
1572	///
1573	/// // SAFETY: The keys do not overlap.
1574	/// let got = unsafe { libraries.get_many_unchecked_mut([
1575	/// "Athenæum",
1576	/// "Library of Congress",
1577	/// ]) };
1578	/// assert_eq!(
1579	/// got,
1580	/// [
1581	/// Some(&mut `1807`),
1582	/// Some(&mut `1800`),
1583	/// ],
1584	/// );
1585	///
1586	/// // SAFETY: The keys do not overlap.
1587	/// let got = unsafe { libraries.get_many_unchecked_mut([
1588	/// "Athenæum",
1589	/// "New York Public Library",
1590	/// ]) };
1591	/// // Missing keys result in None
1592	/// assert_eq!(got, [Some(&mut `1807`), None]);
1593	/// ```
1594	pub unsafe fn get_many_unchecked_mut<Q, const N: usize>(
1595	&mut self,
1596	ks: [&Q; N],
1597	) -> [Option<&'_ mut V>; N]
1598	where
1599	Q: Hash + Equivalent<K> + ?Sized,
1600	{
1601	self.get_many_unchecked_mut_inner(ks)
1602	.map(\|res\| res.map(\|(_, v)\| v))
1603	}
1604
1605	/// Attempts to get mutable references to `N` values in the map at once, with immutable
1606	/// references to the corresponding keys.
1607	///
1608	/// Returns an array of length `N` with the results of each query. For soundness, at most one
1609	/// mutable reference will be returned to any value. `None` will be used if the key is missing.
1610	///
1611	/// # Panics
1612	///
1613	/// Panics if any keys are overlapping.
1614	///
1615	/// # Examples
1616	///
1617	/// ```
1618	/// use hashbrown::HashMap;
1619	///
1620	/// let mut libraries = HashMap::new();
1621	/// libraries.insert("Bodleian Library".to_string(), `1602`);
1622	/// libraries.insert("Athenæum".to_string(), `1807`);
1623	/// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), `1691`);
1624	/// libraries.insert("Library of Congress".to_string(), `1800`);
1625	///
1626	/// let got = libraries.get_many_key_value_mut([
1627	/// "Bodleian Library",
1628	/// "Herzogin-Anna-Amalia-Bibliothek",
1629	/// ]);
1630	/// assert_eq!(
1631	/// got,
1632	/// [
1633	/// Some((&"Bodleian Library".to_string(), &mut `1602`)),
1634	/// Some((&"Herzogin-Anna-Amalia-Bibliothek".to_string(), &mut `1691`)),
1635	/// ],
1636	/// );
1637	/// // Missing keys result in None
1638	/// let got = libraries.get_many_key_value_mut([
1639	/// "Bodleian Library",
1640	/// "Gewandhaus",
1641	/// ]);
1642	/// assert_eq!(got, [Some((&"Bodleian Library".to_string(), &mut `1602`)), None]);
1643	/// ```
1644	///
1645	/// ```should_panic
1646	/// use hashbrown::HashMap;
1647	///
1648	/// let mut libraries = HashMap::new();
1649	/// libraries.insert("Bodleian Library".to_string(), `1602`);
1650	/// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), `1691`);
1651	///
1652	/// // Duplicate keys result in panic!
1653	/// let got = libraries.get_many_key_value_mut([
1654	/// "Bodleian Library",
1655	/// "Herzogin-Anna-Amalia-Bibliothek",
1656	/// "Herzogin-Anna-Amalia-Bibliothek",
1657	/// ]);
1658	/// ```
1659	pub fn get_many_key_value_mut<Q, const N: usize>(
1660	&mut self,
1661	ks: [&Q; N],
1662	) -> [Option<(&'_ K, &'_ mut V)>; N]
1663	where
1664	Q: Hash + Equivalent<K> + ?Sized,
1665	{
1666	self.get_many_mut_inner(ks)
1667	.map(\|res\| res.map(\|(k, v)\| (&*k, v)))
1668	}
1669
1670	/// Attempts to get mutable references to `N` values in the map at once, with immutable
1671	/// references to the corresponding keys, without validating that the values are unique.
1672	///
1673	/// Returns an array of length `N` with the results of each query. `None` will be returned if
1674	/// any of the keys are missing.
1675	///
1676	/// For a safe alternative see [`get_many_key_value_mut`](`HashMap::get_many_key_value_mut`).
1677	///
1678	/// # Safety
1679	///
1680	/// Calling this method with overlapping keys is [undefined behavior]* even if the resulting*
1681	/// references are not used.
1682	///
1683	/// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
1684	///
1685	/// # Examples
1686	///
1687	/// ```
1688	/// use hashbrown::HashMap;
1689	///
1690	/// let mut libraries = HashMap::new();
1691	/// libraries.insert("Bodleian Library".to_string(), `1602`);
1692	/// libraries.insert("Athenæum".to_string(), `1807`);
1693	/// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), `1691`);
1694	/// libraries.insert("Library of Congress".to_string(), `1800`);
1695	///
1696	/// let got = libraries.get_many_key_value_mut([
1697	/// "Bodleian Library",
1698	/// "Herzogin-Anna-Amalia-Bibliothek",
1699	/// ]);
1700	/// assert_eq!(
1701	/// got,
1702	/// [
1703	/// Some((&"Bodleian Library".to_string(), &mut `1602`)),
1704	/// Some((&"Herzogin-Anna-Amalia-Bibliothek".to_string(), &mut `1691`)),
1705	/// ],
1706	/// );
1707	/// // Missing keys result in None
1708	/// let got = libraries.get_many_key_value_mut([
1709	/// "Bodleian Library",
1710	/// "Gewandhaus",
1711	/// ]);
1712	/// assert_eq!(
1713	/// got,
1714	/// [
1715	/// Some((&"Bodleian Library".to_string(), &mut `1602`)),
1716	/// None,
1717	/// ],
1718	/// );
1719	/// ```
1720	pub unsafe fn get_many_key_value_unchecked_mut<Q, const N: usize>(
1721	&mut self,
1722	ks: [&Q; N],
1723	) -> [Option<(&'_ K, &'_ mut V)>; N]
1724	where
1725	Q: Hash + Equivalent<K> + ?Sized,
1726	{
1727	self.get_many_unchecked_mut_inner(ks)
1728	.map(\|res\| res.map(\|(k, v)\| (&*k, v)))
1729	}
1730
1731	fn get_many_mut_inner<Q, const N: usize>(&mut self, ks: [&Q; N]) -> [Option<&'_ mut (K, V)>; N]
1732	where
1733	Q: Hash + Equivalent<K> + ?Sized,
1734	{
1735	let hashes = self.build_hashes_inner(ks);
1736	self.table
1737	.get_many_mut(hashes, \|i, (k, _)\| ks[i].equivalent(k))
1738	}
1739
1740	unsafe fn get_many_unchecked_mut_inner<Q, const N: usize>(
1741	&mut self,
1742	ks: [&Q; N],
1743	) -> [Option<&'_ mut (K, V)>; N]
1744	where
1745	Q: Hash + Equivalent<K> + ?Sized,
1746	{
1747	let hashes = self.build_hashes_inner(ks);
1748	self.table
1749	.get_many_unchecked_mut(hashes, \|i, (k, _)\| ks[i].equivalent(k))
1750	}
1751
1752	fn build_hashes_inner<Q, const N: usize>(&self, ks: [&Q; N]) -> [u64; N]
1753	where
1754	Q: Hash + Equivalent<K> + ?Sized,
1755	{
1756	let mut hashes = [`0_u64`; N];
1757	for i in `0`..N {
1758	hashes[i] = make_hash::<Q, S>(&self.hash_builder, ks[i]);
1759	}
1760	hashes
1761	}
1762
1763	/// Inserts a key-value pair into the map.
1764	///
1765	/// If the map did not have this key present, [`None`] is returned.
1766	///
1767	/// If the map did have this key present, the value is updated, and the old
1768	/// value is returned. The key is not updated, though; this matters for
1769	/// types that can be `==` without being identical. See the [`std::collections`]
1770	/// [module-level documentation] for more.
1771	///
1772	/// [`None`]: https://doc.rust-lang.org/std/option/enum.Option.html#variant.None
1773	/// [`std::collections`]: https://doc.rust-lang.org/std/collections/index.html
1774	/// [module-level documentation]: https://doc.rust-lang.org/std/collections/index.html#insert-and-complex-keys
1775	///
1776	/// # Examples
1777	///
1778	/// ```
1779	/// use hashbrown::HashMap;
1780	///
1781	/// let mut map = HashMap::new();
1782	/// assert_eq!(map.insert(`37`, "a"), None);
1783	/// assert_eq!(map.is_empty(), `false`);
1784	///
1785	/// map.insert(`37`, "b");
1786	/// assert_eq!(map.insert(`37`, "c"), Some("b"));
1787	/// assert_eq!(map[&`37`], "c");
1788	/// ```
1789	#[cfg_attr(feature = "inline-more", inline)]
1790	pub fn insert(&mut self, k: K, v: V) -> Option<V> {
1791	let hash = make_hash::<K, S>(&self.hash_builder, &k);
1792	match self.find_or_find_insert_slot(hash, &k) {
1793	Ok(bucket) => Some(mem::replace(unsafe { &mut bucket.as_mut().1 }, v)),
1794	Err(slot) => {
1795	unsafe {
1796	self.table.insert_in_slot(hash, slot, (k, v));
1797	}
1798	None
1799	}
1800	}
1801	}
1802
1803	#[cfg_attr(feature = "inline-more", inline)]
1804	pub(crate) fn find_or_find_insert_slot<Q>(
1805	&mut self,
1806	hash: u64,
1807	key: &Q,
1808	) -> Result<Bucket<(K, V)>, crate::raw::InsertSlot>
1809	where
1810	Q: Equivalent<K> + ?Sized,
1811	{
1812	self.table.find_or_find_insert_slot(
1813	hash,
1814	equivalent_key(key),
1815	make_hasher(&self.hash_builder),
1816	)
1817	}
1818
1819	/// Insert a key-value pair into the map without checking
1820	/// if the key already exists in the map.
1821	///
1822	/// This operation is faster than regular insert, because it does not perform
1823	/// lookup before insertion.
1824	///
1825	/// This operation is useful during initial population of the map.
1826	/// For example, when constructing a map from another map, we know
1827	/// that keys are unique.
1828	///
1829	/// Returns a reference to the key and value just inserted.
1830	///
1831	/// # Safety
1832	///
1833	/// This operation is safe if a key does not exist in the map.
1834	///
1835	/// However, if a key exists in the map already, the behavior is unspecified:
1836	/// this operation may panic, loop forever, or any following operation with the map
1837	/// may panic, loop forever or return arbitrary result.
1838	///
1839	/// That said, this operation (and following operations) are guaranteed to
1840	/// not violate memory safety.
1841	///
1842	/// However this operation is still unsafe because the resulting `HashMap`
1843	/// may be passed to unsafe code which does expect the map to behave
1844	/// correctly, and would cause unsoundness as a result.
1845	///
1846	/// # Examples
1847	///
1848	/// ```
1849	/// use hashbrown::HashMap;
1850	///
1851	/// let mut map1 = HashMap::new();
1852	/// assert_eq!(map1.insert(`1`, "a"), None);
1853	/// assert_eq!(map1.insert(`2`, "b"), None);
1854	/// assert_eq!(map1.insert(`3`, "c"), None);
1855	/// assert_eq!(map1.len(), `3`);
1856	///
1857	/// let mut map2 = HashMap::new();
1858	///
1859	/// for (key, value) in map1.into_iter() {
1860	/// unsafe {
1861	/// map2.insert_unique_unchecked(key, value);
1862	/// }
1863	/// }
1864	///
1865	/// let (key, value) = unsafe { map2.insert_unique_unchecked(`4`, "d") };
1866	/// assert_eq!(key, &`4`);
1867	/// assert_eq!(value, &mut "d");
1868	/// *value = "e";
1869	///
1870	/// assert_eq!(map2[&`1`], "a");
1871	/// assert_eq!(map2[&`2`], "b");
1872	/// assert_eq!(map2[&`3`], "c");
1873	/// assert_eq!(map2[&`4`], "e");
1874	/// assert_eq!(map2.len(), `4`);
1875	/// ```
1876	#[cfg_attr(feature = "inline-more", inline)]
1877	pub unsafe fn insert_unique_unchecked(&mut self, k: K, v: V) -> (&K, &mut V) {
1878	let hash = make_hash::<K, S>(&self.hash_builder, &k);
1879	let bucket = self
1880	.table
1881	.insert(hash, (k, v), make_hasher::<_, V, S>(&self.hash_builder));
1882	let (k_ref, v_ref) = unsafe { bucket.as_mut() };
1883	(k_ref, v_ref)
1884	}
1885
1886	/// Tries to insert a key-value pair into the map, and returns
1887	/// a mutable reference to the value in the entry.
1888	///
1889	/// # Errors
1890	///
1891	/// If the map already had this key present, nothing is updated, and
1892	/// an error containing the occupied entry and the value is returned.
1893	///
1894	/// # Examples
1895	///
1896	/// Basic usage:
1897	///
1898	/// ```
1899	/// use hashbrown::HashMap;
1900	/// use hashbrown::hash_map::OccupiedError;
1901	///
1902	/// let mut map = HashMap::new();
1903	/// assert_eq!(map.try_insert(`37`, "a").unwrap(), &"a");
1904	///
1905	/// match map.try_insert(`37`, "b") {
1906	/// Err(OccupiedError { entry, value }) => {
1907	/// assert_eq!(entry.key(), &`37`);
1908	/// assert_eq!(entry.get(), &"a");
1909	/// assert_eq!(value, "b");
1910	/// }
1911	/// _ => panic!()
1912	/// }
1913	/// ```
1914	#[cfg_attr(feature = "inline-more", inline)]
1915	pub fn try_insert(
1916	&mut self,
1917	key: K,
1918	value: V,
1919	) -> Result<&mut V, OccupiedError<'_, K, V, S, A>> {
1920	match self.entry(key) {
1921	Entry::Occupied(entry) => Err(OccupiedError { entry, value }),
1922	Entry::Vacant(entry) => Ok(entry.insert(value)),
1923	}
1924	}
1925
1926	/// Removes a key from the map, returning the value at the key if the key
1927	/// was previously in the map. Keeps the allocated memory for reuse.
1928	///
1929	/// The key may be any borrowed form of the map's key type, but
1930	/// [`Hash`] and [`Eq`] on the borrowed form must* match those for*
1931	/// the key type.
1932	///
1933	/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
1934	/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
1935	///
1936	/// # Examples
1937	///
1938	/// ```
1939	/// use hashbrown::HashMap;
1940	///
1941	/// let mut map = HashMap::new();
1942	/// // The map is empty
1943	/// assert!(map.is_empty() && map.capacity() == `0`);
1944	///
1945	/// map.insert(`1`, "a");
1946	///
1947	/// assert_eq!(map.remove(&`1`), Some("a"));
1948	/// assert_eq!(map.remove(&`1`), None);
1949	///
1950	/// // Now map holds none elements
1951	/// assert!(map.is_empty());
1952	/// ```
1953	#[cfg_attr(feature = "inline-more", inline)]
1954	pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
1955	where
1956	Q: Hash + Equivalent<K> + ?Sized,
1957	{
1958	// Avoid `Option::map` because it bloats LLVM IR.
1959	match self.remove_entry(k) {
1960	Some((_, v)) => Some(v),
1961	None => None,
1962	}
1963	}
1964
1965	/// Removes a key from the map, returning the stored key and value if the
1966	/// key was previously in the map. Keeps the allocated memory for reuse.
1967	///
1968	/// The key may be any borrowed form of the map's key type, but
1969	/// [`Hash`] and [`Eq`] on the borrowed form must* match those for*
1970	/// the key type.
1971	///
1972	/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
1973	/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
1974	///
1975	/// # Examples
1976	///
1977	/// ```
1978	/// use hashbrown::HashMap;
1979	///
1980	/// let mut map = HashMap::new();
1981	/// // The map is empty
1982	/// assert!(map.is_empty() && map.capacity() == `0`);
1983	///
1984	/// map.insert(`1`, "a");
1985	///
1986	/// assert_eq!(map.remove_entry(&`1`), Some((`1`, "a")));
1987	/// assert_eq!(map.remove(&`1`), None);
1988	///
1989	/// // Now map hold none elements
1990	/// assert!(map.is_empty());
1991	/// ```
1992	#[cfg_attr(feature = "inline-more", inline)]
1993	pub fn remove_entry<Q>(&mut self, k: &Q) -> Option<(K, V)>
1994	where
1995	Q: Hash + Equivalent<K> + ?Sized,
1996	{
1997	let hash = make_hash::<Q, S>(&self.hash_builder, k);
1998	self.table.remove_entry(hash, equivalent_key(k))
1999	}
2000
2001	/// Returns the total amount of memory allocated internally by the hash
2002	/// set, in bytes.
2003	///
2004	/// The returned number is informational only. It is intended to be
2005	/// primarily used for memory profiling.
2006	#[inline]
2007	pub fn allocation_size(&self) -> usize {
2008	self.table.allocation_size()
2009	}
2010	}
2011
2012	impl<K, V, S, A> PartialEq for HashMap<K, V, S, A>
2013	where
2014	K: Eq + Hash,
2015	V: PartialEq,
2016	S: BuildHasher,
2017	A: Allocator,
2018	{
2019	fn eq(&self, other: &Self) -> bool {
2020	if self.len() != other.len() {
2021	return `false`;
2022	}
2023
2024	self.iter()
2025	.all(\|(key: &K, value: &V)\| other.get(key).map_or(default:`false`, \|v: &V\| value == v))
2026	}
2027	}
2028
2029	impl<K, V, S, A> Eq for HashMap<K, V, S, A>
2030	where
2031	K: Eq + Hash,
2032	V: Eq,
2033	S: BuildHasher,
2034	A: Allocator,
2035	{
2036	}
2037
2038	impl<K, V, S, A> Debug for HashMap<K, V, S, A>
2039	where
2040	K: Debug,
2041	V: Debug,
2042	A: Allocator,
2043	{
2044	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2045	f.debug_map().entries(self.iter()).finish()
2046	}
2047	}
2048
2049	impl<K, V, S, A> Default for HashMap<K, V, S, A>
2050	where
2051	S: Default,
2052	A: Default + Allocator,
2053	{
2054	/// Creates an empty `HashMap<K, V, S, A>`, with the `Default` value for the hasher and allocator.
2055	///
2056	/// # Examples
2057	///
2058	/// ```
2059	/// use hashbrown::HashMap;
2060	/// use std::collections::hash_map::RandomState;
2061	///
2062	/// // You can specify all types of HashMap, including hasher and allocator.
2063	/// // Created map is empty and don't allocate memory
2064	/// let map: HashMap<u32, String> = Default::default();
2065	/// assert_eq!(map.capacity(), `0`);
2066	/// let map: HashMap<u32, String, RandomState> = HashMap::default();
2067	/// assert_eq!(map.capacity(), `0`);
2068	/// ```
2069	#[cfg_attr(feature = "inline-more", inline)]
2070	fn default() -> Self {
2071	Self::with_hasher_in(hash_builder:Default::default(), alloc:Default::default())
2072	}
2073	}
2074
2075	impl<K, Q, V, S, A> Index<&Q> for HashMap<K, V, S, A>
2076	where
2077	K: Eq + Hash,
2078	Q: Hash + Equivalent<K> + ?Sized,
2079	S: BuildHasher,
2080	A: Allocator,
2081	{
2082	type Output = V;
2083
2084	/// Returns a reference to the value corresponding to the supplied key.
2085	///
2086	/// # Panics
2087	///
2088	/// Panics if the key is not present in the `HashMap`.
2089	///
2090	/// # Examples
2091	///
2092	/// ```
2093	/// use hashbrown::HashMap;
2094	///
2095	/// let map: HashMap<_, _> = [("a", "One"), ("b", "Two")].into();
2096	///
2097	/// assert_eq!(map[&"a"], "One");
2098	/// assert_eq!(map[&"b"], "Two");
2099	/// ```
2100	#[cfg_attr(feature = "inline-more", inline)]
2101	fn index(&self, key: &Q) -> &V {
2102	self.get(key).expect(msg:"no entry found for key")
2103	}
2104	}
2105
2106	// The default hasher is used to match the std implementation signature
2107	#[cfg(feature = "default-hasher")]
2108	impl<K, V, A, const N: usize> From<[(K, V); N]> for HashMap<K, V, DefaultHashBuilder, A>
2109	where
2110	K: Eq + Hash,
2111	A: Default + Allocator,
2112	{
2113	/// # Examples
2114	///
2115	/// ```
2116	/// use hashbrown::HashMap;
2117	///
2118	/// let map1 = HashMap::from([(1, 2), (3, 4)]);
2119	/// let map2: HashMap<_, _> = [(1, 2), (3, 4)].into();
2120	/// assert_eq!(map1, map2);
2121	/// ```
2122	fn from(arr: [(K, V); N]) -> Self {
2123	arr.into_iter().collect()
2124	}
2125	}
2126
2127	/// An iterator over the entries of a `HashMap` in arbitrary order.
2128	/// The iterator element type is `(&'a K, &'a V)`.
2129	///
2130	/// This `struct` is created by the [`iter`] method on [`HashMap`]. See its
2131	/// documentation for more.
2132	///
2133	/// [`iter`]: struct.HashMap.html#method.iter
2134	/// [`HashMap`]: struct.HashMap.html
2135	///
2136	/// # Examples
2137	///
2138	/// ```
2139	/// use hashbrown::HashMap;
2140	///
2141	/// let map: HashMap<_, _> = [(`1`, "a"), (`2`, "b"), (`3`, "c")].into();
2142	///
2143	/// let mut iter = map.iter();
2144	/// let mut vec = vec![iter.next(), iter.next(), iter.next()];
2145	///
2146	/// // The `Iter` iterator produces items in arbitrary order, so the
2147	/// // items must be sorted to test them against a sorted array.
2148	/// vec.sort_unstable();
2149	/// assert_eq!(vec, [Some((&`1`, &"a")), Some((&`2`, &"b")), Some((&`3`, &"c"))]);
2150	///
2151	/// // It is fused iterator
2152	/// assert_eq!(iter.next(), None);
2153	/// assert_eq!(iter.next(), None);
2154	/// ```
2155	pub struct Iter<'a, K, V> {
2156	inner: RawIter<(K, V)>,
2157	marker: PhantomData<(&'a K, &'a V)>,
2158	}
2159
2160	// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2161	impl<K, V> Clone for Iter<'_, K, V> {
2162	#[cfg_attr(feature = "inline-more", inline)]
2163	fn clone(&self) -> Self {
2164	Iter {
2165	inner: self.inner.clone(),
2166	marker: PhantomData,
2167	}
2168	}
2169	}
2170
2171	impl<K: Debug, V: Debug> fmt::Debug for Iter<'_, K, V> {
2172	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2173	f.debug_list().entries(self.clone()).finish()
2174	}
2175	}
2176
2177	/// A mutable iterator over the entries of a `HashMap` in arbitrary order.
2178	/// The iterator element type is `(&'a K, &'a mut V)`.
2179	///
2180	/// This `struct` is created by the [`iter_mut`] method on [`HashMap`]. See its
2181	/// documentation for more.
2182	///
2183	/// [`iter_mut`]: struct.HashMap.html#method.iter_mut
2184	/// [`HashMap`]: struct.HashMap.html
2185	///
2186	/// # Examples
2187	///
2188	/// ```
2189	/// use hashbrown::HashMap;
2190	///
2191	/// let mut map: HashMap<_, _> = [(`1`, "One".to_owned()), (`2`, "Two".into())].into();
2192	///
2193	/// let mut iter = map.iter_mut();
2194	/// iter.next().map(\|(_, v)\| v.push_str(" Mississippi"));
2195	/// iter.next().map(\|(_, v)\| v.push_str(" Mississippi"));
2196	///
2197	/// // It is fused iterator
2198	/// assert_eq!(iter.next(), None);
2199	/// assert_eq!(iter.next(), None);
2200	///
2201	/// assert_eq!(map.get(&`1`).unwrap(), &"One Mississippi".to_owned());
2202	/// assert_eq!(map.get(&`2`).unwrap(), &"Two Mississippi".to_owned());
2203	/// ```
2204	pub struct IterMut<'a, K, V> {
2205	inner: RawIter<(K, V)>,
2206	// To ensure invariance with respect to V
2207	marker: PhantomData<(&'a K, &'a mut V)>,
2208	}
2209
2210	// We override the default Send impl which has K: Sync instead of K: Send. Both
2211	// are correct, but this one is more general since it allows keys which
2212	// implement Send but not Sync.
2213	unsafe impl<K: Send, V: Send> Send for IterMut<'_, K, V> {}
2214
2215	impl<K, V> IterMut<'_, K, V> {
2216	/// Returns a iterator of references over the remaining items.
2217	#[cfg_attr(feature = "inline-more", inline)]
2218	pub(super) fn iter(&self) -> Iter<'_, K, V> {
2219	Iter {
2220	inner: self.inner.clone(),
2221	marker: PhantomData,
2222	}
2223	}
2224	}
2225
2226	/// An owning iterator over the entries of a `HashMap` in arbitrary order.
2227	/// The iterator element type is `(K, V)`.
2228	///
2229	/// This `struct` is created by the [`into_iter`] method on [`HashMap`]
2230	/// (provided by the [`IntoIterator`] trait). See its documentation for more.
2231	/// The map cannot be used after calling that method.
2232	///
2233	/// [`into_iter`]: struct.HashMap.html#method.into_iter
2234	/// [`HashMap`]: struct.HashMap.html
2235	/// [`IntoIterator`]: https://doc.rust-lang.org/core/iter/trait.IntoIterator.html
2236	///
2237	/// # Examples
2238	///
2239	/// ```
2240	/// use hashbrown::HashMap;
2241	///
2242	/// let map: HashMap<_, _> = [(`1`, "a"), (`2`, "b"), (`3`, "c")].into();
2243	///
2244	/// let mut iter = map.into_iter();
2245	/// let mut vec = vec![iter.next(), iter.next(), iter.next()];
2246	///
2247	/// // The `IntoIter` iterator produces items in arbitrary order, so the
2248	/// // items must be sorted to test them against a sorted array.
2249	/// vec.sort_unstable();
2250	/// assert_eq!(vec, [Some((`1`, "a")), Some((`2`, "b")), Some((`3`, "c"))]);
2251	///
2252	/// // It is fused iterator
2253	/// assert_eq!(iter.next(), None);
2254	/// assert_eq!(iter.next(), None);
2255	/// ```
2256	pub struct IntoIter<K, V, A: Allocator = Global> {
2257	inner: RawIntoIter<(K, V), A>,
2258	}
2259
2260	impl<K, V, A: Allocator> IntoIter<K, V, A> {
2261	/// Returns a iterator of references over the remaining items.
2262	#[cfg_attr(feature = "inline-more", inline)]
2263	pub(super) fn iter(&self) -> Iter<'_, K, V> {
2264	Iter {
2265	inner: self.inner.iter(),
2266	marker: PhantomData,
2267	}
2268	}
2269	}
2270
2271	/// An owning iterator over the keys of a `HashMap` in arbitrary order.
2272	/// The iterator element type is `K`.
2273	///
2274	/// This `struct` is created by the [`into_keys`] method on [`HashMap`].
2275	/// See its documentation for more.
2276	/// The map cannot be used after calling that method.
2277	///
2278	/// [`into_keys`]: struct.HashMap.html#method.into_keys
2279	/// [`HashMap`]: struct.HashMap.html
2280	///
2281	/// # Examples
2282	///
2283	/// ```
2284	/// use hashbrown::HashMap;
2285	///
2286	/// let map: HashMap<_, _> = [(`1`, "a"), (`2`, "b"), (`3`, "c")].into();
2287	///
2288	/// let mut keys = map.into_keys();
2289	/// let mut vec = vec![keys.next(), keys.next(), keys.next()];
2290	///
2291	/// // The `IntoKeys` iterator produces keys in arbitrary order, so the
2292	/// // keys must be sorted to test them against a sorted array.
2293	/// vec.sort_unstable();
2294	/// assert_eq!(vec, [Some(`1`), Some(`2`), Some(`3`)]);
2295	///
2296	/// // It is fused iterator
2297	/// assert_eq!(keys.next(), None);
2298	/// assert_eq!(keys.next(), None);
2299	/// ```
2300	pub struct IntoKeys<K, V, A: Allocator = Global> {
2301	inner: IntoIter<K, V, A>,
2302	}
2303
2304	impl<K, V, A: Allocator> Default for IntoKeys<K, V, A> {
2305	#[cfg_attr(feature = "inline-more", inline)]
2306	fn default() -> Self {
2307	Self {
2308	inner: Default::default(),
2309	}
2310	}
2311	}
2312	impl<K, V, A: Allocator> Iterator for IntoKeys<K, V, A> {
2313	type Item = K;
2314
2315	#[inline]
2316	fn next(&mut self) -> Option<K> {
2317	self.inner.next().map(\|(k: K, _)\| k)
2318	}
2319	#[inline]
2320	fn size_hint(&self) -> (usize, Option<usize>) {
2321	self.inner.size_hint()
2322	}
2323	#[inline]
2324	fn fold<B, F>(self, init: B, mut f: F) -> B
2325	where
2326	Self: Sized,
2327	F: FnMut(B, Self::Item) -> B,
2328	{
2329	self.inner.fold(init, \|acc: B, (k: K, _)\| f(acc, k))
2330	}
2331	}
2332
2333	impl<K, V, A: Allocator> ExactSizeIterator for IntoKeys<K, V, A> {
2334	#[inline]
2335	fn len(&self) -> usize {
2336	self.inner.len()
2337	}
2338	}
2339
2340	impl<K, V, A: Allocator> FusedIterator for IntoKeys<K, V, A> {}
2341
2342	impl<K: Debug, V: Debug, A: Allocator> fmt::Debug for IntoKeys<K, V, A> {
2343	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2344	f&mut DebugList<'_, '_>.debug_list()
2345	.entries(self.inner.iter().map(\|(k: &K, _)\| k))
2346	.finish()
2347	}
2348	}
2349
2350	/// An owning iterator over the values of a `HashMap` in arbitrary order.
2351	/// The iterator element type is `V`.
2352	///
2353	/// This `struct` is created by the [`into_values`] method on [`HashMap`].
2354	/// See its documentation for more. The map cannot be used after calling that method.
2355	///
2356	/// [`into_values`]: struct.HashMap.html#method.into_values
2357	/// [`HashMap`]: struct.HashMap.html
2358	///
2359	/// # Examples
2360	///
2361	/// ```
2362	/// use hashbrown::HashMap;
2363	///
2364	/// let map: HashMap<_, _> = [(`1`, "a"), (`2`, "b"), (`3`, "c")].into();
2365	///
2366	/// let mut values = map.into_values();
2367	/// let mut vec = vec![values.next(), values.next(), values.next()];
2368	///
2369	/// // The `IntoValues` iterator produces values in arbitrary order, so
2370	/// // the values must be sorted to test them against a sorted array.
2371	/// vec.sort_unstable();
2372	/// assert_eq!(vec, [Some("a"), Some("b"), Some("c")]);
2373	///
2374	/// // It is fused iterator
2375	/// assert_eq!(values.next(), None);
2376	/// assert_eq!(values.next(), None);
2377	/// ```
2378	pub struct IntoValues<K, V, A: Allocator = Global> {
2379	inner: IntoIter<K, V, A>,
2380	}
2381
2382	impl<K, V, A: Allocator> Default for IntoValues<K, V, A> {
2383	#[cfg_attr(feature = "inline-more", inline)]
2384	fn default() -> Self {
2385	Self {
2386	inner: Default::default(),
2387	}
2388	}
2389	}
2390	impl<K, V, A: Allocator> Iterator for IntoValues<K, V, A> {
2391	type Item = V;
2392
2393	#[inline]
2394	fn next(&mut self) -> Option<V> {
2395	self.inner.next().map(\|(_, v: V)\| v)
2396	}
2397	#[inline]
2398	fn size_hint(&self) -> (usize, Option<usize>) {
2399	self.inner.size_hint()
2400	}
2401	#[inline]
2402	fn fold<B, F>(self, init: B, mut f: F) -> B
2403	where
2404	Self: Sized,
2405	F: FnMut(B, Self::Item) -> B,
2406	{
2407	self.inner.fold(init, \|acc: B, (_, v: V)\| f(acc, v))
2408	}
2409	}
2410
2411	impl<K, V, A: Allocator> ExactSizeIterator for IntoValues<K, V, A> {
2412	#[inline]
2413	fn len(&self) -> usize {
2414	self.inner.len()
2415	}
2416	}
2417
2418	impl<K, V, A: Allocator> FusedIterator for IntoValues<K, V, A> {}
2419
2420	impl<K, V: Debug, A: Allocator> fmt::Debug for IntoValues<K, V, A> {
2421	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2422	f&mut DebugList<'_, '_>.debug_list()
2423	.entries(self.inner.iter().map(\|(_, v: &V)\| v))
2424	.finish()
2425	}
2426	}
2427
2428	/// An iterator over the keys of a `HashMap` in arbitrary order.
2429	/// The iterator element type is `&'a K`.
2430	///
2431	/// This `struct` is created by the [`keys`] method on [`HashMap`]. See its
2432	/// documentation for more.
2433	///
2434	/// [`keys`]: struct.HashMap.html#method.keys
2435	/// [`HashMap`]: struct.HashMap.html
2436	///
2437	/// # Examples
2438	///
2439	/// ```
2440	/// use hashbrown::HashMap;
2441	///
2442	/// let map: HashMap<_, _> = [(`1`, "a"), (`2`, "b"), (`3`, "c")].into();
2443	///
2444	/// let mut keys = map.keys();
2445	/// let mut vec = vec![keys.next(), keys.next(), keys.next()];
2446	///
2447	/// // The `Keys` iterator produces keys in arbitrary order, so the
2448	/// // keys must be sorted to test them against a sorted array.
2449	/// vec.sort_unstable();
2450	/// assert_eq!(vec, [Some(&`1`), Some(&`2`), Some(&`3`)]);
2451	///
2452	/// // It is fused iterator
2453	/// assert_eq!(keys.next(), None);
2454	/// assert_eq!(keys.next(), None);
2455	/// ```
2456	pub struct Keys<'a, K, V> {
2457	inner: Iter<'a, K, V>,
2458	}
2459
2460	// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2461	impl<K, V> Clone for Keys<'_, K, V> {
2462	#[cfg_attr(feature = "inline-more", inline)]
2463	fn clone(&self) -> Self {
2464	Keys {
2465	inner: self.inner.clone(),
2466	}
2467	}
2468	}
2469
2470	impl<K: Debug, V> fmt::Debug for Keys<'_, K, V> {
2471	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2472	f.debug_list().entries(self.clone()).finish()
2473	}
2474	}
2475
2476	/// An iterator over the values of a `HashMap` in arbitrary order.
2477	/// The iterator element type is `&'a V`.
2478	///
2479	/// This `struct` is created by the [`values`] method on [`HashMap`]. See its
2480	/// documentation for more.
2481	///
2482	/// [`values`]: struct.HashMap.html#method.values
2483	/// [`HashMap`]: struct.HashMap.html
2484	///
2485	/// # Examples
2486	///
2487	/// ```
2488	/// use hashbrown::HashMap;
2489	///
2490	/// let map: HashMap<_, _> = [(`1`, "a"), (`2`, "b"), (`3`, "c")].into();
2491	///
2492	/// let mut values = map.values();
2493	/// let mut vec = vec![values.next(), values.next(), values.next()];
2494	///
2495	/// // The `Values` iterator produces values in arbitrary order, so the
2496	/// // values must be sorted to test them against a sorted array.
2497	/// vec.sort_unstable();
2498	/// assert_eq!(vec, [Some(&"a"), Some(&"b"), Some(&"c")]);
2499	///
2500	/// // It is fused iterator
2501	/// assert_eq!(values.next(), None);
2502	/// assert_eq!(values.next(), None);
2503	/// ```
2504	pub struct Values<'a, K, V> {
2505	inner: Iter<'a, K, V>,
2506	}
2507
2508	// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2509	impl<K, V> Clone for Values<'_, K, V> {
2510	#[cfg_attr(feature = "inline-more", inline)]
2511	fn clone(&self) -> Self {
2512	Values {
2513	inner: self.inner.clone(),
2514	}
2515	}
2516	}
2517
2518	impl<K, V: Debug> fmt::Debug for Values<'_, K, V> {
2519	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2520	f.debug_list().entries(self.clone()).finish()
2521	}
2522	}
2523
2524	/// A draining iterator over the entries of a `HashMap` in arbitrary
2525	/// order. The iterator element type is `(K, V)`.
2526	///
2527	/// This `struct` is created by the [`drain`] method on [`HashMap`]. See its
2528	/// documentation for more.
2529	///
2530	/// [`drain`]: struct.HashMap.html#method.drain
2531	/// [`HashMap`]: struct.HashMap.html
2532	///
2533	/// # Examples
2534	///
2535	/// ```
2536	/// use hashbrown::HashMap;
2537	///
2538	/// let mut map: HashMap<_, _> = [(`1`, "a"), (`2`, "b"), (`3`, "c")].into();
2539	///
2540	/// let mut drain_iter = map.drain();
2541	/// let mut vec = vec![drain_iter.next(), drain_iter.next(), drain_iter.next()];
2542	///
2543	/// // The `Drain` iterator produces items in arbitrary order, so the
2544	/// // items must be sorted to test them against a sorted array.
2545	/// vec.sort_unstable();
2546	/// assert_eq!(vec, [Some((`1`, "a")), Some((`2`, "b")), Some((`3`, "c"))]);
2547	///
2548	/// // It is fused iterator
2549	/// assert_eq!(drain_iter.next(), None);
2550	/// assert_eq!(drain_iter.next(), None);
2551	/// ```
2552	pub struct Drain<'a, K, V, A: Allocator = Global> {
2553	inner: RawDrain<'a, (K, V), A>,
2554	}
2555
2556	impl<K, V, A: Allocator> Drain<'_, K, V, A> {
2557	/// Returns a iterator of references over the remaining items.
2558	#[cfg_attr(feature = "inline-more", inline)]
2559	pub(super) fn iter(&self) -> Iter<'_, K, V> {
2560	Iter {
2561	inner: self.inner.iter(),
2562	marker: PhantomData,
2563	}
2564	}
2565	}
2566
2567	/// A draining iterator over entries of a `HashMap` which don't satisfy the predicate
2568	/// `f(&k, &mut v)` in arbitrary order. The iterator element type is `(K, V)`.
2569	///
2570	/// This `struct` is created by the [`extract_if`] method on [`HashMap`]. See its
2571	/// documentation for more.
2572	///
2573	/// [`extract_if`]: struct.HashMap.html#method.extract_if
2574	/// [`HashMap`]: struct.HashMap.html
2575	///
2576	/// # Examples
2577	///
2578	/// ```
2579	/// use hashbrown::HashMap;
2580	///
2581	/// let mut map: HashMap<i32, &str> = [(`1`, "a"), (`2`, "b"), (`3`, "c")].into();
2582	///
2583	/// let mut extract_if = map.extract_if(\|k, _v\| k % `2` != `0`);
2584	/// let mut vec = vec![extract_if.next(), extract_if.next()];
2585	///
2586	/// // The `ExtractIf` iterator produces items in arbitrary order, so the
2587	/// // items must be sorted to test them against a sorted array.
2588	/// vec.sort_unstable();
2589	/// assert_eq!(vec, [Some((`1`, "a")),Some((`3`, "c"))]);
2590	///
2591	/// // It is fused iterator
2592	/// assert_eq!(extract_if.next(), None);
2593	/// assert_eq!(extract_if.next(), None);
2594	/// drop(extract_if);
2595	///
2596	/// assert_eq!(map.len(), `1`);
2597	/// ```
2598	#[must_use = "Iterators are lazy unless consumed"]
2599	pub struct ExtractIf<'a, K, V, F, A: Allocator = Global> {
2600	f: F,
2601	inner: RawExtractIf<'a, (K, V), A>,
2602	}
2603
2604	impl<K, V, F, A> Iterator for ExtractIf<'_, K, V, F, A>
2605	where
2606	F: FnMut(&K, &mut V) -> bool,
2607	A: Allocator,
2608	{
2609	type Item = (K, V);
2610
2611	#[cfg_attr(feature = "inline-more", inline)]
2612	fn next(&mut self) -> Option<Self::Item> {
2613	self.inner.next(\|&mut (ref k: &K, ref mut v: &mut V)\| (self.f)(k, v))
2614	}
2615
2616	#[inline]
2617	fn size_hint(&self) -> (usize, Option<usize>) {
2618	(`0`, self.inner.iter.size_hint().1)
2619	}
2620	}
2621
2622	impl<K, V, F> FusedIterator for ExtractIf<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {}
2623
2624	/// A mutable iterator over the values of a `HashMap` in arbitrary order.
2625	/// The iterator element type is `&'a mut V`.
2626	///
2627	/// This `struct` is created by the [`values_mut`] method on [`HashMap`]. See its
2628	/// documentation for more.
2629	///
2630	/// [`values_mut`]: struct.HashMap.html#method.values_mut
2631	/// [`HashMap`]: struct.HashMap.html
2632	///
2633	/// # Examples
2634	///
2635	/// ```
2636	/// use hashbrown::HashMap;
2637	///
2638	/// let mut map: HashMap<_, _> = [(`1`, "One".to_owned()), (`2`, "Two".into())].into();
2639	///
2640	/// let mut values = map.values_mut();
2641	/// values.next().map(\|v\| v.push_str(" Mississippi"));
2642	/// values.next().map(\|v\| v.push_str(" Mississippi"));
2643	///
2644	/// // It is fused iterator
2645	/// assert_eq!(values.next(), None);
2646	/// assert_eq!(values.next(), None);
2647	///
2648	/// assert_eq!(map.get(&`1`).unwrap(), &"One Mississippi".to_owned());
2649	/// assert_eq!(map.get(&`2`).unwrap(), &"Two Mississippi".to_owned());
2650	/// ```
2651	pub struct ValuesMut<'a, K, V> {
2652	inner: IterMut<'a, K, V>,
2653	}
2654
2655	/// A view into a single entry in a map, which may either be vacant or occupied.
2656	///
2657	/// This `enum` is constructed from the [`entry`] method on [`HashMap`].
2658	///
2659	/// [`HashMap`]: struct.HashMap.html
2660	/// [`entry`]: struct.HashMap.html#method.entry
2661	///
2662	/// # Examples
2663	///
2664	/// ```
2665	/// use hashbrown::hash_map::{Entry, HashMap, OccupiedEntry};
2666	///
2667	/// let mut map = HashMap::new();
2668	/// map.extend([("a", `10`), ("b", `20`), ("c", `30`)]);
2669	/// assert_eq!(map.len(), `3`);
2670	///
2671	/// // Existing key (insert)
2672	/// let entry: Entry<_, _, _> = map.entry("a");
2673	/// let _raw_o: OccupiedEntry<_, _, _> = entry.insert(`1`);
2674	/// assert_eq!(map.len(), `3`);
2675	/// // Nonexistent key (insert)
2676	/// map.entry("d").insert(`4`);
2677	///
2678	/// // Existing key (or_insert)
2679	/// let v = map.entry("b").or_insert(`2`);
2680	/// assert_eq!(std::mem::replace(v, `2`), `20`);
2681	/// // Nonexistent key (or_insert)
2682	/// map.entry("e").or_insert(`5`);
2683	///
2684	/// // Existing key (or_insert_with)
2685	/// let v = map.entry("c").or_insert_with(\|\| `3`);
2686	/// assert_eq!(std::mem::replace(v, `3`), `30`);
2687	/// // Nonexistent key (or_insert_with)
2688	/// map.entry("f").or_insert_with(\|\| `6`);
2689	///
2690	/// println!("Our HashMap: {:?}", map);
2691	///
2692	/// let mut vec: Vec<_> = map.iter().map(\|(&k, &v)\| (k, v)).collect();
2693	/// // The `Iter` iterator produces items in arbitrary order, so the
2694	/// // items must be sorted to test them against a sorted array.
2695	/// vec.sort_unstable();
2696	/// assert_eq!(vec, [("a", `1`), ("b", `2`), ("c", `3`), ("d", `4`), ("e", `5`), ("f", `6`)]);
2697	/// ```
2698	pub enum Entry<'a, K, V, S, A = Global>
2699	where
2700	A: Allocator,
2701	{
2702	/// An occupied entry.
2703	///
2704	/// # Examples
2705	///
2706	/// ```
2707	/// use hashbrown::hash_map::{Entry, HashMap};
2708	/// let mut map: HashMap<_, _> = [("a", `100`), ("b", `200`)].into();
2709	///
2710	/// match map.entry("a") {
2711	/// Entry::Vacant(_) => unreachable!(),
2712	/// Entry::Occupied(_) => { }
2713	/// }
2714	/// ```
2715	Occupied(OccupiedEntry<'a, K, V, S, A>),
2716
2717	/// A vacant entry.
2718	///
2719	/// # Examples
2720	///
2721	/// ```
2722	/// use hashbrown::hash_map::{Entry, HashMap};
2723	/// let mut map: HashMap<&str, i32> = HashMap::new();
2724	///
2725	/// match map.entry("a") {
2726	/// Entry::Occupied(_) => unreachable!(),
2727	/// Entry::Vacant(_) => { }
2728	/// }
2729	/// ```
2730	Vacant(VacantEntry<'a, K, V, S, A>),
2731	}
2732
2733	impl<K: Debug, V: Debug, S, A: Allocator> Debug for Entry<'_, K, V, S, A> {
2734	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2735	match *self {
2736	Entry::Vacant(ref v: &VacantEntry<'_, K, V, S, …>) => f.debug_tuple(name:"Entry").field(v).finish(),
2737	Entry::Occupied(ref o: &OccupiedEntry<'_, K, V, S, …>) => f.debug_tuple(name:"Entry").field(o).finish(),
2738	}
2739	}
2740	}
2741
2742	/// A view into an occupied entry in a [`HashMap`].
2743	/// It is part of the [`Entry`] and [`EntryRef`] enums.
2744	///
2745	/// # Examples
2746	///
2747	/// ```
2748	/// use hashbrown::hash_map::{Entry, HashMap, OccupiedEntry};
2749	///
2750	/// let mut map = HashMap::new();
2751	/// map.extend([("a", `10`), ("b", `20`), ("c", `30`)]);
2752	///
2753	/// let _entry_o: OccupiedEntry<_, _, _> = map.entry("a").insert(`100`);
2754	/// assert_eq!(map.len(), `3`);
2755	///
2756	/// // Existing key (insert and update)
2757	/// match map.entry("a") {
2758	/// Entry::Vacant(_) => unreachable!(),
2759	/// Entry::Occupied(mut view) => {
2760	/// assert_eq!(view.get(), &`100`);
2761	/// let v = view.get_mut();
2762	/// v = `10`;
2763	/// assert_eq!(view.insert(`1111`), `1000`);
2764	/// }
2765	/// }
2766	///
2767	/// assert_eq!(map[&"a"], `1111`);
2768	/// assert_eq!(map.len(), `3`);
2769	///
2770	/// // Existing key (take)
2771	/// match map.entry("c") {
2772	/// Entry::Vacant(_) => unreachable!(),
2773	/// Entry::Occupied(view) => {
2774	/// assert_eq!(view.remove_entry(), ("c", `30`));
2775	/// }
2776	/// }
2777	/// assert_eq!(map.get(&"c"), None);
2778	/// assert_eq!(map.len(), `2`);
2779	/// ```
2780	pub struct OccupiedEntry<'a, K, V, S = DefaultHashBuilder, A: Allocator = Global> {
2781	hash: u64,
2782	elem: Bucket<(K, V)>,
2783	table: &'a mut HashMap<K, V, S, A>,
2784	}
2785
2786	unsafe impl<K, V, S, A> Send for OccupiedEntry<'_, K, V, S, A>
2787	where
2788	K: Send,
2789	V: Send,
2790	S: Send,
2791	A: Send + Allocator,
2792	{
2793	}
2794	unsafe impl<K, V, S, A> Sync for OccupiedEntry<'_, K, V, S, A>
2795	where
2796	K: Sync,
2797	V: Sync,
2798	S: Sync,
2799	A: Sync + Allocator,
2800	{
2801	}
2802
2803	impl<K: Debug, V: Debug, S, A: Allocator> Debug for OccupiedEntry<'_, K, V, S, A> {
2804	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2805	f&mut DebugStruct<'_, '_>.debug_struct("OccupiedEntry")
2806	.field("key", self.key())
2807	.field(name:"value", self.get())
2808	.finish()
2809	}
2810	}
2811
2812	/// A view into a vacant entry in a `HashMap`.
2813	/// It is part of the [`Entry`] enum.
2814	///
2815	/// [`Entry`]: enum.Entry.html
2816	///
2817	/// # Examples
2818	///
2819	/// ```
2820	/// use hashbrown::hash_map::{Entry, HashMap, VacantEntry};
2821	///
2822	/// let mut map = HashMap::<&str, i32>::new();
2823	///
2824	/// let entry_v: VacantEntry<_, _, _> = match map.entry("a") {
2825	/// Entry::Vacant(view) => view,
2826	/// Entry::Occupied(_) => unreachable!(),
2827	/// };
2828	/// entry_v.insert(`10`);
2829	/// assert!(map[&"a"] == `10` && map.len() == `1`);
2830	///
2831	/// // Nonexistent key (insert and update)
2832	/// match map.entry("b") {
2833	/// Entry::Occupied(_) => unreachable!(),
2834	/// Entry::Vacant(view) => {
2835	/// let value = view.insert(`2`);
2836	/// assert_eq!(*value, `2`);
2837	/// *value = `20`;
2838	/// }
2839	/// }
2840	/// assert!(map[&"b"] == `20` && map.len() == `2`);
2841	/// ```
2842	pub struct VacantEntry<'a, K, V, S = DefaultHashBuilder, A: Allocator = Global> {
2843	hash: u64,
2844	key: K,
2845	table: &'a mut HashMap<K, V, S, A>,
2846	}
2847
2848	impl<K: Debug, V, S, A: Allocator> Debug for VacantEntry<'_, K, V, S, A> {
2849	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2850	f.debug_tuple(name:"VacantEntry").field(self.key()).finish()
2851	}
2852	}
2853
2854	/// A view into a single entry in a map, which may either be vacant or occupied,
2855	/// with any borrowed form of the map's key type.
2856	///
2857	///
2858	/// This `enum` is constructed from the [`entry_ref`] method on [`HashMap`].
2859	///
2860	/// [`Hash`] and [`Eq`] on the borrowed form of the map's key type must* match those*
2861	/// for the key type. It also require that key may be constructed from the borrowed
2862	/// form through the [`From`] trait.
2863	///
2864	/// [`HashMap`]: struct.HashMap.html
2865	/// [`entry_ref`]: struct.HashMap.html#method.entry_ref
2866	/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
2867	/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
2868	/// [`From`]: https://doc.rust-lang.org/std/convert/trait.From.html
2869	///
2870	/// # Examples
2871	///
2872	/// ```
2873	/// use hashbrown::hash_map::{EntryRef, HashMap, OccupiedEntry};
2874	///
2875	/// let mut map = HashMap::new();
2876	/// map.extend([("a".to_owned(), `10`), ("b".into(), `20`), ("c".into(), `30`)]);
2877	/// assert_eq!(map.len(), `3`);
2878	///
2879	/// // Existing key (insert)
2880	/// let key = String::from("a");
2881	/// let entry: EntryRef<_, _, _, _> = map.entry_ref(&key);
2882	/// let _raw_o: OccupiedEntry<_, _, _, _> = entry.insert(`1`);
2883	/// assert_eq!(map.len(), `3`);
2884	/// // Nonexistent key (insert)
2885	/// map.entry_ref("d").insert(`4`);
2886	///
2887	/// // Existing key (or_insert)
2888	/// let v = map.entry_ref("b").or_insert(`2`);
2889	/// assert_eq!(std::mem::replace(v, `2`), `20`);
2890	/// // Nonexistent key (or_insert)
2891	/// map.entry_ref("e").or_insert(`5`);
2892	///
2893	/// // Existing key (or_insert_with)
2894	/// let v = map.entry_ref("c").or_insert_with(\|\| `3`);
2895	/// assert_eq!(std::mem::replace(v, `3`), `30`);
2896	/// // Nonexistent key (or_insert_with)
2897	/// map.entry_ref("f").or_insert_with(\|\| `6`);
2898	///
2899	/// println!("Our HashMap: {:?}", map);
2900	///
2901	/// for (key, value) in ["a", "b", "c", "d", "e", "f"].into_iter().zip(`1`..=`6`) {
2902	/// assert_eq!(map[key], value)
2903	/// }
2904	/// assert_eq!(map.len(), `6`);
2905	/// ```
2906	pub enum EntryRef<'a, 'b, K, Q: ?Sized, V, S, A = Global>
2907	where
2908	A: Allocator,
2909	{
2910	/// An occupied entry.
2911	///
2912	/// # Examples
2913	///
2914	/// ```
2915	/// use hashbrown::hash_map::{EntryRef, HashMap};
2916	/// let mut map: HashMap<_, _> = [("a".to_owned(), `100`), ("b".into(), `200`)].into();
2917	///
2918	/// match map.entry_ref("a") {
2919	/// EntryRef::Vacant(_) => unreachable!(),
2920	/// EntryRef::Occupied(_) => { }
2921	/// }
2922	/// ```
2923	Occupied(OccupiedEntry<'a, K, V, S, A>),
2924
2925	/// A vacant entry.
2926	///
2927	/// # Examples
2928	///
2929	/// ```
2930	/// use hashbrown::hash_map::{EntryRef, HashMap};
2931	/// let mut map: HashMap<String, i32> = HashMap::new();
2932	///
2933	/// match map.entry_ref("a") {
2934	/// EntryRef::Occupied(_) => unreachable!(),
2935	/// EntryRef::Vacant(_) => { }
2936	/// }
2937	/// ```
2938	Vacant(VacantEntryRef<'a, 'b, K, Q, V, S, A>),
2939	}
2940
2941	impl<K, Q, V, S, A> Debug for EntryRef<'_, '_, K, Q, V, S, A>
2942	where
2943	K: Debug + Borrow<Q>,
2944	Q: Debug + ?Sized,
2945	V: Debug,
2946	A: Allocator,
2947	{
2948	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2949	match *self {
2950	EntryRef::Vacant(ref v: &VacantEntryRef<'_, '_, K, …, …, …, …>) => f.debug_tuple(name:"EntryRef").field(v).finish(),
2951	EntryRef::Occupied(ref o: &OccupiedEntry<'_, K, V, S, …>) => f.debug_tuple(name:"EntryRef").field(o).finish(),
2952	}
2953	}
2954	}
2955
2956	/// A view into a vacant entry in a `HashMap`.
2957	/// It is part of the [`EntryRef`] enum.
2958	///
2959	/// [`EntryRef`]: enum.EntryRef.html
2960	///
2961	/// # Examples
2962	///
2963	/// ```
2964	/// use hashbrown::hash_map::{EntryRef, HashMap, VacantEntryRef};
2965	///
2966	/// let mut map = HashMap::<String, i32>::new();
2967	///
2968	/// let entry_v: VacantEntryRef<_, _, _, _> = match map.entry_ref("a") {
2969	/// EntryRef::Vacant(view) => view,
2970	/// EntryRef::Occupied(_) => unreachable!(),
2971	/// };
2972	/// entry_v.insert(`10`);
2973	/// assert!(map["a"] == `10` && map.len() == `1`);
2974	///
2975	/// // Nonexistent key (insert and update)
2976	/// match map.entry_ref("b") {
2977	/// EntryRef::Occupied(_) => unreachable!(),
2978	/// EntryRef::Vacant(view) => {
2979	/// let value = view.insert(`2`);
2980	/// assert_eq!(*value, `2`);
2981	/// *value = `20`;
2982	/// }
2983	/// }
2984	/// assert!(map["b"] == `20` && map.len() == `2`);
2985	/// ```
2986	pub struct VacantEntryRef<'a, 'b, K, Q: ?Sized, V, S, A: Allocator = Global> {
2987	hash: u64,
2988	key: &'b Q,
2989	table: &'a mut HashMap<K, V, S, A>,
2990	}
2991
2992	impl<K, Q, V, S, A> Debug for VacantEntryRef<'_, '_, K, Q, V, S, A>
2993	where
2994	K: Borrow<Q>,
2995	Q: Debug + ?Sized,
2996	A: Allocator,
2997	{
2998	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2999	f.debug_tuple(name:"VacantEntryRef").field(&self.key()).finish()
3000	}
3001	}
3002
3003	/// The error returned by [`try_insert`](HashMap::try_insert) when the key already exists.
3004	///
3005	/// Contains the occupied entry, and the value that was not inserted.
3006	///
3007	/// # Examples
3008	///
3009	/// ```
3010	/// use hashbrown::hash_map::{HashMap, OccupiedError};
3011	///
3012	/// let mut map: HashMap<_, _> = [("a", `10`), ("b", `20`)].into();
3013	///
3014	/// // try_insert method returns mutable reference to the value if keys are vacant,
3015	/// // but if the map did have key present, nothing is updated, and the provided
3016	/// // value is returned inside `Err(_)` variant
3017	/// match map.try_insert("a", `100`) {
3018	/// Err(OccupiedError { mut entry, value }) => {
3019	/// assert_eq!(entry.key(), &"a");
3020	/// assert_eq!(value, `100`);
3021	/// assert_eq!(entry.insert(`100`), `10`)
3022	/// }
3023	/// _ => unreachable!(),
3024	/// }
3025	/// assert_eq!(map[&"a"], `100`);
3026	/// ```
3027	pub struct OccupiedError<'a, K, V, S, A: Allocator = Global> {
3028	/// The entry in the map that was already occupied.
3029	pub entry: OccupiedEntry<'a, K, V, S, A>,
3030	/// The value which was not inserted, because the entry was already occupied.
3031	pub value: V,
3032	}
3033
3034	impl<K: Debug, V: Debug, S, A: Allocator> Debug for OccupiedError<'_, K, V, S, A> {
3035	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3036	f&mut DebugStruct<'_, '_>.debug_struct("OccupiedError")
3037	.field("key", self.entry.key())
3038	.field("old_value", self.entry.get())
3039	.field(name:"new_value", &self.value)
3040	.finish()
3041	}
3042	}
3043
3044	impl<K: Debug, V: Debug, S, A: Allocator> fmt::Display for OccupiedError<'_, K, V, S, A> {
3045	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3046	write!(
3047	f,
3048	"failed to insert {:?}, key {:?} already exists with value {:?}",
3049	self.value,
3050	self.entry.key(),
3051	self.entry.get(),
3052	)
3053	}
3054	}
3055
3056	impl<'a, K, V, S, A: Allocator> IntoIterator for &'a HashMap<K, V, S, A> {
3057	type Item = (&'a K, &'a V);
3058	type IntoIter = Iter<'a, K, V>;
3059
3060	/// Creates an iterator over the entries of a `HashMap` in arbitrary order.
3061	/// The iterator element type is `(&'a K, &'a V)`.
3062	///
3063	/// Return the same `Iter` struct as by the [`iter`] method on [`HashMap`].
3064	///
3065	/// [`iter`]: struct.HashMap.html#method.iter
3066	/// [`HashMap`]: struct.HashMap.html
3067	///
3068	/// # Examples
3069	///
3070	/// ```
3071	/// use hashbrown::HashMap;
3072	/// let map_one: HashMap<_, _> = [(`1`, "a"), (`2`, "b"), (`3`, "c")].into();
3073	/// let mut map_two = HashMap::new();
3074	///
3075	/// for (key, value) in &map_one {
3076	/// println!("Key: {}, Value: {}", key, value);
3077	/// map_two.insert(key, value);
3078	/// }
3079	///
3080	/// assert_eq!(map_one, map_two);
3081	/// ```
3082	#[cfg_attr(feature = "inline-more", inline)]
3083	fn into_iter(self) -> Iter<'a, K, V> {
3084	self.iter()
3085	}
3086	}
3087
3088	impl<'a, K, V, S, A: Allocator> IntoIterator for &'a mut HashMap<K, V, S, A> {
3089	type Item = (&'a K, &'a mut V);
3090	type IntoIter = IterMut<'a, K, V>;
3091
3092	/// Creates an iterator over the entries of a `HashMap` in arbitrary order
3093	/// with mutable references to the values. The iterator element type is
3094	/// `(&'a K, &'a mut V)`.
3095	///
3096	/// Return the same `IterMut` struct as by the [`iter_mut`] method on
3097	/// [`HashMap`].
3098	///
3099	/// [`iter_mut`]: struct.HashMap.html#method.iter_mut
3100	/// [`HashMap`]: struct.HashMap.html
3101	///
3102	/// # Examples
3103	///
3104	/// ```
3105	/// use hashbrown::HashMap;
3106	/// let mut map: HashMap<_, _> = [("a", `1`), ("b", `2`), ("c", `3`)].into();
3107	///
3108	/// for (key, value) in &mut map {
3109	/// println!("Key: {}, Value: {}", key, value);
3110	/// value = `2`;
3111	/// }
3112	///
3113	/// let mut vec = map.iter().collect::<Vec<_>>();
3114	/// // The `Iter` iterator produces items in arbitrary order, so the
3115	/// // items must be sorted to test them against a sorted array.
3116	/// vec.sort_unstable();
3117	/// assert_eq!(vec, [(&"a", &`2`), (&"b", &`4`), (&"c", &`6`)]);
3118	/// ```
3119	#[cfg_attr(feature = "inline-more", inline)]
3120	fn into_iter(self) -> IterMut<'a, K, V> {
3121	self.iter_mut()
3122	}
3123	}
3124
3125	impl<K, V, S, A: Allocator> IntoIterator for HashMap<K, V, S, A> {
3126	type Item = (K, V);
3127	type IntoIter = IntoIter<K, V, A>;
3128
3129	/// Creates a consuming iterator, that is, one that moves each key-value
3130	/// pair out of the map in arbitrary order. The map cannot be used after
3131	/// calling this.
3132	///
3133	/// # Examples
3134	///
3135	/// ```
3136	/// use hashbrown::HashMap;
3137	///
3138	/// let map: HashMap<_, _> = [("a", `1`), ("b", `2`), ("c", `3`)].into();
3139	///
3140	/// // Not possible with .iter()
3141	/// let mut vec: Vec<(&str, i32)> = map.into_iter().collect();
3142	/// // The `IntoIter` iterator produces items in arbitrary order, so
3143	/// // the items must be sorted to test them against a sorted array.
3144	/// vec.sort_unstable();
3145	/// assert_eq!(vec, [("a", `1`), ("b", `2`), ("c", `3`)]);
3146	/// ```
3147	#[cfg_attr(feature = "inline-more", inline)]
3148	fn into_iter(self) -> IntoIter<K, V, A> {
3149	IntoIter {
3150	inner: self.table.into_iter(),
3151	}
3152	}
3153	}
3154
3155	impl<K, V> Default for Iter<'_, K, V> {
3156	#[cfg_attr(feature = "inline-more", inline)]
3157	fn default() -> Self {
3158	Self {
3159	inner: Default::default(),
3160	marker: PhantomData,
3161	}
3162	}
3163	}
3164	impl<'a, K, V> Iterator for Iter<'a, K, V> {
3165	type Item = (&'a K, &'a V);
3166
3167	#[cfg_attr(feature = "inline-more", inline)]
3168	fn next(&mut self) -> Option<(&'a K, &'a V)> {
3169	// Avoid `Option::map` because it bloats LLVM IR.
3170	match self.inner.next() {
3171	Some(x) => unsafe {
3172	let r = x.as_ref();
3173	Some((&r.0, &r.1))
3174	},
3175	None => None,
3176	}
3177	}
3178	#[cfg_attr(feature = "inline-more", inline)]
3179	fn size_hint(&self) -> (usize, Option<usize>) {
3180	self.inner.size_hint()
3181	}
3182	#[cfg_attr(feature = "inline-more", inline)]
3183	fn fold<B, F>(self, init: B, mut f: F) -> B
3184	where
3185	Self: Sized,
3186	F: FnMut(B, Self::Item) -> B,
3187	{
3188	self.inner.fold(init, \|acc, x\| unsafe {
3189	let (k, v) = x.as_ref();
3190	f(acc, (k, v))
3191	})
3192	}
3193	}
3194	impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
3195	#[cfg_attr(feature = "inline-more", inline)]
3196	fn len(&self) -> usize {
3197	self.inner.len()
3198	}
3199	}
3200
3201	impl<K, V> FusedIterator for Iter<'_, K, V> {}
3202
3203	impl<K, V> Default for IterMut<'_, K, V> {
3204	#[cfg_attr(feature = "inline-more", inline)]
3205	fn default() -> Self {
3206	Self {
3207	inner: Default::default(),
3208	marker: PhantomData,
3209	}
3210	}
3211	}
3212	impl<'a, K, V> Iterator for IterMut<'a, K, V> {
3213	type Item = (&'a K, &'a mut V);
3214
3215	#[cfg_attr(feature = "inline-more", inline)]
3216	fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
3217	// Avoid `Option::map` because it bloats LLVM IR.
3218	match self.inner.next() {
3219	Some(x) => unsafe {
3220	let r = x.as_mut();
3221	Some((&r.0, &mut r.1))
3222	},
3223	None => None,
3224	}
3225	}
3226	#[cfg_attr(feature = "inline-more", inline)]
3227	fn size_hint(&self) -> (usize, Option<usize>) {
3228	self.inner.size_hint()
3229	}
3230	#[cfg_attr(feature = "inline-more", inline)]
3231	fn fold<B, F>(self, init: B, mut f: F) -> B
3232	where
3233	Self: Sized,
3234	F: FnMut(B, Self::Item) -> B,
3235	{
3236	self.inner.fold(init, \|acc, x\| unsafe {
3237	let (k, v) = x.as_mut();
3238	f(acc, (k, v))
3239	})
3240	}
3241	}
3242	impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
3243	#[cfg_attr(feature = "inline-more", inline)]
3244	fn len(&self) -> usize {
3245	self.inner.len()
3246	}
3247	}
3248	impl<K, V> FusedIterator for IterMut<'_, K, V> {}
3249
3250	impl<K, V> fmt::Debug for IterMut<'_, K, V>
3251	where
3252	K: fmt::Debug,
3253	V: fmt::Debug,
3254	{
3255	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3256	f.debug_list().entries(self.iter()).finish()
3257	}
3258	}
3259
3260	impl<K, V, A: Allocator> Default for IntoIter<K, V, A> {
3261	#[cfg_attr(feature = "inline-more", inline)]
3262	fn default() -> Self {
3263	Self {
3264	inner: Default::default(),
3265	}
3266	}
3267	}
3268	impl<K, V, A: Allocator> Iterator for IntoIter<K, V, A> {
3269	type Item = (K, V);
3270
3271	#[cfg_attr(feature = "inline-more", inline)]
3272	fn next(&mut self) -> Option<(K, V)> {
3273	self.inner.next()
3274	}
3275	#[cfg_attr(feature = "inline-more", inline)]
3276	fn size_hint(&self) -> (usize, Option<usize>) {
3277	self.inner.size_hint()
3278	}
3279	#[cfg_attr(feature = "inline-more", inline)]
3280	fn fold<B, F>(self, init: B, f: F) -> B
3281	where
3282	Self: Sized,
3283	F: FnMut(B, Self::Item) -> B,
3284	{
3285	self.inner.fold(init, f)
3286	}
3287	}
3288	impl<K, V, A: Allocator> ExactSizeIterator for IntoIter<K, V, A> {
3289	#[cfg_attr(feature = "inline-more", inline)]
3290	fn len(&self) -> usize {
3291	self.inner.len()
3292	}
3293	}
3294	impl<K, V, A: Allocator> FusedIterator for IntoIter<K, V, A> {}
3295
3296	impl<K: Debug, V: Debug, A: Allocator> fmt::Debug for IntoIter<K, V, A> {
3297	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3298	f.debug_list().entries(self.iter()).finish()
3299	}
3300	}
3301
3302	impl<K, V> Default for Keys<'_, K, V> {
3303	#[cfg_attr(feature = "inline-more", inline)]
3304	fn default() -> Self {
3305	Self {
3306	inner: Default::default(),
3307	}
3308	}
3309	}
3310	impl<'a, K, V> Iterator for Keys<'a, K, V> {
3311	type Item = &'a K;
3312
3313	#[cfg_attr(feature = "inline-more", inline)]
3314	fn next(&mut self) -> Option<&'a K> {
3315	// Avoid `Option::map` because it bloats LLVM IR.
3316	match self.inner.next() {
3317	Some((k: &'a K, _)) => Some(k),
3318	None => None,
3319	}
3320	}
3321	#[cfg_attr(feature = "inline-more", inline)]
3322	fn size_hint(&self) -> (usize, Option<usize>) {
3323	self.inner.size_hint()
3324	}
3325	#[cfg_attr(feature = "inline-more", inline)]
3326	fn fold<B, F>(self, init: B, mut f: F) -> B
3327	where
3328	Self: Sized,
3329	F: FnMut(B, Self::Item) -> B,
3330	{
3331	self.inner.fold(init, \|acc: B, (k: &'a K, _)\| f(acc, k))
3332	}
3333	}
3334	impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
3335	#[cfg_attr(feature = "inline-more", inline)]
3336	fn len(&self) -> usize {
3337	self.inner.len()
3338	}
3339	}
3340	impl<K, V> FusedIterator for Keys<'_, K, V> {}
3341
3342	impl<K, V> Default for Values<'_, K, V> {
3343	#[cfg_attr(feature = "inline-more", inline)]
3344	fn default() -> Self {
3345	Self {
3346	inner: Default::default(),
3347	}
3348	}
3349	}
3350	impl<'a, K, V> Iterator for Values<'a, K, V> {
3351	type Item = &'a V;
3352
3353	#[cfg_attr(feature = "inline-more", inline)]
3354	fn next(&mut self) -> Option<&'a V> {
3355	// Avoid `Option::map` because it bloats LLVM IR.
3356	match self.inner.next() {
3357	Some((_, v: &'a V)) => Some(v),
3358	None => None,
3359	}
3360	}
3361	#[cfg_attr(feature = "inline-more", inline)]
3362	fn size_hint(&self) -> (usize, Option<usize>) {
3363	self.inner.size_hint()
3364	}
3365	#[cfg_attr(feature = "inline-more", inline)]
3366	fn fold<B, F>(self, init: B, mut f: F) -> B
3367	where
3368	Self: Sized,
3369	F: FnMut(B, Self::Item) -> B,
3370	{
3371	self.inner.fold(init, \|acc: B, (_, v: &'a V)\| f(acc, v))
3372	}
3373	}
3374	impl<K, V> ExactSizeIterator for Values<'_, K, V> {
3375	#[cfg_attr(feature = "inline-more", inline)]
3376	fn len(&self) -> usize {
3377	self.inner.len()
3378	}
3379	}
3380	impl<K, V> FusedIterator for Values<'_, K, V> {}
3381
3382	impl<K, V> Default for ValuesMut<'_, K, V> {
3383	#[cfg_attr(feature = "inline-more", inline)]
3384	fn default() -> Self {
3385	Self {
3386	inner: Default::default(),
3387	}
3388	}
3389	}
3390	impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
3391	type Item = &'a mut V;
3392
3393	#[cfg_attr(feature = "inline-more", inline)]
3394	fn next(&mut self) -> Option<&'a mut V> {
3395	// Avoid `Option::map` because it bloats LLVM IR.
3396	match self.inner.next() {
3397	Some((_, v: &'a mut V)) => Some(v),
3398	None => None,
3399	}
3400	}
3401	#[cfg_attr(feature = "inline-more", inline)]
3402	fn size_hint(&self) -> (usize, Option<usize>) {
3403	self.inner.size_hint()
3404	}
3405	#[cfg_attr(feature = "inline-more", inline)]
3406	fn fold<B, F>(self, init: B, mut f: F) -> B
3407	where
3408	Self: Sized,
3409	F: FnMut(B, Self::Item) -> B,
3410	{
3411	self.inner.fold(init, \|acc: B, (_, v: &'a mut V)\| f(acc, v))
3412	}
3413	}
3414	impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
3415	#[cfg_attr(feature = "inline-more", inline)]
3416	fn len(&self) -> usize {
3417	self.inner.len()
3418	}
3419	}
3420	impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
3421
3422	impl<K, V: Debug> fmt::Debug for ValuesMut<'_, K, V> {
3423	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3424	f&mut DebugList<'_, '_>.debug_list()
3425	.entries(self.inner.iter().map(\|(_, val: &V)\| val))
3426	.finish()
3427	}
3428	}
3429
3430	impl<K, V, A: Allocator> Iterator for Drain<'_, K, V, A> {
3431	type Item = (K, V);
3432
3433	#[cfg_attr(feature = "inline-more", inline)]
3434	fn next(&mut self) -> Option<(K, V)> {
3435	self.inner.next()
3436	}
3437	#[cfg_attr(feature = "inline-more", inline)]
3438	fn size_hint(&self) -> (usize, Option<usize>) {
3439	self.inner.size_hint()
3440	}
3441	#[cfg_attr(feature = "inline-more", inline)]
3442	fn fold<B, F>(self, init: B, f: F) -> B
3443	where
3444	Self: Sized,
3445	F: FnMut(B, Self::Item) -> B,
3446	{
3447	self.inner.fold(init, f)
3448	}
3449	}
3450	impl<K, V, A: Allocator> ExactSizeIterator for Drain<'_, K, V, A> {
3451	#[cfg_attr(feature = "inline-more", inline)]
3452	fn len(&self) -> usize {
3453	self.inner.len()
3454	}
3455	}
3456	impl<K, V, A: Allocator> FusedIterator for Drain<'_, K, V, A> {}
3457
3458	impl<K, V, A> fmt::Debug for Drain<'_, K, V, A>
3459	where
3460	K: fmt::Debug,
3461	V: fmt::Debug,
3462	A: Allocator,
3463	{
3464	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3465	f.debug_list().entries(self.iter()).finish()
3466	}
3467	}
3468
3469	impl<'a, K, V, S, A: Allocator> Entry<'a, K, V, S, A> {
3470	/// Sets the value of the entry, and returns an `OccupiedEntry`.
3471	///
3472	/// # Examples
3473	///
3474	/// ```
3475	/// use hashbrown::HashMap;
3476	///
3477	/// let mut map: HashMap<&str, u32> = HashMap::new();
3478	/// let entry = map.entry("horseyland").insert(`37`);
3479	///
3480	/// assert_eq!(entry.key(), &"horseyland");
3481	/// ```
3482	#[cfg_attr(feature = "inline-more", inline)]
3483	pub fn insert(self, value: V) -> OccupiedEntry<'a, K, V, S, A>
3484	where
3485	K: Hash,
3486	S: BuildHasher,
3487	{
3488	match self {
3489	Entry::Occupied(mut entry) => {
3490	entry.insert(value);
3491	entry
3492	}
3493	Entry::Vacant(entry) => entry.insert_entry(value),
3494	}
3495	}
3496
3497	/// Ensures a value is in the entry by inserting the default if empty, and returns
3498	/// a mutable reference to the value in the entry.
3499	///
3500	/// # Examples
3501	///
3502	/// ```
3503	/// use hashbrown::HashMap;
3504	///
3505	/// let mut map: HashMap<&str, u32> = HashMap::new();
3506	///
3507	/// // nonexistent key
3508	/// map.entry("poneyland").or_insert(`3`);
3509	/// assert_eq!(map["poneyland"], `3`);
3510	///
3511	/// // existing key
3512	/// map.entry("poneyland").or_insert(`10`) = `2`;
3513	/// assert_eq!(map["poneyland"], `6`);
3514	/// ```
3515	#[cfg_attr(feature = "inline-more", inline)]
3516	pub fn or_insert(self, default: V) -> &'a mut V
3517	where
3518	K: Hash,
3519	S: BuildHasher,
3520	{
3521	match self {
3522	Entry::Occupied(entry) => entry.into_mut(),
3523	Entry::Vacant(entry) => entry.insert(default),
3524	}
3525	}
3526
3527	/// Ensures a value is in the entry by inserting the result of the default function if empty,
3528	/// and returns a mutable reference to the value in the entry.
3529	///
3530	/// # Examples
3531	///
3532	/// ```
3533	/// use hashbrown::HashMap;
3534	///
3535	/// let mut map: HashMap<&str, u32> = HashMap::new();
3536	///
3537	/// // nonexistent key
3538	/// map.entry("poneyland").or_insert_with(\|\| `3`);
3539	/// assert_eq!(map["poneyland"], `3`);
3540	///
3541	/// // existing key
3542	/// map.entry("poneyland").or_insert_with(\|\| `10`) = `2`;
3543	/// assert_eq!(map["poneyland"], `6`);
3544	/// ```
3545	#[cfg_attr(feature = "inline-more", inline)]
3546	pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V
3547	where
3548	K: Hash,
3549	S: BuildHasher,
3550	{
3551	match self {
3552	Entry::Occupied(entry) => entry.into_mut(),
3553	Entry::Vacant(entry) => entry.insert(default()),
3554	}
3555	}
3556
3557	/// Ensures a value is in the entry by inserting, if empty, the result of the default function.
3558	/// This method allows for generating key-derived values for insertion by providing the default
3559	/// function a reference to the key that was moved during the `.entry(key)` method call.
3560	///
3561	/// The reference to the moved key is provided so that cloning or copying the key is
3562	/// unnecessary, unlike with `.or_insert_with(\|\| ... )`.
3563	///
3564	/// # Examples
3565	///
3566	/// ```
3567	/// use hashbrown::HashMap;
3568	///
3569	/// let mut map: HashMap<&str, usize> = HashMap::new();
3570	///
3571	/// // nonexistent key
3572	/// map.entry("poneyland").or_insert_with_key(\|key\| key.chars().count());
3573	/// assert_eq!(map["poneyland"], `9`);
3574	///
3575	/// // existing key
3576	/// map.entry("poneyland").or_insert_with_key(\|key\| key.chars().count() `10`) *= `2`;
3577	/// assert_eq!(map["poneyland"], `18`);
3578	/// ```
3579	#[cfg_attr(feature = "inline-more", inline)]
3580	pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V
3581	where
3582	K: Hash,
3583	S: BuildHasher,
3584	{
3585	match self {
3586	Entry::Occupied(entry) => entry.into_mut(),
3587	Entry::Vacant(entry) => {
3588	let value = default(entry.key());
3589	entry.insert(value)
3590	}
3591	}
3592	}
3593
3594	/// Returns a reference to this entry's key.
3595	///
3596	/// # Examples
3597	///
3598	/// ```
3599	/// use hashbrown::HashMap;
3600	///
3601	/// let mut map: HashMap<&str, u32> = HashMap::new();
3602	/// map.entry("poneyland").or_insert(`3`);
3603	/// // existing key
3604	/// assert_eq!(map.entry("poneyland").key(), &"poneyland");
3605	/// // nonexistent key
3606	/// assert_eq!(map.entry("horseland").key(), &"horseland");
3607	/// ```
3608	#[cfg_attr(feature = "inline-more", inline)]
3609	pub fn key(&self) -> &K {
3610	match *self {
3611	Entry::Occupied(ref entry) => entry.key(),
3612	Entry::Vacant(ref entry) => entry.key(),
3613	}
3614	}
3615
3616	/// Provides in-place mutable access to an occupied entry before any
3617	/// potential inserts into the map.
3618	///
3619	/// # Examples
3620	///
3621	/// ```
3622	/// use hashbrown::HashMap;
3623	///
3624	/// let mut map: HashMap<&str, u32> = HashMap::new();
3625	///
3626	/// map.entry("poneyland")
3627	/// .and_modify(\|e\| { *e += `1` })
3628	/// .or_insert(`42`);
3629	/// assert_eq!(map["poneyland"], `42`);
3630	///
3631	/// map.entry("poneyland")
3632	/// .and_modify(\|e\| { *e += `1` })
3633	/// .or_insert(`42`);
3634	/// assert_eq!(map["poneyland"], `43`);
3635	/// ```
3636	#[cfg_attr(feature = "inline-more", inline)]
3637	pub fn and_modify<F>(self, f: F) -> Self
3638	where
3639	F: FnOnce(&mut V),
3640	{
3641	match self {
3642	Entry::Occupied(mut entry) => {
3643	f(entry.get_mut());
3644	Entry::Occupied(entry)
3645	}
3646	Entry::Vacant(entry) => Entry::Vacant(entry),
3647	}
3648	}
3649
3650	/// Provides shared access to the key and owned access to the value of
3651	/// an occupied entry and allows to replace or remove it based on the
3652	/// value of the returned option.
3653	///
3654	/// # Examples
3655	///
3656	/// ```
3657	/// use hashbrown::HashMap;
3658	/// use hashbrown::hash_map::Entry;
3659	///
3660	/// let mut map: HashMap<&str, u32> = HashMap::new();
3661	///
3662	/// let entry = map
3663	/// .entry("poneyland")
3664	/// .and_replace_entry_with(\|_k, _v\| panic!());
3665	///
3666	/// match entry {
3667	/// Entry::Vacant(e) => {
3668	/// assert_eq!(e.key(), &"poneyland");
3669	/// }
3670	/// Entry::Occupied(_) => panic!(),
3671	/// }
3672	///
3673	/// map.insert("poneyland", `42`);
3674	///
3675	/// let entry = map
3676	/// .entry("poneyland")
3677	/// .and_replace_entry_with(\|k, v\| {
3678	/// assert_eq!(k, &"poneyland");
3679	/// assert_eq!(v, `42`);
3680	/// Some(v + `1`)
3681	/// });
3682	///
3683	/// match entry {
3684	/// Entry::Occupied(e) => {
3685	/// assert_eq!(e.key(), &"poneyland");
3686	/// assert_eq!(e.get(), &`43`);
3687	/// }
3688	/// Entry::Vacant(_) => panic!(),
3689	/// }
3690	///
3691	/// assert_eq!(map["poneyland"], `43`);
3692	///
3693	/// let entry = map
3694	/// .entry("poneyland")
3695	/// .and_replace_entry_with(\|_k, _v\| None);
3696	///
3697	/// match entry {
3698	/// Entry::Vacant(e) => assert_eq!(e.key(), &"poneyland"),
3699	/// Entry::Occupied(_) => panic!(),
3700	/// }
3701	///
3702	/// assert!(!map.contains_key("poneyland"));
3703	/// ```
3704	#[cfg_attr(feature = "inline-more", inline)]
3705	pub fn and_replace_entry_with<F>(self, f: F) -> Self
3706	where
3707	F: FnOnce(&K, V) -> Option<V>,
3708	{
3709	match self {
3710	Entry::Occupied(entry) => entry.replace_entry_with(f),
3711	Entry::Vacant(_) => self,
3712	}
3713	}
3714	}
3715
3716	impl<'a, K, V: Default, S, A: Allocator> Entry<'a, K, V, S, A> {
3717	/// Ensures a value is in the entry by inserting the default value if empty,
3718	/// and returns a mutable reference to the value in the entry.
3719	///
3720	/// # Examples
3721	///
3722	/// ```
3723	/// use hashbrown::HashMap;
3724	///
3725	/// let mut map: HashMap<&str, Option<u32>> = HashMap::new();
3726	///
3727	/// // nonexistent key
3728	/// map.entry("poneyland").or_default();
3729	/// assert_eq!(map["poneyland"], None);
3730	///
3731	/// map.insert("horseland", Some(`3`));
3732	///
3733	/// // existing key
3734	/// assert_eq!(map.entry("horseland").or_default(), &mut Some(`3`));
3735	/// ```
3736	#[cfg_attr(feature = "inline-more", inline)]
3737	pub fn or_default(self) -> &'a mut V
3738	where
3739	K: Hash,
3740	S: BuildHasher,
3741	{
3742	match self {
3743	Entry::Occupied(entry) => entry.into_mut(),
3744	Entry::Vacant(entry) => entry.insert(Default::default()),
3745	}
3746	}
3747	}
3748
3749	impl<'a, K, V, S, A: Allocator> OccupiedEntry<'a, K, V, S, A> {
3750	/// Gets a reference to the key in the entry.
3751	///
3752	/// # Examples
3753	///
3754	/// ```
3755	/// use hashbrown::hash_map::{Entry, HashMap};
3756	///
3757	/// let mut map: HashMap<&str, u32> = HashMap::new();
3758	/// map.entry("poneyland").or_insert(`12`);
3759	///
3760	/// match map.entry("poneyland") {
3761	/// Entry::Vacant(_) => panic!(),
3762	/// Entry::Occupied(entry) => assert_eq!(entry.key(), &"poneyland"),
3763	/// }
3764	/// ```
3765	#[cfg_attr(feature = "inline-more", inline)]
3766	pub fn key(&self) -> &K {
3767	unsafe { &self.elem.as_ref().0 }
3768	}
3769
3770	/// Take the ownership of the key and value from the map.
3771	/// Keeps the allocated memory for reuse.
3772	///
3773	/// # Examples
3774	///
3775	/// ```
3776	/// use hashbrown::HashMap;
3777	/// use hashbrown::hash_map::Entry;
3778	///
3779	/// let mut map: HashMap<&str, u32> = HashMap::new();
3780	/// // The map is empty
3781	/// assert!(map.is_empty() && map.capacity() == `0`);
3782	///
3783	/// map.entry("poneyland").or_insert(`12`);
3784	///
3785	/// if let Entry::Occupied(o) = map.entry("poneyland") {
3786	/// // We delete the entry from the map.
3787	/// assert_eq!(o.remove_entry(), ("poneyland", `12`));
3788	/// }
3789	///
3790	/// assert_eq!(map.contains_key("poneyland"), `false`);
3791	/// // Now map hold none elements
3792	/// assert!(map.is_empty());
3793	/// ```
3794	#[cfg_attr(feature = "inline-more", inline)]
3795	pub fn remove_entry(self) -> (K, V) {
3796	unsafe { self.table.table.remove(self.elem).0 }
3797	}
3798
3799	/// Gets a reference to the value in the entry.
3800	///
3801	/// # Examples
3802	///
3803	/// ```
3804	/// use hashbrown::HashMap;
3805	/// use hashbrown::hash_map::Entry;
3806	///
3807	/// let mut map: HashMap<&str, u32> = HashMap::new();
3808	/// map.entry("poneyland").or_insert(`12`);
3809	///
3810	/// match map.entry("poneyland") {
3811	/// Entry::Vacant(_) => panic!(),
3812	/// Entry::Occupied(entry) => assert_eq!(entry.get(), &`12`),
3813	/// }
3814	/// ```
3815	#[cfg_attr(feature = "inline-more", inline)]
3816	pub fn get(&self) -> &V {
3817	unsafe { &self.elem.as_ref().1 }
3818	}
3819
3820	/// Gets a mutable reference to the value in the entry.
3821	///
3822	/// If you need a reference to the `OccupiedEntry` which may outlive the
3823	/// destruction of the `Entry` value, see [`into_mut`].
3824	///
3825	/// [`into_mut`]: #method.into_mut
3826	///
3827	/// # Examples
3828	///
3829	/// ```
3830	/// use hashbrown::HashMap;
3831	/// use hashbrown::hash_map::Entry;
3832	///
3833	/// let mut map: HashMap<&str, u32> = HashMap::new();
3834	/// map.entry("poneyland").or_insert(`12`);
3835	///
3836	/// assert_eq!(map["poneyland"], `12`);
3837	/// if let Entry::Occupied(mut o) = map.entry("poneyland") {
3838	/// *o.get_mut() += `10`;
3839	/// assert_eq!(*o.get(), `22`);
3840	///
3841	/// // We can use the same Entry multiple times.
3842	/// *o.get_mut() += `2`;
3843	/// }
3844	///
3845	/// assert_eq!(map["poneyland"], `24`);
3846	/// ```
3847	#[cfg_attr(feature = "inline-more", inline)]
3848	pub fn get_mut(&mut self) -> &mut V {
3849	unsafe { &mut self.elem.as_mut().1 }
3850	}
3851
3852	/// Converts the `OccupiedEntry` into a mutable reference to the value in the entry
3853	/// with a lifetime bound to the map itself.
3854	///
3855	/// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
3856	///
3857	/// [`get_mut`]: #method.get_mut
3858	///
3859	/// # Examples
3860	///
3861	/// ```
3862	/// use hashbrown::hash_map::{Entry, HashMap};
3863	///
3864	/// let mut map: HashMap<&str, u32> = HashMap::new();
3865	/// map.entry("poneyland").or_insert(`12`);
3866	///
3867	/// assert_eq!(map["poneyland"], `12`);
3868	///
3869	/// let value: &mut u32;
3870	/// match map.entry("poneyland") {
3871	/// Entry::Occupied(entry) => value = entry.into_mut(),
3872	/// Entry::Vacant(_) => panic!(),
3873	/// }
3874	/// *value += `10`;
3875	///
3876	/// assert_eq!(map["poneyland"], `22`);
3877	/// ```
3878	#[cfg_attr(feature = "inline-more", inline)]
3879	pub fn into_mut(self) -> &'a mut V {
3880	unsafe { &mut self.elem.as_mut().1 }
3881	}
3882
3883	/// Sets the value of the entry, and returns the entry's old value.
3884	///
3885	/// # Examples
3886	///
3887	/// ```
3888	/// use hashbrown::HashMap;
3889	/// use hashbrown::hash_map::Entry;
3890	///
3891	/// let mut map: HashMap<&str, u32> = HashMap::new();
3892	/// map.entry("poneyland").or_insert(`12`);
3893	///
3894	/// if let Entry::Occupied(mut o) = map.entry("poneyland") {
3895	/// assert_eq!(o.insert(`15`), `12`);
3896	/// }
3897	///
3898	/// assert_eq!(map["poneyland"], `15`);
3899	/// ```
3900	#[cfg_attr(feature = "inline-more", inline)]
3901	pub fn insert(&mut self, value: V) -> V {
3902	mem::replace(self.get_mut(), value)
3903	}
3904
3905	/// Takes the value out of the entry, and returns it.
3906	/// Keeps the allocated memory for reuse.
3907	///
3908	/// # Examples
3909	///
3910	/// ```
3911	/// use hashbrown::HashMap;
3912	/// use hashbrown::hash_map::Entry;
3913	///
3914	/// let mut map: HashMap<&str, u32> = HashMap::new();
3915	/// // The map is empty
3916	/// assert!(map.is_empty() && map.capacity() == `0`);
3917	///
3918	/// map.entry("poneyland").or_insert(`12`);
3919	///
3920	/// if let Entry::Occupied(o) = map.entry("poneyland") {
3921	/// assert_eq!(o.remove(), `12`);
3922	/// }
3923	///
3924	/// assert_eq!(map.contains_key("poneyland"), `false`);
3925	/// // Now map hold none elements
3926	/// assert!(map.is_empty());
3927	/// ```
3928	#[cfg_attr(feature = "inline-more", inline)]
3929	pub fn remove(self) -> V {
3930	self.remove_entry().1
3931	}
3932
3933	/// Provides shared access to the key and owned access to the value of
3934	/// the entry and allows to replace or remove it based on the
3935	/// value of the returned option.
3936	///
3937	/// # Examples
3938	///
3939	/// ```
3940	/// use hashbrown::HashMap;
3941	/// use hashbrown::hash_map::Entry;
3942	///
3943	/// let mut map: HashMap<&str, u32> = HashMap::new();
3944	/// map.insert("poneyland", `42`);
3945	///
3946	/// let entry = match map.entry("poneyland") {
3947	/// Entry::Occupied(e) => {
3948	/// e.replace_entry_with(\|k, v\| {
3949	/// assert_eq!(k, &"poneyland");
3950	/// assert_eq!(v, `42`);
3951	/// Some(v + `1`)
3952	/// })
3953	/// }
3954	/// Entry::Vacant(_) => panic!(),
3955	/// };
3956	///
3957	/// match entry {
3958	/// Entry::Occupied(e) => {
3959	/// assert_eq!(e.key(), &"poneyland");
3960	/// assert_eq!(e.get(), &`43`);
3961	/// }
3962	/// Entry::Vacant(_) => panic!(),
3963	/// }
3964	///
3965	/// assert_eq!(map["poneyland"], `43`);
3966	///
3967	/// let entry = match map.entry("poneyland") {
3968	/// Entry::Occupied(e) => e.replace_entry_with(\|_k, _v\| None),
3969	/// Entry::Vacant(_) => panic!(),
3970	/// };
3971	///
3972	/// match entry {
3973	/// Entry::Vacant(e) => {
3974	/// assert_eq!(e.key(), &"poneyland");
3975	/// }
3976	/// Entry::Occupied(_) => panic!(),
3977	/// }
3978	///
3979	/// assert!(!map.contains_key("poneyland"));
3980	/// ```
3981	#[cfg_attr(feature = "inline-more", inline)]
3982	pub fn replace_entry_with<F>(self, f: F) -> Entry<'a, K, V, S, A>
3983	where
3984	F: FnOnce(&K, V) -> Option<V>,
3985	{
3986	unsafe {
3987	let mut spare_key = None;
3988
3989	self.table
3990	.table
3991	.replace_bucket_with(self.elem.clone(), \|(key, value)\| {
3992	if let Some(new_value) = f(&key, value) {
3993	Some((key, new_value))
3994	} else {
3995	spare_key = Some(key);
3996	None
3997	}
3998	});
3999
4000	if let Some(key) = spare_key {
4001	Entry::Vacant(VacantEntry {
4002	hash: self.hash,
4003	key,
4004	table: self.table,
4005	})
4006	} else {
4007	Entry::Occupied(self)
4008	}
4009	}
4010	}
4011	}
4012
4013	impl<'a, K, V, S, A: Allocator> VacantEntry<'a, K, V, S, A> {
4014	/// Gets a reference to the key that would be used when inserting a value
4015	/// through the `VacantEntry`.
4016	///
4017	/// # Examples
4018	///
4019	/// ```
4020	/// use hashbrown::HashMap;
4021	///
4022	/// let mut map: HashMap<&str, u32> = HashMap::new();
4023	/// assert_eq!(map.entry("poneyland").key(), &"poneyland");
4024	/// ```
4025	#[cfg_attr(feature = "inline-more", inline)]
4026	pub fn key(&self) -> &K {
4027	&self.key
4028	}
4029
4030	/// Take ownership of the key.
4031	///
4032	/// # Examples
4033	///
4034	/// ```
4035	/// use hashbrown::hash_map::{Entry, HashMap};
4036	///
4037	/// let mut map: HashMap<&str, u32> = HashMap::new();
4038	///
4039	/// match map.entry("poneyland") {
4040	/// Entry::Occupied(_) => panic!(),
4041	/// Entry::Vacant(v) => assert_eq!(v.into_key(), "poneyland"),
4042	/// }
4043	/// ```
4044	#[cfg_attr(feature = "inline-more", inline)]
4045	pub fn into_key(self) -> K {
4046	self.key
4047	}
4048
4049	/// Sets the value of the entry with the [`VacantEntry`]'s key,
4050	/// and returns a mutable reference to it.
4051	///
4052	/// # Examples
4053	///
4054	/// ```
4055	/// use hashbrown::HashMap;
4056	/// use hashbrown::hash_map::Entry;
4057	///
4058	/// let mut map: HashMap<&str, u32> = HashMap::new();
4059	///
4060	/// if let Entry::Vacant(o) = map.entry("poneyland") {
4061	/// o.insert(`37`);
4062	/// }
4063	/// assert_eq!(map["poneyland"], `37`);
4064	/// ```
4065	#[cfg_attr(feature = "inline-more", inline)]
4066	pub fn insert(self, value: V) -> &'a mut V
4067	where
4068	K: Hash,
4069	S: BuildHasher,
4070	{
4071	let table = &mut self.table.table;
4072	let entry = table.insert_entry(
4073	self.hash,
4074	(self.key, value),
4075	make_hasher::<_, V, S>(&self.table.hash_builder),
4076	);
4077	&mut entry.1
4078	}
4079
4080	/// Sets the value of the entry with the [`VacantEntry`]'s key,
4081	/// and returns an [`OccupiedEntry`].
4082	///
4083	/// # Examples
4084	///
4085	/// ```
4086	/// use hashbrown::HashMap;
4087	/// use hashbrown::hash_map::Entry;
4088	///
4089	/// let mut map: HashMap<&str, u32> = HashMap::new();
4090	///
4091	/// if let Entry::Vacant(v) = map.entry("poneyland") {
4092	/// let o = v.insert_entry(`37`);
4093	/// assert_eq!(o.get(), &`37`);
4094	/// }
4095	/// ```
4096	#[cfg_attr(feature = "inline-more", inline)]
4097	pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V, S, A>
4098	where
4099	K: Hash,
4100	S: BuildHasher,
4101	{
4102	let elem = self.table.table.insert(
4103	self.hash,
4104	(self.key, value),
4105	make_hasher::<_, V, S>(&self.table.hash_builder),
4106	);
4107	OccupiedEntry {
4108	hash: self.hash,
4109	elem,
4110	table: self.table,
4111	}
4112	}
4113	}
4114
4115	impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator> EntryRef<'a, 'b, K, Q, V, S, A> {
4116	/// Sets the value of the entry, and returns an `OccupiedEntry`.
4117	///
4118	/// # Examples
4119	///
4120	/// ```
4121	/// use hashbrown::HashMap;
4122	///
4123	/// let mut map: HashMap<String, u32> = HashMap::new();
4124	/// let entry = map.entry_ref("horseyland").insert(`37`);
4125	///
4126	/// assert_eq!(entry.key(), "horseyland");
4127	/// ```
4128	#[cfg_attr(feature = "inline-more", inline)]
4129	pub fn insert(self, value: V) -> OccupiedEntry<'a, K, V, S, A>
4130	where
4131	K: Hash,
4132	&'b Q: Into<K>,
4133	S: BuildHasher,
4134	{
4135	match self {
4136	EntryRef::Occupied(mut entry) => {
4137	entry.insert(value);
4138	entry
4139	}
4140	EntryRef::Vacant(entry) => entry.insert_entry(value),
4141	}
4142	}
4143
4144	/// Ensures a value is in the entry by inserting the default if empty, and returns
4145	/// a mutable reference to the value in the entry.
4146	///
4147	/// # Examples
4148	///
4149	/// ```
4150	/// use hashbrown::HashMap;
4151	///
4152	/// let mut map: HashMap<String, u32> = HashMap::new();
4153	///
4154	/// // nonexistent key
4155	/// map.entry_ref("poneyland").or_insert(`3`);
4156	/// assert_eq!(map["poneyland"], `3`);
4157	///
4158	/// // existing key
4159	/// map.entry_ref("poneyland").or_insert(`10`) = `2`;
4160	/// assert_eq!(map["poneyland"], `6`);
4161	/// ```
4162	#[cfg_attr(feature = "inline-more", inline)]
4163	pub fn or_insert(self, default: V) -> &'a mut V
4164	where
4165	K: Hash,
4166	&'b Q: Into<K>,
4167	S: BuildHasher,
4168	{
4169	match self {
4170	EntryRef::Occupied(entry) => entry.into_mut(),
4171	EntryRef::Vacant(entry) => entry.insert(default),
4172	}
4173	}
4174
4175	/// Ensures a value is in the entry by inserting the result of the default function if empty,
4176	/// and returns a mutable reference to the value in the entry.
4177	///
4178	/// # Examples
4179	///
4180	/// ```
4181	/// use hashbrown::HashMap;
4182	///
4183	/// let mut map: HashMap<String, u32> = HashMap::new();
4184	///
4185	/// // nonexistent key
4186	/// map.entry_ref("poneyland").or_insert_with(\|\| `3`);
4187	/// assert_eq!(map["poneyland"], `3`);
4188	///
4189	/// // existing key
4190	/// map.entry_ref("poneyland").or_insert_with(\|\| `10`) = `2`;
4191	/// assert_eq!(map["poneyland"], `6`);
4192	/// ```
4193	#[cfg_attr(feature = "inline-more", inline)]
4194	pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V
4195	where
4196	K: Hash,
4197	&'b Q: Into<K>,
4198	S: BuildHasher,
4199	{
4200	match self {
4201	EntryRef::Occupied(entry) => entry.into_mut(),
4202	EntryRef::Vacant(entry) => entry.insert(default()),
4203	}
4204	}
4205
4206	/// Ensures a value is in the entry by inserting, if empty, the result of the default function.
4207	/// This method allows for generating key-derived values for insertion by providing the default
4208	/// function an access to the borrower form of the key.
4209	///
4210	/// # Examples
4211	///
4212	/// ```
4213	/// use hashbrown::HashMap;
4214	///
4215	/// let mut map: HashMap<String, usize> = HashMap::new();
4216	///
4217	/// // nonexistent key
4218	/// map.entry_ref("poneyland").or_insert_with_key(\|key\| key.chars().count());
4219	/// assert_eq!(map["poneyland"], `9`);
4220	///
4221	/// // existing key
4222	/// map.entry_ref("poneyland").or_insert_with_key(\|key\| key.chars().count() `10`) *= `2`;
4223	/// assert_eq!(map["poneyland"], `18`);
4224	/// ```
4225	#[cfg_attr(feature = "inline-more", inline)]
4226	pub fn or_insert_with_key<F: FnOnce(&Q) -> V>(self, default: F) -> &'a mut V
4227	where
4228	K: Hash + Borrow<Q>,
4229	&'b Q: Into<K>,
4230	S: BuildHasher,
4231	{
4232	match self {
4233	EntryRef::Occupied(entry) => entry.into_mut(),
4234	EntryRef::Vacant(entry) => {
4235	let value = default(entry.key);
4236	entry.insert(value)
4237	}
4238	}
4239	}
4240
4241	/// Returns a reference to this entry's key.
4242	///
4243	/// # Examples
4244	///
4245	/// ```
4246	/// use hashbrown::HashMap;
4247	///
4248	/// let mut map: HashMap<String, u32> = HashMap::new();
4249	/// map.entry_ref("poneyland").or_insert(`3`);
4250	/// // existing key
4251	/// assert_eq!(map.entry_ref("poneyland").key(), "poneyland");
4252	/// // nonexistent key
4253	/// assert_eq!(map.entry_ref("horseland").key(), "horseland");
4254	/// ```
4255	#[cfg_attr(feature = "inline-more", inline)]
4256	pub fn key(&self) -> &Q
4257	where
4258	K: Borrow<Q>,
4259	{
4260	match *self {
4261	EntryRef::Occupied(ref entry) => entry.key().borrow(),
4262	EntryRef::Vacant(ref entry) => entry.key(),
4263	}
4264	}
4265
4266	/// Provides in-place mutable access to an occupied entry before any
4267	/// potential inserts into the map.
4268	///
4269	/// # Examples
4270	///
4271	/// ```
4272	/// use hashbrown::HashMap;
4273	///
4274	/// let mut map: HashMap<String, u32> = HashMap::new();
4275	///
4276	/// map.entry_ref("poneyland")
4277	/// .and_modify(\|e\| { *e += `1` })
4278	/// .or_insert(`42`);
4279	/// assert_eq!(map["poneyland"], `42`);
4280	///
4281	/// map.entry_ref("poneyland")
4282	/// .and_modify(\|e\| { *e += `1` })
4283	/// .or_insert(`42`);
4284	/// assert_eq!(map["poneyland"], `43`);
4285	/// ```
4286	#[cfg_attr(feature = "inline-more", inline)]
4287	pub fn and_modify<F>(self, f: F) -> Self
4288	where
4289	F: FnOnce(&mut V),
4290	{
4291	match self {
4292	EntryRef::Occupied(mut entry) => {
4293	f(entry.get_mut());
4294	EntryRef::Occupied(entry)
4295	}
4296	EntryRef::Vacant(entry) => EntryRef::Vacant(entry),
4297	}
4298	}
4299	}
4300
4301	impl<'a, 'b, K, Q: ?Sized, V: Default, S, A: Allocator> EntryRef<'a, 'b, K, Q, V, S, A> {
4302	/// Ensures a value is in the entry by inserting the default value if empty,
4303	/// and returns a mutable reference to the value in the entry.
4304	///
4305	/// # Examples
4306	///
4307	/// ```
4308	/// use hashbrown::HashMap;
4309	///
4310	/// let mut map: HashMap<String, Option<u32>> = HashMap::new();
4311	///
4312	/// // nonexistent key
4313	/// map.entry_ref("poneyland").or_default();
4314	/// assert_eq!(map["poneyland"], None);
4315	///
4316	/// map.insert("horseland".to_string(), Some(`3`));
4317	///
4318	/// // existing key
4319	/// assert_eq!(map.entry_ref("horseland").or_default(), &mut Some(`3`));
4320	/// ```
4321	#[cfg_attr(feature = "inline-more", inline)]
4322	pub fn or_default(self) -> &'a mut V
4323	where
4324	K: Hash,
4325	&'b Q: Into<K>,
4326	S: BuildHasher,
4327	{
4328	match self {
4329	EntryRef::Occupied(entry) => entry.into_mut(),
4330	EntryRef::Vacant(entry) => entry.insert(Default::default()),
4331	}
4332	}
4333	}
4334
4335	impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator> VacantEntryRef<'a, 'b, K, Q, V, S, A> {
4336	/// Gets a reference to the key that would be used when inserting a value
4337	/// through the `VacantEntryRef`.
4338	///
4339	/// # Examples
4340	///
4341	/// ```
4342	/// use hashbrown::HashMap;
4343	///
4344	/// let mut map: HashMap<String, u32> = HashMap::new();
4345	/// let key: &str = "poneyland";
4346	/// assert_eq!(map.entry_ref(key).key(), "poneyland");
4347	/// ```
4348	#[cfg_attr(feature = "inline-more", inline)]
4349	pub fn key(&self) -> &'b Q {
4350	self.key
4351	}
4352
4353	/// Sets the value of the entry with the `VacantEntryRef`'s key,
4354	/// and returns a mutable reference to it.
4355	///
4356	/// # Examples
4357	///
4358	/// ```
4359	/// use hashbrown::HashMap;
4360	/// use hashbrown::hash_map::EntryRef;
4361	///
4362	/// let mut map: HashMap<String, u32> = HashMap::new();
4363	/// let key: &str = "poneyland";
4364	///
4365	/// if let EntryRef::Vacant(o) = map.entry_ref(key) {
4366	/// o.insert(`37`);
4367	/// }
4368	/// assert_eq!(map["poneyland"], `37`);
4369	/// ```
4370	#[cfg_attr(feature = "inline-more", inline)]
4371	pub fn insert(self, value: V) -> &'a mut V
4372	where
4373	K: Hash,
4374	&'b Q: Into<K>,
4375	S: BuildHasher,
4376	{
4377	let table = &mut self.table.table;
4378	let entry = table.insert_entry(
4379	self.hash,
4380	(self.key.into(), value),
4381	make_hasher::<_, V, S>(&self.table.hash_builder),
4382	);
4383	&mut entry.1
4384	}
4385
4386	/// Sets the value of the entry with the [`VacantEntryRef`]'s key,
4387	/// and returns an [`OccupiedEntry`].
4388	///
4389	/// # Examples
4390	///
4391	/// ```
4392	/// use hashbrown::HashMap;
4393	/// use hashbrown::hash_map::EntryRef;
4394	///
4395	/// let mut map: HashMap<&str, u32> = HashMap::new();
4396	///
4397	/// if let EntryRef::Vacant(v) = map.entry_ref("poneyland") {
4398	/// let o = v.insert_entry(`37`);
4399	/// assert_eq!(o.get(), &`37`);
4400	/// }
4401	/// ```
4402	#[cfg_attr(feature = "inline-more", inline)]
4403	pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V, S, A>
4404	where
4405	K: Hash,
4406	&'b Q: Into<K>,
4407	S: BuildHasher,
4408	{
4409	let elem = self.table.table.insert(
4410	self.hash,
4411	(self.key.into(), value),
4412	make_hasher::<_, V, S>(&self.table.hash_builder),
4413	);
4414	OccupiedEntry {
4415	hash: self.hash,
4416	elem,
4417	table: self.table,
4418	}
4419	}
4420	}
4421
4422	impl<K, V, S, A> FromIterator<(K, V)> for HashMap<K, V, S, A>
4423	where
4424	K: Eq + Hash,
4425	S: BuildHasher + Default,
4426	A: Default + Allocator,
4427	{
4428	#[cfg_attr(feature = "inline-more", inline)]
4429	fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
4430	let iter: ::IntoIter = iter.into_iter();
4431	let mut map: HashMap =
4432	Self::with_capacity_and_hasher_in(capacity:iter.size_hint().0, S::default(), A::default());
4433	iter.for_each(\|(k: K, v: V)\| {
4434	map.insert(k, v);
4435	});
4436	map
4437	}
4438	}
4439
4440	/// Inserts all new key-values from the iterator and replaces values with existing
4441	/// keys with new values returned from the iterator.
4442	impl<K, V, S, A> Extend<(K, V)> for HashMap<K, V, S, A>
4443	where
4444	K: Eq + Hash,
4445	S: BuildHasher,
4446	A: Allocator,
4447	{
4448	/// Inserts all new key-values from the iterator to existing `HashMap<K, V, S, A>`.
4449	/// Replace values with existing keys with new values returned from the iterator.
4450	///
4451	/// # Examples
4452	///
4453	/// ```
4454	/// use hashbrown::hash_map::HashMap;
4455	///
4456	/// let mut map = HashMap::new();
4457	/// map.insert(`1`, `100`);
4458	///
4459	/// let some_iter = [(`1`, `1`), (`2`, `2`)].into_iter();
4460	/// map.extend(some_iter);
4461	/// // Replace values with existing keys with new values returned from the iterator.
4462	/// // So that the map.get(&1) doesn't return Some(&100).
4463	/// assert_eq!(map.get(&`1`), Some(&`1`));
4464	///
4465	/// let some_vec: Vec<_> = vec![(`3`, `3`), (`4`, `4`)];
4466	/// map.extend(some_vec);
4467	///
4468	/// let some_arr = [(`5`, `5`), (`6`, `6`)];
4469	/// map.extend(some_arr);
4470	/// let old_map_len = map.len();
4471	///
4472	/// // You can also extend from another HashMap
4473	/// let mut new_map = HashMap::new();
4474	/// new_map.extend(map);
4475	/// assert_eq!(new_map.len(), old_map_len);
4476	///
4477	/// let mut vec: Vec<_> = new_map.into_iter().collect();
4478	/// // The `IntoIter` iterator produces items in arbitrary order, so the
4479	/// // items must be sorted to test them against a sorted array.
4480	/// vec.sort_unstable();
4481	/// assert_eq!(vec, [(`1`, `1`), (`2`, `2`), (`3`, `3`), (`4`, `4`), (`5`, `5`), (`6`, `6`)]);
4482	/// ```
4483	#[cfg_attr(feature = "inline-more", inline)]
4484	fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
4485	// Keys may be already present or show multiple times in the iterator.
4486	// Reserve the entire hint lower bound if the map is empty.
4487	// Otherwise reserve half the hint (rounded up), so the map
4488	// will only resize twice in the worst case.
4489	let iter = iter.into_iter();
4490	let reserve = if self.is_empty() {
4491	iter.size_hint().0
4492	} else {
4493	(iter.size_hint().0 + `1`) / `2`
4494	};
4495	self.reserve(reserve);
4496	iter.for_each(move \|(k, v)\| {
4497	self.insert(k, v);
4498	});
4499	}
4500
4501	#[inline]
4502	#[cfg(feature = "nightly")]
4503	fn extend_one(&mut self, (k, v): (K, V)) {
4504	self.insert(k, v);
4505	}
4506
4507	#[inline]
4508	#[cfg(feature = "nightly")]
4509	fn extend_reserve(&mut self, additional: usize) {
4510	// Keys may be already present or show multiple times in the iterator.
4511	// Reserve the entire hint lower bound if the map is empty.
4512	// Otherwise reserve half the hint (rounded up), so the map
4513	// will only resize twice in the worst case.
4514	let reserve = if self.is_empty() {
4515	additional
4516	} else {
4517	(additional + `1`) / `2`
4518	};
4519	self.reserve(reserve);
4520	}
4521	}
4522
4523	/// Inserts all new key-values from the iterator and replaces values with existing
4524	/// keys with new values returned from the iterator.
4525	impl<'a, K, V, S, A> Extend<(&'a K, &'a V)> for HashMap<K, V, S, A>
4526	where
4527	K: Eq + Hash + Copy,
4528	V: Copy,
4529	S: BuildHasher,
4530	A: Allocator,
4531	{
4532	/// Inserts all new key-values from the iterator to existing `HashMap<K, V, S, A>`.
4533	/// Replace values with existing keys with new values returned from the iterator.
4534	/// The keys and values must implement [`Copy`] trait.
4535	///
4536	/// [`Copy`]: https://doc.rust-lang.org/core/marker/trait.Copy.html
4537	///
4538	/// # Examples
4539	///
4540	/// ```
4541	/// use hashbrown::hash_map::HashMap;
4542	///
4543	/// let mut map = HashMap::new();
4544	/// map.insert(`1`, `100`);
4545	///
4546	/// let arr = [(`1`, `1`), (`2`, `2`)];
4547	/// let some_iter = arr.iter().map(\|(k, v)\| (k, v));
4548	/// map.extend(some_iter);
4549	/// // Replace values with existing keys with new values returned from the iterator.
4550	/// // So that the map.get(&1) doesn't return Some(&100).
4551	/// assert_eq!(map.get(&`1`), Some(&`1`));
4552	///
4553	/// let some_vec: Vec<_> = vec![(`3`, `3`), (`4`, `4`)];
4554	/// map.extend(some_vec.iter().map(\|(k, v)\| (k, v)));
4555	///
4556	/// let some_arr = [(`5`, `5`), (`6`, `6`)];
4557	/// map.extend(some_arr.iter().map(\|(k, v)\| (k, v)));
4558	///
4559	/// // You can also extend from another HashMap
4560	/// let mut new_map = HashMap::new();
4561	/// new_map.extend(&map);
4562	/// assert_eq!(new_map, map);
4563	///
4564	/// let mut vec: Vec<_> = new_map.into_iter().collect();
4565	/// // The `IntoIter` iterator produces items in arbitrary order, so the
4566	/// // items must be sorted to test them against a sorted array.
4567	/// vec.sort_unstable();
4568	/// assert_eq!(vec, [(`1`, `1`), (`2`, `2`), (`3`, `3`), (`4`, `4`), (`5`, `5`), (`6`, `6`)]);
4569	/// ```
4570	#[cfg_attr(feature = "inline-more", inline)]
4571	fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
4572	self.extend(iter.into_iter().map(\|(&key, &value)\| (key, value)));
4573	}
4574
4575	#[inline]
4576	#[cfg(feature = "nightly")]
4577	fn extend_one(&mut self, (k, v): (&'a K, &'a V)) {
4578	self.insert(k, v);
4579	}
4580
4581	#[inline]
4582	#[cfg(feature = "nightly")]
4583	fn extend_reserve(&mut self, additional: usize) {
4584	Extend::<(K, V)>::extend_reserve(self, additional);
4585	}
4586	}
4587
4588	/// Inserts all new key-values from the iterator and replaces values with existing
4589	/// keys with new values returned from the iterator.
4590	impl<'a, K, V, S, A> Extend<&'a (K, V)> for HashMap<K, V, S, A>
4591	where
4592	K: Eq + Hash + Copy,
4593	V: Copy,
4594	S: BuildHasher,
4595	A: Allocator,
4596	{
4597	/// Inserts all new key-values from the iterator to existing `HashMap<K, V, S, A>`.
4598	/// Replace values with existing keys with new values returned from the iterator.
4599	/// The keys and values must implement [`Copy`] trait.
4600	///
4601	/// [`Copy`]: https://doc.rust-lang.org/core/marker/trait.Copy.html
4602	///
4603	/// # Examples
4604	///
4605	/// ```
4606	/// use hashbrown::hash_map::HashMap;
4607	///
4608	/// let mut map = HashMap::new();
4609	/// map.insert(`1`, `100`);
4610	///
4611	/// let arr = [(`1`, `1`), (`2`, `2`)];
4612	/// let some_iter = arr.iter();
4613	/// map.extend(some_iter);
4614	/// // Replace values with existing keys with new values returned from the iterator.
4615	/// // So that the map.get(&1) doesn't return Some(&100).
4616	/// assert_eq!(map.get(&`1`), Some(&`1`));
4617	///
4618	/// let some_vec: Vec<_> = vec![(`3`, `3`), (`4`, `4`)];
4619	/// map.extend(&some_vec);
4620	///
4621	/// let some_arr = [(`5`, `5`), (`6`, `6`)];
4622	/// map.extend(&some_arr);
4623	///
4624	/// let mut vec: Vec<_> = map.into_iter().collect();
4625	/// // The `IntoIter` iterator produces items in arbitrary order, so the
4626	/// // items must be sorted to test them against a sorted array.
4627	/// vec.sort_unstable();
4628	/// assert_eq!(vec, [(`1`, `1`), (`2`, `2`), (`3`, `3`), (`4`, `4`), (`5`, `5`), (`6`, `6`)]);
4629	/// ```
4630	#[cfg_attr(feature = "inline-more", inline)]
4631	fn extend<T: IntoIterator<Item = &'a (K, V)>>(&mut self, iter: T) {
4632	self.extend(iter.into_iter().map(\|&(key, value)\| (key, value)));
4633	}
4634
4635	#[inline]
4636	#[cfg(feature = "nightly")]
4637	fn extend_one(&mut self, &(k, v): &'a (K, V)) {
4638	self.insert(k, v);
4639	}
4640
4641	#[inline]
4642	#[cfg(feature = "nightly")]
4643	fn extend_reserve(&mut self, additional: usize) {
4644	Extend::<(K, V)>::extend_reserve(self, additional);
4645	}
4646	}
4647
4648	#[allow(dead_code)]
4649	fn assert_covariance() {
4650	fn map_key<'new>(v: HashMap<&'static str, u8>) -> HashMap<&'new str, u8> {
4651	v
4652	}
4653	fn map_val<'new>(v: HashMap<u8, &'static str>) -> HashMap<u8, &'new str> {
4654	v
4655	}
4656	fn iter_key<'a, 'new>(v: Iter<'a, &'static str, u8>) -> Iter<'a, &'new str, u8> {
4657	v
4658	}
4659	fn iter_val<'a, 'new>(v: Iter<'a, u8, &'static str>) -> Iter<'a, u8, &'new str> {
4660	v
4661	}
4662	fn into_iter_key<'new, A: Allocator>(
4663	v: IntoIter<&'static str, u8, A>,
4664	) -> IntoIter<&'new str, u8, A> {
4665	v
4666	}
4667	fn into_iter_val<'new, A: Allocator>(
4668	v: IntoIter<u8, &'static str, A>,
4669	) -> IntoIter<u8, &'new str, A> {
4670	v
4671	}
4672	fn keys_key<'a, 'new>(v: Keys<'a, &'static str, u8>) -> Keys<'a, &'new str, u8> {
4673	v
4674	}
4675	fn keys_val<'a, 'new>(v: Keys<'a, u8, &'static str>) -> Keys<'a, u8, &'new str> {
4676	v
4677	}
4678	fn values_key<'a, 'new>(v: Values<'a, &'static str, u8>) -> Values<'a, &'new str, u8> {
4679	v
4680	}
4681	fn values_val<'a, 'new>(v: Values<'a, u8, &'static str>) -> Values<'a, u8, &'new str> {
4682	v
4683	}
4684	fn drain<'new>(
4685	d: Drain<'static, &'static str, &'static str>,
4686	) -> Drain<'new, &'new str, &'new str> {
4687	d
4688	}
4689	}
4690
4691	#[cfg(test)]
4692	mod test_map {
4693	use super::DefaultHashBuilder;
4694	use super::Entry::{Occupied, Vacant};
4695	use super::EntryRef;
4696	use super::HashMap;
4697	use crate::raw::{AllocError, Allocator, Global};
4698	use alloc::string::{String, ToString};
4699	use alloc::sync::Arc;
4700	use core::alloc::Layout;
4701	use core::ptr::NonNull;
4702	use core::sync::atomic::{AtomicI8, Ordering};
4703	use rand::{rngs::SmallRng, Rng, SeedableRng};
4704	use std::borrow::ToOwned;
4705	use std::cell::RefCell;
4706	use std::vec::Vec;
4707
4708	#[test]
4709	fn test_zero_capacities() {
4710	type HM = HashMap<i32, i32>;
4711
4712	let m = HM::new();
4713	assert_eq!(m.capacity(), `0`);
4714
4715	let m = HM::default();
4716	assert_eq!(m.capacity(), `0`);
4717
4718	let m = HM::with_hasher(DefaultHashBuilder::default());
4719	assert_eq!(m.capacity(), `0`);
4720
4721	let m = HM::with_capacity(`0`);
4722	assert_eq!(m.capacity(), `0`);
4723
4724	let m = HM::with_capacity_and_hasher(`0`, DefaultHashBuilder::default());
4725	assert_eq!(m.capacity(), `0`);
4726
4727	let mut m = HM::new();
4728	m.insert(`1`, `1`);
4729	m.insert(`2`, `2`);
4730	m.remove(&`1`);
4731	m.remove(&`2`);
4732	m.shrink_to_fit();
4733	assert_eq!(m.capacity(), `0`);
4734
4735	let mut m = HM::new();
4736	m.reserve(`0`);
4737	assert_eq!(m.capacity(), `0`);
4738	}
4739
4740	#[test]
4741	fn test_create_capacity_zero() {
4742	let mut m = HashMap::with_capacity(`0`);
4743
4744	assert!(m.insert(`1`, `1`).is_none());
4745
4746	assert!(m.contains_key(&`1`));
4747	assert!(!m.contains_key(&`0`));
4748	}
4749
4750	#[test]
4751	fn test_insert() {
4752	let mut m = HashMap::new();
4753	assert_eq!(m.len(), `0`);
4754	assert!(m.insert(`1`, `2`).is_none());
4755	assert_eq!(m.len(), `1`);
4756	assert!(m.insert(`2`, `4`).is_none());
4757	assert_eq!(m.len(), `2`);
4758	assert_eq!(*m.get(&`1`).unwrap(), `2`);
4759	assert_eq!(*m.get(&`2`).unwrap(), `4`);
4760	}
4761
4762	#[test]
4763	fn test_clone() {
4764	let mut m = HashMap::new();
4765	assert_eq!(m.len(), `0`);
4766	assert!(m.insert(`1`, `2`).is_none());
4767	assert_eq!(m.len(), `1`);
4768	assert!(m.insert(`2`, `4`).is_none());
4769	assert_eq!(m.len(), `2`);
4770	#[allow(clippy::redundant_clone)]
4771	let m2 = m.clone();
4772	assert_eq!(*m2.get(&`1`).unwrap(), `2`);
4773	assert_eq!(*m2.get(&`2`).unwrap(), `4`);
4774	assert_eq!(m2.len(), `2`);
4775	}
4776
4777	#[test]
4778	fn test_clone_from() {
4779	let mut m = HashMap::new();
4780	let mut m2 = HashMap::new();
4781	assert_eq!(m.len(), `0`);
4782	assert!(m.insert(`1`, `2`).is_none());
4783	assert_eq!(m.len(), `1`);
4784	assert!(m.insert(`2`, `4`).is_none());
4785	assert_eq!(m.len(), `2`);
4786	m2.clone_from(&m);
4787	assert_eq!(*m2.get(&`1`).unwrap(), `2`);
4788	assert_eq!(*m2.get(&`2`).unwrap(), `4`);
4789	assert_eq!(m2.len(), `2`);
4790	}
4791
4792	thread_local! { static DROP_VECTOR: RefCell<Vec<i32>> = const { RefCell::new(Vec::new()) } }
4793
4794	#[derive(Hash, PartialEq, Eq)]
4795	struct Droppable {
4796	k: usize,
4797	}
4798
4799	impl Droppable {
4800	fn new(k: usize) -> Droppable {
4801	DROP_VECTOR.with(\|slot\| {
4802	slot.borrow_mut()[k] += `1`;
4803	});
4804
4805	Droppable { k }
4806	}
4807	}
4808
4809	impl Drop for Droppable {
4810	fn drop(&mut self) {
4811	DROP_VECTOR.with(\|slot\| {
4812	slot.borrow_mut()[self.k] -= `1`;
4813	});
4814	}
4815	}
4816
4817	impl Clone for Droppable {
4818	fn clone(&self) -> Self {
4819	Droppable::new(self.k)
4820	}
4821	}
4822
4823	#[test]
4824	fn test_drops() {
4825	DROP_VECTOR.with(\|slot\| {
4826	*slot.borrow_mut() = vec![`0`; `200`];
4827	});
4828
4829	{
4830	let mut m = HashMap::new();
4831
4832	DROP_VECTOR.with(\|v\| {
4833	for i in `0`..`200` {
4834	assert_eq!(v.borrow()[i], `0`);
4835	}
4836	});
4837
4838	for i in `0`..`100` {
4839	let d1 = Droppable::new(i);
4840	let d2 = Droppable::new(i + `100`);
4841	m.insert(d1, d2);
4842	}
4843
4844	DROP_VECTOR.with(\|v\| {
4845	for i in `0`..`200` {
4846	assert_eq!(v.borrow()[i], `1`);
4847	}
4848	});
4849
4850	for i in `0`..`50` {
4851	let k = Droppable::new(i);
4852	let v = m.remove(&k);
4853
4854	assert!(v.is_some());
4855
4856	DROP_VECTOR.with(\|v\| {
4857	assert_eq!(v.borrow()[i], `1`);
4858	assert_eq!(v.borrow()[i + `100`], `1`);
4859	});
4860	}
4861
4862	DROP_VECTOR.with(\|v\| {
4863	for i in `0`..`50` {
4864	assert_eq!(v.borrow()[i], `0`);
4865	assert_eq!(v.borrow()[i + `100`], `0`);
4866	}
4867
4868	for i in `50`..`100` {
4869	assert_eq!(v.borrow()[i], `1`);
4870	assert_eq!(v.borrow()[i + `100`], `1`);
4871	}
4872	});
4873	}
4874
4875	DROP_VECTOR.with(\|v\| {
4876	for i in `0`..`200` {
4877	assert_eq!(v.borrow()[i], `0`);
4878	}
4879	});
4880	}
4881
4882	#[test]
4883	fn test_into_iter_drops() {
4884	DROP_VECTOR.with(\|v\| {
4885	*v.borrow_mut() = vec![`0`; `200`];
4886	});
4887
4888	let hm = {
4889	let mut hm = HashMap::new();
4890
4891	DROP_VECTOR.with(\|v\| {
4892	for i in `0`..`200` {
4893	assert_eq!(v.borrow()[i], `0`);
4894	}
4895	});
4896
4897	for i in `0`..`100` {
4898	let d1 = Droppable::new(i);
4899	let d2 = Droppable::new(i + `100`);
4900	hm.insert(d1, d2);
4901	}
4902
4903	DROP_VECTOR.with(\|v\| {
4904	for i in `0`..`200` {
4905	assert_eq!(v.borrow()[i], `1`);
4906	}
4907	});
4908
4909	hm
4910	};
4911
4912	// By the way, ensure that cloning doesn't screw up the dropping.
4913	drop(hm.clone());
4914
4915	{
4916	let mut half = hm.into_iter().take(`50`);
4917
4918	DROP_VECTOR.with(\|v\| {
4919	for i in `0`..`200` {
4920	assert_eq!(v.borrow()[i], `1`);
4921	}
4922	});
4923
4924	for _ in half.by_ref() {}
4925
4926	DROP_VECTOR.with(\|v\| {
4927	let nk = (`0`..`100`).filter(\|&i\| v.borrow()[i] == `1`).count();
4928
4929	let nv = (`0`..`100`).filter(\|&i\| v.borrow()[i + `100`] == `1`).count();
4930
4931	assert_eq!(nk, `50`);
4932	assert_eq!(nv, `50`);
4933	});
4934	};
4935
4936	DROP_VECTOR.with(\|v\| {
4937	for i in `0`..`200` {
4938	assert_eq!(v.borrow()[i], `0`);
4939	}
4940	});
4941	}
4942
4943	#[test]
4944	fn test_empty_remove() {
4945	let mut m: HashMap<i32, bool> = HashMap::new();
4946	assert_eq!(m.remove(&`0`), None);
4947	}
4948
4949	#[test]
4950	fn test_empty_entry() {
4951	let mut m: HashMap<i32, bool> = HashMap::new();
4952	match m.entry(`0`) {
4953	Occupied(_) => panic!(),
4954	Vacant(_) => {}
4955	}
4956	assert!(*m.entry(`0`).or_insert(`true`));
4957	assert_eq!(m.len(), `1`);
4958	}
4959
4960	#[test]
4961	fn test_empty_entry_ref() {
4962	let mut m: HashMap<std::string::String, bool> = HashMap::new();
4963	match m.entry_ref("poneyland") {
4964	EntryRef::Occupied(_) => panic!(),
4965	EntryRef::Vacant(_) => {}
4966	}
4967	assert!(*m.entry_ref("poneyland").or_insert(`true`));
4968	assert_eq!(m.len(), `1`);
4969	}
4970
4971	#[test]
4972	fn test_empty_iter() {
4973	let mut m: HashMap<i32, bool> = HashMap::new();
4974	assert_eq!(m.drain().next(), None);
4975	assert_eq!(m.keys().next(), None);
4976	assert_eq!(m.values().next(), None);
4977	assert_eq!(m.values_mut().next(), None);
4978	assert_eq!(m.iter().next(), None);
4979	assert_eq!(m.iter_mut().next(), None);
4980	assert_eq!(m.len(), `0`);
4981	assert!(m.is_empty());
4982	assert_eq!(m.into_iter().next(), None);
4983	}
4984
4985	#[test]
4986	#[cfg_attr(miri, ignore)] // FIXME: takes too long
4987	fn test_lots_of_insertions() {
4988	let mut m = HashMap::new();
4989
4990	// Try this a few times to make sure we never screw up the hashmap's
4991	// internal state.
4992	for _ in `0`..`10` {
4993	assert!(m.is_empty());
4994
4995	for i in `1`..`1001` {
4996	assert!(m.insert(i, i).is_none());
4997
4998	for j in `1`..=i {
4999	let r = m.get(&j);
5000	assert_eq!(r, Some(&j));
5001	}
5002
5003	for j in i + `1`..`1001` {
5004	let r = m.get(&j);
5005	assert_eq!(r, None);
5006	}
5007	}
5008
5009	for i in `1001`..`2001` {
5010	assert!(!m.contains_key(&i));
5011	}
5012
5013	// remove forwards
5014	for i in `1`..`1001` {
5015	assert!(m.remove(&i).is_some());
5016
5017	for j in `1`..=i {
5018	assert!(!m.contains_key(&j));
5019	}
5020
5021	for j in i + `1`..`1001` {
5022	assert!(m.contains_key(&j));
5023	}
5024	}
5025
5026	for i in `1`..`1001` {
5027	assert!(!m.contains_key(&i));
5028	}
5029
5030	for i in `1`..`1001` {
5031	assert!(m.insert(i, i).is_none());
5032	}
5033
5034	// remove backwards
5035	for i in (`1`..`1001`).rev() {
5036	assert!(m.remove(&i).is_some());
5037
5038	for j in i..`1001` {
5039	assert!(!m.contains_key(&j));
5040	}
5041
5042	for j in `1`..i {
5043	assert!(m.contains_key(&j));
5044	}
5045	}
5046	}
5047	}
5048
5049	#[test]
5050	fn test_find_mut() {
5051	let mut m = HashMap::new();
5052	assert!(m.insert(`1`, `12`).is_none());
5053	assert!(m.insert(`2`, `8`).is_none());
5054	assert!(m.insert(`5`, `14`).is_none());
5055	let new = `100`;
5056	match m.get_mut(&`5`) {
5057	None => panic!(),
5058	Some(x) => *x = new,
5059	}
5060	assert_eq!(m.get(&`5`), Some(&new));
5061	}
5062
5063	#[test]
5064	fn test_insert_overwrite() {
5065	let mut m = HashMap::new();
5066	assert!(m.insert(`1`, `2`).is_none());
5067	assert_eq!(*m.get(&`1`).unwrap(), `2`);
5068	assert!(m.insert(`1`, `3`).is_some());
5069	assert_eq!(*m.get(&`1`).unwrap(), `3`);
5070	}
5071
5072	#[test]
5073	fn test_insert_conflicts() {
5074	let mut m = HashMap::with_capacity(`4`);
5075	assert!(m.insert(`1`, `2`).is_none());
5076	assert!(m.insert(`5`, `3`).is_none());
5077	assert!(m.insert(`9`, `4`).is_none());
5078	assert_eq!(*m.get(&`9`).unwrap(), `4`);
5079	assert_eq!(*m.get(&`5`).unwrap(), `3`);
5080	assert_eq!(*m.get(&`1`).unwrap(), `2`);
5081	}
5082
5083	#[test]
5084	fn test_conflict_remove() {
5085	let mut m = HashMap::with_capacity(`4`);
5086	assert!(m.insert(`1`, `2`).is_none());
5087	assert_eq!(*m.get(&`1`).unwrap(), `2`);
5088	assert!(m.insert(`5`, `3`).is_none());
5089	assert_eq!(*m.get(&`1`).unwrap(), `2`);
5090	assert_eq!(*m.get(&`5`).unwrap(), `3`);
5091	assert!(m.insert(`9`, `4`).is_none());
5092	assert_eq!(*m.get(&`1`).unwrap(), `2`);
5093	assert_eq!(*m.get(&`5`).unwrap(), `3`);
5094	assert_eq!(*m.get(&`9`).unwrap(), `4`);
5095	assert!(m.remove(&`1`).is_some());
5096	assert_eq!(*m.get(&`9`).unwrap(), `4`);
5097	assert_eq!(*m.get(&`5`).unwrap(), `3`);
5098	}
5099
5100	#[test]
5101	fn test_insert_unique_unchecked() {
5102	let mut map = HashMap::new();
5103	let (k1, v1) = unsafe { map.insert_unique_unchecked(`10`, `11`) };
5104	assert_eq!((&`10`, &mut `11`), (k1, v1));
5105	let (k2, v2) = unsafe { map.insert_unique_unchecked(`20`, `21`) };
5106	assert_eq!((&`20`, &mut `21`), (k2, v2));
5107	assert_eq!(Some(&`11`), map.get(&`10`));
5108	assert_eq!(Some(&`21`), map.get(&`20`));
5109	assert_eq!(None, map.get(&`30`));
5110	}
5111
5112	#[test]
5113	fn test_is_empty() {
5114	let mut m = HashMap::with_capacity(`4`);
5115	assert!(m.insert(`1`, `2`).is_none());
5116	assert!(!m.is_empty());
5117	assert!(m.remove(&`1`).is_some());
5118	assert!(m.is_empty());
5119	}
5120
5121	#[test]
5122	fn test_remove() {
5123	let mut m = HashMap::new();
5124	m.insert(`1`, `2`);
5125	assert_eq!(m.remove(&`1`), Some(`2`));
5126	assert_eq!(m.remove(&`1`), None);
5127	}
5128
5129	#[test]
5130	fn test_remove_entry() {
5131	let mut m = HashMap::new();
5132	m.insert(`1`, `2`);
5133	assert_eq!(m.remove_entry(&`1`), Some((`1`, `2`)));
5134	assert_eq!(m.remove(&`1`), None);
5135	}
5136
5137	#[test]
5138	fn test_iterate() {
5139	let mut m = HashMap::with_capacity(`4`);
5140	for i in `0`..`32` {
5141	assert!(m.insert(i, i * `2`).is_none());
5142	}
5143	assert_eq!(m.len(), `32`);
5144
5145	let mut observed: u32 = `0`;
5146
5147	for (k, v) in &m {
5148	assert_eq!(v, k * `2`);
5149	observed \|= `1` << *k;
5150	}
5151	assert_eq!(observed, `0xFFFF_FFFF`);
5152	}
5153
5154	#[test]
5155	fn test_keys() {
5156	let vec = vec![(`1`, 'a'), (`2`, 'b'), (`3`, 'c')];
5157	let map: HashMap<_, _> = vec.into_iter().collect();
5158	let keys: Vec<_> = map.keys().copied().collect();
5159	assert_eq!(keys.len(), `3`);
5160	assert!(keys.contains(&`1`));
5161	assert!(keys.contains(&`2`));
5162	assert!(keys.contains(&`3`));
5163	}
5164
5165	#[test]
5166	fn test_values() {
5167	let vec = vec![(`1`, 'a'), (`2`, 'b'), (`3`, 'c')];
5168	let map: HashMap<_, _> = vec.into_iter().collect();
5169	let values: Vec<_> = map.values().copied().collect();
5170	assert_eq!(values.len(), `3`);
5171	assert!(values.contains(&'a'));
5172	assert!(values.contains(&'b'));
5173	assert!(values.contains(&'c'));
5174	}
5175
5176	#[test]
5177	fn test_values_mut() {
5178	let vec = vec![(`1`, `1`), (`2`, `2`), (`3`, `3`)];
5179	let mut map: HashMap<_, _> = vec.into_iter().collect();
5180	for value in map.values_mut() {
5181	value = `2`;
5182	}
5183	let values: Vec<_> = map.values().copied().collect();
5184	assert_eq!(values.len(), `3`);
5185	assert!(values.contains(&`2`));
5186	assert!(values.contains(&`4`));
5187	assert!(values.contains(&`6`));
5188	}
5189
5190	#[test]
5191	fn test_into_keys() {
5192	let vec = vec![(`1`, 'a'), (`2`, 'b'), (`3`, 'c')];
5193	let map: HashMap<_, _> = vec.into_iter().collect();
5194	let keys: Vec<_> = map.into_keys().collect();
5195
5196	assert_eq!(keys.len(), `3`);
5197	assert!(keys.contains(&`1`));
5198	assert!(keys.contains(&`2`));
5199	assert!(keys.contains(&`3`));
5200	}
5201
5202	#[test]
5203	fn test_into_values() {
5204	let vec = vec![(`1`, 'a'), (`2`, 'b'), (`3`, 'c')];
5205	let map: HashMap<_, _> = vec.into_iter().collect();
5206	let values: Vec<_> = map.into_values().collect();
5207
5208	assert_eq!(values.len(), `3`);
5209	assert!(values.contains(&'a'));
5210	assert!(values.contains(&'b'));
5211	assert!(values.contains(&'c'));
5212	}
5213
5214	#[test]
5215	fn test_find() {
5216	let mut m = HashMap::new();
5217	assert!(m.get(&`1`).is_none());
5218	m.insert(`1`, `2`);
5219	match m.get(&`1`) {
5220	None => panic!(),
5221	Some(v) => assert_eq!(*v, `2`),
5222	}
5223	}
5224
5225	#[test]
5226	fn test_eq() {
5227	let mut m1 = HashMap::new();
5228	m1.insert(`1`, `2`);
5229	m1.insert(`2`, `3`);
5230	m1.insert(`3`, `4`);
5231
5232	let mut m2 = HashMap::new();
5233	m2.insert(`1`, `2`);
5234	m2.insert(`2`, `3`);
5235
5236	assert!(m1 != m2);
5237
5238	m2.insert(`3`, `4`);
5239
5240	assert_eq!(m1, m2);
5241	}
5242
5243	#[test]
5244	fn test_show() {
5245	let mut map = HashMap::new();
5246	let empty: HashMap<i32, i32> = HashMap::new();
5247
5248	map.insert(`1`, `2`);
5249	map.insert(`3`, `4`);
5250
5251	let map_str = format!("{map:?}");
5252
5253	assert!(map_str == "{1: 2, 3: 4}" \|\| map_str == "{3: 4, 1: 2}");
5254	assert_eq!(format!("{empty:?}"), "{}");
5255	}
5256
5257	#[test]
5258	fn test_expand() {
5259	let mut m = HashMap::new();
5260
5261	assert_eq!(m.len(), `0`);
5262	assert!(m.is_empty());
5263
5264	let mut i = `0`;
5265	let old_raw_cap = m.raw_capacity();
5266	while old_raw_cap == m.raw_capacity() {
5267	m.insert(i, i);
5268	i += `1`;
5269	}
5270
5271	assert_eq!(m.len(), i);
5272	assert!(!m.is_empty());
5273	}
5274
5275	#[test]
5276	fn test_behavior_resize_policy() {
5277	let mut m = HashMap::new();
5278
5279	assert_eq!(m.len(), `0`);
5280	assert_eq!(m.raw_capacity(), `1`);
5281	assert!(m.is_empty());
5282
5283	m.insert(`0`, `0`);
5284	m.remove(&`0`);
5285	assert!(m.is_empty());
5286	let initial_raw_cap = m.raw_capacity();
5287	m.reserve(initial_raw_cap);
5288	let raw_cap = m.raw_capacity();
5289
5290	assert_eq!(raw_cap, initial_raw_cap * `2`);
5291
5292	let mut i = `0`;
5293	for _ in `0`..raw_cap * `3` / `4` {
5294	m.insert(i, i);
5295	i += `1`;
5296	}
5297	// three quarters full
5298
5299	assert_eq!(m.len(), i);
5300	assert_eq!(m.raw_capacity(), raw_cap);
5301
5302	for _ in `0`..raw_cap / `4` {
5303	m.insert(i, i);
5304	i += `1`;
5305	}
5306	// half full
5307
5308	let new_raw_cap = m.raw_capacity();
5309	assert_eq!(new_raw_cap, raw_cap * `2`);
5310
5311	for _ in `0`..raw_cap / `2` - `1` {
5312	i -= `1`;
5313	m.remove(&i);
5314	assert_eq!(m.raw_capacity(), new_raw_cap);
5315	}
5316	// A little more than one quarter full.
5317	m.shrink_to_fit();
5318	assert_eq!(m.raw_capacity(), raw_cap);
5319	// again, a little more than half full
5320	for _ in `0`..raw_cap / `2` {
5321	i -= `1`;
5322	m.remove(&i);
5323	}
5324	m.shrink_to_fit();
5325
5326	assert_eq!(m.len(), i);
5327	assert!(!m.is_empty());
5328	assert_eq!(m.raw_capacity(), initial_raw_cap);
5329	}
5330
5331	#[test]
5332	fn test_reserve_shrink_to_fit() {
5333	let mut m = HashMap::new();
5334	m.insert(`0`, `0`);
5335	m.remove(&`0`);
5336	assert!(m.capacity() >= m.len());
5337	for i in `0`..`128` {
5338	m.insert(i, i);
5339	}
5340	m.reserve(`256`);
5341
5342	let usable_cap = m.capacity();
5343	for i in `128`..(`128` + `256`) {
5344	m.insert(i, i);
5345	assert_eq!(m.capacity(), usable_cap);
5346	}
5347
5348	for i in `100`..(`128` + `256`) {
5349	assert_eq!(m.remove(&i), Some(i));
5350	}
5351	m.shrink_to_fit();
5352
5353	assert_eq!(m.len(), `100`);
5354	assert!(!m.is_empty());
5355	assert!(m.capacity() >= m.len());
5356
5357	for i in `0`..`100` {
5358	assert_eq!(m.remove(&i), Some(i));
5359	}
5360	m.shrink_to_fit();
5361	m.insert(`0`, `0`);
5362
5363	assert_eq!(m.len(), `1`);
5364	assert!(m.capacity() >= m.len());
5365	assert_eq!(m.remove(&`0`), Some(`0`));
5366	}
5367
5368	#[test]
5369	fn test_from_iter() {
5370	let xs = [(`1`, `1`), (`2`, `2`), (`2`, `2`), (`3`, `3`), (`4`, `4`), (`5`, `5`), (`6`, `6`)];
5371
5372	let map: HashMap<_, _> = xs.iter().copied().collect();
5373
5374	for &(k, v) in &xs {
5375	assert_eq!(map.get(&k), Some(&v));
5376	}
5377
5378	assert_eq!(map.iter().len(), xs.len() - `1`);
5379	}
5380
5381	#[test]
5382	fn test_size_hint() {
5383	let xs = [(`1`, `1`), (`2`, `2`), (`3`, `3`), (`4`, `4`), (`5`, `5`), (`6`, `6`)];
5384
5385	let map: HashMap<_, _> = xs.iter().copied().collect();
5386
5387	let mut iter = map.iter();
5388
5389	for _ in iter.by_ref().take(`3`) {}
5390
5391	assert_eq!(iter.size_hint(), (`3`, Some(`3`)));
5392	}
5393
5394	#[test]
5395	fn test_iter_len() {
5396	let xs = [(`1`, `1`), (`2`, `2`), (`3`, `3`), (`4`, `4`), (`5`, `5`), (`6`, `6`)];
5397
5398	let map: HashMap<_, _> = xs.iter().copied().collect();
5399
5400	let mut iter = map.iter();
5401
5402	for _ in iter.by_ref().take(`3`) {}
5403
5404	assert_eq!(iter.len(), `3`);
5405	}
5406
5407	#[test]
5408	fn test_mut_size_hint() {
5409	let xs = [(`1`, `1`), (`2`, `2`), (`3`, `3`), (`4`, `4`), (`5`, `5`), (`6`, `6`)];
5410
5411	let mut map: HashMap<_, _> = xs.iter().copied().collect();
5412
5413	let mut iter = map.iter_mut();
5414
5415	for _ in iter.by_ref().take(`3`) {}
5416
5417	assert_eq!(iter.size_hint(), (`3`, Some(`3`)));
5418	}
5419
5420	#[test]
5421	fn test_iter_mut_len() {
5422	let xs = [(`1`, `1`), (`2`, `2`), (`3`, `3`), (`4`, `4`), (`5`, `5`), (`6`, `6`)];
5423
5424	let mut map: HashMap<_, _> = xs.iter().copied().collect();
5425
5426	let mut iter = map.iter_mut();
5427
5428	for _ in iter.by_ref().take(`3`) {}
5429
5430	assert_eq!(iter.len(), `3`);
5431	}
5432
5433	#[test]
5434	fn test_index() {
5435	let mut map = HashMap::new();
5436
5437	map.insert(`1`, `2`);
5438	map.insert(`2`, `1`);
5439	map.insert(`3`, `4`);
5440
5441	assert_eq!(map[&`2`], `1`);
5442	}
5443
5444	#[test]
5445	#[should_panic]
5446	fn test_index_nonexistent() {
5447	let mut map = HashMap::new();
5448
5449	map.insert(`1`, `2`);
5450	map.insert(`2`, `1`);
5451	map.insert(`3`, `4`);
5452
5453	#[allow(clippy::no_effect)] // false positive lint
5454	map[&`4`];
5455	}
5456
5457	#[test]
5458	fn test_entry() {
5459	let xs = [(`1`, `10`), (`2`, `20`), (`3`, `30`), (`4`, `40`), (`5`, `50`), (`6`, `60`)];
5460
5461	let mut map: HashMap<_, _> = xs.iter().copied().collect();
5462
5463	// Existing key (insert)
5464	match map.entry(`1`) {
5465	Vacant(_) => unreachable!(),
5466	Occupied(mut view) => {
5467	assert_eq!(view.get(), &`10`);
5468	assert_eq!(view.insert(`100`), `10`);
5469	}
5470	}
5471	assert_eq!(map.get(&`1`).unwrap(), &`100`);
5472	assert_eq!(map.len(), `6`);
5473
5474	// Existing key (update)
5475	match map.entry(`2`) {
5476	Vacant(_) => unreachable!(),
5477	Occupied(mut view) => {
5478	let v = view.get_mut();
5479	let new_v = (v) `10`;
5480	*v = new_v;
5481	}
5482	}
5483	assert_eq!(map.get(&`2`).unwrap(), &`200`);
5484	assert_eq!(map.len(), `6`);
5485
5486	// Existing key (take)
5487	match map.entry(`3`) {
5488	Vacant(_) => unreachable!(),
5489	Occupied(view) => {
5490	assert_eq!(view.remove(), `30`);
5491	}
5492	}
5493	assert_eq!(map.get(&`3`), None);
5494	assert_eq!(map.len(), `5`);
5495
5496	// Inexistent key (insert)
5497	match map.entry(`10`) {
5498	Occupied(_) => unreachable!(),
5499	Vacant(view) => {
5500	assert_eq!(*view.insert(`1000`), `1000`);
5501	}
5502	}
5503	assert_eq!(map.get(&`10`).unwrap(), &`1000`);
5504	assert_eq!(map.len(), `6`);
5505	}
5506
5507	#[test]
5508	fn test_entry_ref() {
5509	let xs = [
5510	("One".to_owned(), `10`),
5511	("Two".to_owned(), `20`),
5512	("Three".to_owned(), `30`),
5513	("Four".to_owned(), `40`),
5514	("Five".to_owned(), `50`),
5515	("Six".to_owned(), `60`),
5516	];
5517
5518	let mut map: HashMap<_, _> = xs.iter().cloned().collect();
5519
5520	// Existing key (insert)
5521	match map.entry_ref("One") {
5522	EntryRef::Vacant(_) => unreachable!(),
5523	EntryRef::Occupied(mut view) => {
5524	assert_eq!(view.get(), &`10`);
5525	assert_eq!(view.insert(`100`), `10`);
5526	}
5527	}
5528	assert_eq!(map.get("One").unwrap(), &`100`);
5529	assert_eq!(map.len(), `6`);
5530
5531	// Existing key (update)
5532	match map.entry_ref("Two") {
5533	EntryRef::Vacant(_) => unreachable!(),
5534	EntryRef::Occupied(mut view) => {
5535	let v = view.get_mut();
5536	let new_v = (v) `10`;
5537	*v = new_v;
5538	}
5539	}
5540	assert_eq!(map.get("Two").unwrap(), &`200`);
5541	assert_eq!(map.len(), `6`);
5542
5543	// Existing key (take)
5544	match map.entry_ref("Three") {
5545	EntryRef::Vacant(_) => unreachable!(),
5546	EntryRef::Occupied(view) => {
5547	assert_eq!(view.remove(), `30`);
5548	}
5549	}
5550	assert_eq!(map.get("Three"), None);
5551	assert_eq!(map.len(), `5`);
5552
5553	// Inexistent key (insert)
5554	match map.entry_ref("Ten") {
5555	EntryRef::Occupied(_) => unreachable!(),
5556	EntryRef::Vacant(view) => {
5557	assert_eq!(*view.insert(`1000`), `1000`);
5558	}
5559	}
5560	assert_eq!(map.get("Ten").unwrap(), &`1000`);
5561	assert_eq!(map.len(), `6`);
5562	}
5563
5564	#[test]
5565	fn test_entry_take_doesnt_corrupt() {
5566	#![allow(deprecated)] //rand
5567	// Test for #19292
5568	fn check(m: &HashMap<i32, ()>) {
5569	for k in m.keys() {
5570	assert!(m.contains_key(k), "{k} is in keys() but not in the map?");
5571	}
5572	}
5573
5574	let mut m = HashMap::new();
5575
5576	let mut rng = {
5577	let seed = u64::from_le_bytes(*b"testseed");
5578	SmallRng::seed_from_u64(seed)
5579	};
5580
5581	// Populate the map with some items.
5582	for _ in `0`..`50` {
5583	let x = rng.gen_range(`-10`..`10`);
5584	m.insert(x, ());
5585	}
5586
5587	for _ in `0`..`1000` {
5588	let x = rng.gen_range(`-10`..`10`);
5589	match m.entry(x) {
5590	Vacant(_) => {}
5591	Occupied(e) => {
5592	e.remove();
5593	}
5594	}
5595
5596	check(&m);
5597	}
5598	}
5599
5600	#[test]
5601	fn test_entry_ref_take_doesnt_corrupt() {
5602	#![allow(deprecated)] //rand
5603	// Test for #19292
5604	fn check(m: &HashMap<std::string::String, ()>) {
5605	for k in m.keys() {
5606	assert!(m.contains_key(k), "{k} is in keys() but not in the map?");
5607	}
5608	}
5609
5610	let mut m = HashMap::new();
5611
5612	let mut rng = {
5613	let seed = u64::from_le_bytes(*b"testseed");
5614	SmallRng::seed_from_u64(seed)
5615	};
5616
5617	// Populate the map with some items.
5618	for _ in `0`..`50` {
5619	let mut x = std::string::String::with_capacity(`1`);
5620	x.push(rng.gen_range('a'..='z'));
5621	m.insert(x, ());
5622	}
5623
5624	for _ in `0`..`1000` {
5625	let mut x = std::string::String::with_capacity(`1`);
5626	x.push(rng.gen_range('a'..='z'));
5627	match m.entry_ref(x.as_str()) {
5628	EntryRef::Vacant(_) => {}
5629	EntryRef::Occupied(e) => {
5630	e.remove();
5631	}
5632	}
5633
5634	check(&m);
5635	}
5636	}
5637
5638	#[test]
5639	fn test_extend_ref_k_ref_v() {
5640	let mut a = HashMap::new();
5641	a.insert(`1`, "one");
5642	let mut b = HashMap::new();
5643	b.insert(`2`, "two");
5644	b.insert(`3`, "three");
5645
5646	a.extend(&b);
5647
5648	assert_eq!(a.len(), `3`);
5649	assert_eq!(a[&`1`], "one");
5650	assert_eq!(a[&`2`], "two");
5651	assert_eq!(a[&`3`], "three");
5652	}
5653
5654	#[test]
5655	#[allow(clippy::needless_borrow)]
5656	fn test_extend_ref_kv_tuple() {
5657	use std::ops::AddAssign;
5658	let mut a = HashMap::new();
5659	a.insert(`0`, `0`);
5660
5661	fn create_arr<T: AddAssign<T> + Copy, const N: usize>(start: T, step: T) -> [(T, T); N] {
5662	let mut outs: [(T, T); N] = [(start, start); N];
5663	let mut element = step;
5664	outs.iter_mut().skip(`1`).for_each(\|(k, v)\| {
5665	*k += element;
5666	*v += element;
5667	element += step;
5668	});
5669	outs
5670	}
5671
5672	let for_iter: Vec<_> = (`0`..`100`).map(\|i\| (i, i)).collect();
5673	let iter = for_iter.iter();
5674	let vec: Vec<_> = (`100`..`200`).map(\|i\| (i, i)).collect();
5675	a.extend(iter);
5676	a.extend(&vec);
5677	a.extend(create_arr::<i32, `100`>(`200`, `1`));
5678
5679	assert_eq!(a.len(), `300`);
5680
5681	for item in `0`..`300` {
5682	assert_eq!(a[&item], item);
5683	}
5684	}
5685
5686	#[test]
5687	fn test_capacity_not_less_than_len() {
5688	let mut a = HashMap::new();
5689	let mut item = `0`;
5690
5691	for _ in `0`..`116` {
5692	a.insert(item, `0`);
5693	item += `1`;
5694	}
5695
5696	assert!(a.capacity() > a.len());
5697
5698	let free = a.capacity() - a.len();
5699	for _ in `0`..free {
5700	a.insert(item, `0`);
5701	item += `1`;
5702	}
5703
5704	assert_eq!(a.len(), a.capacity());
5705
5706	// Insert at capacity should cause allocation.
5707	a.insert(item, `0`);
5708	assert!(a.capacity() > a.len());
5709	}
5710
5711	#[test]
5712	fn test_occupied_entry_key() {
5713	let mut a = HashMap::new();
5714	let key = "hello there";
5715	let value = "value goes here";
5716	assert!(a.is_empty());
5717	a.insert(key, value);
5718	assert_eq!(a.len(), `1`);
5719	assert_eq!(a[key], value);
5720
5721	match a.entry(key) {
5722	Vacant(_) => panic!(),
5723	Occupied(e) => assert_eq!(key, *e.key()),
5724	}
5725	assert_eq!(a.len(), `1`);
5726	assert_eq!(a[key], value);
5727	}
5728
5729	#[test]
5730	fn test_occupied_entry_ref_key() {
5731	let mut a = HashMap::new();
5732	let key = "hello there";
5733	let value = "value goes here";
5734	assert!(a.is_empty());
5735	a.insert(key.to_owned(), value);
5736	assert_eq!(a.len(), `1`);
5737	assert_eq!(a[key], value);
5738
5739	match a.entry_ref(key) {
5740	EntryRef::Vacant(_) => panic!(),
5741	EntryRef::Occupied(e) => assert_eq!(key, e.key()),
5742	}
5743	assert_eq!(a.len(), `1`);
5744	assert_eq!(a[key], value);
5745	}
5746
5747	#[test]
5748	fn test_vacant_entry_key() {
5749	let mut a = HashMap::new();
5750	let key = "hello there";
5751	let value = "value goes here";
5752
5753	assert!(a.is_empty());
5754	match a.entry(key) {
5755	Occupied(_) => panic!(),
5756	Vacant(e) => {
5757	assert_eq!(key, *e.key());
5758	e.insert(value);
5759	}
5760	}
5761	assert_eq!(a.len(), `1`);
5762	assert_eq!(a[key], value);
5763	}
5764
5765	#[test]
5766	fn test_vacant_entry_ref_key() {
5767	let mut a: HashMap<std::string::String, &str> = HashMap::new();
5768	let key = "hello there";
5769	let value = "value goes here";
5770
5771	assert!(a.is_empty());
5772	match a.entry_ref(key) {
5773	EntryRef::Occupied(_) => panic!(),
5774	EntryRef::Vacant(e) => {
5775	assert_eq!(key, e.key());
5776	e.insert(value);
5777	}
5778	}
5779	assert_eq!(a.len(), `1`);
5780	assert_eq!(a[key], value);
5781	}
5782
5783	#[test]
5784	fn test_occupied_entry_replace_entry_with() {
5785	let mut a = HashMap::new();
5786
5787	let key = "a key";
5788	let value = "an initial value";
5789	let new_value = "a new value";
5790
5791	let entry = a.entry(key).insert(value).replace_entry_with(\|k, v\| {
5792	assert_eq!(k, &key);
5793	assert_eq!(v, value);
5794	Some(new_value)
5795	});
5796
5797	match entry {
5798	Occupied(e) => {
5799	assert_eq!(e.key(), &key);
5800	assert_eq!(e.get(), &new_value);
5801	}
5802	Vacant(_) => panic!(),
5803	}
5804
5805	assert_eq!(a[key], new_value);
5806	assert_eq!(a.len(), `1`);
5807
5808	let entry = match a.entry(key) {
5809	Occupied(e) => e.replace_entry_with(\|k, v\| {
5810	assert_eq!(k, &key);
5811	assert_eq!(v, new_value);
5812	None
5813	}),
5814	Vacant(_) => panic!(),
5815	};
5816
5817	match entry {
5818	Vacant(e) => assert_eq!(e.key(), &key),
5819	Occupied(_) => panic!(),
5820	}
5821
5822	assert!(!a.contains_key(key));
5823	assert_eq!(a.len(), `0`);
5824	}
5825
5826	#[test]
5827	fn test_entry_and_replace_entry_with() {
5828	let mut a = HashMap::new();
5829
5830	let key = "a key";
5831	let value = "an initial value";
5832	let new_value = "a new value";
5833
5834	let entry = a.entry(key).and_replace_entry_with(\|_, _\| panic!());
5835
5836	match entry {
5837	Vacant(e) => assert_eq!(e.key(), &key),
5838	Occupied(_) => panic!(),
5839	}
5840
5841	a.insert(key, value);
5842
5843	let entry = a.entry(key).and_replace_entry_with(\|k, v\| {
5844	assert_eq!(k, &key);
5845	assert_eq!(v, value);
5846	Some(new_value)
5847	});
5848
5849	match entry {
5850	Occupied(e) => {
5851	assert_eq!(e.key(), &key);
5852	assert_eq!(e.get(), &new_value);
5853	}
5854	Vacant(_) => panic!(),
5855	}
5856
5857	assert_eq!(a[key], new_value);
5858	assert_eq!(a.len(), `1`);
5859
5860	let entry = a.entry(key).and_replace_entry_with(\|k, v\| {
5861	assert_eq!(k, &key);
5862	assert_eq!(v, new_value);
5863	None
5864	});
5865
5866	match entry {
5867	Vacant(e) => assert_eq!(e.key(), &key),
5868	Occupied(_) => panic!(),
5869	}
5870
5871	assert!(!a.contains_key(key));
5872	assert_eq!(a.len(), `0`);
5873	}
5874
5875	#[test]
5876	fn test_replace_entry_with_doesnt_corrupt() {
5877	#![allow(deprecated)] //rand
5878	// Test for #19292
5879	fn check(m: &HashMap<i32, ()>) {
5880	for k in m.keys() {
5881	assert!(m.contains_key(k), "{k} is in keys() but not in the map?");
5882	}
5883	}
5884
5885	let mut m = HashMap::new();
5886
5887	let mut rng = {
5888	let seed = u64::from_le_bytes(*b"testseed");
5889	SmallRng::seed_from_u64(seed)
5890	};
5891
5892	// Populate the map with some items.
5893	for _ in `0`..`50` {
5894	let x = rng.gen_range(`-10`..`10`);
5895	m.insert(x, ());
5896	}
5897
5898	for _ in `0`..`1000` {
5899	let x = rng.gen_range(`-10`..`10`);
5900	m.entry(x).and_replace_entry_with(\|_, _\| None);
5901	check(&m);
5902	}
5903	}
5904
5905	#[test]
5906	fn test_retain() {
5907	let mut map: HashMap<i32, i32> = (`0`..`100`).map(\|x\| (x, x * `10`)).collect();
5908
5909	map.retain(\|&k, _\| k % `2` == `0`);
5910	assert_eq!(map.len(), `50`);
5911	assert_eq!(map[&`2`], `20`);
5912	assert_eq!(map[&`4`], `40`);
5913	assert_eq!(map[&`6`], `60`);
5914	}
5915
5916	#[test]
5917	fn test_extract_if() {
5918	{
5919	let mut map: HashMap<i32, i32> = (`0`..`8`).map(\|x\| (x, x * `10`)).collect();
5920	let drained = map.extract_if(\|&k, _\| k % `2` == `0`);
5921	let mut out = drained.collect::<Vec<_>>();
5922	out.sort_unstable();
5923	assert_eq!(vec![(`0`, `0`), (`2`, `20`), (`4`, `40`), (`6`, `60`)], out);
5924	assert_eq!(map.len(), `4`);
5925	}
5926	{
5927	let mut map: HashMap<i32, i32> = (`0`..`8`).map(\|x\| (x, x * `10`)).collect();
5928	map.extract_if(\|&k, _\| k % `2` == `0`).for_each(drop);
5929	assert_eq!(map.len(), `4`);
5930	}
5931	}
5932
5933	#[test]
5934	#[cfg_attr(miri, ignore)] // FIXME: no OOM signalling (https://github.com/rust-lang/miri/issues/613)
5935	fn test_try_reserve() {
5936	use crate::TryReserveError::{AllocError, CapacityOverflow};
5937
5938	const MAX_ISIZE: usize = isize::MAX as usize;
5939
5940	let mut empty_bytes: HashMap<u8, u8> = HashMap::new();
5941
5942	if let Err(CapacityOverflow) = empty_bytes.try_reserve(usize::MAX) {
5943	} else {
5944	panic!("usize::MAX should trigger an overflow!");
5945	}
5946
5947	if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_ISIZE) {
5948	} else {
5949	panic!("isize::MAX should trigger an overflow!");
5950	}
5951
5952	if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_ISIZE / `5`) {
5953	} else {
5954	// This may succeed if there is enough free memory. Attempt to
5955	// allocate a few more hashmaps to ensure the allocation will fail.
5956	let mut empty_bytes2: HashMap<u8, u8> = HashMap::new();
5957	let _ = empty_bytes2.try_reserve(MAX_ISIZE / `5`);
5958	let mut empty_bytes3: HashMap<u8, u8> = HashMap::new();
5959	let _ = empty_bytes3.try_reserve(MAX_ISIZE / `5`);
5960	let mut empty_bytes4: HashMap<u8, u8> = HashMap::new();
5961	if let Err(AllocError { .. }) = empty_bytes4.try_reserve(MAX_ISIZE / `5`) {
5962	} else {
5963	panic!("isize::MAX / 5 should trigger an OOM!");
5964	}
5965	}
5966	}
5967
5968	#[test]
5969	fn test_const_with_hasher() {
5970	use core::hash::BuildHasher;
5971	use std::collections::hash_map::DefaultHasher;
5972
5973	#[derive(Clone)]
5974	struct MyHasher;
5975	impl BuildHasher for MyHasher {
5976	type Hasher = DefaultHasher;
5977
5978	fn build_hasher(&self) -> DefaultHasher {
5979	DefaultHasher::new()
5980	}
5981	}
5982
5983	const EMPTY_MAP: HashMap<u32, std::string::String, MyHasher> =
5984	HashMap::with_hasher(MyHasher);
5985
5986	let mut map = EMPTY_MAP;
5987	map.insert(`17`, "seventeen".to_owned());
5988	assert_eq!("seventeen", map[&`17`]);
5989	}
5990
5991	#[test]
5992	fn test_get_many_mut() {
5993	let mut map = HashMap::new();
5994	map.insert("foo".to_owned(), `0`);
5995	map.insert("bar".to_owned(), `10`);
5996	map.insert("baz".to_owned(), `20`);
5997	map.insert("qux".to_owned(), `30`);
5998
5999	let xs = map.get_many_mut(["foo", "qux"]);
6000	assert_eq!(xs, [Some(&mut `0`), Some(&mut `30`)]);
6001
6002	let xs = map.get_many_mut(["foo", "dud"]);
6003	assert_eq!(xs, [Some(&mut `0`), None]);
6004
6005	let ys = map.get_many_key_value_mut(["bar", "baz"]);
6006	assert_eq!(
6007	ys,
6008	[
6009	Some((&"bar".to_owned(), &mut `10`)),
6010	Some((&"baz".to_owned(), &mut `20`))
6011	],
6012	);
6013
6014	let ys = map.get_many_key_value_mut(["bar", "dip"]);
6015	assert_eq!(ys, [Some((&"bar".to_string(), &mut `10`)), None]);
6016	}
6017
6018	#[test]
6019	#[should_panic = "duplicate keys found"]
6020	fn test_get_many_mut_duplicate() {
6021	let mut map = HashMap::new();
6022	map.insert("foo".to_owned(), `0`);
6023
6024	let _xs = map.get_many_mut(["foo", "foo"]);
6025	}
6026
6027	#[test]
6028	#[should_panic = "panic in drop"]
6029	fn test_clone_from_double_drop() {
6030	#[derive(Clone)]
6031	struct CheckedDrop {
6032	panic_in_drop: bool,
6033	dropped: bool,
6034	}
6035	impl Drop for CheckedDrop {
6036	fn drop(&mut self) {
6037	if self.panic_in_drop {
6038	self.dropped = `true`;
6039	panic!("panic in drop");
6040	}
6041	if self.dropped {
6042	panic!("double drop");
6043	}
6044	self.dropped = `true`;
6045	}
6046	}
6047	const DISARMED: CheckedDrop = CheckedDrop {
6048	panic_in_drop: `false`,
6049	dropped: `false`,
6050	};
6051	const ARMED: CheckedDrop = CheckedDrop {
6052	panic_in_drop: `true`,
6053	dropped: `false`,
6054	};
6055
6056	let mut map1 = HashMap::new();
6057	map1.insert(`1`, DISARMED);
6058	map1.insert(`2`, DISARMED);
6059	map1.insert(`3`, DISARMED);
6060	map1.insert(`4`, DISARMED);
6061
6062	let mut map2 = HashMap::new();
6063	map2.insert(`1`, DISARMED);
6064	map2.insert(`2`, ARMED);
6065	map2.insert(`3`, DISARMED);
6066	map2.insert(`4`, DISARMED);
6067
6068	map2.clone_from(&map1);
6069	}
6070
6071	#[test]
6072	#[should_panic = "panic in clone"]
6073	fn test_clone_from_memory_leaks() {
6074	use alloc::vec::Vec;
6075
6076	struct CheckedClone {
6077	panic_in_clone: bool,
6078	need_drop: Vec<i32>,
6079	}
6080	impl Clone for CheckedClone {
6081	fn clone(&self) -> Self {
6082	if self.panic_in_clone {
6083	panic!("panic in clone")
6084	}
6085	Self {
6086	panic_in_clone: self.panic_in_clone,
6087	need_drop: self.need_drop.clone(),
6088	}
6089	}
6090	}
6091	let mut map1 = HashMap::new();
6092	map1.insert(
6093	`1`,
6094	CheckedClone {
6095	panic_in_clone: `false`,
6096	need_drop: vec![`0`, `1`, `2`],
6097	},
6098	);
6099	map1.insert(
6100	`2`,
6101	CheckedClone {
6102	panic_in_clone: `false`,
6103	need_drop: vec![`3`, `4`, `5`],
6104	},
6105	);
6106	map1.insert(
6107	`3`,
6108	CheckedClone {
6109	panic_in_clone: `true`,
6110	need_drop: vec![`6`, `7`, `8`],
6111	},
6112	);
6113	let _map2 = map1.clone();
6114	}
6115
6116	struct MyAllocInner {
6117	drop_count: Arc<AtomicI8>,
6118	}
6119
6120	#[derive(Clone)]
6121	struct MyAlloc {
6122	_inner: Arc<MyAllocInner>,
6123	}
6124
6125	impl MyAlloc {
6126	fn new(drop_count: Arc<AtomicI8>) -> Self {
6127	MyAlloc {
6128	_inner: Arc::new(MyAllocInner { drop_count }),
6129	}
6130	}
6131	}
6132
6133	impl Drop for MyAllocInner {
6134	fn drop(&mut self) {
6135	println!("MyAlloc freed.");
6136	self.drop_count.fetch_sub(`1`, Ordering::SeqCst);
6137	}
6138	}
6139
6140	unsafe impl Allocator for MyAlloc {
6141	fn allocate(&self, layout: Layout) -> std::result::Result<NonNull<[u8]>, AllocError> {
6142	let g = Global;
6143	g.allocate(layout)
6144	}
6145
6146	unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
6147	let g = Global;
6148	g.deallocate(ptr, layout)
6149	}
6150	}
6151
6152	#[test]
6153	fn test_hashmap_into_iter_bug() {
6154	let dropped: Arc<AtomicI8> = Arc::new(AtomicI8::new(`1`));
6155
6156	{
6157	let mut map = HashMap::with_capacity_in(`10`, MyAlloc::new(dropped.clone()));
6158	for i in `0`..`10` {
6159	map.entry(i).or_insert_with(\|\| "i".to_string());
6160	}
6161
6162	for (k, v) in map {
6163	println!("{}, {}", k, v);
6164	}
6165	}
6166
6167	// All allocator clones should already be dropped.
6168	assert_eq!(dropped.load(Ordering::SeqCst), `0`);
6169	}
6170
6171	#[derive(Debug)]
6172	struct CheckedCloneDrop<T> {
6173	panic_in_clone: bool,
6174	panic_in_drop: bool,
6175	dropped: bool,
6176	data: T,
6177	}
6178
6179	impl<T> CheckedCloneDrop<T> {
6180	fn new(panic_in_clone: bool, panic_in_drop: bool, data: T) -> Self {
6181	CheckedCloneDrop {
6182	panic_in_clone,
6183	panic_in_drop,
6184	dropped: `false`,
6185	data,
6186	}
6187	}
6188	}
6189
6190	impl<T: Clone> Clone for CheckedCloneDrop<T> {
6191	fn clone(&self) -> Self {
6192	if self.panic_in_clone {
6193	panic!("panic in clone")
6194	}
6195	Self {
6196	panic_in_clone: self.panic_in_clone,
6197	panic_in_drop: self.panic_in_drop,
6198	dropped: self.dropped,
6199	data: self.data.clone(),
6200	}
6201	}
6202	}
6203
6204	impl<T> Drop for CheckedCloneDrop<T> {
6205	fn drop(&mut self) {
6206	if self.panic_in_drop {
6207	self.dropped = `true`;
6208	panic!("panic in drop");
6209	}
6210	if self.dropped {
6211	panic!("double drop");
6212	}
6213	self.dropped = `true`;
6214	}
6215	}
6216
6217	/// Return hashmap with predefined distribution of elements.
6218	/// All elements will be located in the same order as elements
6219	/// returned by iterator.
6220	///
6221	/// This function does not panic, but returns an error as a `String`
6222	/// to distinguish between a test panic and an error in the input data.
6223	fn get_test_map<I, T, A>(
6224	iter: I,
6225	mut fun: impl FnMut(u64) -> T,
6226	alloc: A,
6227	) -> Result<HashMap<u64, CheckedCloneDrop<T>, DefaultHashBuilder, A>, String>
6228	where
6229	I: Iterator<Item = (bool, bool)> + Clone + ExactSizeIterator,
6230	A: Allocator,
6231	T: PartialEq + core::fmt::Debug,
6232	{
6233	use crate::scopeguard::guard;
6234
6235	let mut map: HashMap<u64, CheckedCloneDrop<T>, _, A> =
6236	HashMap::with_capacity_in(iter.size_hint().0, alloc);
6237	{
6238	let mut guard = guard(&mut map, \|map\| {
6239	for (_, value) in map.iter_mut() {
6240	value.panic_in_drop = `false`
6241	}
6242	});
6243
6244	let mut count = `0`;
6245	// Hash and Key must be equal to each other for controlling the elements placement.
6246	for (panic_in_clone, panic_in_drop) in iter.clone() {
6247	if core::mem::needs_drop::<T>() && panic_in_drop {
6248	return Err(String::from(
6249	"panic_in_drop can be set with a type that doesn't need to be dropped",
6250	));
6251	}
6252	guard.table.insert(
6253	count,
6254	(
6255	count,
6256	CheckedCloneDrop::new(panic_in_clone, panic_in_drop, fun(count)),
6257	),
6258	\|(k, _)\| *k,
6259	);
6260	count += `1`;
6261	}
6262
6263	// Let's check that all elements are located as we wanted
6264	let mut check_count = `0`;
6265	for ((key, value), (panic_in_clone, panic_in_drop)) in guard.iter().zip(iter) {
6266	if *key != check_count {
6267	return Err(format!(
6268	"key != check_count,`\n`key: `{}`,`\n`check_count: `{}`",
6269	key, check_count
6270	));
6271	}
6272	if value.dropped
6273	\|\| value.panic_in_clone != panic_in_clone
6274	\|\| value.panic_in_drop != panic_in_drop
6275	\|\| value.data != fun(check_count)
6276	{
6277	return Err(format!(
6278	"Value is not equal to expected,`\n`value: `{:?}`,`\n`expected: \
6279	`CheckedCloneDrop {{ panic_in_clone: {}, panic_in_drop: {}, dropped: {}, data: {:?} }}`",
6280	value, panic_in_clone, panic_in_drop, `false`, fun(check_count)
6281	));
6282	}
6283	check_count += `1`;
6284	}
6285
6286	if guard.len() != check_count as usize {
6287	return Err(format!(
6288	"map.len() != check_count,`\n`map.len(): `{}`,`\n`check_count: `{}`",
6289	guard.len(),
6290	check_count
6291	));
6292	}
6293
6294	if count != check_count {
6295	return Err(format!(
6296	"count != check_count,`\n`count: `{}`,`\n`check_count: `{}`",
6297	count, check_count
6298	));
6299	}
6300	core::mem::forget(guard);
6301	}
6302	Ok(map)
6303	}
6304
6305	const DISARMED: bool = `false`;
6306	const ARMED: bool = `true`;
6307
6308	const ARMED_FLAGS: [bool; `8`] = [
6309	DISARMED, DISARMED, DISARMED, ARMED, DISARMED, DISARMED, DISARMED, DISARMED,
6310	];
6311
6312	const DISARMED_FLAGS: [bool; `8`] = [
6313	DISARMED, DISARMED, DISARMED, DISARMED, DISARMED, DISARMED, DISARMED, DISARMED,
6314	];
6315
6316	#[test]
6317	#[should_panic = "panic in clone"]
6318	fn test_clone_memory_leaks_and_double_drop_one() {
6319	let dropped: Arc<AtomicI8> = Arc::new(AtomicI8::new(`2`));
6320
6321	{
6322	assert_eq!(ARMED_FLAGS.len(), DISARMED_FLAGS.len());
6323
6324	let map: HashMap<u64, CheckedCloneDrop<Vec<u64>>, DefaultHashBuilder, MyAlloc> =
6325	match get_test_map(
6326	ARMED_FLAGS.into_iter().zip(DISARMED_FLAGS),
6327	\|n\| vec![n],
6328	MyAlloc::new(dropped.clone()),
6329	) {
6330	Ok(map) => map,
6331	Err(msg) => panic!("{msg}"),
6332	};
6333
6334	// Clone should normally clone a few elements, and then (when the
6335	// clone function panics), deallocate both its own memory, memory
6336	// of `dropped: Arc<AtomicI8>` and the memory of already cloned
6337	// elements (Vec<i32> memory inside CheckedCloneDrop).
6338	let _map2 = map.clone();
6339	}
6340	}
6341
6342	#[test]
6343	#[should_panic = "panic in drop"]
6344	fn test_clone_memory_leaks_and_double_drop_two() {
6345	let dropped: Arc<AtomicI8> = Arc::new(AtomicI8::new(`2`));
6346
6347	{
6348	assert_eq!(ARMED_FLAGS.len(), DISARMED_FLAGS.len());
6349
6350	let map: HashMap<u64, CheckedCloneDrop<u64>, DefaultHashBuilder, _> = match get_test_map(
6351	DISARMED_FLAGS.into_iter().zip(DISARMED_FLAGS),
6352	\|n\| n,
6353	MyAlloc::new(dropped.clone()),
6354	) {
6355	Ok(map) => map,
6356	Err(msg) => panic!("{msg}"),
6357	};
6358
6359	let mut map2 = match get_test_map(
6360	DISARMED_FLAGS.into_iter().zip(ARMED_FLAGS),
6361	\|n\| n,
6362	MyAlloc::new(dropped.clone()),
6363	) {
6364	Ok(map) => map,
6365	Err(msg) => panic!("{msg}"),
6366	};
6367
6368	// The `clone_from` should try to drop the elements of `map2` without
6369	// double drop and leaking the allocator. Elements that have not been
6370	// dropped leak their memory.
6371	map2.clone_from(&map);
6372	}
6373	}
6374
6375	/// We check that we have a working table if the clone operation from another
6376	/// thread ended in a panic (when buckets of maps are equal to each other).
6377	#[test]
6378	fn test_catch_panic_clone_from_when_len_is_equal() {
6379	use std::thread;
6380
6381	let dropped: Arc<AtomicI8> = Arc::new(AtomicI8::new(`2`));
6382
6383	{
6384	assert_eq!(ARMED_FLAGS.len(), DISARMED_FLAGS.len());
6385
6386	let mut map = match get_test_map(
6387	DISARMED_FLAGS.into_iter().zip(DISARMED_FLAGS),
6388	\|n\| vec![n],
6389	MyAlloc::new(dropped.clone()),
6390	) {
6391	Ok(map) => map,
6392	Err(msg) => panic!("{msg}"),
6393	};
6394
6395	thread::scope(\|s\| {
6396	let result: thread::ScopedJoinHandle<'_, String> = s.spawn(\|\| {
6397	let scope_map =
6398	match get_test_map(ARMED_FLAGS.into_iter().zip(DISARMED_FLAGS), \|n\| vec![n * `2`], MyAlloc::new(dropped.clone())) {
6399	Ok(map) => map,
6400	Err(msg) => return msg,
6401	};
6402	if map.table.buckets() != scope_map.table.buckets() {
6403	return format!(
6404	"map.table.buckets() != scope_map.table.buckets(),`\n`left: `{}`,`\n`right: `{}`",
6405	map.table.buckets(), scope_map.table.buckets()
6406	);
6407	}
6408	map.clone_from(&scope_map);
6409	"We must fail the cloning!!!".to_owned()
6410	});
6411	if let Ok(msg) = result.join() {
6412	panic!("{msg}")
6413	}
6414	});
6415
6416	// Let's check that all iterators work fine and do not return elements
6417	// (especially `RawIterRange`, which does not depend on the number of
6418	// elements in the table, but looks directly at the control bytes)
6419	//
6420	// SAFETY: We know for sure that `RawTable` will outlive
6421	// the returned `RawIter / RawIterRange` iterator.
6422	assert_eq!(map.len(), `0`);
6423	assert_eq!(map.iter().count(), `0`);
6424	assert_eq!(unsafe { map.table.iter().count() }, `0`);
6425	assert_eq!(unsafe { map.table.iter().iter.count() }, `0`);
6426
6427	for idx in `0`..map.table.buckets() {
6428	let idx = idx as u64;
6429	assert!(
6430	map.table.find(idx, \|(k, _)\| *k == idx).is_none(),
6431	"Index: {idx}"
6432	);
6433	}
6434	}
6435
6436	// All allocator clones should already be dropped.
6437	assert_eq!(dropped.load(Ordering::SeqCst), `0`);
6438	}
6439
6440	/// We check that we have a working table if the clone operation from another
6441	/// thread ended in a panic (when buckets of maps are not equal to each other).
6442	#[test]
6443	fn test_catch_panic_clone_from_when_len_is_not_equal() {
6444	use std::thread;
6445
6446	let dropped: Arc<AtomicI8> = Arc::new(AtomicI8::new(`2`));
6447
6448	{
6449	assert_eq!(ARMED_FLAGS.len(), DISARMED_FLAGS.len());
6450
6451	let mut map = match get_test_map(
6452	[DISARMED].into_iter().zip([DISARMED]),
6453	\|n\| vec![n],
6454	MyAlloc::new(dropped.clone()),
6455	) {
6456	Ok(map) => map,
6457	Err(msg) => panic!("{msg}"),
6458	};
6459
6460	thread::scope(\|s\| {
6461	let result: thread::ScopedJoinHandle<'_, String> = s.spawn(\|\| {
6462	let scope_map = match get_test_map(
6463	ARMED_FLAGS.into_iter().zip(DISARMED_FLAGS),
6464	\|n\| vec![n * `2`],
6465	MyAlloc::new(dropped.clone()),
6466	) {
6467	Ok(map) => map,
6468	Err(msg) => return msg,
6469	};
6470	if map.table.buckets() == scope_map.table.buckets() {
6471	return format!(
6472	"map.table.buckets() == scope_map.table.buckets(): `{}`",
6473	map.table.buckets()
6474	);
6475	}
6476	map.clone_from(&scope_map);
6477	"We must fail the cloning!!!".to_owned()
6478	});
6479	if let Ok(msg) = result.join() {
6480	panic!("{msg}")
6481	}
6482	});
6483
6484	// Let's check that all iterators work fine and do not return elements
6485	// (especially `RawIterRange`, which does not depend on the number of
6486	// elements in the table, but looks directly at the control bytes)
6487	//
6488	// SAFETY: We know for sure that `RawTable` will outlive
6489	// the returned `RawIter / RawIterRange` iterator.
6490	assert_eq!(map.len(), `0`);
6491	assert_eq!(map.iter().count(), `0`);
6492	assert_eq!(unsafe { map.table.iter().count() }, `0`);
6493	assert_eq!(unsafe { map.table.iter().iter.count() }, `0`);
6494
6495	for idx in `0`..map.table.buckets() {
6496	let idx = idx as u64;
6497	assert!(
6498	map.table.find(idx, \|(k, _)\| *k == idx).is_none(),
6499	"Index: {idx}"
6500	);
6501	}
6502	}
6503
6504	// All allocator clones should already be dropped.
6505	assert_eq!(dropped.load(Ordering::SeqCst), `0`);
6506	}
6507
6508	#[test]
6509	fn test_allocation_info() {
6510	assert_eq!(HashMap::<(), ()>::new().allocation_size(), `0`);
6511	assert_eq!(HashMap::<u32, u32>::new().allocation_size(), `0`);
6512	assert!(
6513	HashMap::<u32, u32>::with_capacity(`1`).allocation_size() > core::mem::size_of::<u32>()
6514	);
6515	}
6516	}
6517