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 /// 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). No guarantees are made to the
206 /// quality of the random data. The implementation uses the best available
207 /// random data from your platform at the time of creation. This behavior
208 /// can be overridden with one of the constructors.
210 /// It is required that the keys implement the `Eq` and `Hash` traits, although
211 /// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
212 /// If you implement these yourself, it is important that the following
216 /// k1 == k2 -> hash(k1) == hash(k2)
219 /// In other words, if two keys are equal, their hashes must be equal.
221 /// It is a logic error for a key to be modified in such a way that the key's
222 /// hash, as determined by the `Hash` trait, or its equality, as determined by
223 /// the `Eq` trait, changes while it is in the map. This is normally only
224 /// possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
226 /// Relevant papers/articles:
228 /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)
229 /// 2. Emmanuel Goossaert. ["Robin Hood
230 /// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/)
231 /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift
232 /// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)
237 /// use std::collections::HashMap;
239 /// // type inference lets us omit an explicit type signature (which
240 /// // would be `HashMap<&str, &str>` in this example).
241 /// let mut book_reviews = HashMap::new();
243 /// // review some books.
244 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
245 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
246 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
247 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
249 /// // check for a specific one.
250 /// if !book_reviews.contains_key("Les Misérables") {
251 /// println!("We've got {} reviews, but Les Misérables ain't one.",
252 /// book_reviews.len());
255 /// // oops, this review has a lot of spelling mistakes, let's delete it.
256 /// book_reviews.remove("The Adventures of Sherlock Holmes");
258 /// // look up the values associated with some keys.
259 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
260 /// for book in &to_find {
261 /// match book_reviews.get(book) {
262 /// Some(review) => println!("{}: {}", book, review),
263 /// None => println!("{} is unreviewed.", book)
267 /// // iterate over everything.
268 /// for (book, review) in &book_reviews {
269 /// println!("{}: \"{}\"", book, review);
273 /// `HashMap` also implements an [`Entry API`](#method.entry), which allows
274 /// for more complex methods of getting, setting, updating and removing keys and
278 /// use std::collections::HashMap;
280 /// // type inference lets us omit an explicit type signature (which
281 /// // would be `HashMap<&str, u8>` in this example).
282 /// let mut player_stats = HashMap::new();
284 /// fn random_stat_buff() -> u8 {
285 /// // could actually return some random value here - let's just return
286 /// // some fixed value for now
290 /// // insert a key only if it doesn't already exist
291 /// player_stats.entry("health").or_insert(100);
293 /// // insert a key using a function that provides a new value only if it
294 /// // doesn't already exist
295 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
297 /// // update a key, guarding against the key possibly not being set
298 /// let stat = player_stats.entry("attack").or_insert(100);
299 /// *stat += random_stat_buff();
302 /// The easiest way to use `HashMap` with a custom type as key is to derive `Eq` and `Hash`.
303 /// We must also derive `PartialEq`.
306 /// use std::collections::HashMap;
308 /// #[derive(Hash, Eq, PartialEq, Debug)]
315 /// /// Create a new Viking.
316 /// fn new(name: &str, country: &str) -> Viking {
317 /// Viking { name: name.to_string(), country: country.to_string() }
321 /// // Use a HashMap to store the vikings' health points.
322 /// let mut vikings = HashMap::new();
324 /// vikings.insert(Viking::new("Einar", "Norway"), 25);
325 /// vikings.insert(Viking::new("Olaf", "Denmark"), 24);
326 /// vikings.insert(Viking::new("Harald", "Iceland"), 12);
328 /// // Use derived implementation to print the status of the vikings.
329 /// for (viking, health) in &vikings {
330 /// println!("{:?} has {} hp", viking, health);
334 #[stable(feature = "rust1", since = "1.0.0")]
335 pub struct HashMap<K, V, S = RandomState> {
336 // All hashes are keyed on these values, to prevent hash collision attacks.
339 table: RawTable<K, V>,
341 resize_policy: DefaultResizePolicy,
344 /// Search for a pre-hashed key.
346 fn search_hashed<K, V, M, F>(table: M,
349 -> InternalEntry<K, V, M> where
350 M: Deref<Target=RawTable<K, V>>,
351 F: FnMut(&K) -> bool,
353 // This is the only function where capacity can be zero. To avoid
354 // undefined behavior when Bucket::new gets the raw bucket in this
355 // case, immediately return the appropriate search result.
356 if table.capacity() == 0 {
357 return InternalEntry::TableIsEmpty;
360 let size = table.size() as isize;
361 let mut probe = Bucket::new(table, hash);
362 let ib = probe.index() as isize;
365 let full = match probe.peek() {
368 return InternalEntry::Vacant {
370 elem: NoElem(bucket),
373 Full(bucket) => bucket
376 let robin_ib = full.index() as isize - full.displacement() as isize;
379 // Found a luckier bucket than me.
380 // We can finish the search early if we hit any bucket
381 // with a lower distance to initial bucket than we've probed.
382 return InternalEntry::Vacant {
384 elem: NeqElem(full, robin_ib as usize),
388 // If the hash doesn't match, it can't be this one..
389 if hash == full.hash() {
390 // If the key doesn't match, it can't be this one..
391 if is_match(full.read().0) {
392 return InternalEntry::Occupied {
399 debug_assert!(probe.index() as isize != ib + size + 1);
403 fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) {
404 let (empty, retkey, retval) = starting_bucket.take();
405 let mut gap = match empty.gap_peek() {
407 None => return (retkey, retval)
410 while gap.full().displacement() != 0 {
411 gap = match gap.shift() {
417 // Now we've done all our shifting. Return the value we grabbed earlier.
421 /// Perform robin hood bucket stealing at the given `bucket`. You must
422 /// also pass the position of that bucket's initial bucket so we don't have
423 /// to recalculate it.
425 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
426 fn robin_hood<'a, K: 'a, V: 'a>(bucket: FullBucketMut<'a, K, V>,
432 let starting_index = bucket.index();
433 let size = bucket.table().size();
434 // Save the *starting point*.
435 let mut bucket = bucket.stash();
436 // There can be at most `size - dib` buckets to displace, because
437 // in the worst case, there are `size` elements and we already are
438 // `displacement` buckets away from the initial one.
439 let idx_end = starting_index + size - bucket.displacement();
442 let (old_hash, old_key, old_val) = bucket.replace(hash, key, val);
448 let probe = bucket.next();
449 debug_assert!(probe.index() != idx_end);
451 let full_bucket = match probe.peek() {
454 let bucket = bucket.put(hash, key, val);
455 // Now that it's stolen, just read the value's pointer
456 // right out of the table! Go back to the *starting point*.
458 // This use of `into_table` is misleading. It turns the
459 // bucket, which is a FullBucket on top of a
460 // FullBucketMut, into just one FullBucketMut. The "table"
461 // refers to the inner FullBucketMut in this context.
462 return bucket.into_table().into_mut_refs().1;
464 Full(bucket) => bucket
467 let probe_ib = full_bucket.index() - full_bucket.displacement();
469 bucket = full_bucket;
471 // Robin hood! Steal the spot.
480 impl<K, V, S> HashMap<K, V, S>
481 where K: Eq + Hash, S: BuildHasher
483 fn make_hash<X: ?Sized>(&self, x: &X) -> SafeHash where X: Hash {
484 table::make_hash(&self.hash_builder, x)
487 /// Search for a key, yielding the index if it's found in the hashtable.
488 /// If you already have the hash for the key lying around, use
491 fn search<'a, Q: ?Sized>(&'a self, q: &Q) -> InternalEntry<K, V, &'a RawTable<K, V>>
492 where K: Borrow<Q>, Q: Eq + Hash
494 let hash = self.make_hash(q);
495 search_hashed(&self.table, hash, |k| q.eq(k.borrow()))
499 fn search_mut<'a, Q: ?Sized>(&'a mut self, q: &Q) -> InternalEntry<K, V, &'a mut RawTable<K, V>>
500 where K: Borrow<Q>, Q: Eq + Hash
502 let hash = self.make_hash(q);
503 search_hashed(&mut self.table, hash, |k| q.eq(k.borrow()))
506 // The caller should ensure that invariants by Robin Hood Hashing hold.
507 fn insert_hashed_ordered(&mut self, hash: SafeHash, k: K, v: V) {
508 let cap = self.table.capacity();
509 let mut buckets = Bucket::new(&mut self.table, hash);
510 let ib = buckets.index();
512 while buckets.index() != ib + cap {
513 // We don't need to compare hashes for value swap.
514 // Not even DIBs for Robin Hood.
515 buckets = match buckets.peek() {
517 empty.put(hash, k, v);
520 Full(b) => b.into_bucket()
524 panic!("Internal HashMap error: Out of space.");
528 impl<K: Hash + Eq, V> HashMap<K, V, RandomState> {
529 /// Creates an empty HashMap.
534 /// use std::collections::HashMap;
535 /// let mut map: HashMap<&str, isize> = HashMap::new();
538 #[stable(feature = "rust1", since = "1.0.0")]
539 pub fn new() -> HashMap<K, V, RandomState> {
543 /// Creates an empty hash map with the given initial capacity.
548 /// use std::collections::HashMap;
549 /// let mut map: HashMap<&str, isize> = HashMap::with_capacity(10);
552 #[stable(feature = "rust1", since = "1.0.0")]
553 pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> {
554 HashMap::with_capacity_and_hasher(capacity, Default::default())
558 impl<K, V, S> HashMap<K, V, S>
559 where K: Eq + Hash, S: BuildHasher
561 /// Creates an empty hashmap which will use the given hash builder to hash
564 /// The created map has the default initial capacity.
566 /// Warning: `hash_builder` is normally randomly generated, and
567 /// is designed to allow HashMaps to be resistant to attacks that
568 /// cause many collisions and very poor performance. Setting it
569 /// manually using this function can expose a DoS attack vector.
574 /// use std::collections::HashMap;
575 /// use std::collections::hash_map::RandomState;
577 /// let s = RandomState::new();
578 /// let mut map = HashMap::with_hasher(s);
579 /// map.insert(1, 2);
582 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
583 pub fn with_hasher(hash_builder: S) -> HashMap<K, V, S> {
585 hash_builder: hash_builder,
586 resize_policy: DefaultResizePolicy::new(),
587 table: RawTable::new(0),
591 /// Creates an empty HashMap with space for at least `capacity`
592 /// elements, using `hasher` to hash the keys.
594 /// Warning: `hasher` is normally randomly generated, and
595 /// is designed to allow HashMaps to be resistant to attacks that
596 /// cause many collisions and very poor performance. Setting it
597 /// manually using this function can expose a DoS attack vector.
602 /// use std::collections::HashMap;
603 /// use std::collections::hash_map::RandomState;
605 /// let s = RandomState::new();
606 /// let mut map = HashMap::with_capacity_and_hasher(10, s);
607 /// map.insert(1, 2);
610 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
611 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S)
612 -> HashMap<K, V, S> {
613 let resize_policy = DefaultResizePolicy::new();
614 let min_cap = max(INITIAL_CAPACITY, resize_policy.min_capacity(capacity));
615 let internal_cap = min_cap.checked_next_power_of_two().expect("capacity overflow");
616 assert!(internal_cap >= capacity, "capacity overflow");
618 hash_builder: hash_builder,
619 resize_policy: resize_policy,
620 table: RawTable::new(internal_cap),
624 /// Returns a reference to the map's hasher.
625 #[stable(feature = "hashmap_public_hasher", since = "1.9.0")]
626 pub fn hasher(&self) -> &S {
630 /// Returns the number of elements the map can hold without reallocating.
632 /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
633 /// more, but is guaranteed to be able to hold at least this many.
638 /// use std::collections::HashMap;
639 /// let map: HashMap<isize, isize> = HashMap::with_capacity(100);
640 /// assert!(map.capacity() >= 100);
643 #[stable(feature = "rust1", since = "1.0.0")]
644 pub fn capacity(&self) -> usize {
645 self.resize_policy.usable_capacity(self.table.capacity())
648 /// Reserves capacity for at least `additional` more elements to be inserted
649 /// in the `HashMap`. The collection may reserve more space to avoid
650 /// frequent reallocations.
654 /// Panics if the new allocation size overflows `usize`.
659 /// use std::collections::HashMap;
660 /// let mut map: HashMap<&str, isize> = HashMap::new();
663 #[stable(feature = "rust1", since = "1.0.0")]
664 pub fn reserve(&mut self, additional: usize) {
665 let new_size = self.len().checked_add(additional).expect("capacity overflow");
666 let min_cap = self.resize_policy.min_capacity(new_size);
668 // An invalid value shouldn't make us run out of space. This includes
669 // an overflow check.
670 assert!(new_size <= min_cap);
672 if self.table.capacity() < min_cap {
673 let new_capacity = max(min_cap.next_power_of_two(), INITIAL_CAPACITY);
674 self.resize(new_capacity);
678 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
679 /// 1) Make sure the new capacity is enough for all the elements, accounting
680 /// for the load factor.
681 /// 2) Ensure new_capacity is a power of two or zero.
682 fn resize(&mut self, new_capacity: usize) {
683 assert!(self.table.size() <= new_capacity);
684 assert!(new_capacity.is_power_of_two() || new_capacity == 0);
686 let mut old_table = replace(&mut self.table, RawTable::new(new_capacity));
687 let old_size = old_table.size();
689 if old_table.capacity() == 0 || old_table.size() == 0 {
694 // Specialization of the other branch.
695 let mut bucket = Bucket::first(&mut old_table);
697 // "So a few of the first shall be last: for many be called,
700 // We'll most likely encounter a few buckets at the beginning that
701 // have their initial buckets near the end of the table. They were
702 // placed at the beginning as the probe wrapped around the table
703 // during insertion. We must skip forward to a bucket that won't
704 // get reinserted too early and won't unfairly steal others spot.
705 // This eliminates the need for robin hood.
707 bucket = match bucket.peek() {
709 if full.displacement() == 0 {
710 // This bucket occupies its ideal spot.
711 // It indicates the start of another "cluster".
712 bucket = full.into_bucket();
715 // Leaving this bucket in the last cluster for later.
719 // Encountered a hole between clusters.
726 // This is how the buckets might be laid out in memory:
727 // ($ marks an initialized bucket)
729 // |$$$_$$$$$$_$$$$$|
731 // But we've skipped the entire initial cluster of buckets
732 // and will continue iteration in this order:
735 // ^ wrap around once end is reached
738 // ^ exit once table.size == 0
740 bucket = match bucket.peek() {
742 let h = bucket.hash();
743 let (b, k, v) = bucket.take();
744 self.insert_hashed_ordered(h, k, v);
745 if b.table().size() == 0 {
750 Empty(b) => b.into_bucket()
755 assert_eq!(self.table.size(), old_size);
758 /// Shrinks the capacity of the map as much as possible. It will drop
759 /// down as much as possible while maintaining the internal rules
760 /// and possibly leaving some space in accordance with the resize policy.
765 /// use std::collections::HashMap;
767 /// let mut map: HashMap<isize, isize> = HashMap::with_capacity(100);
768 /// map.insert(1, 2);
769 /// map.insert(3, 4);
770 /// assert!(map.capacity() >= 100);
771 /// map.shrink_to_fit();
772 /// assert!(map.capacity() >= 2);
774 #[stable(feature = "rust1", since = "1.0.0")]
775 pub fn shrink_to_fit(&mut self) {
776 let min_capacity = self.resize_policy.min_capacity(self.len());
777 let min_capacity = max(min_capacity.next_power_of_two(), INITIAL_CAPACITY);
779 // An invalid value shouldn't make us run out of space.
780 debug_assert!(self.len() <= min_capacity);
782 if self.table.capacity() != min_capacity {
783 let old_table = replace(&mut self.table, RawTable::new(min_capacity));
784 let old_size = old_table.size();
786 // Shrink the table. Naive algorithm for resizing:
787 for (h, k, v) in old_table.into_iter() {
788 self.insert_hashed_nocheck(h, k, v);
791 debug_assert_eq!(self.table.size(), old_size);
795 /// Insert a pre-hashed key-value pair, without first checking
796 /// that there's enough room in the buckets. Returns a reference to the
797 /// newly insert value.
799 /// If the key already exists, the hashtable will be returned untouched
800 /// and a reference to the existing element will be returned.
801 fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> Option<V> {
802 let entry = search_hashed(&mut self.table, hash, |key| *key == k).into_entry(k);
804 Some(Occupied(mut elem)) => {
807 Some(Vacant(elem)) => {
817 /// An iterator visiting all keys in arbitrary order.
818 /// Iterator element type is `&'a K`.
823 /// use std::collections::HashMap;
825 /// let mut map = HashMap::new();
826 /// map.insert("a", 1);
827 /// map.insert("b", 2);
828 /// map.insert("c", 3);
830 /// for key in map.keys() {
831 /// println!("{}", key);
834 #[stable(feature = "rust1", since = "1.0.0")]
835 pub fn keys(&self) -> Keys<K, V> {
836 Keys { inner: self.iter() }
839 /// An iterator visiting all values in arbitrary order.
840 /// Iterator element type is `&'a V`.
845 /// use std::collections::HashMap;
847 /// let mut map = HashMap::new();
848 /// map.insert("a", 1);
849 /// map.insert("b", 2);
850 /// map.insert("c", 3);
852 /// for val in map.values() {
853 /// println!("{}", val);
856 #[stable(feature = "rust1", since = "1.0.0")]
857 pub fn values(&self) -> Values<K, V> {
858 Values { inner: self.iter() }
861 /// An iterator visiting all values mutably in arbitrary order.
862 /// Iterator element type is `&'a mut V`.
867 /// use std::collections::HashMap;
869 /// let mut map = HashMap::new();
871 /// map.insert("a", 1);
872 /// map.insert("b", 2);
873 /// map.insert("c", 3);
875 /// for val in map.values_mut() {
876 /// *val = *val + 10;
879 /// for val in map.values() {
880 /// print!("{}", val);
883 #[stable(feature = "map_values_mut", since = "1.10.0")]
884 pub fn values_mut(&mut self) -> ValuesMut<K, V> {
885 ValuesMut { inner: self.iter_mut() }
888 /// An iterator visiting all key-value pairs in arbitrary order.
889 /// Iterator element type is `(&'a K, &'a V)`.
894 /// use std::collections::HashMap;
896 /// let mut map = HashMap::new();
897 /// map.insert("a", 1);
898 /// map.insert("b", 2);
899 /// map.insert("c", 3);
901 /// for (key, val) in map.iter() {
902 /// println!("key: {} val: {}", key, val);
905 #[stable(feature = "rust1", since = "1.0.0")]
906 pub fn iter(&self) -> Iter<K, V> {
907 Iter { inner: self.table.iter() }
910 /// An iterator visiting all key-value pairs in arbitrary order,
911 /// with mutable references to the values.
912 /// Iterator element type is `(&'a K, &'a mut V)`.
917 /// use std::collections::HashMap;
919 /// let mut map = HashMap::new();
920 /// map.insert("a", 1);
921 /// map.insert("b", 2);
922 /// map.insert("c", 3);
924 /// // Update all values
925 /// for (_, val) in map.iter_mut() {
929 /// for (key, val) in &map {
930 /// println!("key: {} val: {}", key, val);
933 #[stable(feature = "rust1", since = "1.0.0")]
934 pub fn iter_mut(&mut self) -> IterMut<K, V> {
935 IterMut { inner: self.table.iter_mut() }
938 /// Gets the given key's corresponding entry in the map for in-place manipulation.
943 /// use std::collections::HashMap;
945 /// let mut letters = HashMap::new();
947 /// for ch in "a short treatise on fungi".chars() {
948 /// let counter = letters.entry(ch).or_insert(0);
952 /// assert_eq!(letters[&'s'], 2);
953 /// assert_eq!(letters[&'t'], 3);
954 /// assert_eq!(letters[&'u'], 1);
955 /// assert_eq!(letters.get(&'y'), None);
957 #[stable(feature = "rust1", since = "1.0.0")]
958 pub fn entry(&mut self, key: K) -> Entry<K, V> {
961 self.search_mut(&key).into_entry(key).expect("unreachable")
964 /// Returns the number of elements in the map.
969 /// use std::collections::HashMap;
971 /// let mut a = HashMap::new();
972 /// assert_eq!(a.len(), 0);
973 /// a.insert(1, "a");
974 /// assert_eq!(a.len(), 1);
976 #[stable(feature = "rust1", since = "1.0.0")]
977 pub fn len(&self) -> usize { self.table.size() }
979 /// Returns true if the map contains no elements.
984 /// use std::collections::HashMap;
986 /// let mut a = HashMap::new();
987 /// assert!(a.is_empty());
988 /// a.insert(1, "a");
989 /// assert!(!a.is_empty());
992 #[stable(feature = "rust1", since = "1.0.0")]
993 pub fn is_empty(&self) -> bool { self.len() == 0 }
995 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
996 /// allocated memory for reuse.
1001 /// use std::collections::HashMap;
1003 /// let mut a = HashMap::new();
1004 /// a.insert(1, "a");
1005 /// a.insert(2, "b");
1007 /// for (k, v) in a.drain().take(1) {
1008 /// assert!(k == 1 || k == 2);
1009 /// assert!(v == "a" || v == "b");
1012 /// assert!(a.is_empty());
1015 #[stable(feature = "drain", since = "1.6.0")]
1016 pub fn drain(&mut self) -> Drain<K, V> {
1018 inner: self.table.drain(),
1022 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
1028 /// use std::collections::HashMap;
1030 /// let mut a = HashMap::new();
1031 /// a.insert(1, "a");
1033 /// assert!(a.is_empty());
1035 #[stable(feature = "rust1", since = "1.0.0")]
1037 pub fn clear(&mut self) {
1041 /// Returns a reference to the value corresponding to the key.
1043 /// The key may be any borrowed form of the map's key type, but
1044 /// `Hash` and `Eq` on the borrowed form *must* match those for
1050 /// use std::collections::HashMap;
1052 /// let mut map = HashMap::new();
1053 /// map.insert(1, "a");
1054 /// assert_eq!(map.get(&1), Some(&"a"));
1055 /// assert_eq!(map.get(&2), None);
1057 #[stable(feature = "rust1", since = "1.0.0")]
1058 pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
1059 where K: Borrow<Q>, Q: Hash + Eq
1061 self.search(k).into_occupied_bucket().map(|bucket| bucket.into_refs().1)
1064 /// Returns true if the map contains a value for the specified key.
1066 /// The key may be any borrowed form of the map's key type, but
1067 /// `Hash` and `Eq` on the borrowed form *must* match those for
1073 /// use std::collections::HashMap;
1075 /// let mut map = HashMap::new();
1076 /// map.insert(1, "a");
1077 /// assert_eq!(map.contains_key(&1), true);
1078 /// assert_eq!(map.contains_key(&2), false);
1080 #[stable(feature = "rust1", since = "1.0.0")]
1081 pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
1082 where K: Borrow<Q>, Q: Hash + Eq
1084 self.search(k).into_occupied_bucket().is_some()
1087 /// Returns a mutable reference to the value corresponding to the key.
1089 /// The key may be any borrowed form of the map's key type, but
1090 /// `Hash` and `Eq` on the borrowed form *must* match those for
1096 /// use std::collections::HashMap;
1098 /// let mut map = HashMap::new();
1099 /// map.insert(1, "a");
1100 /// if let Some(x) = map.get_mut(&1) {
1103 /// assert_eq!(map[&1], "b");
1105 #[stable(feature = "rust1", since = "1.0.0")]
1106 pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
1107 where K: Borrow<Q>, Q: Hash + Eq
1109 self.search_mut(k).into_occupied_bucket().map(|bucket| bucket.into_mut_refs().1)
1112 /// Inserts a key-value pair into the map.
1114 /// If the map did not have this key present, `None` is returned.
1116 /// If the map did have this key present, the value is updated, and the old
1117 /// value is returned. The key is not updated, though; this matters for
1118 /// types that can be `==` without being identical. See the [module-level
1119 /// documentation] for more.
1121 /// [module-level documentation]: index.html#insert-and-complex-keys
1126 /// use std::collections::HashMap;
1128 /// let mut map = HashMap::new();
1129 /// assert_eq!(map.insert(37, "a"), None);
1130 /// assert_eq!(map.is_empty(), false);
1132 /// map.insert(37, "b");
1133 /// assert_eq!(map.insert(37, "c"), Some("b"));
1134 /// assert_eq!(map[&37], "c");
1136 #[stable(feature = "rust1", since = "1.0.0")]
1137 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
1138 let hash = self.make_hash(&k);
1140 self.insert_hashed_nocheck(hash, k, v)
1143 /// Removes a key from the map, returning the value at the key if the key
1144 /// was previously in the map.
1146 /// The key may be any borrowed form of the map's key type, but
1147 /// `Hash` and `Eq` on the borrowed form *must* match those for
1153 /// use std::collections::HashMap;
1155 /// let mut map = HashMap::new();
1156 /// map.insert(1, "a");
1157 /// assert_eq!(map.remove(&1), Some("a"));
1158 /// assert_eq!(map.remove(&1), None);
1160 #[stable(feature = "rust1", since = "1.0.0")]
1161 pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
1162 where K: Borrow<Q>, Q: Hash + Eq
1164 if self.table.size() == 0 {
1168 self.search_mut(k).into_occupied_bucket().map(|bucket| pop_internal(bucket).1)
1172 #[stable(feature = "rust1", since = "1.0.0")]
1173 impl<K, V, S> PartialEq for HashMap<K, V, S>
1174 where K: Eq + Hash, V: PartialEq, S: BuildHasher
1176 fn eq(&self, other: &HashMap<K, V, S>) -> bool {
1177 if self.len() != other.len() { return false; }
1179 self.iter().all(|(key, value)|
1180 other.get(key).map_or(false, |v| *value == *v)
1185 #[stable(feature = "rust1", since = "1.0.0")]
1186 impl<K, V, S> Eq for HashMap<K, V, S>
1187 where K: Eq + Hash, V: Eq, S: BuildHasher
1190 #[stable(feature = "rust1", since = "1.0.0")]
1191 impl<K, V, S> Debug for HashMap<K, V, S>
1192 where K: Eq + Hash + Debug, V: Debug, S: BuildHasher
1194 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1195 f.debug_map().entries(self.iter()).finish()
1199 #[stable(feature = "rust1", since = "1.0.0")]
1200 impl<K, V, S> Default for HashMap<K, V, S>
1202 S: BuildHasher + Default,
1204 fn default() -> HashMap<K, V, S> {
1205 HashMap::with_hasher(Default::default())
1209 #[stable(feature = "rust1", since = "1.0.0")]
1210 impl<'a, K, Q: ?Sized, V, S> Index<&'a Q> for HashMap<K, V, S>
1211 where K: Eq + Hash + Borrow<Q>,
1218 fn index(&self, index: &Q) -> &V {
1219 self.get(index).expect("no entry found for key")
1223 /// HashMap iterator.
1224 #[stable(feature = "rust1", since = "1.0.0")]
1225 pub struct Iter<'a, K: 'a, V: 'a> {
1226 inner: table::Iter<'a, K, V>
1229 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1230 #[stable(feature = "rust1", since = "1.0.0")]
1231 impl<'a, K, V> Clone for Iter<'a, K, V> {
1232 fn clone(&self) -> Iter<'a, K, V> {
1234 inner: self.inner.clone()
1239 /// HashMap mutable values iterator.
1240 #[stable(feature = "rust1", since = "1.0.0")]
1241 pub struct IterMut<'a, K: 'a, V: 'a> {
1242 inner: table::IterMut<'a, K, V>
1245 /// HashMap move iterator.
1246 #[stable(feature = "rust1", since = "1.0.0")]
1247 pub struct IntoIter<K, V> {
1248 inner: table::IntoIter<K, V>
1251 /// HashMap keys iterator.
1252 #[stable(feature = "rust1", since = "1.0.0")]
1253 pub struct Keys<'a, K: 'a, V: 'a> {
1254 inner: Iter<'a, K, V>
1257 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1258 #[stable(feature = "rust1", since = "1.0.0")]
1259 impl<'a, K, V> Clone for Keys<'a, K, V> {
1260 fn clone(&self) -> Keys<'a, K, V> {
1262 inner: self.inner.clone()
1267 /// HashMap values iterator.
1268 #[stable(feature = "rust1", since = "1.0.0")]
1269 pub struct Values<'a, K: 'a, V: 'a> {
1270 inner: Iter<'a, K, V>
1273 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1274 #[stable(feature = "rust1", since = "1.0.0")]
1275 impl<'a, K, V> Clone for Values<'a, K, V> {
1276 fn clone(&self) -> Values<'a, K, V> {
1278 inner: self.inner.clone()
1283 /// HashMap drain iterator.
1284 #[stable(feature = "drain", since = "1.6.0")]
1285 pub struct Drain<'a, K: 'a, V: 'a> {
1286 inner: table::Drain<'a, K, V>
1289 /// Mutable HashMap values iterator.
1290 #[stable(feature = "map_values_mut", since = "1.10.0")]
1291 pub struct ValuesMut<'a, K: 'a, V: 'a> {
1292 inner: IterMut<'a, K, V>
1295 enum InternalEntry<K, V, M> {
1297 elem: FullBucket<K, V, M>,
1301 elem: VacantEntryState<K, V, M>,
1306 impl<K, V, M> InternalEntry<K, V, M> {
1308 fn into_occupied_bucket(self) -> Option<FullBucket<K, V, M>> {
1310 InternalEntry::Occupied { elem } => Some(elem),
1316 impl<'a, K, V> InternalEntry<K, V, &'a mut RawTable<K, V>> {
1318 fn into_entry(self, key: K) -> Option<Entry<'a, K, V>> {
1320 InternalEntry::Occupied { elem } => {
1321 Some(Occupied(OccupiedEntry {
1326 InternalEntry::Vacant { hash, elem } => {
1327 Some(Vacant(VacantEntry {
1333 InternalEntry::TableIsEmpty => None
1338 /// A view into a single location in a map, which may be vacant or occupied.
1339 /// This enum is constructed from the [`entry`] method on [`HashMap`].
1341 /// [`HashMap`]: struct.HashMap.html
1342 /// [`entry`]: struct.HashMap.html#method.entry
1343 #[stable(feature = "rust1", since = "1.0.0")]
1344 pub enum Entry<'a, K: 'a, V: 'a> {
1345 /// An occupied Entry.
1346 #[stable(feature = "rust1", since = "1.0.0")]
1348 #[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>
1352 #[stable(feature = "rust1", since = "1.0.0")]
1354 #[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>
1358 /// A view into a single occupied location in a HashMap.
1359 /// It is part of the [`Entry`] enum.
1361 /// [`Entry`]: enum.Entry.html
1362 #[stable(feature = "rust1", since = "1.0.0")]
1363 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
1365 elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
1368 /// A view into a single empty location in a HashMap.
1369 /// It is part of the [`Entry`] enum.
1371 /// [`Entry`]: enum.Entry.html
1372 #[stable(feature = "rust1", since = "1.0.0")]
1373 pub struct VacantEntry<'a, K: 'a, V: 'a> {
1376 elem: VacantEntryState<K, V, &'a mut RawTable<K, V>>,
1379 /// Possible states of a VacantEntry.
1380 enum VacantEntryState<K, V, M> {
1381 /// The index is occupied, but the key to insert has precedence,
1382 /// and will kick the current one out on insertion.
1383 NeqElem(FullBucket<K, V, M>, usize),
1384 /// The index is genuinely vacant.
1385 NoElem(EmptyBucket<K, V, M>),
1388 #[stable(feature = "rust1", since = "1.0.0")]
1389 impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S>
1390 where K: Eq + Hash, S: BuildHasher
1392 type Item = (&'a K, &'a V);
1393 type IntoIter = Iter<'a, K, V>;
1395 fn into_iter(self) -> Iter<'a, K, V> {
1400 #[stable(feature = "rust1", since = "1.0.0")]
1401 impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S>
1402 where K: Eq + Hash, S: BuildHasher
1404 type Item = (&'a K, &'a mut V);
1405 type IntoIter = IterMut<'a, K, V>;
1407 fn into_iter(mut self) -> IterMut<'a, K, V> {
1412 #[stable(feature = "rust1", since = "1.0.0")]
1413 impl<K, V, S> IntoIterator for HashMap<K, V, S>
1414 where K: Eq + Hash, S: BuildHasher
1417 type IntoIter = IntoIter<K, V>;
1419 /// Creates a consuming iterator, that is, one that moves each key-value
1420 /// pair out of the map in arbitrary order. The map cannot be used after
1426 /// use std::collections::HashMap;
1428 /// let mut map = HashMap::new();
1429 /// map.insert("a", 1);
1430 /// map.insert("b", 2);
1431 /// map.insert("c", 3);
1433 /// // Not possible with .iter()
1434 /// let vec: Vec<(&str, isize)> = map.into_iter().collect();
1436 fn into_iter(self) -> IntoIter<K, V> {
1438 inner: self.table.into_iter()
1443 #[stable(feature = "rust1", since = "1.0.0")]
1444 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1445 type Item = (&'a K, &'a V);
1447 #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1448 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1450 #[stable(feature = "rust1", since = "1.0.0")]
1451 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
1452 #[inline] fn len(&self) -> usize { self.inner.len() }
1455 #[stable(feature = "rust1", since = "1.0.0")]
1456 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1457 type Item = (&'a K, &'a mut V);
1459 #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1460 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1462 #[stable(feature = "rust1", since = "1.0.0")]
1463 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
1464 #[inline] fn len(&self) -> usize { self.inner.len() }
1467 #[stable(feature = "rust1", since = "1.0.0")]
1468 impl<K, V> Iterator for IntoIter<K, V> {
1471 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next().map(|(_, k, v)| (k, v)) }
1472 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1474 #[stable(feature = "rust1", since = "1.0.0")]
1475 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
1476 #[inline] fn len(&self) -> usize { self.inner.len() }
1479 #[stable(feature = "rust1", since = "1.0.0")]
1480 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1483 #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next().map(|(k, _)| k) }
1484 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1486 #[stable(feature = "rust1", since = "1.0.0")]
1487 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
1488 #[inline] fn len(&self) -> usize { self.inner.len() }
1491 #[stable(feature = "rust1", since = "1.0.0")]
1492 impl<'a, K, V> Iterator for Values<'a, K, V> {
1495 #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next().map(|(_, v)| v) }
1496 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1498 #[stable(feature = "rust1", since = "1.0.0")]
1499 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
1500 #[inline] fn len(&self) -> usize { self.inner.len() }
1503 #[stable(feature = "map_values_mut", since = "1.10.0")]
1504 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
1505 type Item = &'a mut V;
1507 #[inline] fn next(&mut self) -> Option<(&'a mut V)> { self.inner.next().map(|(_, v)| v) }
1508 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1510 #[stable(feature = "map_values_mut", since = "1.10.0")]
1511 impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
1512 #[inline] fn len(&self) -> usize { self.inner.len() }
1515 #[stable(feature = "rust1", since = "1.0.0")]
1516 impl<'a, K, V> Iterator for Drain<'a, K, V> {
1519 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next().map(|(_, k, v)| (k, v)) }
1520 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1522 #[stable(feature = "rust1", since = "1.0.0")]
1523 impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> {
1524 #[inline] fn len(&self) -> usize { self.inner.len() }
1527 impl<'a, K, V> Entry<'a, K, V> {
1528 #[stable(feature = "rust1", since = "1.0.0")]
1529 /// Ensures a value is in the entry by inserting the default if empty, and returns
1530 /// a mutable reference to the value in the entry.
1535 /// use std::collections::HashMap;
1537 /// let mut map: HashMap<&str, u32> = HashMap::new();
1538 /// map.entry("poneyland").or_insert(12);
1540 /// assert_eq!(map["poneyland"], 12);
1542 /// *map.entry("poneyland").or_insert(12) += 10;
1543 /// assert_eq!(map["poneyland"], 22);
1545 pub fn or_insert(self, default: V) -> &'a mut V {
1547 Occupied(entry) => entry.into_mut(),
1548 Vacant(entry) => entry.insert(default),
1552 #[stable(feature = "rust1", since = "1.0.0")]
1553 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1554 /// and returns a mutable reference to the value in the entry.
1559 /// use std::collections::HashMap;
1561 /// let mut map: HashMap<&str, String> = HashMap::new();
1562 /// let s = "hoho".to_owned();
1564 /// map.entry("poneyland").or_insert_with(|| s);
1566 /// assert_eq!(map["poneyland"], "hoho".to_owned());
1568 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1570 Occupied(entry) => entry.into_mut(),
1571 Vacant(entry) => entry.insert(default()),
1575 /// Returns a reference to this entry's key.
1580 /// use std::collections::HashMap;
1582 /// let mut map: HashMap<&str, u32> = HashMap::new();
1583 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
1585 #[stable(feature = "map_entry_keys", since = "1.10.0")]
1586 pub fn key(&self) -> &K {
1588 Occupied(ref entry) => entry.key(),
1589 Vacant(ref entry) => entry.key(),
1594 impl<'a, K, V> OccupiedEntry<'a, K, V> {
1595 /// Gets a reference to the key in the entry.
1600 /// use std::collections::HashMap;
1602 /// let mut map: HashMap<&str, u32> = HashMap::new();
1603 /// map.entry("poneyland").or_insert(12);
1604 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
1606 #[stable(feature = "map_entry_keys", since = "1.10.0")]
1607 pub fn key(&self) -> &K {
1611 /// Take the ownership of the key and value from the map.
1616 /// #![feature(map_entry_recover_keys)]
1618 /// use std::collections::HashMap;
1619 /// use std::collections::hash_map::Entry;
1621 /// let mut map: HashMap<&str, u32> = HashMap::new();
1622 /// map.entry("poneyland").or_insert(12);
1624 /// if let Entry::Occupied(o) = map.entry("poneyland") {
1625 /// // We delete the entry from the map.
1626 /// o.remove_pair();
1629 /// assert_eq!(map.contains_key("poneyland"), false);
1631 #[unstable(feature = "map_entry_recover_keys", issue = "34285")]
1632 pub fn remove_pair(self) -> (K, V) {
1633 pop_internal(self.elem)
1636 /// Gets a reference to the value in the entry.
1641 /// use std::collections::HashMap;
1642 /// use std::collections::hash_map::Entry;
1644 /// let mut map: HashMap<&str, u32> = HashMap::new();
1645 /// map.entry("poneyland").or_insert(12);
1647 /// if let Entry::Occupied(o) = map.entry("poneyland") {
1648 /// assert_eq!(o.get(), &12);
1651 #[stable(feature = "rust1", since = "1.0.0")]
1652 pub fn get(&self) -> &V {
1656 /// Gets a mutable reference to the value in the entry.
1661 /// use std::collections::HashMap;
1662 /// use std::collections::hash_map::Entry;
1664 /// let mut map: HashMap<&str, u32> = HashMap::new();
1665 /// map.entry("poneyland").or_insert(12);
1667 /// assert_eq!(map["poneyland"], 12);
1668 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
1669 /// *o.get_mut() += 10;
1672 /// assert_eq!(map["poneyland"], 22);
1674 #[stable(feature = "rust1", since = "1.0.0")]
1675 pub fn get_mut(&mut self) -> &mut V {
1676 self.elem.read_mut().1
1679 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1680 /// with a lifetime bound to the map itself.
1685 /// use std::collections::HashMap;
1686 /// use std::collections::hash_map::Entry;
1688 /// let mut map: HashMap<&str, u32> = HashMap::new();
1689 /// map.entry("poneyland").or_insert(12);
1691 /// assert_eq!(map["poneyland"], 12);
1692 /// if let Entry::Occupied(o) = map.entry("poneyland") {
1693 /// *o.into_mut() += 10;
1696 /// assert_eq!(map["poneyland"], 22);
1698 #[stable(feature = "rust1", since = "1.0.0")]
1699 pub fn into_mut(self) -> &'a mut V {
1700 self.elem.into_mut_refs().1
1703 /// Sets the value of the entry, and returns the entry's old value.
1708 /// use std::collections::HashMap;
1709 /// use std::collections::hash_map::Entry;
1711 /// let mut map: HashMap<&str, u32> = HashMap::new();
1712 /// map.entry("poneyland").or_insert(12);
1714 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
1715 /// assert_eq!(o.insert(15), 12);
1718 /// assert_eq!(map["poneyland"], 15);
1720 #[stable(feature = "rust1", since = "1.0.0")]
1721 pub fn insert(&mut self, mut value: V) -> V {
1722 let old_value = self.get_mut();
1723 mem::swap(&mut value, old_value);
1727 /// Takes the value out of the entry, and returns it.
1732 /// use std::collections::HashMap;
1733 /// use std::collections::hash_map::Entry;
1735 /// let mut map: HashMap<&str, u32> = HashMap::new();
1736 /// map.entry("poneyland").or_insert(12);
1738 /// if let Entry::Occupied(o) = map.entry("poneyland") {
1739 /// assert_eq!(o.remove(), 12);
1742 /// assert_eq!(map.contains_key("poneyland"), false);
1744 #[stable(feature = "rust1", since = "1.0.0")]
1745 pub fn remove(self) -> V {
1746 pop_internal(self.elem).1
1749 /// Returns a key that was used for search.
1751 /// The key was retained for further use.
1752 fn take_key(&mut self) -> Option<K> {
1757 impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
1758 /// Gets a reference to the key that would be used when inserting a value
1759 /// through the `VacantEntry`.
1764 /// use std::collections::HashMap;
1766 /// let mut map: HashMap<&str, u32> = HashMap::new();
1767 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
1769 #[stable(feature = "map_entry_keys", since = "1.10.0")]
1770 pub fn key(&self) -> &K {
1774 /// Take ownership of the key.
1779 /// #![feature(map_entry_recover_keys)]
1781 /// use std::collections::HashMap;
1782 /// use std::collections::hash_map::Entry;
1784 /// let mut map: HashMap<&str, u32> = HashMap::new();
1786 /// if let Entry::Vacant(v) = map.entry("poneyland") {
1790 #[unstable(feature = "map_entry_recover_keys", issue = "34285")]
1791 pub fn into_key(self) -> K {
1795 /// Sets the value of the entry with the VacantEntry's key,
1796 /// and returns a mutable reference to it.
1801 /// use std::collections::HashMap;
1802 /// use std::collections::hash_map::Entry;
1804 /// let mut map: HashMap<&str, u32> = HashMap::new();
1806 /// if let Entry::Vacant(o) = map.entry("poneyland") {
1809 /// assert_eq!(map["poneyland"], 37);
1811 #[stable(feature = "rust1", since = "1.0.0")]
1812 pub fn insert(self, value: V) -> &'a mut V {
1814 NeqElem(bucket, ib) => {
1815 robin_hood(bucket, ib, self.hash, self.key, value)
1818 bucket.put(self.hash, self.key, value).into_mut_refs().1
1824 #[stable(feature = "rust1", since = "1.0.0")]
1825 impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
1826 where K: Eq + Hash, S: BuildHasher + Default
1828 fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> HashMap<K, V, S> {
1829 let iterator = iter.into_iter();
1830 let lower = iterator.size_hint().0;
1831 let mut map = HashMap::with_capacity_and_hasher(lower, Default::default());
1832 map.extend(iterator);
1837 #[stable(feature = "rust1", since = "1.0.0")]
1838 impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S>
1839 where K: Eq + Hash, S: BuildHasher
1841 fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
1842 for (k, v) in iter {
1848 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
1849 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S>
1850 where K: Eq + Hash + Copy, V: Copy, S: BuildHasher
1852 fn extend<T: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: T) {
1853 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1857 /// `RandomState` is the default state for `HashMap` types.
1859 /// A particular instance `RandomState` will create the same instances of
1860 /// `Hasher`, but the hashers created by two different `RandomState`
1861 /// instances are unlikely to produce the same result for the same values.
1863 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1864 pub struct RandomState {
1870 /// Constructs a new `RandomState` that is initialized with random keys.
1872 #[allow(deprecated)] // rand
1873 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1874 pub fn new() -> RandomState {
1875 // Historically this function did not cache keys from the OS and instead
1876 // simply always called `rand::thread_rng().gen()` twice. In #31356 it
1877 // was discovered, however, that because we re-seed the thread-local RNG
1878 // from the OS periodically that this can cause excessive slowdown when
1879 // many hash maps are created on a thread. To solve this performance
1880 // trap we cache the first set of randomly generated keys per-thread.
1882 // In doing this, however, we lose the property that all hash maps have
1883 // nondeterministic iteration order as all of those created on the same
1884 // thread would have the same hash keys. This property has been nice in
1885 // the past as it allows for maximal flexibility in the implementation
1886 // of `HashMap` itself.
1888 // The constraint here (if there even is one) is just that maps created
1889 // on the same thread have the same iteration order, and that *may* be
1890 // relied upon even though it is not a documented guarantee at all of
1891 // the `HashMap` type. In any case we've decided that this is reasonable
1892 // for now, so caching keys thread-locally seems fine.
1893 thread_local!(static KEYS: (u64, u64) = {
1894 let r = rand::OsRng::new();
1895 let mut r = r.expect("failed to create an OS RNG");
1899 KEYS.with(|&(k0, k1)| {
1900 RandomState { k0: k0, k1: k1 }
1905 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1906 impl BuildHasher for RandomState {
1907 type Hasher = DefaultHasher;
1909 fn build_hasher(&self) -> DefaultHasher {
1910 DefaultHasher(SipHasher13::new_with_keys(self.k0, self.k1))
1914 /// The default `Hasher` used by `RandomState`.
1916 /// The internal algorithm is not specified, and so it and its hashes should
1917 /// not be relied upon over releases.
1918 #[unstable(feature = "hashmap_default_hasher", issue = "0")]
1919 pub struct DefaultHasher(SipHasher13);
1921 #[unstable(feature = "hashmap_default_hasher", issue = "0")]
1922 impl Hasher for DefaultHasher {
1924 fn write(&mut self, msg: &[u8]) {
1929 fn finish(&self) -> u64 {
1934 #[stable(feature = "rust1", since = "1.0.0")]
1935 impl Default for RandomState {
1937 fn default() -> RandomState {
1942 impl<K, S, Q: ?Sized> super::Recover<Q> for HashMap<K, (), S>
1943 where K: Eq + Hash + Borrow<Q>, S: BuildHasher, Q: Eq + Hash
1947 fn get(&self, key: &Q) -> Option<&K> {
1948 self.search(key).into_occupied_bucket().map(|bucket| bucket.into_refs().0)
1951 fn take(&mut self, key: &Q) -> Option<K> {
1952 if self.table.size() == 0 {
1956 self.search_mut(key).into_occupied_bucket().map(|bucket| pop_internal(bucket).0)
1959 fn replace(&mut self, key: K) -> Option<K> {
1962 match self.entry(key) {
1963 Occupied(mut occupied) => {
1964 let key = occupied.take_key().unwrap();
1965 Some(mem::replace(occupied.elem.read_mut().0, key))
1976 fn assert_covariance() {
1977 fn map_key<'new>(v: HashMap<&'static str, u8>) -> HashMap<&'new str, u8> { v }
1978 fn map_val<'new>(v: HashMap<u8, &'static str>) -> HashMap<u8, &'new str> { v }
1979 fn iter_key<'a, 'new>(v: Iter<'a, &'static str, u8>) -> Iter<'a, &'new str, u8> { v }
1980 fn iter_val<'a, 'new>(v: Iter<'a, u8, &'static str>) -> Iter<'a, u8, &'new str> { v }
1981 fn into_iter_key<'new>(v: IntoIter<&'static str, u8>) -> IntoIter<&'new str, u8> { v }
1982 fn into_iter_val<'new>(v: IntoIter<u8, &'static str>) -> IntoIter<u8, &'new str> { v }
1983 fn keys_key<'a, 'new>(v: Keys<'a, &'static str, u8>) -> Keys<'a, &'new str, u8> { v }
1984 fn keys_val<'a, 'new>(v: Keys<'a, u8, &'static str>) -> Keys<'a, u8, &'new str> { v }
1985 fn values_key<'a, 'new>(v: Values<'a, &'static str, u8>) -> Values<'a, &'new str, u8> { v }
1986 fn values_val<'a, 'new>(v: Values<'a, u8, &'static str>) -> Values<'a, u8, &'new str> { v }
1994 use super::Entry::{Occupied, Vacant};
1996 use rand::{thread_rng, Rng};
1999 fn test_create_capacity_zero() {
2000 let mut m = HashMap::with_capacity(0);
2002 assert!(m.insert(1, 1).is_none());
2004 assert!(m.contains_key(&1));
2005 assert!(!m.contains_key(&0));
2010 let mut m = HashMap::new();
2011 assert_eq!(m.len(), 0);
2012 assert!(m.insert(1, 2).is_none());
2013 assert_eq!(m.len(), 1);
2014 assert!(m.insert(2, 4).is_none());
2015 assert_eq!(m.len(), 2);
2016 assert_eq!(*m.get(&1).unwrap(), 2);
2017 assert_eq!(*m.get(&2).unwrap(), 4);
2022 let mut m = HashMap::new();
2023 assert_eq!(m.len(), 0);
2024 assert!(m.insert(1, 2).is_none());
2025 assert_eq!(m.len(), 1);
2026 assert!(m.insert(2, 4).is_none());
2027 assert_eq!(m.len(), 2);
2029 assert_eq!(*m2.get(&1).unwrap(), 2);
2030 assert_eq!(*m2.get(&2).unwrap(), 4);
2031 assert_eq!(m2.len(), 2);
2034 thread_local! { static DROP_VECTOR: RefCell<Vec<isize>> = RefCell::new(Vec::new()) }
2036 #[derive(Hash, PartialEq, Eq)]
2042 fn new(k: usize) -> Dropable {
2043 DROP_VECTOR.with(|slot| {
2044 slot.borrow_mut()[k] += 1;
2051 impl Drop for Dropable {
2052 fn drop(&mut self) {
2053 DROP_VECTOR.with(|slot| {
2054 slot.borrow_mut()[self.k] -= 1;
2059 impl Clone for Dropable {
2060 fn clone(&self) -> Dropable {
2061 Dropable::new(self.k)
2067 DROP_VECTOR.with(|slot| {
2068 *slot.borrow_mut() = vec![0; 200];
2072 let mut m = HashMap::new();
2074 DROP_VECTOR.with(|v| {
2076 assert_eq!(v.borrow()[i], 0);
2081 let d1 = Dropable::new(i);
2082 let d2 = Dropable::new(i+100);
2086 DROP_VECTOR.with(|v| {
2088 assert_eq!(v.borrow()[i], 1);
2093 let k = Dropable::new(i);
2094 let v = m.remove(&k);
2096 assert!(v.is_some());
2098 DROP_VECTOR.with(|v| {
2099 assert_eq!(v.borrow()[i], 1);
2100 assert_eq!(v.borrow()[i+100], 1);
2104 DROP_VECTOR.with(|v| {
2106 assert_eq!(v.borrow()[i], 0);
2107 assert_eq!(v.borrow()[i+100], 0);
2111 assert_eq!(v.borrow()[i], 1);
2112 assert_eq!(v.borrow()[i+100], 1);
2117 DROP_VECTOR.with(|v| {
2119 assert_eq!(v.borrow()[i], 0);
2125 fn test_into_iter_drops() {
2126 DROP_VECTOR.with(|v| {
2127 *v.borrow_mut() = vec![0; 200];
2131 let mut hm = HashMap::new();
2133 DROP_VECTOR.with(|v| {
2135 assert_eq!(v.borrow()[i], 0);
2140 let d1 = Dropable::new(i);
2141 let d2 = Dropable::new(i+100);
2145 DROP_VECTOR.with(|v| {
2147 assert_eq!(v.borrow()[i], 1);
2154 // By the way, ensure that cloning doesn't screw up the dropping.
2158 let mut half = hm.into_iter().take(50);
2160 DROP_VECTOR.with(|v| {
2162 assert_eq!(v.borrow()[i], 1);
2166 for _ in half.by_ref() {}
2168 DROP_VECTOR.with(|v| {
2169 let nk = (0..100).filter(|&i| {
2173 let nv = (0..100).filter(|&i| {
2174 v.borrow()[i+100] == 1
2182 DROP_VECTOR.with(|v| {
2184 assert_eq!(v.borrow()[i], 0);
2190 fn test_empty_remove() {
2191 let mut m: HashMap<isize, bool> = HashMap::new();
2192 assert_eq!(m.remove(&0), None);
2196 fn test_empty_entry() {
2197 let mut m: HashMap<isize, bool> = HashMap::new();
2199 Occupied(_) => panic!(),
2202 assert!(*m.entry(0).or_insert(true));
2203 assert_eq!(m.len(), 1);
2207 fn test_empty_iter() {
2208 let mut m: HashMap<isize, bool> = HashMap::new();
2209 assert_eq!(m.drain().next(), None);
2210 assert_eq!(m.keys().next(), None);
2211 assert_eq!(m.values().next(), None);
2212 assert_eq!(m.values_mut().next(), None);
2213 assert_eq!(m.iter().next(), None);
2214 assert_eq!(m.iter_mut().next(), None);
2215 assert_eq!(m.len(), 0);
2216 assert!(m.is_empty());
2217 assert_eq!(m.into_iter().next(), None);
2221 fn test_lots_of_insertions() {
2222 let mut m = HashMap::new();
2224 // Try this a few times to make sure we never screw up the hashmap's
2227 assert!(m.is_empty());
2230 assert!(m.insert(i, i).is_none());
2234 assert_eq!(r, Some(&j));
2237 for j in i+1..1001 {
2239 assert_eq!(r, None);
2243 for i in 1001..2001 {
2244 assert!(!m.contains_key(&i));
2249 assert!(m.remove(&i).is_some());
2252 assert!(!m.contains_key(&j));
2255 for j in i+1..1001 {
2256 assert!(m.contains_key(&j));
2261 assert!(!m.contains_key(&i));
2265 assert!(m.insert(i, i).is_none());
2269 for i in (1..1001).rev() {
2270 assert!(m.remove(&i).is_some());
2273 assert!(!m.contains_key(&j));
2277 assert!(m.contains_key(&j));
2284 fn test_find_mut() {
2285 let mut m = HashMap::new();
2286 assert!(m.insert(1, 12).is_none());
2287 assert!(m.insert(2, 8).is_none());
2288 assert!(m.insert(5, 14).is_none());
2290 match m.get_mut(&5) {
2291 None => panic!(), Some(x) => *x = new
2293 assert_eq!(m.get(&5), Some(&new));
2297 fn test_insert_overwrite() {
2298 let mut m = HashMap::new();
2299 assert!(m.insert(1, 2).is_none());
2300 assert_eq!(*m.get(&1).unwrap(), 2);
2301 assert!(!m.insert(1, 3).is_none());
2302 assert_eq!(*m.get(&1).unwrap(), 3);
2306 fn test_insert_conflicts() {
2307 let mut m = HashMap::with_capacity(4);
2308 assert!(m.insert(1, 2).is_none());
2309 assert!(m.insert(5, 3).is_none());
2310 assert!(m.insert(9, 4).is_none());
2311 assert_eq!(*m.get(&9).unwrap(), 4);
2312 assert_eq!(*m.get(&5).unwrap(), 3);
2313 assert_eq!(*m.get(&1).unwrap(), 2);
2317 fn test_conflict_remove() {
2318 let mut m = HashMap::with_capacity(4);
2319 assert!(m.insert(1, 2).is_none());
2320 assert_eq!(*m.get(&1).unwrap(), 2);
2321 assert!(m.insert(5, 3).is_none());
2322 assert_eq!(*m.get(&1).unwrap(), 2);
2323 assert_eq!(*m.get(&5).unwrap(), 3);
2324 assert!(m.insert(9, 4).is_none());
2325 assert_eq!(*m.get(&1).unwrap(), 2);
2326 assert_eq!(*m.get(&5).unwrap(), 3);
2327 assert_eq!(*m.get(&9).unwrap(), 4);
2328 assert!(m.remove(&1).is_some());
2329 assert_eq!(*m.get(&9).unwrap(), 4);
2330 assert_eq!(*m.get(&5).unwrap(), 3);
2334 fn test_is_empty() {
2335 let mut m = HashMap::with_capacity(4);
2336 assert!(m.insert(1, 2).is_none());
2337 assert!(!m.is_empty());
2338 assert!(m.remove(&1).is_some());
2339 assert!(m.is_empty());
2344 let mut m = HashMap::new();
2346 assert_eq!(m.remove(&1), Some(2));
2347 assert_eq!(m.remove(&1), None);
2352 let mut m = HashMap::with_capacity(4);
2354 assert!(m.insert(i, i*2).is_none());
2356 assert_eq!(m.len(), 32);
2358 let mut observed: u32 = 0;
2361 assert_eq!(*v, *k * 2);
2362 observed |= 1 << *k;
2364 assert_eq!(observed, 0xFFFF_FFFF);
2369 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
2370 let map: HashMap<_, _> = vec.into_iter().collect();
2371 let keys: Vec<_> = map.keys().cloned().collect();
2372 assert_eq!(keys.len(), 3);
2373 assert!(keys.contains(&1));
2374 assert!(keys.contains(&2));
2375 assert!(keys.contains(&3));
2380 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
2381 let map: HashMap<_, _> = vec.into_iter().collect();
2382 let values: Vec<_> = map.values().cloned().collect();
2383 assert_eq!(values.len(), 3);
2384 assert!(values.contains(&'a'));
2385 assert!(values.contains(&'b'));
2386 assert!(values.contains(&'c'));
2390 fn test_values_mut() {
2391 let vec = vec![(1, 1), (2, 2), (3, 3)];
2392 let mut map: HashMap<_, _> = vec.into_iter().collect();
2393 for value in map.values_mut() {
2394 *value = (*value) * 2
2396 let values: Vec<_> = map.values().cloned().collect();
2397 assert_eq!(values.len(), 3);
2398 assert!(values.contains(&2));
2399 assert!(values.contains(&4));
2400 assert!(values.contains(&6));
2405 let mut m = HashMap::new();
2406 assert!(m.get(&1).is_none());
2410 Some(v) => assert_eq!(*v, 2)
2416 let mut m1 = HashMap::new();
2421 let mut m2 = HashMap::new();
2434 let mut map = HashMap::new();
2435 let empty: HashMap<i32, i32> = HashMap::new();
2440 let map_str = format!("{:?}", map);
2442 assert!(map_str == "{1: 2, 3: 4}" ||
2443 map_str == "{3: 4, 1: 2}");
2444 assert_eq!(format!("{:?}", empty), "{}");
2449 let mut m = HashMap::new();
2451 assert_eq!(m.len(), 0);
2452 assert!(m.is_empty());
2455 let old_cap = m.table.capacity();
2456 while old_cap == m.table.capacity() {
2461 assert_eq!(m.len(), i);
2462 assert!(!m.is_empty());
2466 fn test_behavior_resize_policy() {
2467 let mut m = HashMap::new();
2469 assert_eq!(m.len(), 0);
2470 assert_eq!(m.table.capacity(), 0);
2471 assert!(m.is_empty());
2475 assert!(m.is_empty());
2476 let initial_cap = m.table.capacity();
2477 m.reserve(initial_cap);
2478 let cap = m.table.capacity();
2480 assert_eq!(cap, initial_cap * 2);
2483 for _ in 0..cap * 3 / 4 {
2487 // three quarters full
2489 assert_eq!(m.len(), i);
2490 assert_eq!(m.table.capacity(), cap);
2492 for _ in 0..cap / 4 {
2498 let new_cap = m.table.capacity();
2499 assert_eq!(new_cap, cap * 2);
2501 for _ in 0..cap / 2 - 1 {
2504 assert_eq!(m.table.capacity(), new_cap);
2506 // A little more than one quarter full.
2508 assert_eq!(m.table.capacity(), cap);
2509 // again, a little more than half full
2510 for _ in 0..cap / 2 - 1 {
2516 assert_eq!(m.len(), i);
2517 assert!(!m.is_empty());
2518 assert_eq!(m.table.capacity(), initial_cap);
2522 fn test_reserve_shrink_to_fit() {
2523 let mut m = HashMap::new();
2526 assert!(m.capacity() >= m.len());
2532 let usable_cap = m.capacity();
2533 for i in 128..(128 + 256) {
2535 assert_eq!(m.capacity(), usable_cap);
2538 for i in 100..(128 + 256) {
2539 assert_eq!(m.remove(&i), Some(i));
2543 assert_eq!(m.len(), 100);
2544 assert!(!m.is_empty());
2545 assert!(m.capacity() >= m.len());
2548 assert_eq!(m.remove(&i), Some(i));
2553 assert_eq!(m.len(), 1);
2554 assert!(m.capacity() >= m.len());
2555 assert_eq!(m.remove(&0), Some(0));
2559 fn test_from_iter() {
2560 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2562 let map: HashMap<_, _> = xs.iter().cloned().collect();
2564 for &(k, v) in &xs {
2565 assert_eq!(map.get(&k), Some(&v));
2570 fn test_size_hint() {
2571 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2573 let map: HashMap<_, _> = xs.iter().cloned().collect();
2575 let mut iter = map.iter();
2577 for _ in iter.by_ref().take(3) {}
2579 assert_eq!(iter.size_hint(), (3, Some(3)));
2583 fn test_iter_len() {
2584 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2586 let map: HashMap<_, _> = xs.iter().cloned().collect();
2588 let mut iter = map.iter();
2590 for _ in iter.by_ref().take(3) {}
2592 assert_eq!(iter.len(), 3);
2596 fn test_mut_size_hint() {
2597 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2599 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2601 let mut iter = map.iter_mut();
2603 for _ in iter.by_ref().take(3) {}
2605 assert_eq!(iter.size_hint(), (3, Some(3)));
2609 fn test_iter_mut_len() {
2610 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2612 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2614 let mut iter = map.iter_mut();
2616 for _ in iter.by_ref().take(3) {}
2618 assert_eq!(iter.len(), 3);
2623 let mut map = HashMap::new();
2629 assert_eq!(map[&2], 1);
2634 fn test_index_nonexistent() {
2635 let mut map = HashMap::new();
2646 let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2648 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2650 // Existing key (insert)
2651 match map.entry(1) {
2652 Vacant(_) => unreachable!(),
2653 Occupied(mut view) => {
2654 assert_eq!(view.get(), &10);
2655 assert_eq!(view.insert(100), 10);
2658 assert_eq!(map.get(&1).unwrap(), &100);
2659 assert_eq!(map.len(), 6);
2662 // Existing key (update)
2663 match map.entry(2) {
2664 Vacant(_) => unreachable!(),
2665 Occupied(mut view) => {
2666 let v = view.get_mut();
2667 let new_v = (*v) * 10;
2671 assert_eq!(map.get(&2).unwrap(), &200);
2672 assert_eq!(map.len(), 6);
2674 // Existing key (take)
2675 match map.entry(3) {
2676 Vacant(_) => unreachable!(),
2678 assert_eq!(view.remove(), 30);
2681 assert_eq!(map.get(&3), None);
2682 assert_eq!(map.len(), 5);
2685 // Inexistent key (insert)
2686 match map.entry(10) {
2687 Occupied(_) => unreachable!(),
2689 assert_eq!(*view.insert(1000), 1000);
2692 assert_eq!(map.get(&10).unwrap(), &1000);
2693 assert_eq!(map.len(), 6);
2697 fn test_entry_take_doesnt_corrupt() {
2698 #![allow(deprecated)] //rand
2700 fn check(m: &HashMap<isize, ()>) {
2702 assert!(m.contains_key(k),
2703 "{} is in keys() but not in the map?", k);
2707 let mut m = HashMap::new();
2708 let mut rng = thread_rng();
2710 // Populate the map with some items.
2712 let x = rng.gen_range(-10, 10);
2717 let x = rng.gen_range(-10, 10);
2721 println!("{}: remove {}", i, x);
2731 fn test_extend_ref() {
2732 let mut a = HashMap::new();
2734 let mut b = HashMap::new();
2736 b.insert(3, "three");
2740 assert_eq!(a.len(), 3);
2741 assert_eq!(a[&1], "one");
2742 assert_eq!(a[&2], "two");
2743 assert_eq!(a[&3], "three");
2747 fn test_capacity_not_less_than_len() {
2748 let mut a = HashMap::new();
2756 assert!(a.capacity() > a.len());
2758 let free = a.capacity() - a.len();
2764 assert_eq!(a.len(), a.capacity());
2766 // Insert at capacity should cause allocation.
2768 assert!(a.capacity() > a.len());
2772 fn test_occupied_entry_key() {
2773 let mut a = HashMap::new();
2774 let key = "hello there";
2775 let value = "value goes here";
2776 assert!(a.is_empty());
2777 a.insert(key.clone(), value.clone());
2778 assert_eq!(a.len(), 1);
2779 assert_eq!(a[key], value);
2781 match a.entry(key.clone()) {
2782 Vacant(_) => panic!(),
2783 Occupied(e) => assert_eq!(key, *e.key()),
2785 assert_eq!(a.len(), 1);
2786 assert_eq!(a[key], value);
2790 fn test_vacant_entry_key() {
2791 let mut a = HashMap::new();
2792 let key = "hello there";
2793 let value = "value goes here";
2795 assert!(a.is_empty());
2796 match a.entry(key.clone()) {
2797 Occupied(_) => panic!(),
2799 assert_eq!(key, *e.key());
2800 e.insert(value.clone());
2803 assert_eq!(a.len(), 1);
2804 assert_eq!(a[key], value);