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, SipHasher, BuildHasher}
;
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 /// The hashes are all keyed by the thread-local random number generator
203 /// on creation by default. This means that the ordering of the keys is
204 /// randomized, but makes the tables more resistant to
205 /// denial-of-service attacks (Hash DoS). This behavior can be
206 /// overridden with one of the constructors.
208 /// It is required that the keys implement the `Eq` and `Hash` traits, although
209 /// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
210 /// If you implement these yourself, it is important that the following
214 /// k1 == k2 -> hash(k1) == hash(k2)
217 /// In other words, if two keys are equal, their hashes must be equal.
219 /// It is a logic error for a key to be modified in such a way that the key's
220 /// hash, as determined by the `Hash` trait, or its equality, as determined by
221 /// the `Eq` trait, changes while it is in the map. This is normally only
222 /// possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
224 /// Relevant papers/articles:
226 /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)
227 /// 2. Emmanuel Goossaert. ["Robin Hood
228 /// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/)
229 /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift
230 /// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)
235 /// use std::collections::HashMap;
237 /// // type inference lets us omit an explicit type signature (which
238 /// // would be `HashMap<&str, &str>` in this example).
239 /// let mut book_reviews = HashMap::new();
241 /// // review some books.
242 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
243 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
244 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
245 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
247 /// // check for a specific one.
248 /// if !book_reviews.contains_key("Les Misérables") {
249 /// println!("We've got {} reviews, but Les Misérables ain't one.",
250 /// book_reviews.len());
253 /// // oops, this review has a lot of spelling mistakes, let's delete it.
254 /// book_reviews.remove("The Adventures of Sherlock Holmes");
256 /// // look up the values associated with some keys.
257 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
258 /// for book in &to_find {
259 /// match book_reviews.get(book) {
260 /// Some(review) => println!("{}: {}", book, review),
261 /// None => println!("{} is unreviewed.", book)
265 /// // iterate over everything.
266 /// for (book, review) in &book_reviews {
267 /// println!("{}: \"{}\"", book, review);
271 /// `HashMap` also implements an [`Entry API`](#method.entry), which allows
272 /// for more complex methods of getting, setting, updating and removing keys and
276 /// use std::collections::HashMap;
278 /// // type inference lets us omit an explicit type signature (which
279 /// // would be `HashMap<&str, u8>` in this example).
280 /// let mut player_stats = HashMap::new();
282 /// fn random_stat_buff() -> u8 {
283 /// // could actually return some random value here - let's just return
284 /// // some fixed value for now
288 /// // insert a key only if it doesn't already exist
289 /// player_stats.entry("health").or_insert(100);
291 /// // insert a key using a function that provides a new value only if it
292 /// // doesn't already exist
293 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
295 /// // update a key, guarding against the key possibly not being set
296 /// let stat = player_stats.entry("attack").or_insert(100);
297 /// *stat += random_stat_buff();
300 /// The easiest way to use `HashMap` with a custom type as key is to derive `Eq` and `Hash`.
301 /// We must also derive `PartialEq`.
304 /// use std::collections::HashMap;
306 /// #[derive(Hash, Eq, PartialEq, Debug)]
313 /// /// Create a new Viking.
314 /// fn new(name: &str, country: &str) -> Viking {
315 /// Viking { name: name.to_string(), country: country.to_string() }
319 /// // Use a HashMap to store the vikings' health points.
320 /// let mut vikings = HashMap::new();
322 /// vikings.insert(Viking::new("Einar", "Norway"), 25);
323 /// vikings.insert(Viking::new("Olaf", "Denmark"), 24);
324 /// vikings.insert(Viking::new("Harald", "Iceland"), 12);
326 /// // Use derived implementation to print the status of the vikings.
327 /// for (viking, health) in &vikings {
328 /// println!("{:?} has {} hp", viking, health);
332 #[stable(feature = "rust1", since = "1.0.0")]
333 pub struct HashMap
<K
, V
, S
= RandomState
> {
334 // All hashes are keyed on these values, to prevent hash collision attacks.
337 table
: RawTable
<K
, V
>,
339 resize_policy
: DefaultResizePolicy
,
342 /// Search for a pre-hashed key.
344 fn search_hashed
<K
, V
, M
, F
>(table
: M
,
347 -> InternalEntry
<K
, V
, M
> where
348 M
: Deref
<Target
=RawTable
<K
, V
>>,
349 F
: FnMut(&K
) -> bool
,
351 // This is the only function where capacity can be zero. To avoid
352 // undefined behavior when Bucket::new gets the raw bucket in this
353 // case, immediately return the appropriate search result.
354 if table
.capacity() == 0 {
355 return InternalEntry
::TableIsEmpty
;
358 let size
= table
.size() as isize;
359 let mut probe
= Bucket
::new(table
, hash
);
360 let ib
= probe
.index() as isize;
363 let full
= match probe
.peek() {
366 return InternalEntry
::Vacant
{
368 elem
: NoElem(bucket
),
371 Full(bucket
) => bucket
374 let robin_ib
= full
.index() as isize - full
.displacement() as isize;
377 // Found a luckier bucket than me.
378 // We can finish the search early if we hit any bucket
379 // with a lower distance to initial bucket than we've probed.
380 return InternalEntry
::Vacant
{
382 elem
: NeqElem(full
, robin_ib
as usize),
386 // If the hash doesn't match, it can't be this one..
387 if hash
== full
.hash() {
388 // If the key doesn't match, it can't be this one..
389 if is_match(full
.read().0) {
390 return InternalEntry
::Occupied
{
397 debug_assert
!(probe
.index() as isize != ib
+ size
+ 1);
401 fn pop_internal
<K
, V
>(starting_bucket
: FullBucketMut
<K
, V
>) -> (K
, V
) {
402 let (empty
, retkey
, retval
) = starting_bucket
.take();
403 let mut gap
= match empty
.gap_peek() {
405 None
=> return (retkey
, retval
)
408 while gap
.full().displacement() != 0 {
409 gap
= match gap
.shift() {
415 // Now we've done all our shifting. Return the value we grabbed earlier.
419 /// Perform robin hood bucket stealing at the given `bucket`. You must
420 /// also pass the position of that bucket's initial bucket so we don't have
421 /// to recalculate it.
423 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
424 fn robin_hood
<'a
, K
: 'a
, V
: 'a
>(bucket
: FullBucketMut
<'a
, K
, V
>,
430 let starting_index
= bucket
.index();
431 let size
= bucket
.table().size();
432 // Save the *starting point*.
433 let mut bucket
= bucket
.stash();
434 // There can be at most `size - dib` buckets to displace, because
435 // in the worst case, there are `size` elements and we already are
436 // `displacement` buckets away from the initial one.
437 let idx_end
= starting_index
+ size
- bucket
.displacement();
440 let (old_hash
, old_key
, old_val
) = bucket
.replace(hash
, key
, val
);
446 let probe
= bucket
.next();
447 debug_assert
!(probe
.index() != idx_end
);
449 let full_bucket
= match probe
.peek() {
452 let bucket
= bucket
.put(hash
, key
, val
);
453 // Now that it's stolen, just read the value's pointer
454 // right out of the table! Go back to the *starting point*.
456 // This use of `into_table` is misleading. It turns the
457 // bucket, which is a FullBucket on top of a
458 // FullBucketMut, into just one FullBucketMut. The "table"
459 // refers to the inner FullBucketMut in this context.
460 return bucket
.into_table().into_mut_refs().1;
462 Full(bucket
) => bucket
465 let probe_ib
= full_bucket
.index() - full_bucket
.displacement();
467 bucket
= full_bucket
;
469 // Robin hood! Steal the spot.
478 impl<K
, V
, S
> HashMap
<K
, V
, S
>
479 where K
: Eq
+ Hash
, S
: BuildHasher
481 fn make_hash
<X
: ?Sized
>(&self, x
: &X
) -> SafeHash
where X
: Hash
{
482 table
::make_hash(&self.hash_builder
, x
)
485 /// Search for a key, yielding the index if it's found in the hashtable.
486 /// If you already have the hash for the key lying around, use
489 fn search
<'a
, Q
: ?Sized
>(&'a
self, q
: &Q
) -> InternalEntry
<K
, V
, &'a RawTable
<K
, V
>>
490 where K
: Borrow
<Q
>, Q
: Eq
+ Hash
492 let hash
= self.make_hash(q
);
493 search_hashed(&self.table
, hash
, |k
| q
.eq(k
.borrow()))
497 fn search_mut
<'a
, Q
: ?Sized
>(&'a
mut self, q
: &Q
) -> InternalEntry
<K
, V
, &'a
mut RawTable
<K
, V
>>
498 where K
: Borrow
<Q
>, Q
: Eq
+ Hash
500 let hash
= self.make_hash(q
);
501 search_hashed(&mut self.table
, hash
, |k
| q
.eq(k
.borrow()))
504 // The caller should ensure that invariants by Robin Hood Hashing hold.
505 fn insert_hashed_ordered(&mut self, hash
: SafeHash
, k
: K
, v
: V
) {
506 let cap
= self.table
.capacity();
507 let mut buckets
= Bucket
::new(&mut self.table
, hash
);
508 let ib
= buckets
.index();
510 while buckets
.index() != ib
+ cap
{
511 // We don't need to compare hashes for value swap.
512 // Not even DIBs for Robin Hood.
513 buckets
= match buckets
.peek() {
515 empty
.put(hash
, k
, v
);
518 Full(b
) => b
.into_bucket()
522 panic
!("Internal HashMap error: Out of space.");
526 impl<K
: Hash
+ Eq
, V
> HashMap
<K
, V
, RandomState
> {
527 /// Creates an empty HashMap.
532 /// use std::collections::HashMap;
533 /// let mut map: HashMap<&str, isize> = HashMap::new();
536 #[stable(feature = "rust1", since = "1.0.0")]
537 pub fn new() -> HashMap
<K
, V
, RandomState
> {
541 /// Creates an empty hash map with the given initial capacity.
546 /// use std::collections::HashMap;
547 /// let mut map: HashMap<&str, isize> = HashMap::with_capacity(10);
550 #[stable(feature = "rust1", since = "1.0.0")]
551 pub fn with_capacity(capacity
: usize) -> HashMap
<K
, V
, RandomState
> {
552 HashMap
::with_capacity_and_hasher(capacity
, Default
::default())
556 impl<K
, V
, S
> HashMap
<K
, V
, S
>
557 where K
: Eq
+ Hash
, S
: BuildHasher
559 /// Creates an empty hashmap which will use the given hash builder to hash
562 /// The created map has the default initial capacity.
564 /// Warning: `hash_builder` is normally randomly generated, and
565 /// is designed to allow HashMaps to be resistant to attacks that
566 /// cause many collisions and very poor performance. Setting it
567 /// manually using this function can expose a DoS attack vector.
572 /// use std::collections::HashMap;
573 /// use std::collections::hash_map::RandomState;
575 /// let s = RandomState::new();
576 /// let mut map = HashMap::with_hasher(s);
577 /// map.insert(1, 2);
580 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
581 pub fn with_hasher(hash_builder
: S
) -> HashMap
<K
, V
, S
> {
583 hash_builder
: hash_builder
,
584 resize_policy
: DefaultResizePolicy
::new(),
585 table
: RawTable
::new(0),
589 /// Creates an empty HashMap with space for at least `capacity`
590 /// elements, using `hasher` to hash the keys.
592 /// Warning: `hasher` is normally randomly generated, and
593 /// is designed to allow HashMaps to be resistant to attacks that
594 /// cause many collisions and very poor performance. Setting it
595 /// manually using this function can expose a DoS attack vector.
600 /// use std::collections::HashMap;
601 /// use std::collections::hash_map::RandomState;
603 /// let s = RandomState::new();
604 /// let mut map = HashMap::with_capacity_and_hasher(10, s);
605 /// map.insert(1, 2);
608 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
609 pub fn with_capacity_and_hasher(capacity
: usize, hash_builder
: S
)
610 -> HashMap
<K
, V
, S
> {
611 let resize_policy
= DefaultResizePolicy
::new();
612 let min_cap
= max(INITIAL_CAPACITY
, resize_policy
.min_capacity(capacity
));
613 let internal_cap
= min_cap
.checked_next_power_of_two().expect("capacity overflow");
614 assert
!(internal_cap
>= capacity
, "capacity overflow");
616 hash_builder
: hash_builder
,
617 resize_policy
: resize_policy
,
618 table
: RawTable
::new(internal_cap
),
622 /// Returns a reference to the map's hasher.
623 #[stable(feature = "hashmap_public_hasher", since = "1.9.0")]
624 pub fn hasher(&self) -> &S
{
628 /// Returns the number of elements the map can hold without reallocating.
630 /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
631 /// more, but is guaranteed to be able to hold at least this many.
636 /// use std::collections::HashMap;
637 /// let map: HashMap<isize, isize> = HashMap::with_capacity(100);
638 /// assert!(map.capacity() >= 100);
641 #[stable(feature = "rust1", since = "1.0.0")]
642 pub fn capacity(&self) -> usize {
643 self.resize_policy
.usable_capacity(self.table
.capacity())
646 /// Reserves capacity for at least `additional` more elements to be inserted
647 /// in the `HashMap`. The collection may reserve more space to avoid
648 /// frequent reallocations.
652 /// Panics if the new allocation size overflows `usize`.
657 /// use std::collections::HashMap;
658 /// let mut map: HashMap<&str, isize> = HashMap::new();
661 #[stable(feature = "rust1", since = "1.0.0")]
662 pub fn reserve(&mut self, additional
: usize) {
663 let new_size
= self.len().checked_add(additional
).expect("capacity overflow");
664 let min_cap
= self.resize_policy
.min_capacity(new_size
);
666 // An invalid value shouldn't make us run out of space. This includes
667 // an overflow check.
668 assert
!(new_size
<= min_cap
);
670 if self.table
.capacity() < min_cap
{
671 let new_capacity
= max(min_cap
.next_power_of_two(), INITIAL_CAPACITY
);
672 self.resize(new_capacity
);
676 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
677 /// 1) Make sure the new capacity is enough for all the elements, accounting
678 /// for the load factor.
679 /// 2) Ensure new_capacity is a power of two or zero.
680 fn resize(&mut self, new_capacity
: usize) {
681 assert
!(self.table
.size() <= new_capacity
);
682 assert
!(new_capacity
.is_power_of_two() || new_capacity
== 0);
684 let mut old_table
= replace(&mut self.table
, RawTable
::new(new_capacity
));
685 let old_size
= old_table
.size();
687 if old_table
.capacity() == 0 || old_table
.size() == 0 {
692 // Specialization of the other branch.
693 let mut bucket
= Bucket
::first(&mut old_table
);
695 // "So a few of the first shall be last: for many be called,
698 // We'll most likely encounter a few buckets at the beginning that
699 // have their initial buckets near the end of the table. They were
700 // placed at the beginning as the probe wrapped around the table
701 // during insertion. We must skip forward to a bucket that won't
702 // get reinserted too early and won't unfairly steal others spot.
703 // This eliminates the need for robin hood.
705 bucket
= match bucket
.peek() {
707 if full
.displacement() == 0 {
708 // This bucket occupies its ideal spot.
709 // It indicates the start of another "cluster".
710 bucket
= full
.into_bucket();
713 // Leaving this bucket in the last cluster for later.
717 // Encountered a hole between clusters.
724 // This is how the buckets might be laid out in memory:
725 // ($ marks an initialized bucket)
727 // |$$$_$$$$$$_$$$$$|
729 // But we've skipped the entire initial cluster of buckets
730 // and will continue iteration in this order:
733 // ^ wrap around once end is reached
736 // ^ exit once table.size == 0
738 bucket
= match bucket
.peek() {
740 let h
= bucket
.hash();
741 let (b
, k
, v
) = bucket
.take();
742 self.insert_hashed_ordered(h
, k
, v
);
743 if b
.table().size() == 0 {
748 Empty(b
) => b
.into_bucket()
753 assert_eq
!(self.table
.size(), old_size
);
756 /// Shrinks the capacity of the map as much as possible. It will drop
757 /// down as much as possible while maintaining the internal rules
758 /// and possibly leaving some space in accordance with the resize policy.
763 /// use std::collections::HashMap;
765 /// let mut map: HashMap<isize, isize> = HashMap::with_capacity(100);
766 /// map.insert(1, 2);
767 /// map.insert(3, 4);
768 /// assert!(map.capacity() >= 100);
769 /// map.shrink_to_fit();
770 /// assert!(map.capacity() >= 2);
772 #[stable(feature = "rust1", since = "1.0.0")]
773 pub fn shrink_to_fit(&mut self) {
774 let min_capacity
= self.resize_policy
.min_capacity(self.len());
775 let min_capacity
= max(min_capacity
.next_power_of_two(), INITIAL_CAPACITY
);
777 // An invalid value shouldn't make us run out of space.
778 debug_assert
!(self.len() <= min_capacity
);
780 if self.table
.capacity() != min_capacity
{
781 let old_table
= replace(&mut self.table
, RawTable
::new(min_capacity
));
782 let old_size
= old_table
.size();
784 // Shrink the table. Naive algorithm for resizing:
785 for (h
, k
, v
) in old_table
.into_iter() {
786 self.insert_hashed_nocheck(h
, k
, v
);
789 debug_assert_eq
!(self.table
.size(), old_size
);
793 /// Insert a pre-hashed key-value pair, without first checking
794 /// that there's enough room in the buckets. Returns a reference to the
795 /// newly insert value.
797 /// If the key already exists, the hashtable will be returned untouched
798 /// and a reference to the existing element will be returned.
799 fn insert_hashed_nocheck(&mut self, hash
: SafeHash
, k
: K
, v
: V
) -> Option
<V
> {
800 let entry
= search_hashed(&mut self.table
, hash
, |key
| *key
== k
).into_entry(k
);
802 Some(Occupied(mut elem
)) => {
805 Some(Vacant(elem
)) => {
815 /// An iterator visiting all keys in arbitrary order.
816 /// Iterator element type is `&'a K`.
821 /// use std::collections::HashMap;
823 /// let mut map = HashMap::new();
824 /// map.insert("a", 1);
825 /// map.insert("b", 2);
826 /// map.insert("c", 3);
828 /// for key in map.keys() {
829 /// println!("{}", key);
832 #[stable(feature = "rust1", since = "1.0.0")]
833 pub fn keys
<'a
>(&'a
self) -> Keys
<'a
, K
, V
> {
834 Keys { inner: self.iter() }
837 /// An iterator visiting all values in arbitrary order.
838 /// Iterator element type is `&'a V`.
843 /// use std::collections::HashMap;
845 /// let mut map = HashMap::new();
846 /// map.insert("a", 1);
847 /// map.insert("b", 2);
848 /// map.insert("c", 3);
850 /// for val in map.values() {
851 /// println!("{}", val);
854 #[stable(feature = "rust1", since = "1.0.0")]
855 pub fn values
<'a
>(&'a
self) -> Values
<'a
, K
, V
> {
856 Values { inner: self.iter() }
859 /// An iterator visiting all values mutably in arbitrary order.
860 /// Iterator element type is `&'a mut V`.
865 /// # #![feature(map_values_mut)]
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 /// print!("{}", val);
882 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
883 pub fn values_mut
<'a
>(&'a
mut self) -> ValuesMut
<'a
, 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 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
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 #[stable(feature = "rust1", since = "1.0.0")]
1339 pub enum Entry
<'a
, K
: 'a
, V
: 'a
> {
1340 /// An occupied Entry.
1341 #[stable(feature = "rust1", since = "1.0.0")]
1343 #[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>
1347 #[stable(feature = "rust1", since = "1.0.0")]
1349 #[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>
1353 /// A view into a single occupied location in a HashMap.
1354 #[stable(feature = "rust1", since = "1.0.0")]
1355 pub struct OccupiedEntry
<'a
, K
: 'a
, V
: 'a
> {
1357 elem
: FullBucket
<K
, V
, &'a
mut RawTable
<K
, V
>>,
1360 /// A view into a single empty location in a HashMap.
1361 #[stable(feature = "rust1", since = "1.0.0")]
1362 pub struct VacantEntry
<'a
, K
: 'a
, V
: 'a
> {
1365 elem
: VacantEntryState
<K
, V
, &'a
mut RawTable
<K
, V
>>,
1368 /// Possible states of a VacantEntry.
1369 enum VacantEntryState
<K
, V
, M
> {
1370 /// The index is occupied, but the key to insert has precedence,
1371 /// and will kick the current one out on insertion.
1372 NeqElem(FullBucket
<K
, V
, M
>, usize),
1373 /// The index is genuinely vacant.
1374 NoElem(EmptyBucket
<K
, V
, M
>),
1377 #[stable(feature = "rust1", since = "1.0.0")]
1378 impl<'a
, K
, V
, S
> IntoIterator
for &'a HashMap
<K
, V
, S
>
1379 where K
: Eq
+ Hash
, S
: BuildHasher
1381 type Item
= (&'a K
, &'a V
);
1382 type IntoIter
= Iter
<'a
, K
, V
>;
1384 fn into_iter(self) -> Iter
<'a
, K
, V
> {
1389 #[stable(feature = "rust1", since = "1.0.0")]
1390 impl<'a
, K
, V
, S
> IntoIterator
for &'a
mut HashMap
<K
, V
, S
>
1391 where K
: Eq
+ Hash
, S
: BuildHasher
1393 type Item
= (&'a K
, &'a
mut V
);
1394 type IntoIter
= IterMut
<'a
, K
, V
>;
1396 fn into_iter(mut self) -> IterMut
<'a
, K
, V
> {
1401 #[stable(feature = "rust1", since = "1.0.0")]
1402 impl<K
, V
, S
> IntoIterator
for HashMap
<K
, V
, S
>
1403 where K
: Eq
+ Hash
, S
: BuildHasher
1406 type IntoIter
= IntoIter
<K
, V
>;
1408 /// Creates a consuming iterator, that is, one that moves each key-value
1409 /// pair out of the map in arbitrary order. The map cannot be used after
1415 /// use std::collections::HashMap;
1417 /// let mut map = HashMap::new();
1418 /// map.insert("a", 1);
1419 /// map.insert("b", 2);
1420 /// map.insert("c", 3);
1422 /// // Not possible with .iter()
1423 /// let vec: Vec<(&str, isize)> = map.into_iter().collect();
1425 fn into_iter(self) -> IntoIter
<K
, V
> {
1427 inner
: self.table
.into_iter()
1432 #[stable(feature = "rust1", since = "1.0.0")]
1433 impl<'a
, K
, V
> Iterator
for Iter
<'a
, K
, V
> {
1434 type Item
= (&'a K
, &'a V
);
1436 #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1437 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1439 #[stable(feature = "rust1", since = "1.0.0")]
1440 impl<'a
, K
, V
> ExactSizeIterator
for Iter
<'a
, K
, V
> {
1441 #[inline] fn len(&self) -> usize { self.inner.len() }
1444 #[stable(feature = "rust1", since = "1.0.0")]
1445 impl<'a
, K
, V
> Iterator
for IterMut
<'a
, K
, V
> {
1446 type Item
= (&'a K
, &'a
mut V
);
1448 #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1449 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1451 #[stable(feature = "rust1", since = "1.0.0")]
1452 impl<'a
, K
, V
> ExactSizeIterator
for IterMut
<'a
, K
, V
> {
1453 #[inline] fn len(&self) -> usize { self.inner.len() }
1456 #[stable(feature = "rust1", since = "1.0.0")]
1457 impl<K
, V
> Iterator
for IntoIter
<K
, V
> {
1460 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next().map(|(_, k, v)| (k, v)) }
1461 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1463 #[stable(feature = "rust1", since = "1.0.0")]
1464 impl<K
, V
> ExactSizeIterator
for IntoIter
<K
, V
> {
1465 #[inline] fn len(&self) -> usize { self.inner.len() }
1468 #[stable(feature = "rust1", since = "1.0.0")]
1469 impl<'a
, K
, V
> Iterator
for Keys
<'a
, K
, V
> {
1472 #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next().map(|(k, _)| k) }
1473 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1475 #[stable(feature = "rust1", since = "1.0.0")]
1476 impl<'a
, K
, V
> ExactSizeIterator
for Keys
<'a
, K
, V
> {
1477 #[inline] fn len(&self) -> usize { self.inner.len() }
1480 #[stable(feature = "rust1", since = "1.0.0")]
1481 impl<'a
, K
, V
> Iterator
for Values
<'a
, K
, V
> {
1484 #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next().map(|(_, v)| v) }
1485 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1487 #[stable(feature = "rust1", since = "1.0.0")]
1488 impl<'a
, K
, V
> ExactSizeIterator
for Values
<'a
, K
, V
> {
1489 #[inline] fn len(&self) -> usize { self.inner.len() }
1492 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
1493 impl<'a
, K
, V
> Iterator
for ValuesMut
<'a
, K
, V
> {
1494 type Item
= &'a
mut V
;
1496 #[inline] fn next(&mut self) -> Option<(&'a mut V)> { self.inner.next().map(|(_, v)| v) }
1497 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1499 #[unstable(feature = "map_values_mut", reason = "recently added", issue = "32551")]
1500 impl<'a
, K
, V
> ExactSizeIterator
for ValuesMut
<'a
, K
, V
> {
1501 #[inline] fn len(&self) -> usize { self.inner.len() }
1504 #[stable(feature = "rust1", since = "1.0.0")]
1505 impl<'a
, K
, V
> Iterator
for Drain
<'a
, K
, V
> {
1508 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next().map(|(_, k, v)| (k, v)) }
1509 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1511 #[stable(feature = "rust1", since = "1.0.0")]
1512 impl<'a
, K
, V
> ExactSizeIterator
for Drain
<'a
, K
, V
> {
1513 #[inline] fn len(&self) -> usize { self.inner.len() }
1516 impl<'a
, K
, V
> Entry
<'a
, K
, V
> {
1517 #[stable(feature = "rust1", since = "1.0.0")]
1518 /// Ensures a value is in the entry by inserting the default if empty, and returns
1519 /// a mutable reference to the value in the entry.
1520 pub fn or_insert(self, default: V
) -> &'a
mut V
{
1522 Occupied(entry
) => entry
.into_mut(),
1523 Vacant(entry
) => entry
.insert(default),
1527 #[stable(feature = "rust1", since = "1.0.0")]
1528 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1529 /// and returns a mutable reference to the value in the entry.
1530 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
{
1532 Occupied(entry
) => entry
.into_mut(),
1533 Vacant(entry
) => entry
.insert(default()),
1538 impl<'a
, K
, V
> OccupiedEntry
<'a
, K
, V
> {
1539 /// Gets a reference to the key in the entry.
1540 #[unstable(feature = "map_entry_keys", issue = "32281")]
1541 pub fn key(&self) -> &K
{
1545 /// Gets a reference to the value in the entry.
1546 #[stable(feature = "rust1", since = "1.0.0")]
1547 pub fn get(&self) -> &V
{
1551 /// Gets a mutable reference to the value in the entry.
1552 #[stable(feature = "rust1", since = "1.0.0")]
1553 pub fn get_mut(&mut self) -> &mut V
{
1554 self.elem
.read_mut().1
1557 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1558 /// with a lifetime bound to the map itself
1559 #[stable(feature = "rust1", since = "1.0.0")]
1560 pub fn into_mut(self) -> &'a
mut V
{
1561 self.elem
.into_mut_refs().1
1564 /// Sets the value of the entry, and returns the entry's old value
1565 #[stable(feature = "rust1", since = "1.0.0")]
1566 pub fn insert(&mut self, mut value
: V
) -> V
{
1567 let old_value
= self.get_mut();
1568 mem
::swap(&mut value
, old_value
);
1572 /// Takes the value out of the entry, and returns it
1573 #[stable(feature = "rust1", since = "1.0.0")]
1574 pub fn remove(self) -> V
{
1575 pop_internal(self.elem
).1
1577 /// Returns a key that was used for search.
1579 /// The key was retained for further use.
1580 fn take_key(&mut self) -> Option
<K
> {
1585 impl<'a
, K
: 'a
, V
: 'a
> VacantEntry
<'a
, K
, V
> {
1586 /// Gets a reference to the key that would be used when inserting a value
1587 /// through the VacantEntry.
1588 #[unstable(feature = "map_entry_keys", issue = "32281")]
1589 pub fn key(&self) -> &K
{
1593 /// Sets the value of the entry with the VacantEntry's key,
1594 /// and returns a mutable reference to it
1595 #[stable(feature = "rust1", since = "1.0.0")]
1596 pub fn insert(self, value
: V
) -> &'a
mut V
{
1598 NeqElem(bucket
, ib
) => {
1599 robin_hood(bucket
, ib
, self.hash
, self.key
, value
)
1602 bucket
.put(self.hash
, self.key
, value
).into_mut_refs().1
1608 #[stable(feature = "rust1", since = "1.0.0")]
1609 impl<K
, V
, S
> FromIterator
<(K
, V
)> for HashMap
<K
, V
, S
>
1610 where K
: Eq
+ Hash
, S
: BuildHasher
+ Default
1612 fn from_iter
<T
: IntoIterator
<Item
=(K
, V
)>>(iter
: T
) -> HashMap
<K
, V
, S
> {
1613 let iterator
= iter
.into_iter();
1614 let lower
= iterator
.size_hint().0;
1615 let mut map
= HashMap
::with_capacity_and_hasher(lower
, Default
::default());
1616 map
.extend(iterator
);
1621 #[stable(feature = "rust1", since = "1.0.0")]
1622 impl<K
, V
, S
> Extend
<(K
, V
)> for HashMap
<K
, V
, S
>
1623 where K
: Eq
+ Hash
, S
: BuildHasher
1625 fn extend
<T
: IntoIterator
<Item
=(K
, V
)>>(&mut self, iter
: T
) {
1626 for (k
, v
) in iter
{
1632 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
1633 impl<'a
, K
, V
, S
> Extend
<(&'a K
, &'a V
)> for HashMap
<K
, V
, S
>
1634 where K
: Eq
+ Hash
+ Copy
, V
: Copy
, S
: BuildHasher
1636 fn extend
<T
: IntoIterator
<Item
=(&'a K
, &'a V
)>>(&mut self, iter
: T
) {
1637 self.extend(iter
.into_iter().map(|(&key
, &value
)| (key
, value
)));
1641 /// `RandomState` is the default state for `HashMap` types.
1643 /// A particular instance `RandomState` will create the same instances of
1644 /// `Hasher`, but the hashers created by two different `RandomState`
1645 /// instances are unlikely to produce the same result for the same values.
1647 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1648 pub struct RandomState
{
1654 /// Constructs a new `RandomState` that is initialized with random keys.
1656 #[allow(deprecated)] // rand
1657 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1658 pub fn new() -> RandomState
{
1659 let mut r
= rand
::thread_rng();
1660 RandomState { k0: r.gen(), k1: r.gen() }
1664 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1665 impl BuildHasher
for RandomState
{
1666 type Hasher
= SipHasher
;
1668 fn build_hasher(&self) -> SipHasher
{
1669 SipHasher
::new_with_keys(self.k0
, self.k1
)
1673 #[stable(feature = "rust1", since = "1.0.0")]
1674 impl Default
for RandomState
{
1676 fn default() -> RandomState
{
1681 impl<K
, S
, Q
: ?Sized
> super::Recover
<Q
> for HashMap
<K
, (), S
>
1682 where K
: Eq
+ Hash
+ Borrow
<Q
>, S
: BuildHasher
, Q
: Eq
+ Hash
1686 fn get(&self, key
: &Q
) -> Option
<&K
> {
1687 self.search(key
).into_occupied_bucket().map(|bucket
| bucket
.into_refs().0)
1690 fn take(&mut self, key
: &Q
) -> Option
<K
> {
1691 if self.table
.size() == 0 {
1695 self.search_mut(key
).into_occupied_bucket().map(|bucket
| pop_internal(bucket
).0)
1698 fn replace(&mut self, key
: K
) -> Option
<K
> {
1701 match self.entry(key
) {
1702 Occupied(mut occupied
) => {
1703 let key
= occupied
.take_key().unwrap();
1704 Some(mem
::replace(occupied
.elem
.read_mut().0, key
))
1715 fn assert_covariance() {
1716 fn map_key
<'new
>(v
: HashMap
<&'
static str, u8>) -> HashMap
<&'new
str, u8> { v }
1717 fn map_val
<'new
>(v
: HashMap
<u8, &'
static str>) -> HashMap
<u8, &'new
str> { v }
1718 fn iter_key
<'a
, 'new
>(v
: Iter
<'a
, &'
static str, u8>) -> Iter
<'a
, &'new
str, u8> { v }
1719 fn iter_val
<'a
, 'new
>(v
: Iter
<'a
, u8, &'
static str>) -> Iter
<'a
, u8, &'new
str> { v }
1720 fn into_iter_key
<'new
>(v
: IntoIter
<&'
static str, u8>) -> IntoIter
<&'new
str, u8> { v }
1721 fn into_iter_val
<'new
>(v
: IntoIter
<u8, &'
static str>) -> IntoIter
<u8, &'new
str> { v }
1722 fn keys_key
<'a
, 'new
>(v
: Keys
<'a
, &'
static str, u8>) -> Keys
<'a
, &'new
str, u8> { v }
1723 fn keys_val
<'a
, 'new
>(v
: Keys
<'a
, u8, &'
static str>) -> Keys
<'a
, u8, &'new
str> { v }
1724 fn values_key
<'a
, 'new
>(v
: Values
<'a
, &'
static str, u8>) -> Values
<'a
, &'new
str, u8> { v }
1725 fn values_val
<'a
, 'new
>(v
: Values
<'a
, u8, &'
static str>) -> Values
<'a
, u8, &'new
str> { v }
1733 use super::Entry
::{Occupied, Vacant}
;
1735 use rand
::{thread_rng, Rng}
;
1738 fn test_create_capacity_zero() {
1739 let mut m
= HashMap
::with_capacity(0);
1741 assert
!(m
.insert(1, 1).is_none());
1743 assert
!(m
.contains_key(&1));
1744 assert
!(!m
.contains_key(&0));
1749 let mut m
= HashMap
::new();
1750 assert_eq
!(m
.len(), 0);
1751 assert
!(m
.insert(1, 2).is_none());
1752 assert_eq
!(m
.len(), 1);
1753 assert
!(m
.insert(2, 4).is_none());
1754 assert_eq
!(m
.len(), 2);
1755 assert_eq
!(*m
.get(&1).unwrap(), 2);
1756 assert_eq
!(*m
.get(&2).unwrap(), 4);
1761 let mut m
= HashMap
::new();
1762 assert_eq
!(m
.len(), 0);
1763 assert
!(m
.insert(1, 2).is_none());
1764 assert_eq
!(m
.len(), 1);
1765 assert
!(m
.insert(2, 4).is_none());
1766 assert_eq
!(m
.len(), 2);
1768 assert_eq
!(*m2
.get(&1).unwrap(), 2);
1769 assert_eq
!(*m2
.get(&2).unwrap(), 4);
1770 assert_eq
!(m2
.len(), 2);
1773 thread_local
! { static DROP_VECTOR: RefCell<Vec<isize>> = RefCell::new(Vec::new()) }
1775 #[derive(Hash, PartialEq, Eq)]
1781 fn new(k
: usize) -> Dropable
{
1782 DROP_VECTOR
.with(|slot
| {
1783 slot
.borrow_mut()[k
] += 1;
1790 impl Drop
for Dropable
{
1791 fn drop(&mut self) {
1792 DROP_VECTOR
.with(|slot
| {
1793 slot
.borrow_mut()[self.k
] -= 1;
1798 impl Clone
for Dropable
{
1799 fn clone(&self) -> Dropable
{
1800 Dropable
::new(self.k
)
1806 DROP_VECTOR
.with(|slot
| {
1807 *slot
.borrow_mut() = vec
![0; 200];
1811 let mut m
= HashMap
::new();
1813 DROP_VECTOR
.with(|v
| {
1815 assert_eq
!(v
.borrow()[i
], 0);
1820 let d1
= Dropable
::new(i
);
1821 let d2
= Dropable
::new(i
+100);
1825 DROP_VECTOR
.with(|v
| {
1827 assert_eq
!(v
.borrow()[i
], 1);
1832 let k
= Dropable
::new(i
);
1833 let v
= m
.remove(&k
);
1835 assert
!(v
.is_some());
1837 DROP_VECTOR
.with(|v
| {
1838 assert_eq
!(v
.borrow()[i
], 1);
1839 assert_eq
!(v
.borrow()[i
+100], 1);
1843 DROP_VECTOR
.with(|v
| {
1845 assert_eq
!(v
.borrow()[i
], 0);
1846 assert_eq
!(v
.borrow()[i
+100], 0);
1850 assert_eq
!(v
.borrow()[i
], 1);
1851 assert_eq
!(v
.borrow()[i
+100], 1);
1856 DROP_VECTOR
.with(|v
| {
1858 assert_eq
!(v
.borrow()[i
], 0);
1864 fn test_into_iter_drops() {
1865 DROP_VECTOR
.with(|v
| {
1866 *v
.borrow_mut() = vec
![0; 200];
1870 let mut hm
= HashMap
::new();
1872 DROP_VECTOR
.with(|v
| {
1874 assert_eq
!(v
.borrow()[i
], 0);
1879 let d1
= Dropable
::new(i
);
1880 let d2
= Dropable
::new(i
+100);
1884 DROP_VECTOR
.with(|v
| {
1886 assert_eq
!(v
.borrow()[i
], 1);
1893 // By the way, ensure that cloning doesn't screw up the dropping.
1897 let mut half
= hm
.into_iter().take(50);
1899 DROP_VECTOR
.with(|v
| {
1901 assert_eq
!(v
.borrow()[i
], 1);
1905 for _
in half
.by_ref() {}
1907 DROP_VECTOR
.with(|v
| {
1908 let nk
= (0..100).filter(|&i
| {
1912 let nv
= (0..100).filter(|&i
| {
1913 v
.borrow()[i
+100] == 1
1921 DROP_VECTOR
.with(|v
| {
1923 assert_eq
!(v
.borrow()[i
], 0);
1929 fn test_empty_remove() {
1930 let mut m
: HashMap
<isize, bool
> = HashMap
::new();
1931 assert_eq
!(m
.remove(&0), None
);
1935 fn test_empty_entry() {
1936 let mut m
: HashMap
<isize, bool
> = HashMap
::new();
1938 Occupied(_
) => panic
!(),
1941 assert
!(*m
.entry(0).or_insert(true));
1942 assert_eq
!(m
.len(), 1);
1946 fn test_empty_iter() {
1947 let mut m
: HashMap
<isize, bool
> = HashMap
::new();
1948 assert_eq
!(m
.drain().next(), None
);
1949 assert_eq
!(m
.keys().next(), None
);
1950 assert_eq
!(m
.values().next(), None
);
1951 assert_eq
!(m
.values_mut().next(), None
);
1952 assert_eq
!(m
.iter().next(), None
);
1953 assert_eq
!(m
.iter_mut().next(), None
);
1954 assert_eq
!(m
.len(), 0);
1955 assert
!(m
.is_empty());
1956 assert_eq
!(m
.into_iter().next(), None
);
1960 fn test_lots_of_insertions() {
1961 let mut m
= HashMap
::new();
1963 // Try this a few times to make sure we never screw up the hashmap's
1966 assert
!(m
.is_empty());
1969 assert
!(m
.insert(i
, i
).is_none());
1973 assert_eq
!(r
, Some(&j
));
1976 for j
in i
+1..1001 {
1978 assert_eq
!(r
, None
);
1982 for i
in 1001..2001 {
1983 assert
!(!m
.contains_key(&i
));
1988 assert
!(m
.remove(&i
).is_some());
1991 assert
!(!m
.contains_key(&j
));
1994 for j
in i
+1..1001 {
1995 assert
!(m
.contains_key(&j
));
2000 assert
!(!m
.contains_key(&i
));
2004 assert
!(m
.insert(i
, i
).is_none());
2008 for i
in (1..1001).rev() {
2009 assert
!(m
.remove(&i
).is_some());
2012 assert
!(!m
.contains_key(&j
));
2016 assert
!(m
.contains_key(&j
));
2023 fn test_find_mut() {
2024 let mut m
= HashMap
::new();
2025 assert
!(m
.insert(1, 12).is_none());
2026 assert
!(m
.insert(2, 8).is_none());
2027 assert
!(m
.insert(5, 14).is_none());
2029 match m
.get_mut(&5) {
2030 None
=> panic
!(), Some(x
) => *x
= new
2032 assert_eq
!(m
.get(&5), Some(&new
));
2036 fn test_insert_overwrite() {
2037 let mut m
= HashMap
::new();
2038 assert
!(m
.insert(1, 2).is_none());
2039 assert_eq
!(*m
.get(&1).unwrap(), 2);
2040 assert
!(!m
.insert(1, 3).is_none());
2041 assert_eq
!(*m
.get(&1).unwrap(), 3);
2045 fn test_insert_conflicts() {
2046 let mut m
= HashMap
::with_capacity(4);
2047 assert
!(m
.insert(1, 2).is_none());
2048 assert
!(m
.insert(5, 3).is_none());
2049 assert
!(m
.insert(9, 4).is_none());
2050 assert_eq
!(*m
.get(&9).unwrap(), 4);
2051 assert_eq
!(*m
.get(&5).unwrap(), 3);
2052 assert_eq
!(*m
.get(&1).unwrap(), 2);
2056 fn test_conflict_remove() {
2057 let mut m
= HashMap
::with_capacity(4);
2058 assert
!(m
.insert(1, 2).is_none());
2059 assert_eq
!(*m
.get(&1).unwrap(), 2);
2060 assert
!(m
.insert(5, 3).is_none());
2061 assert_eq
!(*m
.get(&1).unwrap(), 2);
2062 assert_eq
!(*m
.get(&5).unwrap(), 3);
2063 assert
!(m
.insert(9, 4).is_none());
2064 assert_eq
!(*m
.get(&1).unwrap(), 2);
2065 assert_eq
!(*m
.get(&5).unwrap(), 3);
2066 assert_eq
!(*m
.get(&9).unwrap(), 4);
2067 assert
!(m
.remove(&1).is_some());
2068 assert_eq
!(*m
.get(&9).unwrap(), 4);
2069 assert_eq
!(*m
.get(&5).unwrap(), 3);
2073 fn test_is_empty() {
2074 let mut m
= HashMap
::with_capacity(4);
2075 assert
!(m
.insert(1, 2).is_none());
2076 assert
!(!m
.is_empty());
2077 assert
!(m
.remove(&1).is_some());
2078 assert
!(m
.is_empty());
2083 let mut m
= HashMap
::new();
2085 assert_eq
!(m
.remove(&1), Some(2));
2086 assert_eq
!(m
.remove(&1), None
);
2091 let mut m
= HashMap
::with_capacity(4);
2093 assert
!(m
.insert(i
, i
*2).is_none());
2095 assert_eq
!(m
.len(), 32);
2097 let mut observed
: u32 = 0;
2100 assert_eq
!(*v
, *k
* 2);
2101 observed
|= 1 << *k
;
2103 assert_eq
!(observed
, 0xFFFF_FFFF);
2108 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
2109 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
2110 let keys
: Vec
<_
> = map
.keys().cloned().collect();
2111 assert_eq
!(keys
.len(), 3);
2112 assert
!(keys
.contains(&1));
2113 assert
!(keys
.contains(&2));
2114 assert
!(keys
.contains(&3));
2119 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
2120 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
2121 let values
: Vec
<_
> = map
.values().cloned().collect();
2122 assert_eq
!(values
.len(), 3);
2123 assert
!(values
.contains(&'a'
));
2124 assert
!(values
.contains(&'b'
));
2125 assert
!(values
.contains(&'c'
));
2129 fn test_values_mut() {
2130 let vec
= vec
![(1, 1), (2, 2), (3, 3)];
2131 let mut map
: HashMap
<_
, _
> = vec
.into_iter().collect();
2132 for value
in map
.values_mut() {
2133 *value
= (*value
) * 2
2135 let values
: Vec
<_
> = map
.values().cloned().collect();
2136 assert_eq
!(values
.len(), 3);
2137 assert
!(values
.contains(&2));
2138 assert
!(values
.contains(&4));
2139 assert
!(values
.contains(&6));
2144 let mut m
= HashMap
::new();
2145 assert
!(m
.get(&1).is_none());
2149 Some(v
) => assert_eq
!(*v
, 2)
2155 let mut m1
= HashMap
::new();
2160 let mut m2
= HashMap
::new();
2173 let mut map
= HashMap
::new();
2174 let empty
: HashMap
<i32, i32> = HashMap
::new();
2179 let map_str
= format
!("{:?}", map
);
2181 assert
!(map_str
== "{1: 2, 3: 4}" ||
2182 map_str
== "{3: 4, 1: 2}");
2183 assert_eq
!(format
!("{:?}", empty
), "{}");
2188 let mut m
= HashMap
::new();
2190 assert_eq
!(m
.len(), 0);
2191 assert
!(m
.is_empty());
2194 let old_cap
= m
.table
.capacity();
2195 while old_cap
== m
.table
.capacity() {
2200 assert_eq
!(m
.len(), i
);
2201 assert
!(!m
.is_empty());
2205 fn test_behavior_resize_policy() {
2206 let mut m
= HashMap
::new();
2208 assert_eq
!(m
.len(), 0);
2209 assert_eq
!(m
.table
.capacity(), 0);
2210 assert
!(m
.is_empty());
2214 assert
!(m
.is_empty());
2215 let initial_cap
= m
.table
.capacity();
2216 m
.reserve(initial_cap
);
2217 let cap
= m
.table
.capacity();
2219 assert_eq
!(cap
, initial_cap
* 2);
2222 for _
in 0..cap
* 3 / 4 {
2226 // three quarters full
2228 assert_eq
!(m
.len(), i
);
2229 assert_eq
!(m
.table
.capacity(), cap
);
2231 for _
in 0..cap
/ 4 {
2237 let new_cap
= m
.table
.capacity();
2238 assert_eq
!(new_cap
, cap
* 2);
2240 for _
in 0..cap
/ 2 - 1 {
2243 assert_eq
!(m
.table
.capacity(), new_cap
);
2245 // A little more than one quarter full.
2247 assert_eq
!(m
.table
.capacity(), cap
);
2248 // again, a little more than half full
2249 for _
in 0..cap
/ 2 - 1 {
2255 assert_eq
!(m
.len(), i
);
2256 assert
!(!m
.is_empty());
2257 assert_eq
!(m
.table
.capacity(), initial_cap
);
2261 fn test_reserve_shrink_to_fit() {
2262 let mut m
= HashMap
::new();
2265 assert
!(m
.capacity() >= m
.len());
2271 let usable_cap
= m
.capacity();
2272 for i
in 128..(128 + 256) {
2274 assert_eq
!(m
.capacity(), usable_cap
);
2277 for i
in 100..(128 + 256) {
2278 assert_eq
!(m
.remove(&i
), Some(i
));
2282 assert_eq
!(m
.len(), 100);
2283 assert
!(!m
.is_empty());
2284 assert
!(m
.capacity() >= m
.len());
2287 assert_eq
!(m
.remove(&i
), Some(i
));
2292 assert_eq
!(m
.len(), 1);
2293 assert
!(m
.capacity() >= m
.len());
2294 assert_eq
!(m
.remove(&0), Some(0));
2298 fn test_from_iter() {
2299 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2301 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2303 for &(k
, v
) in &xs
{
2304 assert_eq
!(map
.get(&k
), Some(&v
));
2309 fn test_size_hint() {
2310 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2312 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2314 let mut iter
= map
.iter();
2316 for _
in iter
.by_ref().take(3) {}
2318 assert_eq
!(iter
.size_hint(), (3, Some(3)));
2322 fn test_iter_len() {
2323 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2325 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2327 let mut iter
= map
.iter();
2329 for _
in iter
.by_ref().take(3) {}
2331 assert_eq
!(iter
.len(), 3);
2335 fn test_mut_size_hint() {
2336 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2338 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2340 let mut iter
= map
.iter_mut();
2342 for _
in iter
.by_ref().take(3) {}
2344 assert_eq
!(iter
.size_hint(), (3, Some(3)));
2348 fn test_iter_mut_len() {
2349 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2351 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2353 let mut iter
= map
.iter_mut();
2355 for _
in iter
.by_ref().take(3) {}
2357 assert_eq
!(iter
.len(), 3);
2362 let mut map
= HashMap
::new();
2368 assert_eq
!(map
[&2], 1);
2373 fn test_index_nonexistent() {
2374 let mut map
= HashMap
::new();
2385 let xs
= [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2387 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2389 // Existing key (insert)
2390 match map
.entry(1) {
2391 Vacant(_
) => unreachable
!(),
2392 Occupied(mut view
) => {
2393 assert_eq
!(view
.get(), &10);
2394 assert_eq
!(view
.insert(100), 10);
2397 assert_eq
!(map
.get(&1).unwrap(), &100);
2398 assert_eq
!(map
.len(), 6);
2401 // Existing key (update)
2402 match map
.entry(2) {
2403 Vacant(_
) => unreachable
!(),
2404 Occupied(mut view
) => {
2405 let v
= view
.get_mut();
2406 let new_v
= (*v
) * 10;
2410 assert_eq
!(map
.get(&2).unwrap(), &200);
2411 assert_eq
!(map
.len(), 6);
2413 // Existing key (take)
2414 match map
.entry(3) {
2415 Vacant(_
) => unreachable
!(),
2417 assert_eq
!(view
.remove(), 30);
2420 assert_eq
!(map
.get(&3), None
);
2421 assert_eq
!(map
.len(), 5);
2424 // Inexistent key (insert)
2425 match map
.entry(10) {
2426 Occupied(_
) => unreachable
!(),
2428 assert_eq
!(*view
.insert(1000), 1000);
2431 assert_eq
!(map
.get(&10).unwrap(), &1000);
2432 assert_eq
!(map
.len(), 6);
2436 fn test_entry_take_doesnt_corrupt() {
2437 #![allow(deprecated)] //rand
2439 fn check(m
: &HashMap
<isize, ()>) {
2441 assert
!(m
.contains_key(k
),
2442 "{} is in keys() but not in the map?", k
);
2446 let mut m
= HashMap
::new();
2447 let mut rng
= thread_rng();
2449 // Populate the map with some items.
2451 let x
= rng
.gen_range(-10, 10);
2456 let x
= rng
.gen_range(-10, 10);
2460 println
!("{}: remove {}", i
, x
);
2470 fn test_extend_ref() {
2471 let mut a
= HashMap
::new();
2473 let mut b
= HashMap
::new();
2475 b
.insert(3, "three");
2479 assert_eq
!(a
.len(), 3);
2480 assert_eq
!(a
[&1], "one");
2481 assert_eq
!(a
[&2], "two");
2482 assert_eq
!(a
[&3], "three");
2486 fn test_capacity_not_less_than_len() {
2487 let mut a
= HashMap
::new();
2495 assert
!(a
.capacity() > a
.len());
2497 let free
= a
.capacity() - a
.len();
2503 assert_eq
!(a
.len(), a
.capacity());
2505 // Insert at capacity should cause allocation.
2507 assert
!(a
.capacity() > a
.len());
2511 fn test_occupied_entry_key() {
2512 let mut a
= HashMap
::new();
2513 let key
= "hello there";
2514 let value
= "value goes here";
2515 assert
!(a
.is_empty());
2516 a
.insert(key
.clone(), value
.clone());
2517 assert_eq
!(a
.len(), 1);
2518 assert_eq
!(a
[key
], value
);
2520 match a
.entry(key
.clone()) {
2521 Vacant(_
) => panic
!(),
2522 Occupied(e
) => assert_eq
!(key
, *e
.key()),
2524 assert_eq
!(a
.len(), 1);
2525 assert_eq
!(a
[key
], value
);
2529 fn test_vacant_entry_key() {
2530 let mut a
= HashMap
::new();
2531 let key
= "hello there";
2532 let value
= "value goes here";
2534 assert
!(a
.is_empty());
2535 match a
.entry(key
.clone()) {
2536 Occupied(_
) => panic
!(),
2538 assert_eq
!(key
, *e
.key());
2539 e
.insert(value
.clone());
2542 assert_eq
!(a
.len(), 1);
2543 assert_eq
!(a
[key
], value
);