1 // Copyright 2014-2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
12 use self::VacantEntryState
::*;
17 use fmt
::{self, Debug}
;
19 use hash
::{Hash, Hasher, BuildHasher, SipHasher13}
;
20 use iter
::{FromIterator, FusedIterator}
;
21 use mem
::{self, replace}
;
22 use ops
::{Deref, Index}
;
23 use rand
::{self, Rng}
;
25 use super::table
::{self, Bucket, EmptyBucket, FullBucket, FullBucketMut, RawTable, SafeHash}
;
26 use super::table
::BucketState
::{Empty, Full}
;
28 const MIN_NONZERO_RAW_CAPACITY
: usize = 32; // must be a power of two
30 /// The default behavior of HashMap implements a maximum load factor of 90.9%.
32 struct DefaultResizePolicy
;
34 impl DefaultResizePolicy
{
35 fn new() -> DefaultResizePolicy
{
39 /// A hash map's "capacity" is the number of elements it can hold without
40 /// being resized. Its "raw capacity" is the number of slots required to
41 /// provide that capacity, accounting for maximum loading. The raw capacity
42 /// is always zero or a power of two.
44 fn raw_capacity(&self, len
: usize) -> usize {
48 // 1. Account for loading: `raw_capacity >= len * 1.1`.
49 // 2. Ensure it is a power of two.
50 // 3. Ensure it is at least the minimum size.
51 let mut raw_cap
= len
* 11 / 10;
52 assert
!(raw_cap
>= len
, "raw_cap overflow");
53 raw_cap
= raw_cap
.checked_next_power_of_two().expect("raw_capacity overflow");
54 raw_cap
= max(MIN_NONZERO_RAW_CAPACITY
, raw_cap
);
59 /// The capacity of the given raw capacity.
61 fn capacity(&self, raw_cap
: usize) -> usize {
62 // This doesn't have to be checked for overflow since allocation size
63 // in bytes will overflow earlier than multiplication by 10.
65 // As per https://github.com/rust-lang/rust/pull/30991 this is updated
66 // to be: (raw_cap * den + den - 1) / num
67 (raw_cap
* 10 + 10 - 1) / 11
71 // The main performance trick in this hashmap is called Robin Hood Hashing.
72 // It gains its excellent performance from one essential operation:
74 // If an insertion collides with an existing element, and that element's
75 // "probe distance" (how far away the element is from its ideal location)
76 // is higher than how far we've already probed, swap the elements.
78 // This massively lowers variance in probe distance, and allows us to get very
79 // high load factors with good performance. The 90% load factor I use is rather
82 // > Why a load factor of approximately 90%?
84 // In general, all the distances to initial buckets will converge on the mean.
85 // At a load factor of α, the odds of finding the target bucket after k
86 // probes is approximately 1-α^k. If we set this equal to 50% (since we converge
87 // on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round
88 // this down to make the math easier on the CPU and avoid its FPU.
89 // Since on average we start the probing in the middle of a cache line, this
90 // strategy pulls in two cache lines of hashes on every lookup. I think that's
91 // pretty good, but if you want to trade off some space, it could go down to one
92 // cache line on average with an α of 0.84.
94 // > Wait, what? Where did you get 1-α^k from?
96 // On the first probe, your odds of a collision with an existing element is α.
97 // The odds of doing this twice in a row is approximately α^2. For three times,
98 // α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT
99 // colliding after k tries is 1-α^k.
101 // The paper from 1986 cited below mentions an implementation which keeps track
102 // of the distance-to-initial-bucket histogram. This approach is not suitable
103 // for modern architectures because it requires maintaining an internal data
104 // structure. This allows very good first guesses, but we are most concerned
105 // with guessing entire cache lines, not individual indexes. Furthermore, array
106 // accesses are no longer linear and in one direction, as we have now. There
107 // is also memory and cache pressure that this would entail that would be very
108 // difficult to properly see in a microbenchmark.
110 // ## Future Improvements (FIXME!)
112 // Allow the load factor to be changed dynamically and/or at initialization.
114 // Also, would it be possible for us to reuse storage when growing the
115 // underlying table? This is exactly the use case for 'realloc', and may
116 // be worth exploring.
118 // ## Future Optimizations (FIXME!)
120 // Another possible design choice that I made without any real reason is
121 // parameterizing the raw table over keys and values. Technically, all we need
122 // is the size and alignment of keys and values, and the code should be just as
123 // efficient (well, we might need one for power-of-two size and one for not...).
124 // This has the potential to reduce code bloat in rust executables, without
125 // really losing anything except 4 words (key size, key alignment, val size,
126 // val alignment) which can be passed in to every call of a `RawTable` function.
127 // This would definitely be an avenue worth exploring if people start complaining
128 // about the size of rust executables.
130 // Annotate exceedingly likely branches in `table::make_hash`
131 // and `search_hashed` to reduce instruction cache pressure
132 // and mispredictions once it becomes possible (blocked on issue #11092).
134 // Shrinking the table could simply reallocate in place after moving buckets
135 // to the first half.
137 // The growth algorithm (fragment of the Proof of Correctness)
138 // --------------------
140 // The growth algorithm is basically a fast path of the naive reinsertion-
141 // during-resize algorithm. Other paths should never be taken.
143 // Consider growing a robin hood hashtable of capacity n. Normally, we do this
144 // by allocating a new table of capacity `2n`, and then individually reinsert
145 // each element in the old table into the new one. This guarantees that the
146 // new table is a valid robin hood hashtable with all the desired statistical
147 // properties. Remark that the order we reinsert the elements in should not
148 // matter. For simplicity and efficiency, we will consider only linear
149 // reinsertions, which consist of reinserting all elements in the old table
150 // into the new one by increasing order of index. However we will not be
151 // starting our reinsertions from index 0 in general. If we start from index
152 // i, for the purpose of reinsertion we will consider all elements with real
153 // index j < i to have virtual index n + j.
155 // Our hash generation scheme consists of generating a 64-bit hash and
156 // truncating the most significant bits. When moving to the new table, we
157 // simply introduce a new bit to the front of the hash. Therefore, if an
158 // elements has ideal index i in the old table, it can have one of two ideal
159 // locations in the new table. If the new bit is 0, then the new ideal index
160 // is i. If the new bit is 1, then the new ideal index is n + i. Intuitively,
161 // we are producing two independent tables of size n, and for each element we
162 // independently choose which table to insert it into with equal probability.
163 // However the rather than wrapping around themselves on overflowing their
164 // indexes, the first table overflows into the first, and the first into the
165 // second. Visually, our new table will look something like:
167 // [yy_xxx_xxxx_xxx|xx_yyy_yyyy_yyy]
169 // Where x's are elements inserted into the first table, y's are elements
170 // inserted into the second, and _'s are empty sections. We now define a few
171 // key concepts that we will use later. Note that this is a very abstract
172 // perspective of the table. A real resized table would be at least half
175 // Theorem: A linear robin hood reinsertion from the first ideal element
176 // produces identical results to a linear naive reinsertion from the same
179 // FIXME(Gankro, pczarn): review the proof and put it all in a separate README.md
181 /// A hash map implementation which uses linear probing with Robin Hood bucket
184 /// By default, `HashMap` uses a hashing algorithm selected to provide
185 /// resistance against HashDoS attacks. The algorithm is randomly seeded, and a
186 /// reasonable best-effort is made to generate this seed from a high quality,
187 /// secure source of randomness provided by the host without blocking the
188 /// program. Because of this, the randomness of the seed is dependant on the
189 /// quality of the system's random number generator at the time it is created.
190 /// In particular, seeds generated when the system's entropy pool is abnormally
191 /// low such as during system boot may be of a lower quality.
193 /// The default hashing algorithm is currently SipHash 1-3, though this is
194 /// subject to change at any point in the future. While its performance is very
195 /// competitive for medium sized keys, other hashing algorithms will outperform
196 /// it for small keys such as integers as well as large keys such as long
197 /// strings, though those algorithms will typically *not* protect against
198 /// attacks such as HashDoS.
200 /// The hashing algorithm can be replaced on a per-`HashMap` basis using the
201 /// `HashMap::default`, `HashMap::with_hasher`, and
202 /// `HashMap::with_capacity_and_hasher` methods. Many alternative algorithms
203 /// are available on crates.io, such as the `fnv` crate.
205 /// It is required that the keys implement the [`Eq`] and [`Hash`] traits, although
206 /// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
207 /// If you implement these yourself, it is important that the following
211 /// k1 == k2 -> hash(k1) == hash(k2)
214 /// In other words, if two keys are equal, their hashes must be equal.
216 /// It is a logic error for a key to be modified in such a way that the key's
217 /// hash, as determined by the [`Hash`] trait, or its equality, as determined by
218 /// the [`Eq`] trait, changes while it is in the map. This is normally only
219 /// possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
221 /// Relevant papers/articles:
223 /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)
224 /// 2. Emmanuel Goossaert. ["Robin Hood
225 /// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/)
226 /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift
227 /// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)
232 /// use std::collections::HashMap;
234 /// // type inference lets us omit an explicit type signature (which
235 /// // would be `HashMap<&str, &str>` in this example).
236 /// let mut book_reviews = HashMap::new();
238 /// // review some books.
239 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
240 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
241 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
242 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
244 /// // check for a specific one.
245 /// if !book_reviews.contains_key("Les Misérables") {
246 /// println!("We've got {} reviews, but Les Misérables ain't one.",
247 /// book_reviews.len());
250 /// // oops, this review has a lot of spelling mistakes, let's delete it.
251 /// book_reviews.remove("The Adventures of Sherlock Holmes");
253 /// // look up the values associated with some keys.
254 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
255 /// for book in &to_find {
256 /// match book_reviews.get(book) {
257 /// Some(review) => println!("{}: {}", book, review),
258 /// None => println!("{} is unreviewed.", book)
262 /// // iterate over everything.
263 /// for (book, review) in &book_reviews {
264 /// println!("{}: \"{}\"", book, review);
268 /// `HashMap` also implements an [`Entry API`](#method.entry), which allows
269 /// for more complex methods of getting, setting, updating and removing keys and
273 /// use std::collections::HashMap;
275 /// // type inference lets us omit an explicit type signature (which
276 /// // would be `HashMap<&str, u8>` in this example).
277 /// let mut player_stats = HashMap::new();
279 /// fn random_stat_buff() -> u8 {
280 /// // could actually return some random value here - let's just return
281 /// // some fixed value for now
285 /// // insert a key only if it doesn't already exist
286 /// player_stats.entry("health").or_insert(100);
288 /// // insert a key using a function that provides a new value only if it
289 /// // doesn't already exist
290 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
292 /// // update a key, guarding against the key possibly not being set
293 /// let stat = player_stats.entry("attack").or_insert(100);
294 /// *stat += random_stat_buff();
297 /// The easiest way to use `HashMap` with a custom type as key is to derive [`Eq`] and [`Hash`].
298 /// We must also derive [`PartialEq`].
300 /// [`Eq`]: ../../std/cmp/trait.Eq.html
301 /// [`Hash`]: ../../std/hash/trait.Hash.html
302 /// [`PartialEq`]: ../../std/cmp/trait.PartialEq.html
303 /// [`RefCell`]: ../../std/cell/struct.RefCell.html
304 /// [`Cell`]: ../../std/cell/struct.Cell.html
307 /// use std::collections::HashMap;
309 /// #[derive(Hash, Eq, PartialEq, Debug)]
316 /// /// Create a new Viking.
317 /// fn new(name: &str, country: &str) -> Viking {
318 /// Viking { name: name.to_string(), country: country.to_string() }
322 /// // Use a HashMap to store the vikings' health points.
323 /// let mut vikings = HashMap::new();
325 /// vikings.insert(Viking::new("Einar", "Norway"), 25);
326 /// vikings.insert(Viking::new("Olaf", "Denmark"), 24);
327 /// vikings.insert(Viking::new("Harald", "Iceland"), 12);
329 /// // Use derived implementation to print the status of the vikings.
330 /// for (viking, health) in &vikings {
331 /// println!("{:?} has {} hp", viking, health);
335 /// A HashMap with fixed list of elements can be initialized from an array:
338 /// use std::collections::HashMap;
341 /// let timber_resources: HashMap<&str, i32> =
342 /// [("Norway", 100),
345 /// .iter().cloned().collect();
346 /// // use the values stored in map
351 #[stable(feature = "rust1", since = "1.0.0")]
352 pub struct HashMap
<K
, V
, S
= RandomState
> {
353 // All hashes are keyed on these values, to prevent hash collision attacks.
356 table
: RawTable
<K
, V
>,
358 resize_policy
: DefaultResizePolicy
,
361 /// Search for a pre-hashed key.
363 fn search_hashed
<K
, V
, M
, F
>(table
: M
, hash
: SafeHash
, mut is_match
: F
) -> InternalEntry
<K
, V
, M
>
364 where M
: Deref
<Target
= RawTable
<K
, V
>>,
367 // This is the only function where capacity can be zero. To avoid
368 // undefined behavior when Bucket::new gets the raw bucket in this
369 // case, immediately return the appropriate search result.
370 if table
.capacity() == 0 {
371 return InternalEntry
::TableIsEmpty
;
374 let size
= table
.size() as isize;
375 let mut probe
= Bucket
::new(table
, hash
);
376 let ib
= probe
.index() as isize;
379 let full
= match probe
.peek() {
382 return InternalEntry
::Vacant
{
384 elem
: NoElem(bucket
),
387 Full(bucket
) => bucket
,
390 let robin_ib
= full
.index() as isize - full
.displacement() as isize;
393 // Found a luckier bucket than me.
394 // We can finish the search early if we hit any bucket
395 // with a lower distance to initial bucket than we've probed.
396 return InternalEntry
::Vacant
{
398 elem
: NeqElem(full
, robin_ib
as usize),
402 // If the hash doesn't match, it can't be this one..
403 if hash
== full
.hash() {
404 // If the key doesn't match, it can't be this one..
405 if is_match(full
.read().0) {
406 return InternalEntry
::Occupied { elem: full }
;
411 debug_assert
!(probe
.index() as isize != ib
+ size
+ 1);
415 fn pop_internal
<K
, V
>(starting_bucket
: FullBucketMut
<K
, V
>) -> (K
, V
) {
416 let (empty
, retkey
, retval
) = starting_bucket
.take();
417 let mut gap
= match empty
.gap_peek() {
419 None
=> return (retkey
, retval
),
422 while gap
.full().displacement() != 0 {
423 gap
= match gap
.shift() {
429 // Now we've done all our shifting. Return the value we grabbed earlier.
433 /// Perform robin hood bucket stealing at the given `bucket`. You must
434 /// also pass the position of that bucket's initial bucket so we don't have
435 /// to recalculate it.
437 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
438 fn robin_hood
<'a
, K
: 'a
, V
: 'a
>(bucket
: FullBucketMut
<'a
, K
, V
>,
444 let starting_index
= bucket
.index();
445 let size
= bucket
.table().size();
446 // Save the *starting point*.
447 let mut bucket
= bucket
.stash();
448 // There can be at most `size - dib` buckets to displace, because
449 // in the worst case, there are `size` elements and we already are
450 // `displacement` buckets away from the initial one.
451 let idx_end
= starting_index
+ size
- bucket
.displacement();
454 let (old_hash
, old_key
, old_val
) = bucket
.replace(hash
, key
, val
);
460 let probe
= bucket
.next();
461 debug_assert
!(probe
.index() != idx_end
);
463 let full_bucket
= match probe
.peek() {
466 let bucket
= bucket
.put(hash
, key
, val
);
467 // Now that it's stolen, just read the value's pointer
468 // right out of the table! Go back to the *starting point*.
470 // This use of `into_table` is misleading. It turns the
471 // bucket, which is a FullBucket on top of a
472 // FullBucketMut, into just one FullBucketMut. The "table"
473 // refers to the inner FullBucketMut in this context.
474 return bucket
.into_table().into_mut_refs().1;
476 Full(bucket
) => bucket
,
479 let probe_ib
= full_bucket
.index() - full_bucket
.displacement();
481 bucket
= full_bucket
;
483 // Robin hood! Steal the spot.
492 impl<K
, V
, S
> HashMap
<K
, V
, S
>
496 fn make_hash
<X
: ?Sized
>(&self, x
: &X
) -> SafeHash
499 table
::make_hash(&self.hash_builder
, x
)
502 /// Search for a key, yielding the index if it's found in the hashtable.
503 /// If you already have the hash for the key lying around, use
506 fn search
<'a
, Q
: ?Sized
>(&'a
self, q
: &Q
) -> InternalEntry
<K
, V
, &'a RawTable
<K
, V
>>
510 let hash
= self.make_hash(q
);
511 search_hashed(&self.table
, hash
, |k
| q
.eq(k
.borrow()))
515 fn search_mut
<'a
, Q
: ?Sized
>(&'a
mut self, q
: &Q
) -> InternalEntry
<K
, V
, &'a
mut RawTable
<K
, V
>>
519 let hash
= self.make_hash(q
);
520 search_hashed(&mut self.table
, hash
, |k
| q
.eq(k
.borrow()))
523 // The caller should ensure that invariants by Robin Hood Hashing hold.
524 fn insert_hashed_ordered(&mut self, hash
: SafeHash
, k
: K
, v
: V
) {
525 let raw_cap
= self.raw_capacity();
526 let mut buckets
= Bucket
::new(&mut self.table
, hash
);
527 let ib
= buckets
.index();
529 while buckets
.index() != ib
+ raw_cap
{
530 // We don't need to compare hashes for value swap.
531 // Not even DIBs for Robin Hood.
532 buckets
= match buckets
.peek() {
534 empty
.put(hash
, k
, v
);
537 Full(b
) => b
.into_bucket(),
541 panic
!("Internal HashMap error: Out of space.");
545 impl<K
: Hash
+ Eq
, V
> HashMap
<K
, V
, RandomState
> {
546 /// Creates an empty `HashMap`.
551 /// use std::collections::HashMap;
552 /// let mut map: HashMap<&str, isize> = HashMap::new();
555 #[stable(feature = "rust1", since = "1.0.0")]
556 pub fn new() -> HashMap
<K
, V
, RandomState
> {
560 /// Creates an empty `HashMap` with the specified capacity.
562 /// The hash map will be able to hold at least `capacity` elements without
563 /// reallocating. If `capacity` is 0, the hash map will not allocate.
568 /// use std::collections::HashMap;
569 /// let mut map: HashMap<&str, isize> = HashMap::with_capacity(10);
572 #[stable(feature = "rust1", since = "1.0.0")]
573 pub fn with_capacity(capacity
: usize) -> HashMap
<K
, V
, RandomState
> {
574 HashMap
::with_capacity_and_hasher(capacity
, Default
::default())
578 impl<K
, V
, S
> HashMap
<K
, V
, S
>
582 /// Creates an empty `HashMap` which will use the given hash builder to hash
585 /// The created map has the default initial capacity.
587 /// Warning: `hash_builder` is normally randomly generated, and
588 /// is designed to allow HashMaps to be resistant to attacks that
589 /// cause many collisions and very poor performance. Setting it
590 /// manually using this function can expose a DoS attack vector.
595 /// use std::collections::HashMap;
596 /// use std::collections::hash_map::RandomState;
598 /// let s = RandomState::new();
599 /// let mut map = HashMap::with_hasher(s);
600 /// map.insert(1, 2);
603 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
604 pub fn with_hasher(hash_builder
: S
) -> HashMap
<K
, V
, S
> {
606 hash_builder
: hash_builder
,
607 resize_policy
: DefaultResizePolicy
::new(),
608 table
: RawTable
::new(0),
612 /// Creates an empty `HashMap` with the specified capacity, using `hasher`
613 /// to hash the keys.
615 /// The hash map will be able to hold at least `capacity` elements without
616 /// reallocating. If `capacity` is 0, the hash map will not allocate.
617 /// Warning: `hasher` is normally randomly generated, and
618 /// is designed to allow HashMaps to be resistant to attacks that
619 /// cause many collisions and very poor performance. Setting it
620 /// manually using this function can expose a DoS attack vector.
625 /// use std::collections::HashMap;
626 /// use std::collections::hash_map::RandomState;
628 /// let s = RandomState::new();
629 /// let mut map = HashMap::with_capacity_and_hasher(10, s);
630 /// map.insert(1, 2);
633 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
634 pub fn with_capacity_and_hasher(capacity
: usize, hash_builder
: S
) -> HashMap
<K
, V
, S
> {
635 let resize_policy
= DefaultResizePolicy
::new();
636 let raw_cap
= resize_policy
.raw_capacity(capacity
);
638 hash_builder
: hash_builder
,
639 resize_policy
: resize_policy
,
640 table
: RawTable
::new(raw_cap
),
644 /// Returns a reference to the map's hasher.
645 #[stable(feature = "hashmap_public_hasher", since = "1.9.0")]
646 pub fn hasher(&self) -> &S
{
650 /// Returns the number of elements the map can hold without reallocating.
652 /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
653 /// more, but is guaranteed to be able to hold at least this many.
658 /// use std::collections::HashMap;
659 /// let map: HashMap<isize, isize> = HashMap::with_capacity(100);
660 /// assert!(map.capacity() >= 100);
663 #[stable(feature = "rust1", since = "1.0.0")]
664 pub fn capacity(&self) -> usize {
665 self.resize_policy
.capacity(self.raw_capacity())
668 /// Returns the hash map's raw capacity.
670 fn raw_capacity(&self) -> usize {
671 self.table
.capacity()
674 /// Reserves capacity for at least `additional` more elements to be inserted
675 /// in the `HashMap`. The collection may reserve more space to avoid
676 /// frequent reallocations.
680 /// Panics if the new allocation size overflows `usize`.
685 /// use std::collections::HashMap;
686 /// let mut map: HashMap<&str, isize> = HashMap::new();
689 #[stable(feature = "rust1", since = "1.0.0")]
690 pub fn reserve(&mut self, additional
: usize) {
691 let remaining
= self.capacity() - self.len(); // this can't overflow
692 if remaining
< additional
{
693 let min_cap
= self.len().checked_add(additional
).expect("reserve overflow");
694 let raw_cap
= self.resize_policy
.raw_capacity(min_cap
);
695 self.resize(raw_cap
);
699 /// Resizes the internal vectors to a new capacity. It's your
700 /// responsibility to:
701 /// 1) Ensure `new_raw_cap` is enough for all the elements, accounting
702 /// for the load factor.
703 /// 2) Ensure `new_raw_cap` is a power of two or zero.
704 fn resize(&mut self, new_raw_cap
: usize) {
705 assert
!(self.table
.size() <= new_raw_cap
);
706 assert
!(new_raw_cap
.is_power_of_two() || new_raw_cap
== 0);
708 let mut old_table
= replace(&mut self.table
, RawTable
::new(new_raw_cap
));
709 let old_size
= old_table
.size();
711 if old_table
.capacity() == 0 || old_table
.size() == 0 {
716 // Specialization of the other branch.
717 let mut bucket
= Bucket
::first(&mut old_table
);
719 // "So a few of the first shall be last: for many be called,
722 // We'll most likely encounter a few buckets at the beginning that
723 // have their initial buckets near the end of the table. They were
724 // placed at the beginning as the probe wrapped around the table
725 // during insertion. We must skip forward to a bucket that won't
726 // get reinserted too early and won't unfairly steal others spot.
727 // This eliminates the need for robin hood.
729 bucket
= match bucket
.peek() {
731 if full
.displacement() == 0 {
732 // This bucket occupies its ideal spot.
733 // It indicates the start of another "cluster".
734 bucket
= full
.into_bucket();
737 // Leaving this bucket in the last cluster for later.
741 // Encountered a hole between clusters.
748 // This is how the buckets might be laid out in memory:
749 // ($ marks an initialized bucket)
751 // |$$$_$$$$$$_$$$$$|
753 // But we've skipped the entire initial cluster of buckets
754 // and will continue iteration in this order:
757 // ^ wrap around once end is reached
760 // ^ exit once table.size == 0
762 bucket
= match bucket
.peek() {
764 let h
= bucket
.hash();
765 let (b
, k
, v
) = bucket
.take();
766 self.insert_hashed_ordered(h
, k
, v
);
767 if b
.table().size() == 0 {
772 Empty(b
) => b
.into_bucket(),
777 assert_eq
!(self.table
.size(), old_size
);
780 /// Shrinks the capacity of the map as much as possible. It will drop
781 /// down as much as possible while maintaining the internal rules
782 /// and possibly leaving some space in accordance with the resize policy.
787 /// use std::collections::HashMap;
789 /// let mut map: HashMap<isize, isize> = HashMap::with_capacity(100);
790 /// map.insert(1, 2);
791 /// map.insert(3, 4);
792 /// assert!(map.capacity() >= 100);
793 /// map.shrink_to_fit();
794 /// assert!(map.capacity() >= 2);
796 #[stable(feature = "rust1", since = "1.0.0")]
797 pub fn shrink_to_fit(&mut self) {
798 let new_raw_cap
= self.resize_policy
.raw_capacity(self.len());
799 if self.raw_capacity() != new_raw_cap
{
800 let old_table
= replace(&mut self.table
, RawTable
::new(new_raw_cap
));
801 let old_size
= old_table
.size();
803 // Shrink the table. Naive algorithm for resizing:
804 for (h
, k
, v
) in old_table
.into_iter() {
805 self.insert_hashed_nocheck(h
, k
, v
);
808 debug_assert_eq
!(self.table
.size(), old_size
);
812 /// Insert a pre-hashed key-value pair, without first checking
813 /// that there's enough room in the buckets. Returns a reference to the
814 /// newly insert value.
816 /// If the key already exists, the hashtable will be returned untouched
817 /// and a reference to the existing element will be returned.
818 fn insert_hashed_nocheck(&mut self, hash
: SafeHash
, k
: K
, v
: V
) -> Option
<V
> {
819 let entry
= search_hashed(&mut self.table
, hash
, |key
| *key
== k
).into_entry(k
);
821 Some(Occupied(mut elem
)) => Some(elem
.insert(v
)),
822 Some(Vacant(elem
)) => {
826 None
=> unreachable
!(),
830 /// An iterator visiting all keys in arbitrary order.
831 /// Iterator element type is `&'a K`.
836 /// use std::collections::HashMap;
838 /// let mut map = HashMap::new();
839 /// map.insert("a", 1);
840 /// map.insert("b", 2);
841 /// map.insert("c", 3);
843 /// for key in map.keys() {
844 /// println!("{}", key);
847 #[stable(feature = "rust1", since = "1.0.0")]
848 pub fn keys(&self) -> Keys
<K
, V
> {
849 Keys { inner: self.iter() }
852 /// An iterator visiting all values in arbitrary order.
853 /// Iterator element type is `&'a V`.
858 /// use std::collections::HashMap;
860 /// let mut map = HashMap::new();
861 /// map.insert("a", 1);
862 /// map.insert("b", 2);
863 /// map.insert("c", 3);
865 /// for val in map.values() {
866 /// println!("{}", val);
869 #[stable(feature = "rust1", since = "1.0.0")]
870 pub fn values(&self) -> Values
<K
, V
> {
871 Values { inner: self.iter() }
874 /// An iterator visiting all values mutably in arbitrary order.
875 /// Iterator element type is `&'a mut V`.
880 /// use std::collections::HashMap;
882 /// let mut map = HashMap::new();
884 /// map.insert("a", 1);
885 /// map.insert("b", 2);
886 /// map.insert("c", 3);
888 /// for val in map.values_mut() {
889 /// *val = *val + 10;
892 /// for val in map.values() {
893 /// println!("{}", val);
896 #[stable(feature = "map_values_mut", since = "1.10.0")]
897 pub fn values_mut(&mut self) -> ValuesMut
<K
, V
> {
898 ValuesMut { inner: self.iter_mut() }
901 /// An iterator visiting all key-value pairs in arbitrary order.
902 /// Iterator element type is `(&'a K, &'a V)`.
907 /// use std::collections::HashMap;
909 /// let mut map = HashMap::new();
910 /// map.insert("a", 1);
911 /// map.insert("b", 2);
912 /// map.insert("c", 3);
914 /// for (key, val) in map.iter() {
915 /// println!("key: {} val: {}", key, val);
918 #[stable(feature = "rust1", since = "1.0.0")]
919 pub fn iter(&self) -> Iter
<K
, V
> {
920 Iter { inner: self.table.iter() }
923 /// An iterator visiting all key-value pairs in arbitrary order,
924 /// with mutable references to the values.
925 /// Iterator element type is `(&'a K, &'a mut V)`.
930 /// use std::collections::HashMap;
932 /// let mut map = HashMap::new();
933 /// map.insert("a", 1);
934 /// map.insert("b", 2);
935 /// map.insert("c", 3);
937 /// // Update all values
938 /// for (_, val) in map.iter_mut() {
942 /// for (key, val) in &map {
943 /// println!("key: {} val: {}", key, val);
946 #[stable(feature = "rust1", since = "1.0.0")]
947 pub fn iter_mut(&mut self) -> IterMut
<K
, V
> {
948 IterMut { inner: self.table.iter_mut() }
951 /// Gets the given key's corresponding entry in the map for in-place manipulation.
956 /// use std::collections::HashMap;
958 /// let mut letters = HashMap::new();
960 /// for ch in "a short treatise on fungi".chars() {
961 /// let counter = letters.entry(ch).or_insert(0);
965 /// assert_eq!(letters[&'s'], 2);
966 /// assert_eq!(letters[&'t'], 3);
967 /// assert_eq!(letters[&'u'], 1);
968 /// assert_eq!(letters.get(&'y'), None);
970 #[stable(feature = "rust1", since = "1.0.0")]
971 pub fn entry(&mut self, key
: K
) -> Entry
<K
, V
> {
974 self.search_mut(&key
).into_entry(key
).expect("unreachable")
977 /// Returns the number of elements in the map.
982 /// use std::collections::HashMap;
984 /// let mut a = HashMap::new();
985 /// assert_eq!(a.len(), 0);
986 /// a.insert(1, "a");
987 /// assert_eq!(a.len(), 1);
989 #[stable(feature = "rust1", since = "1.0.0")]
990 pub fn len(&self) -> usize {
994 /// Returns true if the map contains no elements.
999 /// use std::collections::HashMap;
1001 /// let mut a = HashMap::new();
1002 /// assert!(a.is_empty());
1003 /// a.insert(1, "a");
1004 /// assert!(!a.is_empty());
1007 #[stable(feature = "rust1", since = "1.0.0")]
1008 pub fn is_empty(&self) -> bool
{
1012 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
1013 /// allocated memory for reuse.
1018 /// use std::collections::HashMap;
1020 /// let mut a = HashMap::new();
1021 /// a.insert(1, "a");
1022 /// a.insert(2, "b");
1024 /// for (k, v) in a.drain().take(1) {
1025 /// assert!(k == 1 || k == 2);
1026 /// assert!(v == "a" || v == "b");
1029 /// assert!(a.is_empty());
1032 #[stable(feature = "drain", since = "1.6.0")]
1033 pub fn drain(&mut self) -> Drain
<K
, V
> {
1034 Drain { inner: self.table.drain() }
1037 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
1043 /// use std::collections::HashMap;
1045 /// let mut a = HashMap::new();
1046 /// a.insert(1, "a");
1048 /// assert!(a.is_empty());
1050 #[stable(feature = "rust1", since = "1.0.0")]
1052 pub fn clear(&mut self) {
1056 /// Returns a reference to the value corresponding to the key.
1058 /// The key may be any borrowed form of the map's key type, but
1059 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1062 /// [`Eq`]: ../../std/cmp/trait.Eq.html
1063 /// [`Hash`]: ../../std/hash/trait.Hash.html
1068 /// use std::collections::HashMap;
1070 /// let mut map = HashMap::new();
1071 /// map.insert(1, "a");
1072 /// assert_eq!(map.get(&1), Some(&"a"));
1073 /// assert_eq!(map.get(&2), None);
1075 #[stable(feature = "rust1", since = "1.0.0")]
1076 pub fn get
<Q
: ?Sized
>(&self, k
: &Q
) -> Option
<&V
>
1080 self.search(k
).into_occupied_bucket().map(|bucket
| bucket
.into_refs().1)
1083 /// Returns true if the map contains a value for the specified key.
1085 /// The key may be any borrowed form of the map's key type, but
1086 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1089 /// [`Eq`]: ../../std/cmp/trait.Eq.html
1090 /// [`Hash`]: ../../std/hash/trait.Hash.html
1095 /// use std::collections::HashMap;
1097 /// let mut map = HashMap::new();
1098 /// map.insert(1, "a");
1099 /// assert_eq!(map.contains_key(&1), true);
1100 /// assert_eq!(map.contains_key(&2), false);
1102 #[stable(feature = "rust1", since = "1.0.0")]
1103 pub fn contains_key
<Q
: ?Sized
>(&self, k
: &Q
) -> bool
1107 self.search(k
).into_occupied_bucket().is_some()
1110 /// Returns a mutable reference to the value corresponding to the key.
1112 /// The key may be any borrowed form of the map's key type, but
1113 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1116 /// [`Eq`]: ../../std/cmp/trait.Eq.html
1117 /// [`Hash`]: ../../std/hash/trait.Hash.html
1122 /// use std::collections::HashMap;
1124 /// let mut map = HashMap::new();
1125 /// map.insert(1, "a");
1126 /// if let Some(x) = map.get_mut(&1) {
1129 /// assert_eq!(map[&1], "b");
1131 #[stable(feature = "rust1", since = "1.0.0")]
1132 pub fn get_mut
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<&mut V
>
1136 self.search_mut(k
).into_occupied_bucket().map(|bucket
| bucket
.into_mut_refs().1)
1139 /// Inserts a key-value pair into the map.
1141 /// If the map did not have this key present, `None` is returned.
1143 /// If the map did have this key present, the value is updated, and the old
1144 /// value is returned. The key is not updated, though; this matters for
1145 /// types that can be `==` without being identical. See the [module-level
1146 /// documentation] for more.
1148 /// [module-level documentation]: index.html#insert-and-complex-keys
1153 /// use std::collections::HashMap;
1155 /// let mut map = HashMap::new();
1156 /// assert_eq!(map.insert(37, "a"), None);
1157 /// assert_eq!(map.is_empty(), false);
1159 /// map.insert(37, "b");
1160 /// assert_eq!(map.insert(37, "c"), Some("b"));
1161 /// assert_eq!(map[&37], "c");
1163 #[stable(feature = "rust1", since = "1.0.0")]
1164 pub fn insert(&mut self, k
: K
, v
: V
) -> Option
<V
> {
1165 let hash
= self.make_hash(&k
);
1167 self.insert_hashed_nocheck(hash
, k
, v
)
1170 /// Removes a key from the map, returning the value at the key if the key
1171 /// was previously in the map.
1173 /// The key may be any borrowed form of the map's key type, but
1174 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1177 /// [`Eq`]: ../../std/cmp/trait.Eq.html
1178 /// [`Hash`]: ../../std/hash/trait.Hash.html
1183 /// use std::collections::HashMap;
1185 /// let mut map = HashMap::new();
1186 /// map.insert(1, "a");
1187 /// assert_eq!(map.remove(&1), Some("a"));
1188 /// assert_eq!(map.remove(&1), None);
1190 #[stable(feature = "rust1", since = "1.0.0")]
1191 pub fn remove
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<V
>
1195 if self.table
.size() == 0 {
1199 self.search_mut(k
).into_occupied_bucket().map(|bucket
| pop_internal(bucket
).1)
1203 #[stable(feature = "rust1", since = "1.0.0")]
1204 impl<K
, V
, S
> PartialEq
for HashMap
<K
, V
, S
>
1209 fn eq(&self, other
: &HashMap
<K
, V
, S
>) -> bool
{
1210 if self.len() != other
.len() {
1214 self.iter().all(|(key
, value
)| other
.get(key
).map_or(false, |v
| *value
== *v
))
1218 #[stable(feature = "rust1", since = "1.0.0")]
1219 impl<K
, V
, S
> Eq
for HashMap
<K
, V
, S
>
1226 #[stable(feature = "rust1", since = "1.0.0")]
1227 impl<K
, V
, S
> Debug
for HashMap
<K
, V
, S
>
1228 where K
: Eq
+ Hash
+ Debug
,
1232 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1233 f
.debug_map().entries(self.iter()).finish()
1237 #[stable(feature = "rust1", since = "1.0.0")]
1238 impl<K
, V
, S
> Default
for HashMap
<K
, V
, S
>
1240 S
: BuildHasher
+ Default
1242 /// Creates an empty `HashMap<K, V, S>`, with the `Default` value for the hasher.
1243 fn default() -> HashMap
<K
, V
, S
> {
1244 HashMap
::with_hasher(Default
::default())
1248 #[stable(feature = "rust1", since = "1.0.0")]
1249 impl<'a
, K
, Q
: ?Sized
, V
, S
> Index
<&'a Q
> for HashMap
<K
, V
, S
>
1250 where K
: Eq
+ Hash
+ Borrow
<Q
>,
1257 fn index(&self, index
: &Q
) -> &V
{
1258 self.get(index
).expect("no entry found for key")
1262 /// HashMap iterator.
1263 #[stable(feature = "rust1", since = "1.0.0")]
1264 pub struct Iter
<'a
, K
: 'a
, V
: 'a
> {
1265 inner
: table
::Iter
<'a
, K
, V
>,
1268 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1269 #[stable(feature = "rust1", since = "1.0.0")]
1270 impl<'a
, K
, V
> Clone
for Iter
<'a
, K
, V
> {
1271 fn clone(&self) -> Iter
<'a
, K
, V
> {
1272 Iter { inner: self.inner.clone() }
1276 /// HashMap mutable values iterator.
1277 #[stable(feature = "rust1", since = "1.0.0")]
1278 pub struct IterMut
<'a
, K
: 'a
, V
: 'a
> {
1279 inner
: table
::IterMut
<'a
, K
, V
>,
1282 /// HashMap move iterator.
1283 #[stable(feature = "rust1", since = "1.0.0")]
1284 pub struct IntoIter
<K
, V
> {
1285 inner
: table
::IntoIter
<K
, V
>,
1288 /// HashMap keys iterator.
1289 #[stable(feature = "rust1", since = "1.0.0")]
1290 pub struct Keys
<'a
, K
: 'a
, V
: 'a
> {
1291 inner
: Iter
<'a
, K
, V
>,
1294 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1295 #[stable(feature = "rust1", since = "1.0.0")]
1296 impl<'a
, K
, V
> Clone
for Keys
<'a
, K
, V
> {
1297 fn clone(&self) -> Keys
<'a
, K
, V
> {
1298 Keys { inner: self.inner.clone() }
1302 /// HashMap values iterator.
1303 #[stable(feature = "rust1", since = "1.0.0")]
1304 pub struct Values
<'a
, K
: 'a
, V
: 'a
> {
1305 inner
: Iter
<'a
, K
, V
>,
1308 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1309 #[stable(feature = "rust1", since = "1.0.0")]
1310 impl<'a
, K
, V
> Clone
for Values
<'a
, K
, V
> {
1311 fn clone(&self) -> Values
<'a
, K
, V
> {
1312 Values { inner: self.inner.clone() }
1316 /// HashMap drain iterator.
1317 #[stable(feature = "drain", since = "1.6.0")]
1318 pub struct Drain
<'a
, K
: 'a
, V
: 'a
> {
1319 inner
: table
::Drain
<'a
, K
, V
>,
1322 /// Mutable HashMap values iterator.
1323 #[stable(feature = "map_values_mut", since = "1.10.0")]
1324 pub struct ValuesMut
<'a
, K
: 'a
, V
: 'a
> {
1325 inner
: IterMut
<'a
, K
, V
>,
1328 enum InternalEntry
<K
, V
, M
> {
1329 Occupied { elem: FullBucket<K, V, M> }
,
1332 elem
: VacantEntryState
<K
, V
, M
>,
1337 impl<K
, V
, M
> InternalEntry
<K
, V
, M
> {
1339 fn into_occupied_bucket(self) -> Option
<FullBucket
<K
, V
, M
>> {
1341 InternalEntry
::Occupied { elem }
=> Some(elem
),
1347 impl<'a
, K
, V
> InternalEntry
<K
, V
, &'a
mut RawTable
<K
, V
>> {
1349 fn into_entry(self, key
: K
) -> Option
<Entry
<'a
, K
, V
>> {
1351 InternalEntry
::Occupied { elem }
=> {
1352 Some(Occupied(OccupiedEntry
{
1357 InternalEntry
::Vacant { hash, elem }
=> {
1358 Some(Vacant(VacantEntry
{
1364 InternalEntry
::TableIsEmpty
=> None
,
1369 /// A view into a single location in a map, which may be vacant or occupied.
1370 /// This enum is constructed from the [`entry`] method on [`HashMap`].
1372 /// [`HashMap`]: struct.HashMap.html
1373 /// [`entry`]: struct.HashMap.html#method.entry
1374 #[stable(feature = "rust1", since = "1.0.0")]
1375 pub enum Entry
<'a
, K
: 'a
, V
: 'a
> {
1376 /// An occupied Entry.
1377 #[stable(feature = "rust1", since = "1.0.0")]
1378 Occupied(#[stable(feature = "rust1", since = "1.0.0")]
1379 OccupiedEntry
<'a
, K
, V
>),
1382 #[stable(feature = "rust1", since = "1.0.0")]
1383 Vacant(#[stable(feature = "rust1", since = "1.0.0")]
1384 VacantEntry
<'a
, K
, V
>),
1387 #[stable(feature= "debug_hash_map", since = "1.12.0")]
1388 impl<'a
, K
: 'a
+ Debug
, V
: 'a
+ Debug
> Debug
for Entry
<'a
, K
, V
> {
1389 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1392 f
.debug_tuple("Entry")
1396 Occupied(ref o
) => {
1397 f
.debug_tuple("Entry")
1405 /// A view into a single occupied location in a HashMap.
1406 /// It is part of the [`Entry`] enum.
1408 /// [`Entry`]: enum.Entry.html
1409 #[stable(feature = "rust1", since = "1.0.0")]
1410 pub struct OccupiedEntry
<'a
, K
: 'a
, V
: 'a
> {
1412 elem
: FullBucket
<K
, V
, &'a
mut RawTable
<K
, V
>>,
1415 #[stable(feature= "debug_hash_map", since = "1.12.0")]
1416 impl<'a
, K
: 'a
+ Debug
, V
: 'a
+ Debug
> Debug
for OccupiedEntry
<'a
, K
, V
> {
1417 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1418 f
.debug_struct("OccupiedEntry")
1419 .field("key", self.key())
1420 .field("value", self.get())
1425 /// A view into a single empty location in a HashMap.
1426 /// It is part of the [`Entry`] enum.
1428 /// [`Entry`]: enum.Entry.html
1429 #[stable(feature = "rust1", since = "1.0.0")]
1430 pub struct VacantEntry
<'a
, K
: 'a
, V
: 'a
> {
1433 elem
: VacantEntryState
<K
, V
, &'a
mut RawTable
<K
, V
>>,
1436 #[stable(feature= "debug_hash_map", since = "1.12.0")]
1437 impl<'a
, K
: 'a
+ Debug
, V
: 'a
> Debug
for VacantEntry
<'a
, K
, V
> {
1438 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1439 f
.debug_tuple("VacantEntry")
1445 /// Possible states of a VacantEntry.
1446 enum VacantEntryState
<K
, V
, M
> {
1447 /// The index is occupied, but the key to insert has precedence,
1448 /// and will kick the current one out on insertion.
1449 NeqElem(FullBucket
<K
, V
, M
>, usize),
1450 /// The index is genuinely vacant.
1451 NoElem(EmptyBucket
<K
, V
, M
>),
1454 #[stable(feature = "rust1", since = "1.0.0")]
1455 impl<'a
, K
, V
, S
> IntoIterator
for &'a HashMap
<K
, V
, S
>
1459 type Item
= (&'a K
, &'a V
);
1460 type IntoIter
= Iter
<'a
, K
, V
>;
1462 fn into_iter(self) -> Iter
<'a
, K
, V
> {
1467 #[stable(feature = "rust1", since = "1.0.0")]
1468 impl<'a
, K
, V
, S
> IntoIterator
for &'a
mut HashMap
<K
, V
, S
>
1472 type Item
= (&'a K
, &'a
mut V
);
1473 type IntoIter
= IterMut
<'a
, K
, V
>;
1475 fn into_iter(mut self) -> IterMut
<'a
, K
, V
> {
1480 #[stable(feature = "rust1", since = "1.0.0")]
1481 impl<K
, V
, S
> IntoIterator
for HashMap
<K
, V
, S
>
1486 type IntoIter
= IntoIter
<K
, V
>;
1488 /// Creates a consuming iterator, that is, one that moves each key-value
1489 /// pair out of the map in arbitrary order. The map cannot be used after
1495 /// use std::collections::HashMap;
1497 /// let mut map = HashMap::new();
1498 /// map.insert("a", 1);
1499 /// map.insert("b", 2);
1500 /// map.insert("c", 3);
1502 /// // Not possible with .iter()
1503 /// let vec: Vec<(&str, isize)> = map.into_iter().collect();
1505 fn into_iter(self) -> IntoIter
<K
, V
> {
1506 IntoIter { inner: self.table.into_iter() }
1510 #[stable(feature = "rust1", since = "1.0.0")]
1511 impl<'a
, K
, V
> Iterator
for Iter
<'a
, K
, V
> {
1512 type Item
= (&'a K
, &'a V
);
1515 fn next(&mut self) -> Option
<(&'a K
, &'a V
)> {
1519 fn size_hint(&self) -> (usize, Option
<usize>) {
1520 self.inner
.size_hint()
1523 #[stable(feature = "rust1", since = "1.0.0")]
1524 impl<'a
, K
, V
> ExactSizeIterator
for Iter
<'a
, K
, V
> {
1526 fn len(&self) -> usize {
1531 #[unstable(feature = "fused", issue = "35602")]
1532 impl<'a
, K
, V
> FusedIterator
for Iter
<'a
, K
, V
> {}
1534 #[stable(feature = "rust1", since = "1.0.0")]
1535 impl<'a
, K
, V
> Iterator
for IterMut
<'a
, K
, V
> {
1536 type Item
= (&'a K
, &'a
mut V
);
1539 fn next(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1543 fn size_hint(&self) -> (usize, Option
<usize>) {
1544 self.inner
.size_hint()
1547 #[stable(feature = "rust1", since = "1.0.0")]
1548 impl<'a
, K
, V
> ExactSizeIterator
for IterMut
<'a
, K
, V
> {
1550 fn len(&self) -> usize {
1554 #[unstable(feature = "fused", issue = "35602")]
1555 impl<'a
, K
, V
> FusedIterator
for IterMut
<'a
, K
, V
> {}
1557 #[stable(feature = "rust1", since = "1.0.0")]
1558 impl<K
, V
> Iterator
for IntoIter
<K
, V
> {
1562 fn next(&mut self) -> Option
<(K
, V
)> {
1563 self.inner
.next().map(|(_
, k
, v
)| (k
, v
))
1566 fn size_hint(&self) -> (usize, Option
<usize>) {
1567 self.inner
.size_hint()
1570 #[stable(feature = "rust1", since = "1.0.0")]
1571 impl<K
, V
> ExactSizeIterator
for IntoIter
<K
, V
> {
1573 fn len(&self) -> usize {
1577 #[unstable(feature = "fused", issue = "35602")]
1578 impl<K
, V
> FusedIterator
for IntoIter
<K
, V
> {}
1580 #[stable(feature = "rust1", since = "1.0.0")]
1581 impl<'a
, K
, V
> Iterator
for Keys
<'a
, K
, V
> {
1585 fn next(&mut self) -> Option
<(&'a K
)> {
1586 self.inner
.next().map(|(k
, _
)| k
)
1589 fn size_hint(&self) -> (usize, Option
<usize>) {
1590 self.inner
.size_hint()
1593 #[stable(feature = "rust1", since = "1.0.0")]
1594 impl<'a
, K
, V
> ExactSizeIterator
for Keys
<'a
, K
, V
> {
1596 fn len(&self) -> usize {
1600 #[unstable(feature = "fused", issue = "35602")]
1601 impl<'a
, K
, V
> FusedIterator
for Keys
<'a
, K
, V
> {}
1603 #[stable(feature = "rust1", since = "1.0.0")]
1604 impl<'a
, K
, V
> Iterator
for Values
<'a
, K
, V
> {
1608 fn next(&mut self) -> Option
<(&'a V
)> {
1609 self.inner
.next().map(|(_
, v
)| v
)
1612 fn size_hint(&self) -> (usize, Option
<usize>) {
1613 self.inner
.size_hint()
1616 #[stable(feature = "rust1", since = "1.0.0")]
1617 impl<'a
, K
, V
> ExactSizeIterator
for Values
<'a
, K
, V
> {
1619 fn len(&self) -> usize {
1623 #[unstable(feature = "fused", issue = "35602")]
1624 impl<'a
, K
, V
> FusedIterator
for Values
<'a
, K
, V
> {}
1626 #[stable(feature = "map_values_mut", since = "1.10.0")]
1627 impl<'a
, K
, V
> Iterator
for ValuesMut
<'a
, K
, V
> {
1628 type Item
= &'a
mut V
;
1631 fn next(&mut self) -> Option
<(&'a
mut V
)> {
1632 self.inner
.next().map(|(_
, v
)| v
)
1635 fn size_hint(&self) -> (usize, Option
<usize>) {
1636 self.inner
.size_hint()
1639 #[stable(feature = "map_values_mut", since = "1.10.0")]
1640 impl<'a
, K
, V
> ExactSizeIterator
for ValuesMut
<'a
, K
, V
> {
1642 fn len(&self) -> usize {
1646 #[unstable(feature = "fused", issue = "35602")]
1647 impl<'a
, K
, V
> FusedIterator
for ValuesMut
<'a
, K
, V
> {}
1649 #[stable(feature = "drain", since = "1.6.0")]
1650 impl<'a
, K
, V
> Iterator
for Drain
<'a
, K
, V
> {
1654 fn next(&mut self) -> Option
<(K
, V
)> {
1655 self.inner
.next().map(|(_
, k
, v
)| (k
, v
))
1658 fn size_hint(&self) -> (usize, Option
<usize>) {
1659 self.inner
.size_hint()
1662 #[stable(feature = "drain", since = "1.6.0")]
1663 impl<'a
, K
, V
> ExactSizeIterator
for Drain
<'a
, K
, V
> {
1665 fn len(&self) -> usize {
1669 #[unstable(feature = "fused", issue = "35602")]
1670 impl<'a
, K
, V
> FusedIterator
for Drain
<'a
, K
, V
> {}
1672 impl<'a
, K
, V
> Entry
<'a
, K
, V
> {
1673 #[stable(feature = "rust1", since = "1.0.0")]
1674 /// Ensures a value is in the entry by inserting the default if empty, and returns
1675 /// a mutable reference to the value in the entry.
1680 /// use std::collections::HashMap;
1682 /// let mut map: HashMap<&str, u32> = HashMap::new();
1683 /// map.entry("poneyland").or_insert(12);
1685 /// assert_eq!(map["poneyland"], 12);
1687 /// *map.entry("poneyland").or_insert(12) += 10;
1688 /// assert_eq!(map["poneyland"], 22);
1690 pub fn or_insert(self, default: V
) -> &'a
mut V
{
1692 Occupied(entry
) => entry
.into_mut(),
1693 Vacant(entry
) => entry
.insert(default),
1697 #[stable(feature = "rust1", since = "1.0.0")]
1698 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1699 /// and returns a mutable reference to the value in the entry.
1704 /// use std::collections::HashMap;
1706 /// let mut map: HashMap<&str, String> = HashMap::new();
1707 /// let s = "hoho".to_owned();
1709 /// map.entry("poneyland").or_insert_with(|| s);
1711 /// assert_eq!(map["poneyland"], "hoho".to_owned());
1713 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
{
1715 Occupied(entry
) => entry
.into_mut(),
1716 Vacant(entry
) => entry
.insert(default()),
1720 /// Returns a reference to this entry's key.
1725 /// use std::collections::HashMap;
1727 /// let mut map: HashMap<&str, u32> = HashMap::new();
1728 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
1730 #[stable(feature = "map_entry_keys", since = "1.10.0")]
1731 pub fn key(&self) -> &K
{
1733 Occupied(ref entry
) => entry
.key(),
1734 Vacant(ref entry
) => entry
.key(),
1739 impl<'a
, K
, V
> OccupiedEntry
<'a
, K
, V
> {
1740 /// Gets a reference to the key in the entry.
1745 /// use std::collections::HashMap;
1747 /// let mut map: HashMap<&str, u32> = HashMap::new();
1748 /// map.entry("poneyland").or_insert(12);
1749 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
1751 #[stable(feature = "map_entry_keys", since = "1.10.0")]
1752 pub fn key(&self) -> &K
{
1756 /// Deprecated, renamed to `remove_entry`
1757 #[unstable(feature = "map_entry_recover_keys", issue = "34285")]
1758 #[rustc_deprecated(since = "1.12.0", reason = "renamed to `remove_entry`")]
1759 pub fn remove_pair(self) -> (K
, V
) {
1763 /// Take the ownership of the key and value from the map.
1768 /// use std::collections::HashMap;
1769 /// use std::collections::hash_map::Entry;
1771 /// let mut map: HashMap<&str, u32> = HashMap::new();
1772 /// map.entry("poneyland").or_insert(12);
1774 /// if let Entry::Occupied(o) = map.entry("poneyland") {
1775 /// // We delete the entry from the map.
1776 /// o.remove_entry();
1779 /// assert_eq!(map.contains_key("poneyland"), false);
1781 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
1782 pub fn remove_entry(self) -> (K
, V
) {
1783 pop_internal(self.elem
)
1786 /// Gets a reference to the value in the entry.
1791 /// use std::collections::HashMap;
1792 /// use std::collections::hash_map::Entry;
1794 /// let mut map: HashMap<&str, u32> = HashMap::new();
1795 /// map.entry("poneyland").or_insert(12);
1797 /// if let Entry::Occupied(o) = map.entry("poneyland") {
1798 /// assert_eq!(o.get(), &12);
1801 #[stable(feature = "rust1", since = "1.0.0")]
1802 pub fn get(&self) -> &V
{
1806 /// Gets a mutable reference to the value in the entry.
1811 /// use std::collections::HashMap;
1812 /// use std::collections::hash_map::Entry;
1814 /// let mut map: HashMap<&str, u32> = HashMap::new();
1815 /// map.entry("poneyland").or_insert(12);
1817 /// assert_eq!(map["poneyland"], 12);
1818 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
1819 /// *o.get_mut() += 10;
1822 /// assert_eq!(map["poneyland"], 22);
1824 #[stable(feature = "rust1", since = "1.0.0")]
1825 pub fn get_mut(&mut self) -> &mut V
{
1826 self.elem
.read_mut().1
1829 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1830 /// with a lifetime bound to the map itself.
1835 /// use std::collections::HashMap;
1836 /// use std::collections::hash_map::Entry;
1838 /// let mut map: HashMap<&str, u32> = HashMap::new();
1839 /// map.entry("poneyland").or_insert(12);
1841 /// assert_eq!(map["poneyland"], 12);
1842 /// if let Entry::Occupied(o) = map.entry("poneyland") {
1843 /// *o.into_mut() += 10;
1846 /// assert_eq!(map["poneyland"], 22);
1848 #[stable(feature = "rust1", since = "1.0.0")]
1849 pub fn into_mut(self) -> &'a
mut V
{
1850 self.elem
.into_mut_refs().1
1853 /// Sets the value of the entry, and returns the entry's old value.
1858 /// use std::collections::HashMap;
1859 /// use std::collections::hash_map::Entry;
1861 /// let mut map: HashMap<&str, u32> = HashMap::new();
1862 /// map.entry("poneyland").or_insert(12);
1864 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
1865 /// assert_eq!(o.insert(15), 12);
1868 /// assert_eq!(map["poneyland"], 15);
1870 #[stable(feature = "rust1", since = "1.0.0")]
1871 pub fn insert(&mut self, mut value
: V
) -> V
{
1872 let old_value
= self.get_mut();
1873 mem
::swap(&mut value
, old_value
);
1877 /// Takes the value out of the entry, and returns it.
1882 /// use std::collections::HashMap;
1883 /// use std::collections::hash_map::Entry;
1885 /// let mut map: HashMap<&str, u32> = HashMap::new();
1886 /// map.entry("poneyland").or_insert(12);
1888 /// if let Entry::Occupied(o) = map.entry("poneyland") {
1889 /// assert_eq!(o.remove(), 12);
1892 /// assert_eq!(map.contains_key("poneyland"), false);
1894 #[stable(feature = "rust1", since = "1.0.0")]
1895 pub fn remove(self) -> V
{
1896 pop_internal(self.elem
).1
1899 /// Returns a key that was used for search.
1901 /// The key was retained for further use.
1902 fn take_key(&mut self) -> Option
<K
> {
1907 impl<'a
, K
: 'a
, V
: 'a
> VacantEntry
<'a
, K
, V
> {
1908 /// Gets a reference to the key that would be used when inserting a value
1909 /// through the `VacantEntry`.
1914 /// use std::collections::HashMap;
1916 /// let mut map: HashMap<&str, u32> = HashMap::new();
1917 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
1919 #[stable(feature = "map_entry_keys", since = "1.10.0")]
1920 pub fn key(&self) -> &K
{
1924 /// Take ownership of the key.
1929 /// use std::collections::HashMap;
1930 /// use std::collections::hash_map::Entry;
1932 /// let mut map: HashMap<&str, u32> = HashMap::new();
1934 /// if let Entry::Vacant(v) = map.entry("poneyland") {
1938 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
1939 pub fn into_key(self) -> K
{
1943 /// Sets the value of the entry with the VacantEntry's key,
1944 /// and returns a mutable reference to it.
1949 /// use std::collections::HashMap;
1950 /// use std::collections::hash_map::Entry;
1952 /// let mut map: HashMap<&str, u32> = HashMap::new();
1954 /// if let Entry::Vacant(o) = map.entry("poneyland") {
1957 /// assert_eq!(map["poneyland"], 37);
1959 #[stable(feature = "rust1", since = "1.0.0")]
1960 pub fn insert(self, value
: V
) -> &'a
mut V
{
1962 NeqElem(bucket
, ib
) => robin_hood(bucket
, ib
, self.hash
, self.key
, value
),
1963 NoElem(bucket
) => bucket
.put(self.hash
, self.key
, value
).into_mut_refs().1,
1968 #[stable(feature = "rust1", since = "1.0.0")]
1969 impl<K
, V
, S
> FromIterator
<(K
, V
)> for HashMap
<K
, V
, S
>
1971 S
: BuildHasher
+ Default
1973 fn from_iter
<T
: IntoIterator
<Item
= (K
, V
)>>(iter
: T
) -> HashMap
<K
, V
, S
> {
1974 let iterator
= iter
.into_iter();
1975 let lower
= iterator
.size_hint().0;
1976 let mut map
= HashMap
::with_capacity_and_hasher(lower
, Default
::default());
1977 map
.extend(iterator
);
1982 #[stable(feature = "rust1", since = "1.0.0")]
1983 impl<K
, V
, S
> Extend
<(K
, V
)> for HashMap
<K
, V
, S
>
1987 fn extend
<T
: IntoIterator
<Item
= (K
, V
)>>(&mut self, iter
: T
) {
1988 for (k
, v
) in iter
{
1994 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
1995 impl<'a
, K
, V
, S
> Extend
<(&'a K
, &'a V
)> for HashMap
<K
, V
, S
>
1996 where K
: Eq
+ Hash
+ Copy
,
2000 fn extend
<T
: IntoIterator
<Item
= (&'a K
, &'a V
)>>(&mut self, iter
: T
) {
2001 self.extend(iter
.into_iter().map(|(&key
, &value
)| (key
, value
)));
2005 /// `RandomState` is the default state for [`HashMap`] types.
2007 /// A particular instance `RandomState` will create the same instances of
2008 /// [`Hasher`], but the hashers created by two different `RandomState`
2009 /// instances are unlikely to produce the same result for the same values.
2011 /// [`HashMap`]: struct.HashMap.html
2012 /// [`Hasher`]: ../../hash/trait.Hasher.html
2017 /// use std::collections::HashMap;
2018 /// use std::collections::hash_map::RandomState;
2020 /// let s = RandomState::new();
2021 /// let mut map = HashMap::with_hasher(s);
2022 /// map.insert(1, 2);
2025 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
2026 pub struct RandomState
{
2032 /// Constructs a new `RandomState` that is initialized with random keys.
2037 /// use std::collections::hash_map::RandomState;
2039 /// let s = RandomState::new();
2042 #[allow(deprecated)]
2044 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
2045 pub fn new() -> RandomState
{
2046 // Historically this function did not cache keys from the OS and instead
2047 // simply always called `rand::thread_rng().gen()` twice. In #31356 it
2048 // was discovered, however, that because we re-seed the thread-local RNG
2049 // from the OS periodically that this can cause excessive slowdown when
2050 // many hash maps are created on a thread. To solve this performance
2051 // trap we cache the first set of randomly generated keys per-thread.
2053 // Later in #36481 it was discovered that exposing a deterministic
2054 // iteration order allows a form of DOS attack. To counter that we
2055 // increment one of the seeds on every RandomState creation, giving
2056 // every corresponding HashMap a different iteration order.
2057 thread_local
!(static KEYS
: Cell
<(u64, u64)> = {
2058 let r
= rand
::OsRng
::new();
2059 let mut r
= r
.expect("failed to create an OS RNG");
2060 Cell
::new((r
.gen(), r
.gen()))
2064 let (k0
, k1
) = keys
.get();
2065 keys
.set((k0
.wrapping_add(1), k1
));
2066 RandomState { k0: k0, k1: k1 }
2071 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
2072 impl BuildHasher
for RandomState
{
2073 type Hasher
= DefaultHasher
;
2075 #[allow(deprecated)]
2076 fn build_hasher(&self) -> DefaultHasher
{
2077 DefaultHasher(SipHasher13
::new_with_keys(self.k0
, self.k1
))
2081 /// The default [`Hasher`] used by [`RandomState`].
2083 /// The internal algorithm is not specified, and so it and its hashes should
2084 /// not be relied upon over releases.
2086 /// [`RandomState`]: struct.RandomState.html
2087 /// [`Hasher`]: ../../hash/trait.Hasher.html
2088 #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
2089 #[allow(deprecated)]
2091 pub struct DefaultHasher(SipHasher13
);
2093 impl DefaultHasher
{
2094 /// Creates a new `DefaultHasher`.
2096 /// This hasher is not guaranteed to be the same as all other
2097 /// `DefaultHasher` instances, but is the same as all other `DefaultHasher`
2098 /// instances created through `new` or `default`.
2099 #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
2100 #[allow(deprecated)]
2101 pub fn new() -> DefaultHasher
{
2102 DefaultHasher(SipHasher13
::new_with_keys(0, 0))
2106 #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
2107 impl Default
for DefaultHasher
{
2108 fn default() -> DefaultHasher
{
2109 DefaultHasher
::new()
2113 #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
2114 impl Hasher
for DefaultHasher
{
2116 fn write(&mut self, msg
: &[u8]) {
2121 fn finish(&self) -> u64 {
2126 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
2127 impl Default
for RandomState
{
2128 /// Constructs a new `RandomState`.
2130 fn default() -> RandomState
{
2135 impl<K
, S
, Q
: ?Sized
> super::Recover
<Q
> for HashMap
<K
, (), S
>
2136 where K
: Eq
+ Hash
+ Borrow
<Q
>,
2142 fn get(&self, key
: &Q
) -> Option
<&K
> {
2143 self.search(key
).into_occupied_bucket().map(|bucket
| bucket
.into_refs().0)
2146 fn take(&mut self, key
: &Q
) -> Option
<K
> {
2147 if self.table
.size() == 0 {
2151 self.search_mut(key
).into_occupied_bucket().map(|bucket
| pop_internal(bucket
).0)
2154 fn replace(&mut self, key
: K
) -> Option
<K
> {
2157 match self.entry(key
) {
2158 Occupied(mut occupied
) => {
2159 let key
= occupied
.take_key().unwrap();
2160 Some(mem
::replace(occupied
.elem
.read_mut().0, key
))
2171 fn assert_covariance() {
2172 fn map_key
<'new
>(v
: HashMap
<&'
static str, u8>) -> HashMap
<&'new
str, u8> {
2175 fn map_val
<'new
>(v
: HashMap
<u8, &'
static str>) -> HashMap
<u8, &'new
str> {
2178 fn iter_key
<'a
, 'new
>(v
: Iter
<'a
, &'
static str, u8>) -> Iter
<'a
, &'new
str, u8> {
2181 fn iter_val
<'a
, 'new
>(v
: Iter
<'a
, u8, &'
static str>) -> Iter
<'a
, u8, &'new
str> {
2184 fn into_iter_key
<'new
>(v
: IntoIter
<&'
static str, u8>) -> IntoIter
<&'new
str, u8> {
2187 fn into_iter_val
<'new
>(v
: IntoIter
<u8, &'
static str>) -> IntoIter
<u8, &'new
str> {
2190 fn keys_key
<'a
, 'new
>(v
: Keys
<'a
, &'
static str, u8>) -> Keys
<'a
, &'new
str, u8> {
2193 fn keys_val
<'a
, 'new
>(v
: Keys
<'a
, u8, &'
static str>) -> Keys
<'a
, u8, &'new
str> {
2196 fn values_key
<'a
, 'new
>(v
: Values
<'a
, &'
static str, u8>) -> Values
<'a
, &'new
str, u8> {
2199 fn values_val
<'a
, 'new
>(v
: Values
<'a
, u8, &'
static str>) -> Values
<'a
, u8, &'new
str> {
2202 fn drain
<'new
>(d
: Drain
<'
static, &'
static str, &'
static str>)
2203 -> Drain
<'new
, &'new
str, &'new
str> {
2211 use super::Entry
::{Occupied, Vacant}
;
2212 use super::RandomState
;
2214 use rand
::{thread_rng, Rng}
;
2217 fn test_zero_capacities() {
2218 type HM
= HashMap
<i32, i32>;
2221 assert_eq
!(m
.capacity(), 0);
2223 let m
= HM
::default();
2224 assert_eq
!(m
.capacity(), 0);
2226 let m
= HM
::with_hasher(RandomState
::new());
2227 assert_eq
!(m
.capacity(), 0);
2229 let m
= HM
::with_capacity(0);
2230 assert_eq
!(m
.capacity(), 0);
2232 let m
= HM
::with_capacity_and_hasher(0, RandomState
::new());
2233 assert_eq
!(m
.capacity(), 0);
2235 let mut m
= HM
::new();
2241 assert_eq
!(m
.capacity(), 0);
2243 let mut m
= HM
::new();
2245 assert_eq
!(m
.capacity(), 0);
2249 fn test_create_capacity_zero() {
2250 let mut m
= HashMap
::with_capacity(0);
2252 assert
!(m
.insert(1, 1).is_none());
2254 assert
!(m
.contains_key(&1));
2255 assert
!(!m
.contains_key(&0));
2260 let mut m
= HashMap
::new();
2261 assert_eq
!(m
.len(), 0);
2262 assert
!(m
.insert(1, 2).is_none());
2263 assert_eq
!(m
.len(), 1);
2264 assert
!(m
.insert(2, 4).is_none());
2265 assert_eq
!(m
.len(), 2);
2266 assert_eq
!(*m
.get(&1).unwrap(), 2);
2267 assert_eq
!(*m
.get(&2).unwrap(), 4);
2272 let mut m
= HashMap
::new();
2273 assert_eq
!(m
.len(), 0);
2274 assert
!(m
.insert(1, 2).is_none());
2275 assert_eq
!(m
.len(), 1);
2276 assert
!(m
.insert(2, 4).is_none());
2277 assert_eq
!(m
.len(), 2);
2279 assert_eq
!(*m2
.get(&1).unwrap(), 2);
2280 assert_eq
!(*m2
.get(&2).unwrap(), 4);
2281 assert_eq
!(m2
.len(), 2);
2284 thread_local
! { static DROP_VECTOR: RefCell<Vec<isize>> = RefCell::new(Vec::new()) }
2286 #[derive(Hash, PartialEq, Eq)]
2292 fn new(k
: usize) -> Dropable
{
2293 DROP_VECTOR
.with(|slot
| {
2294 slot
.borrow_mut()[k
] += 1;
2301 impl Drop
for Dropable
{
2302 fn drop(&mut self) {
2303 DROP_VECTOR
.with(|slot
| {
2304 slot
.borrow_mut()[self.k
] -= 1;
2309 impl Clone
for Dropable
{
2310 fn clone(&self) -> Dropable
{
2311 Dropable
::new(self.k
)
2317 DROP_VECTOR
.with(|slot
| {
2318 *slot
.borrow_mut() = vec
![0; 200];
2322 let mut m
= HashMap
::new();
2324 DROP_VECTOR
.with(|v
| {
2326 assert_eq
!(v
.borrow()[i
], 0);
2331 let d1
= Dropable
::new(i
);
2332 let d2
= Dropable
::new(i
+ 100);
2336 DROP_VECTOR
.with(|v
| {
2338 assert_eq
!(v
.borrow()[i
], 1);
2343 let k
= Dropable
::new(i
);
2344 let v
= m
.remove(&k
);
2346 assert
!(v
.is_some());
2348 DROP_VECTOR
.with(|v
| {
2349 assert_eq
!(v
.borrow()[i
], 1);
2350 assert_eq
!(v
.borrow()[i
+100], 1);
2354 DROP_VECTOR
.with(|v
| {
2356 assert_eq
!(v
.borrow()[i
], 0);
2357 assert_eq
!(v
.borrow()[i
+100], 0);
2361 assert_eq
!(v
.borrow()[i
], 1);
2362 assert_eq
!(v
.borrow()[i
+100], 1);
2367 DROP_VECTOR
.with(|v
| {
2369 assert_eq
!(v
.borrow()[i
], 0);
2375 fn test_into_iter_drops() {
2376 DROP_VECTOR
.with(|v
| {
2377 *v
.borrow_mut() = vec
![0; 200];
2381 let mut hm
= HashMap
::new();
2383 DROP_VECTOR
.with(|v
| {
2385 assert_eq
!(v
.borrow()[i
], 0);
2390 let d1
= Dropable
::new(i
);
2391 let d2
= Dropable
::new(i
+ 100);
2395 DROP_VECTOR
.with(|v
| {
2397 assert_eq
!(v
.borrow()[i
], 1);
2404 // By the way, ensure that cloning doesn't screw up the dropping.
2408 let mut half
= hm
.into_iter().take(50);
2410 DROP_VECTOR
.with(|v
| {
2412 assert_eq
!(v
.borrow()[i
], 1);
2416 for _
in half
.by_ref() {}
2418 DROP_VECTOR
.with(|v
| {
2420 .filter(|&i
| v
.borrow()[i
] == 1)
2424 .filter(|&i
| v
.borrow()[i
+ 100] == 1)
2432 DROP_VECTOR
.with(|v
| {
2434 assert_eq
!(v
.borrow()[i
], 0);
2440 fn test_empty_remove() {
2441 let mut m
: HashMap
<isize, bool
> = HashMap
::new();
2442 assert_eq
!(m
.remove(&0), None
);
2446 fn test_empty_entry() {
2447 let mut m
: HashMap
<isize, bool
> = HashMap
::new();
2449 Occupied(_
) => panic
!(),
2452 assert
!(*m
.entry(0).or_insert(true));
2453 assert_eq
!(m
.len(), 1);
2457 fn test_empty_iter() {
2458 let mut m
: HashMap
<isize, bool
> = HashMap
::new();
2459 assert_eq
!(m
.drain().next(), None
);
2460 assert_eq
!(m
.keys().next(), None
);
2461 assert_eq
!(m
.values().next(), None
);
2462 assert_eq
!(m
.values_mut().next(), None
);
2463 assert_eq
!(m
.iter().next(), None
);
2464 assert_eq
!(m
.iter_mut().next(), None
);
2465 assert_eq
!(m
.len(), 0);
2466 assert
!(m
.is_empty());
2467 assert_eq
!(m
.into_iter().next(), None
);
2471 fn test_lots_of_insertions() {
2472 let mut m
= HashMap
::new();
2474 // Try this a few times to make sure we never screw up the hashmap's
2477 assert
!(m
.is_empty());
2480 assert
!(m
.insert(i
, i
).is_none());
2484 assert_eq
!(r
, Some(&j
));
2487 for j
in i
+ 1..1001 {
2489 assert_eq
!(r
, None
);
2493 for i
in 1001..2001 {
2494 assert
!(!m
.contains_key(&i
));
2499 assert
!(m
.remove(&i
).is_some());
2502 assert
!(!m
.contains_key(&j
));
2505 for j
in i
+ 1..1001 {
2506 assert
!(m
.contains_key(&j
));
2511 assert
!(!m
.contains_key(&i
));
2515 assert
!(m
.insert(i
, i
).is_none());
2519 for i
in (1..1001).rev() {
2520 assert
!(m
.remove(&i
).is_some());
2523 assert
!(!m
.contains_key(&j
));
2527 assert
!(m
.contains_key(&j
));
2534 fn test_find_mut() {
2535 let mut m
= HashMap
::new();
2536 assert
!(m
.insert(1, 12).is_none());
2537 assert
!(m
.insert(2, 8).is_none());
2538 assert
!(m
.insert(5, 14).is_none());
2540 match m
.get_mut(&5) {
2542 Some(x
) => *x
= new
,
2544 assert_eq
!(m
.get(&5), Some(&new
));
2548 fn test_insert_overwrite() {
2549 let mut m
= HashMap
::new();
2550 assert
!(m
.insert(1, 2).is_none());
2551 assert_eq
!(*m
.get(&1).unwrap(), 2);
2552 assert
!(!m
.insert(1, 3).is_none());
2553 assert_eq
!(*m
.get(&1).unwrap(), 3);
2557 fn test_insert_conflicts() {
2558 let mut m
= HashMap
::with_capacity(4);
2559 assert
!(m
.insert(1, 2).is_none());
2560 assert
!(m
.insert(5, 3).is_none());
2561 assert
!(m
.insert(9, 4).is_none());
2562 assert_eq
!(*m
.get(&9).unwrap(), 4);
2563 assert_eq
!(*m
.get(&5).unwrap(), 3);
2564 assert_eq
!(*m
.get(&1).unwrap(), 2);
2568 fn test_conflict_remove() {
2569 let mut m
= HashMap
::with_capacity(4);
2570 assert
!(m
.insert(1, 2).is_none());
2571 assert_eq
!(*m
.get(&1).unwrap(), 2);
2572 assert
!(m
.insert(5, 3).is_none());
2573 assert_eq
!(*m
.get(&1).unwrap(), 2);
2574 assert_eq
!(*m
.get(&5).unwrap(), 3);
2575 assert
!(m
.insert(9, 4).is_none());
2576 assert_eq
!(*m
.get(&1).unwrap(), 2);
2577 assert_eq
!(*m
.get(&5).unwrap(), 3);
2578 assert_eq
!(*m
.get(&9).unwrap(), 4);
2579 assert
!(m
.remove(&1).is_some());
2580 assert_eq
!(*m
.get(&9).unwrap(), 4);
2581 assert_eq
!(*m
.get(&5).unwrap(), 3);
2585 fn test_is_empty() {
2586 let mut m
= HashMap
::with_capacity(4);
2587 assert
!(m
.insert(1, 2).is_none());
2588 assert
!(!m
.is_empty());
2589 assert
!(m
.remove(&1).is_some());
2590 assert
!(m
.is_empty());
2595 let mut m
= HashMap
::new();
2597 assert_eq
!(m
.remove(&1), Some(2));
2598 assert_eq
!(m
.remove(&1), None
);
2603 let mut m
= HashMap
::with_capacity(4);
2605 assert
!(m
.insert(i
, i
*2).is_none());
2607 assert_eq
!(m
.len(), 32);
2609 let mut observed
: u32 = 0;
2612 assert_eq
!(*v
, *k
* 2);
2613 observed
|= 1 << *k
;
2615 assert_eq
!(observed
, 0xFFFF_FFFF);
2620 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
2621 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
2622 let keys
: Vec
<_
> = map
.keys().cloned().collect();
2623 assert_eq
!(keys
.len(), 3);
2624 assert
!(keys
.contains(&1));
2625 assert
!(keys
.contains(&2));
2626 assert
!(keys
.contains(&3));
2631 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
2632 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
2633 let values
: Vec
<_
> = map
.values().cloned().collect();
2634 assert_eq
!(values
.len(), 3);
2635 assert
!(values
.contains(&'a'
));
2636 assert
!(values
.contains(&'b'
));
2637 assert
!(values
.contains(&'c'
));
2641 fn test_values_mut() {
2642 let vec
= vec
![(1, 1), (2, 2), (3, 3)];
2643 let mut map
: HashMap
<_
, _
> = vec
.into_iter().collect();
2644 for value
in map
.values_mut() {
2645 *value
= (*value
) * 2
2647 let values
: Vec
<_
> = map
.values().cloned().collect();
2648 assert_eq
!(values
.len(), 3);
2649 assert
!(values
.contains(&2));
2650 assert
!(values
.contains(&4));
2651 assert
!(values
.contains(&6));
2656 let mut m
= HashMap
::new();
2657 assert
!(m
.get(&1).is_none());
2661 Some(v
) => assert_eq
!(*v
, 2),
2667 let mut m1
= HashMap
::new();
2672 let mut m2
= HashMap
::new();
2685 let mut map
= HashMap
::new();
2686 let empty
: HashMap
<i32, i32> = HashMap
::new();
2691 let map_str
= format
!("{:?}", map
);
2693 assert
!(map_str
== "{1: 2, 3: 4}" ||
2694 map_str
== "{3: 4, 1: 2}");
2695 assert_eq
!(format
!("{:?}", empty
), "{}");
2700 let mut m
= HashMap
::new();
2702 assert_eq
!(m
.len(), 0);
2703 assert
!(m
.is_empty());
2706 let old_raw_cap
= m
.raw_capacity();
2707 while old_raw_cap
== m
.raw_capacity() {
2712 assert_eq
!(m
.len(), i
);
2713 assert
!(!m
.is_empty());
2717 fn test_behavior_resize_policy() {
2718 let mut m
= HashMap
::new();
2720 assert_eq
!(m
.len(), 0);
2721 assert_eq
!(m
.raw_capacity(), 0);
2722 assert
!(m
.is_empty());
2726 assert
!(m
.is_empty());
2727 let initial_raw_cap
= m
.raw_capacity();
2728 m
.reserve(initial_raw_cap
);
2729 let raw_cap
= m
.raw_capacity();
2731 assert_eq
!(raw_cap
, initial_raw_cap
* 2);
2734 for _
in 0..raw_cap
* 3 / 4 {
2738 // three quarters full
2740 assert_eq
!(m
.len(), i
);
2741 assert_eq
!(m
.raw_capacity(), raw_cap
);
2743 for _
in 0..raw_cap
/ 4 {
2749 let new_raw_cap
= m
.raw_capacity();
2750 assert_eq
!(new_raw_cap
, raw_cap
* 2);
2752 for _
in 0..raw_cap
/ 2 - 1 {
2755 assert_eq
!(m
.raw_capacity(), new_raw_cap
);
2757 // A little more than one quarter full.
2759 assert_eq
!(m
.raw_capacity(), raw_cap
);
2760 // again, a little more than half full
2761 for _
in 0..raw_cap
/ 2 - 1 {
2767 assert_eq
!(m
.len(), i
);
2768 assert
!(!m
.is_empty());
2769 assert_eq
!(m
.raw_capacity(), initial_raw_cap
);
2773 fn test_reserve_shrink_to_fit() {
2774 let mut m
= HashMap
::new();
2777 assert
!(m
.capacity() >= m
.len());
2783 let usable_cap
= m
.capacity();
2784 for i
in 128..(128 + 256) {
2786 assert_eq
!(m
.capacity(), usable_cap
);
2789 for i
in 100..(128 + 256) {
2790 assert_eq
!(m
.remove(&i
), Some(i
));
2794 assert_eq
!(m
.len(), 100);
2795 assert
!(!m
.is_empty());
2796 assert
!(m
.capacity() >= m
.len());
2799 assert_eq
!(m
.remove(&i
), Some(i
));
2804 assert_eq
!(m
.len(), 1);
2805 assert
!(m
.capacity() >= m
.len());
2806 assert_eq
!(m
.remove(&0), Some(0));
2810 fn test_from_iter() {
2811 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2813 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2815 for &(k
, v
) in &xs
{
2816 assert_eq
!(map
.get(&k
), Some(&v
));
2821 fn test_size_hint() {
2822 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2824 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2826 let mut iter
= map
.iter();
2828 for _
in iter
.by_ref().take(3) {}
2830 assert_eq
!(iter
.size_hint(), (3, Some(3)));
2834 fn test_iter_len() {
2835 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2837 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2839 let mut iter
= map
.iter();
2841 for _
in iter
.by_ref().take(3) {}
2843 assert_eq
!(iter
.len(), 3);
2847 fn test_mut_size_hint() {
2848 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2850 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2852 let mut iter
= map
.iter_mut();
2854 for _
in iter
.by_ref().take(3) {}
2856 assert_eq
!(iter
.size_hint(), (3, Some(3)));
2860 fn test_iter_mut_len() {
2861 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2863 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2865 let mut iter
= map
.iter_mut();
2867 for _
in iter
.by_ref().take(3) {}
2869 assert_eq
!(iter
.len(), 3);
2874 let mut map
= HashMap
::new();
2880 assert_eq
!(map
[&2], 1);
2885 fn test_index_nonexistent() {
2886 let mut map
= HashMap
::new();
2897 let xs
= [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2899 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2901 // Existing key (insert)
2902 match map
.entry(1) {
2903 Vacant(_
) => unreachable
!(),
2904 Occupied(mut view
) => {
2905 assert_eq
!(view
.get(), &10);
2906 assert_eq
!(view
.insert(100), 10);
2909 assert_eq
!(map
.get(&1).unwrap(), &100);
2910 assert_eq
!(map
.len(), 6);
2913 // Existing key (update)
2914 match map
.entry(2) {
2915 Vacant(_
) => unreachable
!(),
2916 Occupied(mut view
) => {
2917 let v
= view
.get_mut();
2918 let new_v
= (*v
) * 10;
2922 assert_eq
!(map
.get(&2).unwrap(), &200);
2923 assert_eq
!(map
.len(), 6);
2925 // Existing key (take)
2926 match map
.entry(3) {
2927 Vacant(_
) => unreachable
!(),
2929 assert_eq
!(view
.remove(), 30);
2932 assert_eq
!(map
.get(&3), None
);
2933 assert_eq
!(map
.len(), 5);
2936 // Inexistent key (insert)
2937 match map
.entry(10) {
2938 Occupied(_
) => unreachable
!(),
2940 assert_eq
!(*view
.insert(1000), 1000);
2943 assert_eq
!(map
.get(&10).unwrap(), &1000);
2944 assert_eq
!(map
.len(), 6);
2948 fn test_entry_take_doesnt_corrupt() {
2949 #![allow(deprecated)] //rand
2951 fn check(m
: &HashMap
<isize, ()>) {
2953 assert
!(m
.contains_key(k
),
2954 "{} is in keys() but not in the map?", k
);
2958 let mut m
= HashMap
::new();
2959 let mut rng
= thread_rng();
2961 // Populate the map with some items.
2963 let x
= rng
.gen_range(-10, 10);
2968 let x
= rng
.gen_range(-10, 10);
2972 println
!("{}: remove {}", i
, x
);
2982 fn test_extend_ref() {
2983 let mut a
= HashMap
::new();
2985 let mut b
= HashMap
::new();
2987 b
.insert(3, "three");
2991 assert_eq
!(a
.len(), 3);
2992 assert_eq
!(a
[&1], "one");
2993 assert_eq
!(a
[&2], "two");
2994 assert_eq
!(a
[&3], "three");
2998 fn test_capacity_not_less_than_len() {
2999 let mut a
= HashMap
::new();
3007 assert
!(a
.capacity() > a
.len());
3009 let free
= a
.capacity() - a
.len();
3015 assert_eq
!(a
.len(), a
.capacity());
3017 // Insert at capacity should cause allocation.
3019 assert
!(a
.capacity() > a
.len());
3023 fn test_occupied_entry_key() {
3024 let mut a
= HashMap
::new();
3025 let key
= "hello there";
3026 let value
= "value goes here";
3027 assert
!(a
.is_empty());
3028 a
.insert(key
.clone(), value
.clone());
3029 assert_eq
!(a
.len(), 1);
3030 assert_eq
!(a
[key
], value
);
3032 match a
.entry(key
.clone()) {
3033 Vacant(_
) => panic
!(),
3034 Occupied(e
) => assert_eq
!(key
, *e
.key()),
3036 assert_eq
!(a
.len(), 1);
3037 assert_eq
!(a
[key
], value
);
3041 fn test_vacant_entry_key() {
3042 let mut a
= HashMap
::new();
3043 let key
= "hello there";
3044 let value
= "value goes here";
3046 assert
!(a
.is_empty());
3047 match a
.entry(key
.clone()) {
3048 Occupied(_
) => panic
!(),
3050 assert_eq
!(key
, *e
.key());
3051 e
.insert(value
.clone());
3054 assert_eq
!(a
.len(), 1);
3055 assert_eq
!(a
[key
], value
);