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
::*;
16 use fmt
::{self, Debug}
;
17 use hash
::{Hash, Hasher, BuildHasher, SipHasher13}
;
18 use iter
::FromIterator
;
19 use mem
::{self, replace}
;
20 use ops
::{Deref, Index}
;
21 use rand
::{self, Rng}
;
32 use super::table
::BucketState
::{
37 const INITIAL_LOG2_CAP
: usize = 5;
38 const INITIAL_CAPACITY
: usize = 1 << INITIAL_LOG2_CAP
; // 2^5
40 /// The default behavior of HashMap implements a load factor of 90.9%.
41 /// This behavior is characterized by the following condition:
43 /// - if size > 0.909 * capacity: grow the map
45 struct DefaultResizePolicy
;
47 impl DefaultResizePolicy
{
48 fn new() -> DefaultResizePolicy
{
53 fn min_capacity(&self, usable_size
: usize) -> usize {
54 // Here, we are rephrasing the logic by specifying the lower limit
57 // - if `cap < size * 1.1`: grow the map
61 /// An inverse of `min_capacity`, approximately.
63 fn usable_capacity(&self, cap
: usize) -> usize {
64 // As the number of entries approaches usable capacity,
65 // min_capacity(size) must be smaller than the internal capacity,
66 // so that the map is not resized:
67 // `min_capacity(usable_capacity(x)) <= x`.
68 // The left-hand side can only be smaller due to flooring by integer
71 // This doesn't have to be checked for overflow since allocation size
72 // in bytes will overflow earlier than multiplication by 10.
74 // As per https://github.com/rust-lang/rust/pull/30991 this is updated
75 // to be: (cap * den + den - 1) / num
76 (cap
* 10 + 10 - 1) / 11
81 fn test_resize_policy() {
82 let rp
= DefaultResizePolicy
;
84 assert
!(rp
.min_capacity(rp
.usable_capacity(n
)) <= n
);
85 assert
!(rp
.usable_capacity(rp
.min_capacity(n
)) <= n
);
89 // The main performance trick in this hashmap is called Robin Hood Hashing.
90 // It gains its excellent performance from one essential operation:
92 // If an insertion collides with an existing element, and that element's
93 // "probe distance" (how far away the element is from its ideal location)
94 // is higher than how far we've already probed, swap the elements.
96 // This massively lowers variance in probe distance, and allows us to get very
97 // high load factors with good performance. The 90% load factor I use is rather
100 // > Why a load factor of approximately 90%?
102 // In general, all the distances to initial buckets will converge on the mean.
103 // At a load factor of α, the odds of finding the target bucket after k
104 // probes is approximately 1-α^k. If we set this equal to 50% (since we converge
105 // on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round
106 // this down to make the math easier on the CPU and avoid its FPU.
107 // Since on average we start the probing in the middle of a cache line, this
108 // strategy pulls in two cache lines of hashes on every lookup. I think that's
109 // pretty good, but if you want to trade off some space, it could go down to one
110 // cache line on average with an α of 0.84.
112 // > Wait, what? Where did you get 1-α^k from?
114 // On the first probe, your odds of a collision with an existing element is α.
115 // The odds of doing this twice in a row is approximately α^2. For three times,
116 // α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT
117 // colliding after k tries is 1-α^k.
119 // The paper from 1986 cited below mentions an implementation which keeps track
120 // of the distance-to-initial-bucket histogram. This approach is not suitable
121 // for modern architectures because it requires maintaining an internal data
122 // structure. This allows very good first guesses, but we are most concerned
123 // with guessing entire cache lines, not individual indexes. Furthermore, array
124 // accesses are no longer linear and in one direction, as we have now. There
125 // is also memory and cache pressure that this would entail that would be very
126 // difficult to properly see in a microbenchmark.
128 // ## Future Improvements (FIXME!)
130 // Allow the load factor to be changed dynamically and/or at initialization.
132 // Also, would it be possible for us to reuse storage when growing the
133 // underlying table? This is exactly the use case for 'realloc', and may
134 // be worth exploring.
136 // ## Future Optimizations (FIXME!)
138 // Another possible design choice that I made without any real reason is
139 // parameterizing the raw table over keys and values. Technically, all we need
140 // is the size and alignment of keys and values, and the code should be just as
141 // efficient (well, we might need one for power-of-two size and one for not...).
142 // This has the potential to reduce code bloat in rust executables, without
143 // really losing anything except 4 words (key size, key alignment, val size,
144 // val alignment) which can be passed in to every call of a `RawTable` function.
145 // This would definitely be an avenue worth exploring if people start complaining
146 // about the size of rust executables.
148 // Annotate exceedingly likely branches in `table::make_hash`
149 // and `search_hashed` to reduce instruction cache pressure
150 // and mispredictions once it becomes possible (blocked on issue #11092).
152 // Shrinking the table could simply reallocate in place after moving buckets
153 // to the first half.
155 // The growth algorithm (fragment of the Proof of Correctness)
156 // --------------------
158 // The growth algorithm is basically a fast path of the naive reinsertion-
159 // during-resize algorithm. Other paths should never be taken.
161 // Consider growing a robin hood hashtable of capacity n. Normally, we do this
162 // by allocating a new table of capacity `2n`, and then individually reinsert
163 // each element in the old table into the new one. This guarantees that the
164 // new table is a valid robin hood hashtable with all the desired statistical
165 // properties. Remark that the order we reinsert the elements in should not
166 // matter. For simplicity and efficiency, we will consider only linear
167 // reinsertions, which consist of reinserting all elements in the old table
168 // into the new one by increasing order of index. However we will not be
169 // starting our reinsertions from index 0 in general. If we start from index
170 // i, for the purpose of reinsertion we will consider all elements with real
171 // index j < i to have virtual index n + j.
173 // Our hash generation scheme consists of generating a 64-bit hash and
174 // truncating the most significant bits. When moving to the new table, we
175 // simply introduce a new bit to the front of the hash. Therefore, if an
176 // elements has ideal index i in the old table, it can have one of two ideal
177 // locations in the new table. If the new bit is 0, then the new ideal index
178 // is i. If the new bit is 1, then the new ideal index is n + i. Intuitively,
179 // we are producing two independent tables of size n, and for each element we
180 // independently choose which table to insert it into with equal probability.
181 // However the rather than wrapping around themselves on overflowing their
182 // indexes, the first table overflows into the first, and the first into the
183 // second. Visually, our new table will look something like:
185 // [yy_xxx_xxxx_xxx|xx_yyy_yyyy_yyy]
187 // Where x's are elements inserted into the first table, y's are elements
188 // inserted into the second, and _'s are empty sections. We now define a few
189 // key concepts that we will use later. Note that this is a very abstract
190 // perspective of the table. A real resized table would be at least half
193 // Theorem: A linear robin hood reinsertion from the first ideal element
194 // produces identical results to a linear naive reinsertion from the same
197 // FIXME(Gankro, pczarn): review the proof and put it all in a separate README.md
199 /// A hash map implementation which uses linear probing with Robin
200 /// Hood bucket stealing.
202 /// By default, HashMap uses a somewhat slow hashing algorithm which can provide resistance
203 /// to DoS attacks. Rust makes a best attempt at acquiring random numbers without IO
204 /// blocking from your system. Because of this HashMap is not guaranteed to provide
205 /// DoS resistance since the numbers generated might not be truly random. If you do
206 /// require this behavior you can create your own hashing function using
207 /// [BuildHasherDefault](../hash/struct.BuildHasherDefault.html).
209 /// It is required that the keys implement the `Eq` and `Hash` traits, although
210 /// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
211 /// If you implement these yourself, it is important that the following
215 /// k1 == k2 -> hash(k1) == hash(k2)
218 /// In other words, if two keys are equal, their hashes must be equal.
220 /// It is a logic error for a key to be modified in such a way that the key's
221 /// hash, as determined by the `Hash` trait, or its equality, as determined by
222 /// the `Eq` trait, changes while it is in the map. This is normally only
223 /// possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
225 /// Relevant papers/articles:
227 /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)
228 /// 2. Emmanuel Goossaert. ["Robin Hood
229 /// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/)
230 /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift
231 /// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)
236 /// use std::collections::HashMap;
238 /// // type inference lets us omit an explicit type signature (which
239 /// // would be `HashMap<&str, &str>` in this example).
240 /// let mut book_reviews = HashMap::new();
242 /// // review some books.
243 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
244 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
245 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
246 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
248 /// // check for a specific one.
249 /// if !book_reviews.contains_key("Les Misérables") {
250 /// println!("We've got {} reviews, but Les Misérables ain't one.",
251 /// book_reviews.len());
254 /// // oops, this review has a lot of spelling mistakes, let's delete it.
255 /// book_reviews.remove("The Adventures of Sherlock Holmes");
257 /// // look up the values associated with some keys.
258 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
259 /// for book in &to_find {
260 /// match book_reviews.get(book) {
261 /// Some(review) => println!("{}: {}", book, review),
262 /// None => println!("{} is unreviewed.", book)
266 /// // iterate over everything.
267 /// for (book, review) in &book_reviews {
268 /// println!("{}: \"{}\"", book, review);
272 /// `HashMap` also implements an [`Entry API`](#method.entry), which allows
273 /// for more complex methods of getting, setting, updating and removing keys and
277 /// use std::collections::HashMap;
279 /// // type inference lets us omit an explicit type signature (which
280 /// // would be `HashMap<&str, u8>` in this example).
281 /// let mut player_stats = HashMap::new();
283 /// fn random_stat_buff() -> u8 {
284 /// // could actually return some random value here - let's just return
285 /// // some fixed value for now
289 /// // insert a key only if it doesn't already exist
290 /// player_stats.entry("health").or_insert(100);
292 /// // insert a key using a function that provides a new value only if it
293 /// // doesn't already exist
294 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
296 /// // update a key, guarding against the key possibly not being set
297 /// let stat = player_stats.entry("attack").or_insert(100);
298 /// *stat += random_stat_buff();
301 /// The easiest way to use `HashMap` with a custom type as key is to derive `Eq` and `Hash`.
302 /// We must also derive `PartialEq`.
305 /// use std::collections::HashMap;
307 /// #[derive(Hash, Eq, PartialEq, Debug)]
314 /// /// Create a new Viking.
315 /// fn new(name: &str, country: &str) -> Viking {
316 /// Viking { name: name.to_string(), country: country.to_string() }
320 /// // Use a HashMap to store the vikings' health points.
321 /// let mut vikings = HashMap::new();
323 /// vikings.insert(Viking::new("Einar", "Norway"), 25);
324 /// vikings.insert(Viking::new("Olaf", "Denmark"), 24);
325 /// vikings.insert(Viking::new("Harald", "Iceland"), 12);
327 /// // Use derived implementation to print the status of the vikings.
328 /// for (viking, health) in &vikings {
329 /// println!("{:?} has {} hp", viking, health);
333 #[stable(feature = "rust1", since = "1.0.0")]
334 pub struct HashMap
<K
, V
, S
= RandomState
> {
335 // All hashes are keyed on these values, to prevent hash collision attacks.
338 table
: RawTable
<K
, V
>,
340 resize_policy
: DefaultResizePolicy
,
343 /// Search for a pre-hashed key.
345 fn search_hashed
<K
, V
, M
, F
>(table
: M
,
348 -> InternalEntry
<K
, V
, M
> where
349 M
: Deref
<Target
=RawTable
<K
, V
>>,
350 F
: FnMut(&K
) -> bool
,
352 // This is the only function where capacity can be zero. To avoid
353 // undefined behavior when Bucket::new gets the raw bucket in this
354 // case, immediately return the appropriate search result.
355 if table
.capacity() == 0 {
356 return InternalEntry
::TableIsEmpty
;
359 let size
= table
.size() as isize;
360 let mut probe
= Bucket
::new(table
, hash
);
361 let ib
= probe
.index() as isize;
364 let full
= match probe
.peek() {
367 return InternalEntry
::Vacant
{
369 elem
: NoElem(bucket
),
372 Full(bucket
) => bucket
375 let robin_ib
= full
.index() as isize - full
.displacement() as isize;
378 // Found a luckier bucket than me.
379 // We can finish the search early if we hit any bucket
380 // with a lower distance to initial bucket than we've probed.
381 return InternalEntry
::Vacant
{
383 elem
: NeqElem(full
, robin_ib
as usize),
387 // If the hash doesn't match, it can't be this one..
388 if hash
== full
.hash() {
389 // If the key doesn't match, it can't be this one..
390 if is_match(full
.read().0) {
391 return InternalEntry
::Occupied
{
398 debug_assert
!(probe
.index() as isize != ib
+ size
+ 1);
402 fn pop_internal
<K
, V
>(starting_bucket
: FullBucketMut
<K
, V
>) -> (K
, V
) {
403 let (empty
, retkey
, retval
) = starting_bucket
.take();
404 let mut gap
= match empty
.gap_peek() {
406 None
=> return (retkey
, retval
)
409 while gap
.full().displacement() != 0 {
410 gap
= match gap
.shift() {
416 // Now we've done all our shifting. Return the value we grabbed earlier.
420 /// Perform robin hood bucket stealing at the given `bucket`. You must
421 /// also pass the position of that bucket's initial bucket so we don't have
422 /// to recalculate it.
424 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
425 fn robin_hood
<'a
, K
: 'a
, V
: 'a
>(bucket
: FullBucketMut
<'a
, K
, V
>,
431 let starting_index
= bucket
.index();
432 let size
= bucket
.table().size();
433 // Save the *starting point*.
434 let mut bucket
= bucket
.stash();
435 // There can be at most `size - dib` buckets to displace, because
436 // in the worst case, there are `size` elements and we already are
437 // `displacement` buckets away from the initial one.
438 let idx_end
= starting_index
+ size
- bucket
.displacement();
441 let (old_hash
, old_key
, old_val
) = bucket
.replace(hash
, key
, val
);
447 let probe
= bucket
.next();
448 debug_assert
!(probe
.index() != idx_end
);
450 let full_bucket
= match probe
.peek() {
453 let bucket
= bucket
.put(hash
, key
, val
);
454 // Now that it's stolen, just read the value's pointer
455 // right out of the table! Go back to the *starting point*.
457 // This use of `into_table` is misleading. It turns the
458 // bucket, which is a FullBucket on top of a
459 // FullBucketMut, into just one FullBucketMut. The "table"
460 // refers to the inner FullBucketMut in this context.
461 return bucket
.into_table().into_mut_refs().1;
463 Full(bucket
) => bucket
466 let probe_ib
= full_bucket
.index() - full_bucket
.displacement();
468 bucket
= full_bucket
;
470 // Robin hood! Steal the spot.
479 impl<K
, V
, S
> HashMap
<K
, V
, S
>
480 where K
: Eq
+ Hash
, S
: BuildHasher
482 fn make_hash
<X
: ?Sized
>(&self, x
: &X
) -> SafeHash
where X
: Hash
{
483 table
::make_hash(&self.hash_builder
, x
)
486 /// Search for a key, yielding the index if it's found in the hashtable.
487 /// If you already have the hash for the key lying around, use
490 fn search
<'a
, Q
: ?Sized
>(&'a
self, q
: &Q
) -> InternalEntry
<K
, V
, &'a RawTable
<K
, V
>>
491 where K
: Borrow
<Q
>, Q
: Eq
+ Hash
493 let hash
= self.make_hash(q
);
494 search_hashed(&self.table
, hash
, |k
| q
.eq(k
.borrow()))
498 fn search_mut
<'a
, Q
: ?Sized
>(&'a
mut self, q
: &Q
) -> InternalEntry
<K
, V
, &'a
mut RawTable
<K
, V
>>
499 where K
: Borrow
<Q
>, Q
: Eq
+ Hash
501 let hash
= self.make_hash(q
);
502 search_hashed(&mut self.table
, hash
, |k
| q
.eq(k
.borrow()))
505 // The caller should ensure that invariants by Robin Hood Hashing hold.
506 fn insert_hashed_ordered(&mut self, hash
: SafeHash
, k
: K
, v
: V
) {
507 let cap
= self.table
.capacity();
508 let mut buckets
= Bucket
::new(&mut self.table
, hash
);
509 let ib
= buckets
.index();
511 while buckets
.index() != ib
+ cap
{
512 // We don't need to compare hashes for value swap.
513 // Not even DIBs for Robin Hood.
514 buckets
= match buckets
.peek() {
516 empty
.put(hash
, k
, v
);
519 Full(b
) => b
.into_bucket()
523 panic
!("Internal HashMap error: Out of space.");
527 impl<K
: Hash
+ Eq
, V
> HashMap
<K
, V
, RandomState
> {
528 /// Creates an empty HashMap.
533 /// use std::collections::HashMap;
534 /// let mut map: HashMap<&str, isize> = HashMap::new();
537 #[stable(feature = "rust1", since = "1.0.0")]
538 pub fn new() -> HashMap
<K
, V
, RandomState
> {
542 /// Creates an empty hash map with the given initial capacity.
547 /// use std::collections::HashMap;
548 /// let mut map: HashMap<&str, isize> = HashMap::with_capacity(10);
551 #[stable(feature = "rust1", since = "1.0.0")]
552 pub fn with_capacity(capacity
: usize) -> HashMap
<K
, V
, RandomState
> {
553 HashMap
::with_capacity_and_hasher(capacity
, Default
::default())
557 impl<K
, V
, S
> HashMap
<K
, V
, S
>
558 where K
: Eq
+ Hash
, S
: BuildHasher
560 /// Creates an empty hashmap which will use the given hash builder to hash
563 /// The created map has the default initial capacity.
565 /// Warning: `hash_builder` is normally randomly generated, and
566 /// is designed to allow HashMaps to be resistant to attacks that
567 /// cause many collisions and very poor performance. Setting it
568 /// manually using this function can expose a DoS attack vector.
573 /// use std::collections::HashMap;
574 /// use std::collections::hash_map::RandomState;
576 /// let s = RandomState::new();
577 /// let mut map = HashMap::with_hasher(s);
578 /// map.insert(1, 2);
581 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
582 pub fn with_hasher(hash_builder
: S
) -> HashMap
<K
, V
, S
> {
584 hash_builder
: hash_builder
,
585 resize_policy
: DefaultResizePolicy
::new(),
586 table
: RawTable
::new(0),
590 /// Creates an empty HashMap with space for at least `capacity`
591 /// elements, using `hasher` to hash the keys.
593 /// Warning: `hasher` is normally randomly generated, and
594 /// is designed to allow HashMaps to be resistant to attacks that
595 /// cause many collisions and very poor performance. Setting it
596 /// manually using this function can expose a DoS attack vector.
601 /// use std::collections::HashMap;
602 /// use std::collections::hash_map::RandomState;
604 /// let s = RandomState::new();
605 /// let mut map = HashMap::with_capacity_and_hasher(10, s);
606 /// map.insert(1, 2);
609 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
610 pub fn with_capacity_and_hasher(capacity
: usize, hash_builder
: S
)
611 -> HashMap
<K
, V
, S
> {
612 let resize_policy
= DefaultResizePolicy
::new();
613 let min_cap
= max(INITIAL_CAPACITY
, resize_policy
.min_capacity(capacity
));
614 let internal_cap
= min_cap
.checked_next_power_of_two().expect("capacity overflow");
615 assert
!(internal_cap
>= capacity
, "capacity overflow");
617 hash_builder
: hash_builder
,
618 resize_policy
: resize_policy
,
619 table
: RawTable
::new(internal_cap
),
623 /// Returns a reference to the map's hasher.
624 #[stable(feature = "hashmap_public_hasher", since = "1.9.0")]
625 pub fn hasher(&self) -> &S
{
629 /// Returns the number of elements the map can hold without reallocating.
631 /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
632 /// more, but is guaranteed to be able to hold at least this many.
637 /// use std::collections::HashMap;
638 /// let map: HashMap<isize, isize> = HashMap::with_capacity(100);
639 /// assert!(map.capacity() >= 100);
642 #[stable(feature = "rust1", since = "1.0.0")]
643 pub fn capacity(&self) -> usize {
644 self.resize_policy
.usable_capacity(self.table
.capacity())
647 /// Reserves capacity for at least `additional` more elements to be inserted
648 /// in the `HashMap`. The collection may reserve more space to avoid
649 /// frequent reallocations.
653 /// Panics if the new allocation size overflows `usize`.
658 /// use std::collections::HashMap;
659 /// let mut map: HashMap<&str, isize> = HashMap::new();
662 #[stable(feature = "rust1", since = "1.0.0")]
663 pub fn reserve(&mut self, additional
: usize) {
664 let new_size
= self.len().checked_add(additional
).expect("capacity overflow");
665 let min_cap
= self.resize_policy
.min_capacity(new_size
);
667 // An invalid value shouldn't make us run out of space. This includes
668 // an overflow check.
669 assert
!(new_size
<= min_cap
);
671 if self.table
.capacity() < min_cap
{
672 let new_capacity
= max(min_cap
.next_power_of_two(), INITIAL_CAPACITY
);
673 self.resize(new_capacity
);
677 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
678 /// 1) Make sure the new capacity is enough for all the elements, accounting
679 /// for the load factor.
680 /// 2) Ensure new_capacity is a power of two or zero.
681 fn resize(&mut self, new_capacity
: usize) {
682 assert
!(self.table
.size() <= new_capacity
);
683 assert
!(new_capacity
.is_power_of_two() || new_capacity
== 0);
685 let mut old_table
= replace(&mut self.table
, RawTable
::new(new_capacity
));
686 let old_size
= old_table
.size();
688 if old_table
.capacity() == 0 || old_table
.size() == 0 {
693 // Specialization of the other branch.
694 let mut bucket
= Bucket
::first(&mut old_table
);
696 // "So a few of the first shall be last: for many be called,
699 // We'll most likely encounter a few buckets at the beginning that
700 // have their initial buckets near the end of the table. They were
701 // placed at the beginning as the probe wrapped around the table
702 // during insertion. We must skip forward to a bucket that won't
703 // get reinserted too early and won't unfairly steal others spot.
704 // This eliminates the need for robin hood.
706 bucket
= match bucket
.peek() {
708 if full
.displacement() == 0 {
709 // This bucket occupies its ideal spot.
710 // It indicates the start of another "cluster".
711 bucket
= full
.into_bucket();
714 // Leaving this bucket in the last cluster for later.
718 // Encountered a hole between clusters.
725 // This is how the buckets might be laid out in memory:
726 // ($ marks an initialized bucket)
728 // |$$$_$$$$$$_$$$$$|
730 // But we've skipped the entire initial cluster of buckets
731 // and will continue iteration in this order:
734 // ^ wrap around once end is reached
737 // ^ exit once table.size == 0
739 bucket
= match bucket
.peek() {
741 let h
= bucket
.hash();
742 let (b
, k
, v
) = bucket
.take();
743 self.insert_hashed_ordered(h
, k
, v
);
744 if b
.table().size() == 0 {
749 Empty(b
) => b
.into_bucket()
754 assert_eq
!(self.table
.size(), old_size
);
757 /// Shrinks the capacity of the map as much as possible. It will drop
758 /// down as much as possible while maintaining the internal rules
759 /// and possibly leaving some space in accordance with the resize policy.
764 /// use std::collections::HashMap;
766 /// let mut map: HashMap<isize, isize> = HashMap::with_capacity(100);
767 /// map.insert(1, 2);
768 /// map.insert(3, 4);
769 /// assert!(map.capacity() >= 100);
770 /// map.shrink_to_fit();
771 /// assert!(map.capacity() >= 2);
773 #[stable(feature = "rust1", since = "1.0.0")]
774 pub fn shrink_to_fit(&mut self) {
775 let min_capacity
= self.resize_policy
.min_capacity(self.len());
776 let min_capacity
= max(min_capacity
.next_power_of_two(), INITIAL_CAPACITY
);
778 // An invalid value shouldn't make us run out of space.
779 debug_assert
!(self.len() <= min_capacity
);
781 if self.table
.capacity() != min_capacity
{
782 let old_table
= replace(&mut self.table
, RawTable
::new(min_capacity
));
783 let old_size
= old_table
.size();
785 // Shrink the table. Naive algorithm for resizing:
786 for (h
, k
, v
) in old_table
.into_iter() {
787 self.insert_hashed_nocheck(h
, k
, v
);
790 debug_assert_eq
!(self.table
.size(), old_size
);
794 /// Insert a pre-hashed key-value pair, without first checking
795 /// that there's enough room in the buckets. Returns a reference to the
796 /// newly insert value.
798 /// If the key already exists, the hashtable will be returned untouched
799 /// and a reference to the existing element will be returned.
800 fn insert_hashed_nocheck(&mut self, hash
: SafeHash
, k
: K
, v
: V
) -> Option
<V
> {
801 let entry
= search_hashed(&mut self.table
, hash
, |key
| *key
== k
).into_entry(k
);
803 Some(Occupied(mut elem
)) => {
806 Some(Vacant(elem
)) => {
816 /// An iterator visiting all keys in arbitrary order.
817 /// Iterator element type is `&'a K`.
822 /// use std::collections::HashMap;
824 /// let mut map = HashMap::new();
825 /// map.insert("a", 1);
826 /// map.insert("b", 2);
827 /// map.insert("c", 3);
829 /// for key in map.keys() {
830 /// println!("{}", key);
833 #[stable(feature = "rust1", since = "1.0.0")]
834 pub fn keys(&self) -> Keys
<K
, V
> {
835 Keys { inner: self.iter() }
838 /// An iterator visiting all values in arbitrary order.
839 /// Iterator element type is `&'a V`.
844 /// use std::collections::HashMap;
846 /// let mut map = HashMap::new();
847 /// map.insert("a", 1);
848 /// map.insert("b", 2);
849 /// map.insert("c", 3);
851 /// for val in map.values() {
852 /// println!("{}", val);
855 #[stable(feature = "rust1", since = "1.0.0")]
856 pub fn values(&self) -> Values
<K
, V
> {
857 Values { inner: self.iter() }
860 /// An iterator visiting all values mutably in arbitrary order.
861 /// Iterator element type is `&'a mut V`.
866 /// use std::collections::HashMap;
868 /// let mut map = HashMap::new();
870 /// map.insert("a", 1);
871 /// map.insert("b", 2);
872 /// map.insert("c", 3);
874 /// for val in map.values_mut() {
875 /// *val = *val + 10;
878 /// for val in map.values() {
879 /// println!("{}", val);
882 #[stable(feature = "map_values_mut", since = "1.10.0")]
883 pub fn values_mut(&mut self) -> ValuesMut
<K
, V
> {
884 ValuesMut { inner: self.iter_mut() }
887 /// An iterator visiting all key-value pairs in arbitrary order.
888 /// Iterator element type is `(&'a K, &'a V)`.
893 /// use std::collections::HashMap;
895 /// let mut map = HashMap::new();
896 /// map.insert("a", 1);
897 /// map.insert("b", 2);
898 /// map.insert("c", 3);
900 /// for (key, val) in map.iter() {
901 /// println!("key: {} val: {}", key, val);
904 #[stable(feature = "rust1", since = "1.0.0")]
905 pub fn iter(&self) -> Iter
<K
, V
> {
906 Iter { inner: self.table.iter() }
909 /// An iterator visiting all key-value pairs in arbitrary order,
910 /// with mutable references to the values.
911 /// Iterator element type is `(&'a K, &'a mut V)`.
916 /// use std::collections::HashMap;
918 /// let mut map = HashMap::new();
919 /// map.insert("a", 1);
920 /// map.insert("b", 2);
921 /// map.insert("c", 3);
923 /// // Update all values
924 /// for (_, val) in map.iter_mut() {
928 /// for (key, val) in &map {
929 /// println!("key: {} val: {}", key, val);
932 #[stable(feature = "rust1", since = "1.0.0")]
933 pub fn iter_mut(&mut self) -> IterMut
<K
, V
> {
934 IterMut { inner: self.table.iter_mut() }
937 /// Gets the given key's corresponding entry in the map for in-place manipulation.
942 /// use std::collections::HashMap;
944 /// let mut letters = HashMap::new();
946 /// for ch in "a short treatise on fungi".chars() {
947 /// let counter = letters.entry(ch).or_insert(0);
951 /// assert_eq!(letters[&'s'], 2);
952 /// assert_eq!(letters[&'t'], 3);
953 /// assert_eq!(letters[&'u'], 1);
954 /// assert_eq!(letters.get(&'y'), None);
956 #[stable(feature = "rust1", since = "1.0.0")]
957 pub fn entry(&mut self, key
: K
) -> Entry
<K
, V
> {
960 self.search_mut(&key
).into_entry(key
).expect("unreachable")
963 /// Returns the number of elements in the map.
968 /// use std::collections::HashMap;
970 /// let mut a = HashMap::new();
971 /// assert_eq!(a.len(), 0);
972 /// a.insert(1, "a");
973 /// assert_eq!(a.len(), 1);
975 #[stable(feature = "rust1", since = "1.0.0")]
976 pub fn len(&self) -> usize { self.table.size() }
978 /// Returns true if the map contains no elements.
983 /// use std::collections::HashMap;
985 /// let mut a = HashMap::new();
986 /// assert!(a.is_empty());
987 /// a.insert(1, "a");
988 /// assert!(!a.is_empty());
991 #[stable(feature = "rust1", since = "1.0.0")]
992 pub fn is_empty(&self) -> bool { self.len() == 0 }
994 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
995 /// allocated memory for reuse.
1000 /// use std::collections::HashMap;
1002 /// let mut a = HashMap::new();
1003 /// a.insert(1, "a");
1004 /// a.insert(2, "b");
1006 /// for (k, v) in a.drain().take(1) {
1007 /// assert!(k == 1 || k == 2);
1008 /// assert!(v == "a" || v == "b");
1011 /// assert!(a.is_empty());
1014 #[stable(feature = "drain", since = "1.6.0")]
1015 pub fn drain(&mut self) -> Drain
<K
, V
> {
1017 inner
: self.table
.drain(),
1021 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
1027 /// use std::collections::HashMap;
1029 /// let mut a = HashMap::new();
1030 /// a.insert(1, "a");
1032 /// assert!(a.is_empty());
1034 #[stable(feature = "rust1", since = "1.0.0")]
1036 pub fn clear(&mut self) {
1040 /// Returns a reference to the value corresponding to the key.
1042 /// The key may be any borrowed form of the map's key type, but
1043 /// `Hash` and `Eq` on the borrowed form *must* match those for
1049 /// use std::collections::HashMap;
1051 /// let mut map = HashMap::new();
1052 /// map.insert(1, "a");
1053 /// assert_eq!(map.get(&1), Some(&"a"));
1054 /// assert_eq!(map.get(&2), None);
1056 #[stable(feature = "rust1", since = "1.0.0")]
1057 pub fn get
<Q
: ?Sized
>(&self, k
: &Q
) -> Option
<&V
>
1058 where K
: Borrow
<Q
>, Q
: Hash
+ Eq
1060 self.search(k
).into_occupied_bucket().map(|bucket
| bucket
.into_refs().1)
1063 /// Returns true if the map contains a value for the specified key.
1065 /// The key may be any borrowed form of the map's key type, but
1066 /// `Hash` and `Eq` on the borrowed form *must* match those for
1072 /// use std::collections::HashMap;
1074 /// let mut map = HashMap::new();
1075 /// map.insert(1, "a");
1076 /// assert_eq!(map.contains_key(&1), true);
1077 /// assert_eq!(map.contains_key(&2), false);
1079 #[stable(feature = "rust1", since = "1.0.0")]
1080 pub fn contains_key
<Q
: ?Sized
>(&self, k
: &Q
) -> bool
1081 where K
: Borrow
<Q
>, Q
: Hash
+ Eq
1083 self.search(k
).into_occupied_bucket().is_some()
1086 /// Returns a mutable reference to the value corresponding to the key.
1088 /// The key may be any borrowed form of the map's key type, but
1089 /// `Hash` and `Eq` on the borrowed form *must* match those for
1095 /// use std::collections::HashMap;
1097 /// let mut map = HashMap::new();
1098 /// map.insert(1, "a");
1099 /// if let Some(x) = map.get_mut(&1) {
1102 /// assert_eq!(map[&1], "b");
1104 #[stable(feature = "rust1", since = "1.0.0")]
1105 pub fn get_mut
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<&mut V
>
1106 where K
: Borrow
<Q
>, Q
: Hash
+ Eq
1108 self.search_mut(k
).into_occupied_bucket().map(|bucket
| bucket
.into_mut_refs().1)
1111 /// Inserts a key-value pair into the map.
1113 /// If the map did not have this key present, `None` is returned.
1115 /// If the map did have this key present, the value is updated, and the old
1116 /// value is returned. The key is not updated, though; this matters for
1117 /// types that can be `==` without being identical. See the [module-level
1118 /// documentation] for more.
1120 /// [module-level documentation]: index.html#insert-and-complex-keys
1125 /// use std::collections::HashMap;
1127 /// let mut map = HashMap::new();
1128 /// assert_eq!(map.insert(37, "a"), None);
1129 /// assert_eq!(map.is_empty(), false);
1131 /// map.insert(37, "b");
1132 /// assert_eq!(map.insert(37, "c"), Some("b"));
1133 /// assert_eq!(map[&37], "c");
1135 #[stable(feature = "rust1", since = "1.0.0")]
1136 pub fn insert(&mut self, k
: K
, v
: V
) -> Option
<V
> {
1137 let hash
= self.make_hash(&k
);
1139 self.insert_hashed_nocheck(hash
, k
, v
)
1142 /// Removes a key from the map, returning the value at the key if the key
1143 /// was previously in the map.
1145 /// The key may be any borrowed form of the map's key type, but
1146 /// `Hash` and `Eq` on the borrowed form *must* match those for
1152 /// use std::collections::HashMap;
1154 /// let mut map = HashMap::new();
1155 /// map.insert(1, "a");
1156 /// assert_eq!(map.remove(&1), Some("a"));
1157 /// assert_eq!(map.remove(&1), None);
1159 #[stable(feature = "rust1", since = "1.0.0")]
1160 pub fn remove
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<V
>
1161 where K
: Borrow
<Q
>, Q
: Hash
+ Eq
1163 if self.table
.size() == 0 {
1167 self.search_mut(k
).into_occupied_bucket().map(|bucket
| pop_internal(bucket
).1)
1171 #[stable(feature = "rust1", since = "1.0.0")]
1172 impl<K
, V
, S
> PartialEq
for HashMap
<K
, V
, S
>
1173 where K
: Eq
+ Hash
, V
: PartialEq
, S
: BuildHasher
1175 fn eq(&self, other
: &HashMap
<K
, V
, S
>) -> bool
{
1176 if self.len() != other
.len() { return false; }
1178 self.iter().all(|(key
, value
)|
1179 other
.get(key
).map_or(false, |v
| *value
== *v
)
1184 #[stable(feature = "rust1", since = "1.0.0")]
1185 impl<K
, V
, S
> Eq
for HashMap
<K
, V
, S
>
1186 where K
: Eq
+ Hash
, V
: Eq
, S
: BuildHasher
1189 #[stable(feature = "rust1", since = "1.0.0")]
1190 impl<K
, V
, S
> Debug
for HashMap
<K
, V
, S
>
1191 where K
: Eq
+ Hash
+ Debug
, V
: Debug
, S
: BuildHasher
1193 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1194 f
.debug_map().entries(self.iter()).finish()
1198 #[stable(feature = "rust1", since = "1.0.0")]
1199 impl<K
, V
, S
> Default
for HashMap
<K
, V
, S
>
1201 S
: BuildHasher
+ Default
,
1203 fn default() -> HashMap
<K
, V
, S
> {
1204 HashMap
::with_hasher(Default
::default())
1208 #[stable(feature = "rust1", since = "1.0.0")]
1209 impl<'a
, K
, Q
: ?Sized
, V
, S
> Index
<&'a Q
> for HashMap
<K
, V
, S
>
1210 where K
: Eq
+ Hash
+ Borrow
<Q
>,
1217 fn index(&self, index
: &Q
) -> &V
{
1218 self.get(index
).expect("no entry found for key")
1222 /// HashMap iterator.
1223 #[stable(feature = "rust1", since = "1.0.0")]
1224 pub struct Iter
<'a
, K
: 'a
, V
: 'a
> {
1225 inner
: table
::Iter
<'a
, K
, V
>
1228 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1229 #[stable(feature = "rust1", since = "1.0.0")]
1230 impl<'a
, K
, V
> Clone
for Iter
<'a
, K
, V
> {
1231 fn clone(&self) -> Iter
<'a
, K
, V
> {
1233 inner
: self.inner
.clone()
1238 /// HashMap mutable values iterator.
1239 #[stable(feature = "rust1", since = "1.0.0")]
1240 pub struct IterMut
<'a
, K
: 'a
, V
: 'a
> {
1241 inner
: table
::IterMut
<'a
, K
, V
>
1244 /// HashMap move iterator.
1245 #[stable(feature = "rust1", since = "1.0.0")]
1246 pub struct IntoIter
<K
, V
> {
1247 inner
: table
::IntoIter
<K
, V
>
1250 /// HashMap keys iterator.
1251 #[stable(feature = "rust1", since = "1.0.0")]
1252 pub struct Keys
<'a
, K
: 'a
, V
: 'a
> {
1253 inner
: Iter
<'a
, K
, V
>
1256 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1257 #[stable(feature = "rust1", since = "1.0.0")]
1258 impl<'a
, K
, V
> Clone
for Keys
<'a
, K
, V
> {
1259 fn clone(&self) -> Keys
<'a
, K
, V
> {
1261 inner
: self.inner
.clone()
1266 /// HashMap values iterator.
1267 #[stable(feature = "rust1", since = "1.0.0")]
1268 pub struct Values
<'a
, K
: 'a
, V
: 'a
> {
1269 inner
: Iter
<'a
, K
, V
>
1272 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1273 #[stable(feature = "rust1", since = "1.0.0")]
1274 impl<'a
, K
, V
> Clone
for Values
<'a
, K
, V
> {
1275 fn clone(&self) -> Values
<'a
, K
, V
> {
1277 inner
: self.inner
.clone()
1282 /// HashMap drain iterator.
1283 #[stable(feature = "drain", since = "1.6.0")]
1284 pub struct Drain
<'a
, K
: 'a
, V
: 'a
> {
1285 inner
: table
::Drain
<'a
, K
, V
>
1288 /// Mutable HashMap values iterator.
1289 #[stable(feature = "map_values_mut", since = "1.10.0")]
1290 pub struct ValuesMut
<'a
, K
: 'a
, V
: 'a
> {
1291 inner
: IterMut
<'a
, K
, V
>
1294 enum InternalEntry
<K
, V
, M
> {
1296 elem
: FullBucket
<K
, V
, M
>,
1300 elem
: VacantEntryState
<K
, V
, M
>,
1305 impl<K
, V
, M
> InternalEntry
<K
, V
, M
> {
1307 fn into_occupied_bucket(self) -> Option
<FullBucket
<K
, V
, M
>> {
1309 InternalEntry
::Occupied { elem }
=> Some(elem
),
1315 impl<'a
, K
, V
> InternalEntry
<K
, V
, &'a
mut RawTable
<K
, V
>> {
1317 fn into_entry(self, key
: K
) -> Option
<Entry
<'a
, K
, V
>> {
1319 InternalEntry
::Occupied { elem }
=> {
1320 Some(Occupied(OccupiedEntry
{
1325 InternalEntry
::Vacant { hash, elem }
=> {
1326 Some(Vacant(VacantEntry
{
1332 InternalEntry
::TableIsEmpty
=> None
1337 /// A view into a single location in a map, which may be vacant or occupied.
1338 /// This enum is constructed from the [`entry`] method on [`HashMap`].
1340 /// [`HashMap`]: struct.HashMap.html
1341 /// [`entry`]: struct.HashMap.html#method.entry
1342 #[stable(feature = "rust1", since = "1.0.0")]
1343 pub enum Entry
<'a
, K
: 'a
, V
: 'a
> {
1344 /// An occupied Entry.
1345 #[stable(feature = "rust1", since = "1.0.0")]
1347 #[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>
1351 #[stable(feature = "rust1", since = "1.0.0")]
1353 #[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>
1357 #[stable(feature= "debug_hash_map", since = "1.12.0")]
1358 impl<'a
, K
: 'a
+ Debug
, V
: 'a
+ Debug
> Debug
for Entry
<'a
, K
, V
> {
1359 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1361 Vacant(ref v
) => f
.debug_tuple("Entry")
1364 Occupied(ref o
) => f
.debug_tuple("Entry")
1371 /// A view into a single occupied location in a HashMap.
1372 /// It is part of the [`Entry`] enum.
1374 /// [`Entry`]: enum.Entry.html
1375 #[stable(feature = "rust1", since = "1.0.0")]
1376 pub struct OccupiedEntry
<'a
, K
: 'a
, V
: 'a
> {
1378 elem
: FullBucket
<K
, V
, &'a
mut RawTable
<K
, V
>>,
1381 #[stable(feature= "debug_hash_map", since = "1.12.0")]
1382 impl<'a
, K
: 'a
+ Debug
, V
: 'a
+ Debug
> Debug
for OccupiedEntry
<'a
, K
, V
> {
1383 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1384 f
.debug_struct("OccupiedEntry")
1385 .field("key", self.key())
1386 .field("value", self.get())
1391 /// A view into a single empty location in a HashMap.
1392 /// It is part of the [`Entry`] enum.
1394 /// [`Entry`]: enum.Entry.html
1395 #[stable(feature = "rust1", since = "1.0.0")]
1396 pub struct VacantEntry
<'a
, K
: 'a
, V
: 'a
> {
1399 elem
: VacantEntryState
<K
, V
, &'a
mut RawTable
<K
, V
>>,
1402 #[stable(feature= "debug_hash_map", since = "1.12.0")]
1403 impl<'a
, K
: 'a
+ Debug
, V
: 'a
> Debug
for VacantEntry
<'a
, K
, V
> {
1404 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1405 f
.debug_tuple("VacantEntry")
1411 /// Possible states of a VacantEntry.
1412 enum VacantEntryState
<K
, V
, M
> {
1413 /// The index is occupied, but the key to insert has precedence,
1414 /// and will kick the current one out on insertion.
1415 NeqElem(FullBucket
<K
, V
, M
>, usize),
1416 /// The index is genuinely vacant.
1417 NoElem(EmptyBucket
<K
, V
, M
>),
1420 #[stable(feature = "rust1", since = "1.0.0")]
1421 impl<'a
, K
, V
, S
> IntoIterator
for &'a HashMap
<K
, V
, S
>
1422 where K
: Eq
+ Hash
, S
: BuildHasher
1424 type Item
= (&'a K
, &'a V
);
1425 type IntoIter
= Iter
<'a
, K
, V
>;
1427 fn into_iter(self) -> Iter
<'a
, K
, V
> {
1432 #[stable(feature = "rust1", since = "1.0.0")]
1433 impl<'a
, K
, V
, S
> IntoIterator
for &'a
mut HashMap
<K
, V
, S
>
1434 where K
: Eq
+ Hash
, S
: BuildHasher
1436 type Item
= (&'a K
, &'a
mut V
);
1437 type IntoIter
= IterMut
<'a
, K
, V
>;
1439 fn into_iter(mut self) -> IterMut
<'a
, K
, V
> {
1444 #[stable(feature = "rust1", since = "1.0.0")]
1445 impl<K
, V
, S
> IntoIterator
for HashMap
<K
, V
, S
>
1446 where K
: Eq
+ Hash
, S
: BuildHasher
1449 type IntoIter
= IntoIter
<K
, V
>;
1451 /// Creates a consuming iterator, that is, one that moves each key-value
1452 /// pair out of the map in arbitrary order. The map cannot be used after
1458 /// use std::collections::HashMap;
1460 /// let mut map = HashMap::new();
1461 /// map.insert("a", 1);
1462 /// map.insert("b", 2);
1463 /// map.insert("c", 3);
1465 /// // Not possible with .iter()
1466 /// let vec: Vec<(&str, isize)> = map.into_iter().collect();
1468 fn into_iter(self) -> IntoIter
<K
, V
> {
1470 inner
: self.table
.into_iter()
1475 #[stable(feature = "rust1", since = "1.0.0")]
1476 impl<'a
, K
, V
> Iterator
for Iter
<'a
, K
, V
> {
1477 type Item
= (&'a K
, &'a V
);
1479 #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1480 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1482 #[stable(feature = "rust1", since = "1.0.0")]
1483 impl<'a
, K
, V
> ExactSizeIterator
for Iter
<'a
, K
, V
> {
1484 #[inline] fn len(&self) -> usize { self.inner.len() }
1487 #[stable(feature = "rust1", since = "1.0.0")]
1488 impl<'a
, K
, V
> Iterator
for IterMut
<'a
, K
, V
> {
1489 type Item
= (&'a K
, &'a
mut V
);
1491 #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1492 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1494 #[stable(feature = "rust1", since = "1.0.0")]
1495 impl<'a
, K
, V
> ExactSizeIterator
for IterMut
<'a
, K
, V
> {
1496 #[inline] fn len(&self) -> usize { self.inner.len() }
1499 #[stable(feature = "rust1", since = "1.0.0")]
1500 impl<K
, V
> Iterator
for IntoIter
<K
, V
> {
1503 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next().map(|(_, k, v)| (k, v)) }
1504 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1506 #[stable(feature = "rust1", since = "1.0.0")]
1507 impl<K
, V
> ExactSizeIterator
for IntoIter
<K
, V
> {
1508 #[inline] fn len(&self) -> usize { self.inner.len() }
1511 #[stable(feature = "rust1", since = "1.0.0")]
1512 impl<'a
, K
, V
> Iterator
for Keys
<'a
, K
, V
> {
1515 #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next().map(|(k, _)| k) }
1516 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1518 #[stable(feature = "rust1", since = "1.0.0")]
1519 impl<'a
, K
, V
> ExactSizeIterator
for Keys
<'a
, K
, V
> {
1520 #[inline] fn len(&self) -> usize { self.inner.len() }
1523 #[stable(feature = "rust1", since = "1.0.0")]
1524 impl<'a
, K
, V
> Iterator
for Values
<'a
, K
, V
> {
1527 #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next().map(|(_, v)| v) }
1528 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1530 #[stable(feature = "rust1", since = "1.0.0")]
1531 impl<'a
, K
, V
> ExactSizeIterator
for Values
<'a
, K
, V
> {
1532 #[inline] fn len(&self) -> usize { self.inner.len() }
1535 #[stable(feature = "map_values_mut", since = "1.10.0")]
1536 impl<'a
, K
, V
> Iterator
for ValuesMut
<'a
, K
, V
> {
1537 type Item
= &'a
mut V
;
1539 #[inline] fn next(&mut self) -> Option<(&'a mut V)> { self.inner.next().map(|(_, v)| v) }
1540 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1542 #[stable(feature = "map_values_mut", since = "1.10.0")]
1543 impl<'a
, K
, V
> ExactSizeIterator
for ValuesMut
<'a
, K
, V
> {
1544 #[inline] fn len(&self) -> usize { self.inner.len() }
1547 #[stable(feature = "rust1", since = "1.0.0")]
1548 impl<'a
, K
, V
> Iterator
for Drain
<'a
, K
, V
> {
1551 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next().map(|(_, k, v)| (k, v)) }
1552 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1554 #[stable(feature = "rust1", since = "1.0.0")]
1555 impl<'a
, K
, V
> ExactSizeIterator
for Drain
<'a
, K
, V
> {
1556 #[inline] fn len(&self) -> usize { self.inner.len() }
1559 impl<'a
, K
, V
> Entry
<'a
, K
, V
> {
1560 #[stable(feature = "rust1", since = "1.0.0")]
1561 /// Ensures a value is in the entry by inserting the default if empty, and returns
1562 /// a mutable reference to the value in the entry.
1567 /// use std::collections::HashMap;
1569 /// let mut map: HashMap<&str, u32> = HashMap::new();
1570 /// map.entry("poneyland").or_insert(12);
1572 /// assert_eq!(map["poneyland"], 12);
1574 /// *map.entry("poneyland").or_insert(12) += 10;
1575 /// assert_eq!(map["poneyland"], 22);
1577 pub fn or_insert(self, default: V
) -> &'a
mut V
{
1579 Occupied(entry
) => entry
.into_mut(),
1580 Vacant(entry
) => entry
.insert(default),
1584 #[stable(feature = "rust1", since = "1.0.0")]
1585 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1586 /// and returns a mutable reference to the value in the entry.
1591 /// use std::collections::HashMap;
1593 /// let mut map: HashMap<&str, String> = HashMap::new();
1594 /// let s = "hoho".to_owned();
1596 /// map.entry("poneyland").or_insert_with(|| s);
1598 /// assert_eq!(map["poneyland"], "hoho".to_owned());
1600 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
{
1602 Occupied(entry
) => entry
.into_mut(),
1603 Vacant(entry
) => entry
.insert(default()),
1607 /// Returns a reference to this entry's key.
1612 /// use std::collections::HashMap;
1614 /// let mut map: HashMap<&str, u32> = HashMap::new();
1615 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
1617 #[stable(feature = "map_entry_keys", since = "1.10.0")]
1618 pub fn key(&self) -> &K
{
1620 Occupied(ref entry
) => entry
.key(),
1621 Vacant(ref entry
) => entry
.key(),
1626 impl<'a
, K
, V
> OccupiedEntry
<'a
, K
, V
> {
1627 /// Gets a reference to the key in the entry.
1632 /// use std::collections::HashMap;
1634 /// let mut map: HashMap<&str, u32> = HashMap::new();
1635 /// map.entry("poneyland").or_insert(12);
1636 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
1638 #[stable(feature = "map_entry_keys", since = "1.10.0")]
1639 pub fn key(&self) -> &K
{
1643 /// Deprecated, renamed to `remove_entry`
1644 #[unstable(feature = "map_entry_recover_keys", issue = "34285")]
1645 #[rustc_deprecated(since = "1.12.0", reason = "renamed to `remove_entry`")]
1646 pub fn remove_pair(self) -> (K
, V
) {
1650 /// Take the ownership of the key and value from the map.
1655 /// use std::collections::HashMap;
1656 /// use std::collections::hash_map::Entry;
1658 /// let mut map: HashMap<&str, u32> = HashMap::new();
1659 /// map.entry("poneyland").or_insert(12);
1661 /// if let Entry::Occupied(o) = map.entry("poneyland") {
1662 /// // We delete the entry from the map.
1663 /// o.remove_entry();
1666 /// assert_eq!(map.contains_key("poneyland"), false);
1668 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
1669 pub fn remove_entry(self) -> (K
, V
) {
1670 pop_internal(self.elem
)
1673 /// Gets a reference to the value in the entry.
1678 /// use std::collections::HashMap;
1679 /// use std::collections::hash_map::Entry;
1681 /// let mut map: HashMap<&str, u32> = HashMap::new();
1682 /// map.entry("poneyland").or_insert(12);
1684 /// if let Entry::Occupied(o) = map.entry("poneyland") {
1685 /// assert_eq!(o.get(), &12);
1688 #[stable(feature = "rust1", since = "1.0.0")]
1689 pub fn get(&self) -> &V
{
1693 /// Gets a mutable reference to the value in the entry.
1698 /// use std::collections::HashMap;
1699 /// use std::collections::hash_map::Entry;
1701 /// let mut map: HashMap<&str, u32> = HashMap::new();
1702 /// map.entry("poneyland").or_insert(12);
1704 /// assert_eq!(map["poneyland"], 12);
1705 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
1706 /// *o.get_mut() += 10;
1709 /// assert_eq!(map["poneyland"], 22);
1711 #[stable(feature = "rust1", since = "1.0.0")]
1712 pub fn get_mut(&mut self) -> &mut V
{
1713 self.elem
.read_mut().1
1716 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1717 /// with a lifetime bound to the map itself.
1722 /// use std::collections::HashMap;
1723 /// use std::collections::hash_map::Entry;
1725 /// let mut map: HashMap<&str, u32> = HashMap::new();
1726 /// map.entry("poneyland").or_insert(12);
1728 /// assert_eq!(map["poneyland"], 12);
1729 /// if let Entry::Occupied(o) = map.entry("poneyland") {
1730 /// *o.into_mut() += 10;
1733 /// assert_eq!(map["poneyland"], 22);
1735 #[stable(feature = "rust1", since = "1.0.0")]
1736 pub fn into_mut(self) -> &'a
mut V
{
1737 self.elem
.into_mut_refs().1
1740 /// Sets the value of the entry, and returns the entry's old value.
1745 /// use std::collections::HashMap;
1746 /// use std::collections::hash_map::Entry;
1748 /// let mut map: HashMap<&str, u32> = HashMap::new();
1749 /// map.entry("poneyland").or_insert(12);
1751 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
1752 /// assert_eq!(o.insert(15), 12);
1755 /// assert_eq!(map["poneyland"], 15);
1757 #[stable(feature = "rust1", since = "1.0.0")]
1758 pub fn insert(&mut self, mut value
: V
) -> V
{
1759 let old_value
= self.get_mut();
1760 mem
::swap(&mut value
, old_value
);
1764 /// Takes the value out of the entry, and returns it.
1769 /// use std::collections::HashMap;
1770 /// use std::collections::hash_map::Entry;
1772 /// let mut map: HashMap<&str, u32> = HashMap::new();
1773 /// map.entry("poneyland").or_insert(12);
1775 /// if let Entry::Occupied(o) = map.entry("poneyland") {
1776 /// assert_eq!(o.remove(), 12);
1779 /// assert_eq!(map.contains_key("poneyland"), false);
1781 #[stable(feature = "rust1", since = "1.0.0")]
1782 pub fn remove(self) -> V
{
1783 pop_internal(self.elem
).1
1786 /// Returns a key that was used for search.
1788 /// The key was retained for further use.
1789 fn take_key(&mut self) -> Option
<K
> {
1794 impl<'a
, K
: 'a
, V
: 'a
> VacantEntry
<'a
, K
, V
> {
1795 /// Gets a reference to the key that would be used when inserting a value
1796 /// through the `VacantEntry`.
1801 /// use std::collections::HashMap;
1803 /// let mut map: HashMap<&str, u32> = HashMap::new();
1804 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
1806 #[stable(feature = "map_entry_keys", since = "1.10.0")]
1807 pub fn key(&self) -> &K
{
1811 /// Take ownership of the key.
1816 /// use std::collections::HashMap;
1817 /// use std::collections::hash_map::Entry;
1819 /// let mut map: HashMap<&str, u32> = HashMap::new();
1821 /// if let Entry::Vacant(v) = map.entry("poneyland") {
1825 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
1826 pub fn into_key(self) -> K
{
1830 /// Sets the value of the entry with the VacantEntry's key,
1831 /// and returns a mutable reference to it.
1836 /// use std::collections::HashMap;
1837 /// use std::collections::hash_map::Entry;
1839 /// let mut map: HashMap<&str, u32> = HashMap::new();
1841 /// if let Entry::Vacant(o) = map.entry("poneyland") {
1844 /// assert_eq!(map["poneyland"], 37);
1846 #[stable(feature = "rust1", since = "1.0.0")]
1847 pub fn insert(self, value
: V
) -> &'a
mut V
{
1849 NeqElem(bucket
, ib
) => {
1850 robin_hood(bucket
, ib
, self.hash
, self.key
, value
)
1853 bucket
.put(self.hash
, self.key
, value
).into_mut_refs().1
1859 #[stable(feature = "rust1", since = "1.0.0")]
1860 impl<K
, V
, S
> FromIterator
<(K
, V
)> for HashMap
<K
, V
, S
>
1861 where K
: Eq
+ Hash
, S
: BuildHasher
+ Default
1863 fn from_iter
<T
: IntoIterator
<Item
=(K
, V
)>>(iter
: T
) -> HashMap
<K
, V
, S
> {
1864 let iterator
= iter
.into_iter();
1865 let lower
= iterator
.size_hint().0;
1866 let mut map
= HashMap
::with_capacity_and_hasher(lower
, Default
::default());
1867 map
.extend(iterator
);
1872 #[stable(feature = "rust1", since = "1.0.0")]
1873 impl<K
, V
, S
> Extend
<(K
, V
)> for HashMap
<K
, V
, S
>
1874 where K
: Eq
+ Hash
, S
: BuildHasher
1876 fn extend
<T
: IntoIterator
<Item
=(K
, V
)>>(&mut self, iter
: T
) {
1877 for (k
, v
) in iter
{
1883 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
1884 impl<'a
, K
, V
, S
> Extend
<(&'a K
, &'a V
)> for HashMap
<K
, V
, S
>
1885 where K
: Eq
+ Hash
+ Copy
, V
: Copy
, S
: BuildHasher
1887 fn extend
<T
: IntoIterator
<Item
=(&'a K
, &'a V
)>>(&mut self, iter
: T
) {
1888 self.extend(iter
.into_iter().map(|(&key
, &value
)| (key
, value
)));
1892 /// `RandomState` is the default state for `HashMap` types.
1894 /// A particular instance `RandomState` will create the same instances of
1895 /// `Hasher`, but the hashers created by two different `RandomState`
1896 /// instances are unlikely to produce the same result for the same values.
1901 /// use std::collections::HashMap;
1902 /// use std::collections::hash_map::RandomState;
1904 /// let s = RandomState::new();
1905 /// let mut map = HashMap::with_hasher(s);
1906 /// map.insert(1, 2);
1909 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1910 pub struct RandomState
{
1916 /// Constructs a new `RandomState` that is initialized with random keys.
1921 /// use std::collections::hash_map::RandomState;
1923 /// let s = RandomState::new();
1926 #[allow(deprecated)] // rand
1927 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1928 pub fn new() -> RandomState
{
1929 // Historically this function did not cache keys from the OS and instead
1930 // simply always called `rand::thread_rng().gen()` twice. In #31356 it
1931 // was discovered, however, that because we re-seed the thread-local RNG
1932 // from the OS periodically that this can cause excessive slowdown when
1933 // many hash maps are created on a thread. To solve this performance
1934 // trap we cache the first set of randomly generated keys per-thread.
1936 // In doing this, however, we lose the property that all hash maps have
1937 // nondeterministic iteration order as all of those created on the same
1938 // thread would have the same hash keys. This property has been nice in
1939 // the past as it allows for maximal flexibility in the implementation
1940 // of `HashMap` itself.
1942 // The constraint here (if there even is one) is just that maps created
1943 // on the same thread have the same iteration order, and that *may* be
1944 // relied upon even though it is not a documented guarantee at all of
1945 // the `HashMap` type. In any case we've decided that this is reasonable
1946 // for now, so caching keys thread-locally seems fine.
1947 thread_local
!(static KEYS
: (u64, u64) = {
1948 let r
= rand
::OsRng
::new();
1949 let mut r
= r
.expect("failed to create an OS RNG");
1953 KEYS
.with(|&(k0
, k1
)| {
1954 RandomState { k0: k0, k1: k1 }
1959 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1960 impl BuildHasher
for RandomState
{
1961 type Hasher
= DefaultHasher
;
1963 fn build_hasher(&self) -> DefaultHasher
{
1964 DefaultHasher(SipHasher13
::new_with_keys(self.k0
, self.k1
))
1968 /// The default `Hasher` used by `RandomState`.
1970 /// The internal algorithm is not specified, and so it and its hashes should
1971 /// not be relied upon over releases.
1972 #[unstable(feature = "hashmap_default_hasher", issue = "0")]
1973 pub struct DefaultHasher(SipHasher13
);
1975 #[unstable(feature = "hashmap_default_hasher", issue = "0")]
1976 impl Hasher
for DefaultHasher
{
1978 fn write(&mut self, msg
: &[u8]) {
1983 fn finish(&self) -> u64 {
1988 #[stable(feature = "rust1", since = "1.0.0")]
1989 impl Default
for RandomState
{
1991 fn default() -> RandomState
{
1996 impl<K
, S
, Q
: ?Sized
> super::Recover
<Q
> for HashMap
<K
, (), S
>
1997 where K
: Eq
+ Hash
+ Borrow
<Q
>, S
: BuildHasher
, Q
: Eq
+ Hash
2001 fn get(&self, key
: &Q
) -> Option
<&K
> {
2002 self.search(key
).into_occupied_bucket().map(|bucket
| bucket
.into_refs().0)
2005 fn take(&mut self, key
: &Q
) -> Option
<K
> {
2006 if self.table
.size() == 0 {
2010 self.search_mut(key
).into_occupied_bucket().map(|bucket
| pop_internal(bucket
).0)
2013 fn replace(&mut self, key
: K
) -> Option
<K
> {
2016 match self.entry(key
) {
2017 Occupied(mut occupied
) => {
2018 let key
= occupied
.take_key().unwrap();
2019 Some(mem
::replace(occupied
.elem
.read_mut().0, key
))
2030 fn assert_covariance() {
2031 fn map_key
<'new
>(v
: HashMap
<&'
static str, u8>) -> HashMap
<&'new
str, u8> { v }
2032 fn map_val
<'new
>(v
: HashMap
<u8, &'
static str>) -> HashMap
<u8, &'new
str> { v }
2033 fn iter_key
<'a
, 'new
>(v
: Iter
<'a
, &'
static str, u8>) -> Iter
<'a
, &'new
str, u8> { v }
2034 fn iter_val
<'a
, 'new
>(v
: Iter
<'a
, u8, &'
static str>) -> Iter
<'a
, u8, &'new
str> { v }
2035 fn into_iter_key
<'new
>(v
: IntoIter
<&'
static str, u8>) -> IntoIter
<&'new
str, u8> { v }
2036 fn into_iter_val
<'new
>(v
: IntoIter
<u8, &'
static str>) -> IntoIter
<u8, &'new
str> { v }
2037 fn keys_key
<'a
, 'new
>(v
: Keys
<'a
, &'
static str, u8>) -> Keys
<'a
, &'new
str, u8> { v }
2038 fn keys_val
<'a
, 'new
>(v
: Keys
<'a
, u8, &'
static str>) -> Keys
<'a
, u8, &'new
str> { v }
2039 fn values_key
<'a
, 'new
>(v
: Values
<'a
, &'
static str, u8>) -> Values
<'a
, &'new
str, u8> { v }
2040 fn values_val
<'a
, 'new
>(v
: Values
<'a
, u8, &'
static str>) -> Values
<'a
, u8, &'new
str> { v }
2048 use super::Entry
::{Occupied, Vacant}
;
2050 use rand
::{thread_rng, Rng}
;
2053 fn test_create_capacity_zero() {
2054 let mut m
= HashMap
::with_capacity(0);
2056 assert
!(m
.insert(1, 1).is_none());
2058 assert
!(m
.contains_key(&1));
2059 assert
!(!m
.contains_key(&0));
2064 let mut m
= HashMap
::new();
2065 assert_eq
!(m
.len(), 0);
2066 assert
!(m
.insert(1, 2).is_none());
2067 assert_eq
!(m
.len(), 1);
2068 assert
!(m
.insert(2, 4).is_none());
2069 assert_eq
!(m
.len(), 2);
2070 assert_eq
!(*m
.get(&1).unwrap(), 2);
2071 assert_eq
!(*m
.get(&2).unwrap(), 4);
2076 let mut m
= HashMap
::new();
2077 assert_eq
!(m
.len(), 0);
2078 assert
!(m
.insert(1, 2).is_none());
2079 assert_eq
!(m
.len(), 1);
2080 assert
!(m
.insert(2, 4).is_none());
2081 assert_eq
!(m
.len(), 2);
2083 assert_eq
!(*m2
.get(&1).unwrap(), 2);
2084 assert_eq
!(*m2
.get(&2).unwrap(), 4);
2085 assert_eq
!(m2
.len(), 2);
2088 thread_local
! { static DROP_VECTOR: RefCell<Vec<isize>> = RefCell::new(Vec::new()) }
2090 #[derive(Hash, PartialEq, Eq)]
2096 fn new(k
: usize) -> Dropable
{
2097 DROP_VECTOR
.with(|slot
| {
2098 slot
.borrow_mut()[k
] += 1;
2105 impl Drop
for Dropable
{
2106 fn drop(&mut self) {
2107 DROP_VECTOR
.with(|slot
| {
2108 slot
.borrow_mut()[self.k
] -= 1;
2113 impl Clone
for Dropable
{
2114 fn clone(&self) -> Dropable
{
2115 Dropable
::new(self.k
)
2121 DROP_VECTOR
.with(|slot
| {
2122 *slot
.borrow_mut() = vec
![0; 200];
2126 let mut m
= HashMap
::new();
2128 DROP_VECTOR
.with(|v
| {
2130 assert_eq
!(v
.borrow()[i
], 0);
2135 let d1
= Dropable
::new(i
);
2136 let d2
= Dropable
::new(i
+100);
2140 DROP_VECTOR
.with(|v
| {
2142 assert_eq
!(v
.borrow()[i
], 1);
2147 let k
= Dropable
::new(i
);
2148 let v
= m
.remove(&k
);
2150 assert
!(v
.is_some());
2152 DROP_VECTOR
.with(|v
| {
2153 assert_eq
!(v
.borrow()[i
], 1);
2154 assert_eq
!(v
.borrow()[i
+100], 1);
2158 DROP_VECTOR
.with(|v
| {
2160 assert_eq
!(v
.borrow()[i
], 0);
2161 assert_eq
!(v
.borrow()[i
+100], 0);
2165 assert_eq
!(v
.borrow()[i
], 1);
2166 assert_eq
!(v
.borrow()[i
+100], 1);
2171 DROP_VECTOR
.with(|v
| {
2173 assert_eq
!(v
.borrow()[i
], 0);
2179 fn test_into_iter_drops() {
2180 DROP_VECTOR
.with(|v
| {
2181 *v
.borrow_mut() = vec
![0; 200];
2185 let mut hm
= HashMap
::new();
2187 DROP_VECTOR
.with(|v
| {
2189 assert_eq
!(v
.borrow()[i
], 0);
2194 let d1
= Dropable
::new(i
);
2195 let d2
= Dropable
::new(i
+100);
2199 DROP_VECTOR
.with(|v
| {
2201 assert_eq
!(v
.borrow()[i
], 1);
2208 // By the way, ensure that cloning doesn't screw up the dropping.
2212 let mut half
= hm
.into_iter().take(50);
2214 DROP_VECTOR
.with(|v
| {
2216 assert_eq
!(v
.borrow()[i
], 1);
2220 for _
in half
.by_ref() {}
2222 DROP_VECTOR
.with(|v
| {
2223 let nk
= (0..100).filter(|&i
| {
2227 let nv
= (0..100).filter(|&i
| {
2228 v
.borrow()[i
+100] == 1
2236 DROP_VECTOR
.with(|v
| {
2238 assert_eq
!(v
.borrow()[i
], 0);
2244 fn test_empty_remove() {
2245 let mut m
: HashMap
<isize, bool
> = HashMap
::new();
2246 assert_eq
!(m
.remove(&0), None
);
2250 fn test_empty_entry() {
2251 let mut m
: HashMap
<isize, bool
> = HashMap
::new();
2253 Occupied(_
) => panic
!(),
2256 assert
!(*m
.entry(0).or_insert(true));
2257 assert_eq
!(m
.len(), 1);
2261 fn test_empty_iter() {
2262 let mut m
: HashMap
<isize, bool
> = HashMap
::new();
2263 assert_eq
!(m
.drain().next(), None
);
2264 assert_eq
!(m
.keys().next(), None
);
2265 assert_eq
!(m
.values().next(), None
);
2266 assert_eq
!(m
.values_mut().next(), None
);
2267 assert_eq
!(m
.iter().next(), None
);
2268 assert_eq
!(m
.iter_mut().next(), None
);
2269 assert_eq
!(m
.len(), 0);
2270 assert
!(m
.is_empty());
2271 assert_eq
!(m
.into_iter().next(), None
);
2275 fn test_lots_of_insertions() {
2276 let mut m
= HashMap
::new();
2278 // Try this a few times to make sure we never screw up the hashmap's
2281 assert
!(m
.is_empty());
2284 assert
!(m
.insert(i
, i
).is_none());
2288 assert_eq
!(r
, Some(&j
));
2291 for j
in i
+1..1001 {
2293 assert_eq
!(r
, None
);
2297 for i
in 1001..2001 {
2298 assert
!(!m
.contains_key(&i
));
2303 assert
!(m
.remove(&i
).is_some());
2306 assert
!(!m
.contains_key(&j
));
2309 for j
in i
+1..1001 {
2310 assert
!(m
.contains_key(&j
));
2315 assert
!(!m
.contains_key(&i
));
2319 assert
!(m
.insert(i
, i
).is_none());
2323 for i
in (1..1001).rev() {
2324 assert
!(m
.remove(&i
).is_some());
2327 assert
!(!m
.contains_key(&j
));
2331 assert
!(m
.contains_key(&j
));
2338 fn test_find_mut() {
2339 let mut m
= HashMap
::new();
2340 assert
!(m
.insert(1, 12).is_none());
2341 assert
!(m
.insert(2, 8).is_none());
2342 assert
!(m
.insert(5, 14).is_none());
2344 match m
.get_mut(&5) {
2345 None
=> panic
!(), Some(x
) => *x
= new
2347 assert_eq
!(m
.get(&5), Some(&new
));
2351 fn test_insert_overwrite() {
2352 let mut m
= HashMap
::new();
2353 assert
!(m
.insert(1, 2).is_none());
2354 assert_eq
!(*m
.get(&1).unwrap(), 2);
2355 assert
!(!m
.insert(1, 3).is_none());
2356 assert_eq
!(*m
.get(&1).unwrap(), 3);
2360 fn test_insert_conflicts() {
2361 let mut m
= HashMap
::with_capacity(4);
2362 assert
!(m
.insert(1, 2).is_none());
2363 assert
!(m
.insert(5, 3).is_none());
2364 assert
!(m
.insert(9, 4).is_none());
2365 assert_eq
!(*m
.get(&9).unwrap(), 4);
2366 assert_eq
!(*m
.get(&5).unwrap(), 3);
2367 assert_eq
!(*m
.get(&1).unwrap(), 2);
2371 fn test_conflict_remove() {
2372 let mut m
= HashMap
::with_capacity(4);
2373 assert
!(m
.insert(1, 2).is_none());
2374 assert_eq
!(*m
.get(&1).unwrap(), 2);
2375 assert
!(m
.insert(5, 3).is_none());
2376 assert_eq
!(*m
.get(&1).unwrap(), 2);
2377 assert_eq
!(*m
.get(&5).unwrap(), 3);
2378 assert
!(m
.insert(9, 4).is_none());
2379 assert_eq
!(*m
.get(&1).unwrap(), 2);
2380 assert_eq
!(*m
.get(&5).unwrap(), 3);
2381 assert_eq
!(*m
.get(&9).unwrap(), 4);
2382 assert
!(m
.remove(&1).is_some());
2383 assert_eq
!(*m
.get(&9).unwrap(), 4);
2384 assert_eq
!(*m
.get(&5).unwrap(), 3);
2388 fn test_is_empty() {
2389 let mut m
= HashMap
::with_capacity(4);
2390 assert
!(m
.insert(1, 2).is_none());
2391 assert
!(!m
.is_empty());
2392 assert
!(m
.remove(&1).is_some());
2393 assert
!(m
.is_empty());
2398 let mut m
= HashMap
::new();
2400 assert_eq
!(m
.remove(&1), Some(2));
2401 assert_eq
!(m
.remove(&1), None
);
2406 let mut m
= HashMap
::with_capacity(4);
2408 assert
!(m
.insert(i
, i
*2).is_none());
2410 assert_eq
!(m
.len(), 32);
2412 let mut observed
: u32 = 0;
2415 assert_eq
!(*v
, *k
* 2);
2416 observed
|= 1 << *k
;
2418 assert_eq
!(observed
, 0xFFFF_FFFF);
2423 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
2424 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
2425 let keys
: Vec
<_
> = map
.keys().cloned().collect();
2426 assert_eq
!(keys
.len(), 3);
2427 assert
!(keys
.contains(&1));
2428 assert
!(keys
.contains(&2));
2429 assert
!(keys
.contains(&3));
2434 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
2435 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
2436 let values
: Vec
<_
> = map
.values().cloned().collect();
2437 assert_eq
!(values
.len(), 3);
2438 assert
!(values
.contains(&'a'
));
2439 assert
!(values
.contains(&'b'
));
2440 assert
!(values
.contains(&'c'
));
2444 fn test_values_mut() {
2445 let vec
= vec
![(1, 1), (2, 2), (3, 3)];
2446 let mut map
: HashMap
<_
, _
> = vec
.into_iter().collect();
2447 for value
in map
.values_mut() {
2448 *value
= (*value
) * 2
2450 let values
: Vec
<_
> = map
.values().cloned().collect();
2451 assert_eq
!(values
.len(), 3);
2452 assert
!(values
.contains(&2));
2453 assert
!(values
.contains(&4));
2454 assert
!(values
.contains(&6));
2459 let mut m
= HashMap
::new();
2460 assert
!(m
.get(&1).is_none());
2464 Some(v
) => assert_eq
!(*v
, 2)
2470 let mut m1
= HashMap
::new();
2475 let mut m2
= HashMap
::new();
2488 let mut map
= HashMap
::new();
2489 let empty
: HashMap
<i32, i32> = HashMap
::new();
2494 let map_str
= format
!("{:?}", map
);
2496 assert
!(map_str
== "{1: 2, 3: 4}" ||
2497 map_str
== "{3: 4, 1: 2}");
2498 assert_eq
!(format
!("{:?}", empty
), "{}");
2503 let mut m
= HashMap
::new();
2505 assert_eq
!(m
.len(), 0);
2506 assert
!(m
.is_empty());
2509 let old_cap
= m
.table
.capacity();
2510 while old_cap
== m
.table
.capacity() {
2515 assert_eq
!(m
.len(), i
);
2516 assert
!(!m
.is_empty());
2520 fn test_behavior_resize_policy() {
2521 let mut m
= HashMap
::new();
2523 assert_eq
!(m
.len(), 0);
2524 assert_eq
!(m
.table
.capacity(), 0);
2525 assert
!(m
.is_empty());
2529 assert
!(m
.is_empty());
2530 let initial_cap
= m
.table
.capacity();
2531 m
.reserve(initial_cap
);
2532 let cap
= m
.table
.capacity();
2534 assert_eq
!(cap
, initial_cap
* 2);
2537 for _
in 0..cap
* 3 / 4 {
2541 // three quarters full
2543 assert_eq
!(m
.len(), i
);
2544 assert_eq
!(m
.table
.capacity(), cap
);
2546 for _
in 0..cap
/ 4 {
2552 let new_cap
= m
.table
.capacity();
2553 assert_eq
!(new_cap
, cap
* 2);
2555 for _
in 0..cap
/ 2 - 1 {
2558 assert_eq
!(m
.table
.capacity(), new_cap
);
2560 // A little more than one quarter full.
2562 assert_eq
!(m
.table
.capacity(), cap
);
2563 // again, a little more than half full
2564 for _
in 0..cap
/ 2 - 1 {
2570 assert_eq
!(m
.len(), i
);
2571 assert
!(!m
.is_empty());
2572 assert_eq
!(m
.table
.capacity(), initial_cap
);
2576 fn test_reserve_shrink_to_fit() {
2577 let mut m
= HashMap
::new();
2580 assert
!(m
.capacity() >= m
.len());
2586 let usable_cap
= m
.capacity();
2587 for i
in 128..(128 + 256) {
2589 assert_eq
!(m
.capacity(), usable_cap
);
2592 for i
in 100..(128 + 256) {
2593 assert_eq
!(m
.remove(&i
), Some(i
));
2597 assert_eq
!(m
.len(), 100);
2598 assert
!(!m
.is_empty());
2599 assert
!(m
.capacity() >= m
.len());
2602 assert_eq
!(m
.remove(&i
), Some(i
));
2607 assert_eq
!(m
.len(), 1);
2608 assert
!(m
.capacity() >= m
.len());
2609 assert_eq
!(m
.remove(&0), Some(0));
2613 fn test_from_iter() {
2614 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2616 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2618 for &(k
, v
) in &xs
{
2619 assert_eq
!(map
.get(&k
), Some(&v
));
2624 fn test_size_hint() {
2625 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2627 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2629 let mut iter
= map
.iter();
2631 for _
in iter
.by_ref().take(3) {}
2633 assert_eq
!(iter
.size_hint(), (3, Some(3)));
2637 fn test_iter_len() {
2638 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2640 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2642 let mut iter
= map
.iter();
2644 for _
in iter
.by_ref().take(3) {}
2646 assert_eq
!(iter
.len(), 3);
2650 fn test_mut_size_hint() {
2651 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2653 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2655 let mut iter
= map
.iter_mut();
2657 for _
in iter
.by_ref().take(3) {}
2659 assert_eq
!(iter
.size_hint(), (3, Some(3)));
2663 fn test_iter_mut_len() {
2664 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2666 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2668 let mut iter
= map
.iter_mut();
2670 for _
in iter
.by_ref().take(3) {}
2672 assert_eq
!(iter
.len(), 3);
2677 let mut map
= HashMap
::new();
2683 assert_eq
!(map
[&2], 1);
2688 fn test_index_nonexistent() {
2689 let mut map
= HashMap
::new();
2700 let xs
= [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2702 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2704 // Existing key (insert)
2705 match map
.entry(1) {
2706 Vacant(_
) => unreachable
!(),
2707 Occupied(mut view
) => {
2708 assert_eq
!(view
.get(), &10);
2709 assert_eq
!(view
.insert(100), 10);
2712 assert_eq
!(map
.get(&1).unwrap(), &100);
2713 assert_eq
!(map
.len(), 6);
2716 // Existing key (update)
2717 match map
.entry(2) {
2718 Vacant(_
) => unreachable
!(),
2719 Occupied(mut view
) => {
2720 let v
= view
.get_mut();
2721 let new_v
= (*v
) * 10;
2725 assert_eq
!(map
.get(&2).unwrap(), &200);
2726 assert_eq
!(map
.len(), 6);
2728 // Existing key (take)
2729 match map
.entry(3) {
2730 Vacant(_
) => unreachable
!(),
2732 assert_eq
!(view
.remove(), 30);
2735 assert_eq
!(map
.get(&3), None
);
2736 assert_eq
!(map
.len(), 5);
2739 // Inexistent key (insert)
2740 match map
.entry(10) {
2741 Occupied(_
) => unreachable
!(),
2743 assert_eq
!(*view
.insert(1000), 1000);
2746 assert_eq
!(map
.get(&10).unwrap(), &1000);
2747 assert_eq
!(map
.len(), 6);
2751 fn test_entry_take_doesnt_corrupt() {
2752 #![allow(deprecated)] //rand
2754 fn check(m
: &HashMap
<isize, ()>) {
2756 assert
!(m
.contains_key(k
),
2757 "{} is in keys() but not in the map?", k
);
2761 let mut m
= HashMap
::new();
2762 let mut rng
= thread_rng();
2764 // Populate the map with some items.
2766 let x
= rng
.gen_range(-10, 10);
2771 let x
= rng
.gen_range(-10, 10);
2775 println
!("{}: remove {}", i
, x
);
2785 fn test_extend_ref() {
2786 let mut a
= HashMap
::new();
2788 let mut b
= HashMap
::new();
2790 b
.insert(3, "three");
2794 assert_eq
!(a
.len(), 3);
2795 assert_eq
!(a
[&1], "one");
2796 assert_eq
!(a
[&2], "two");
2797 assert_eq
!(a
[&3], "three");
2801 fn test_capacity_not_less_than_len() {
2802 let mut a
= HashMap
::new();
2810 assert
!(a
.capacity() > a
.len());
2812 let free
= a
.capacity() - a
.len();
2818 assert_eq
!(a
.len(), a
.capacity());
2820 // Insert at capacity should cause allocation.
2822 assert
!(a
.capacity() > a
.len());
2826 fn test_occupied_entry_key() {
2827 let mut a
= HashMap
::new();
2828 let key
= "hello there";
2829 let value
= "value goes here";
2830 assert
!(a
.is_empty());
2831 a
.insert(key
.clone(), value
.clone());
2832 assert_eq
!(a
.len(), 1);
2833 assert_eq
!(a
[key
], value
);
2835 match a
.entry(key
.clone()) {
2836 Vacant(_
) => panic
!(),
2837 Occupied(e
) => assert_eq
!(key
, *e
.key()),
2839 assert_eq
!(a
.len(), 1);
2840 assert_eq
!(a
[key
], value
);
2844 fn test_vacant_entry_key() {
2845 let mut a
= HashMap
::new();
2846 let key
= "hello there";
2847 let value
= "value goes here";
2849 assert
!(a
.is_empty());
2850 match a
.entry(key
.clone()) {
2851 Occupied(_
) => panic
!(),
2853 assert_eq
!(key
, *e
.key());
2854 e
.insert(value
.clone());
2857 assert_eq
!(a
.len(), 1);
2858 assert_eq
!(a
[key
], value
);