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::SearchResult::*;
13 use self::VacantEntryState::*;
17 use fmt::{self, Debug};
18 use hash::{Hash, SipHasher, BuildHasher};
19 use iter::{self, Map, FromIterator};
20 use mem::{self, replace};
21 use ops::{Deref, Index};
22 use rand::{self, Rng};
34 use super::table::BucketState::{
39 const INITIAL_LOG2_CAP: usize = 5;
40 const INITIAL_CAPACITY: usize = 1 << INITIAL_LOG2_CAP; // 2^5
42 /// The default behavior of HashMap implements a load factor of 90.9%.
43 /// This behavior is characterized by the following condition:
45 /// - if size > 0.909 * capacity: grow the map
47 struct DefaultResizePolicy;
49 impl DefaultResizePolicy {
50 fn new() -> DefaultResizePolicy {
55 fn min_capacity(&self, usable_size: usize) -> usize {
56 // Here, we are rephrasing the logic by specifying the lower limit
59 // - if `cap < size * 1.1`: grow the map
63 /// An inverse of `min_capacity`, approximately.
65 fn usable_capacity(&self, cap: usize) -> usize {
66 // As the number of entries approaches usable capacity,
67 // min_capacity(size) must be smaller than the internal capacity,
68 // so that the map is not resized:
69 // `min_capacity(usable_capacity(x)) <= x`.
70 // The left-hand side can only be smaller due to flooring by integer
73 // This doesn't have to be checked for overflow since allocation size
74 // in bytes will overflow earlier than multiplication by 10.
76 // As per https://github.com/rust-lang/rust/pull/30991 this is updated
77 // to be: (cap * den + den - 1) / num
78 (cap * 10 + 10 - 1) / 11
83 fn test_resize_policy() {
84 let rp = DefaultResizePolicy;
86 assert!(rp.min_capacity(rp.usable_capacity(n)) <= n);
87 assert!(rp.usable_capacity(rp.min_capacity(n)) <= n);
91 // The main performance trick in this hashmap is called Robin Hood Hashing.
92 // It gains its excellent performance from one essential operation:
94 // If an insertion collides with an existing element, and that element's
95 // "probe distance" (how far away the element is from its ideal location)
96 // is higher than how far we've already probed, swap the elements.
98 // This massively lowers variance in probe distance, and allows us to get very
99 // high load factors with good performance. The 90% load factor I use is rather
102 // > Why a load factor of approximately 90%?
104 // In general, all the distances to initial buckets will converge on the mean.
105 // At a load factor of α, the odds of finding the target bucket after k
106 // probes is approximately 1-α^k. If we set this equal to 50% (since we converge
107 // on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round
108 // this down to make the math easier on the CPU and avoid its FPU.
109 // Since on average we start the probing in the middle of a cache line, this
110 // strategy pulls in two cache lines of hashes on every lookup. I think that's
111 // pretty good, but if you want to trade off some space, it could go down to one
112 // cache line on average with an α of 0.84.
114 // > Wait, what? Where did you get 1-α^k from?
116 // On the first probe, your odds of a collision with an existing element is α.
117 // The odds of doing this twice in a row is approximately α^2. For three times,
118 // α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT
119 // colliding after k tries is 1-α^k.
121 // The paper from 1986 cited below mentions an implementation which keeps track
122 // of the distance-to-initial-bucket histogram. This approach is not suitable
123 // for modern architectures because it requires maintaining an internal data
124 // structure. This allows very good first guesses, but we are most concerned
125 // with guessing entire cache lines, not individual indexes. Furthermore, array
126 // accesses are no longer linear and in one direction, as we have now. There
127 // is also memory and cache pressure that this would entail that would be very
128 // difficult to properly see in a microbenchmark.
130 // ## Future Improvements (FIXME!)
132 // Allow the load factor to be changed dynamically and/or at initialization.
134 // Also, would it be possible for us to reuse storage when growing the
135 // underlying table? This is exactly the use case for 'realloc', and may
136 // be worth exploring.
138 // ## Future Optimizations (FIXME!)
140 // Another possible design choice that I made without any real reason is
141 // parameterizing the raw table over keys and values. Technically, all we need
142 // is the size and alignment of keys and values, and the code should be just as
143 // efficient (well, we might need one for power-of-two size and one for not...).
144 // This has the potential to reduce code bloat in rust executables, without
145 // really losing anything except 4 words (key size, key alignment, val size,
146 // val alignment) which can be passed in to every call of a `RawTable` function.
147 // This would definitely be an avenue worth exploring if people start complaining
148 // about the size of rust executables.
150 // Annotate exceedingly likely branches in `table::make_hash`
151 // and `search_hashed` to reduce instruction cache pressure
152 // and mispredictions once it becomes possible (blocked on issue #11092).
154 // Shrinking the table could simply reallocate in place after moving buckets
155 // to the first half.
157 // The growth algorithm (fragment of the Proof of Correctness)
158 // --------------------
160 // The growth algorithm is basically a fast path of the naive reinsertion-
161 // during-resize algorithm. Other paths should never be taken.
163 // Consider growing a robin hood hashtable of capacity n. Normally, we do this
164 // by allocating a new table of capacity `2n`, and then individually reinsert
165 // each element in the old table into the new one. This guarantees that the
166 // new table is a valid robin hood hashtable with all the desired statistical
167 // properties. Remark that the order we reinsert the elements in should not
168 // matter. For simplicity and efficiency, we will consider only linear
169 // reinsertions, which consist of reinserting all elements in the old table
170 // into the new one by increasing order of index. However we will not be
171 // starting our reinsertions from index 0 in general. If we start from index
172 // i, for the purpose of reinsertion we will consider all elements with real
173 // index j < i to have virtual index n + j.
175 // Our hash generation scheme consists of generating a 64-bit hash and
176 // truncating the most significant bits. When moving to the new table, we
177 // simply introduce a new bit to the front of the hash. Therefore, if an
178 // elements has ideal index i in the old table, it can have one of two ideal
179 // locations in the new table. If the new bit is 0, then the new ideal index
180 // is i. If the new bit is 1, then the new ideal index is n + i. Intuitively,
181 // we are producing two independent tables of size n, and for each element we
182 // independently choose which table to insert it into with equal probability.
183 // However the rather than wrapping around themselves on overflowing their
184 // indexes, the first table overflows into the first, and the first into the
185 // second. Visually, our new table will look something like:
187 // [yy_xxx_xxxx_xxx|xx_yyy_yyyy_yyy]
189 // Where x's are elements inserted into the first table, y's are elements
190 // inserted into the second, and _'s are empty sections. We now define a few
191 // key concepts that we will use later. Note that this is a very abstract
192 // perspective of the table. A real resized table would be at least half
195 // Theorem: A linear robin hood reinsertion from the first ideal element
196 // produces identical results to a linear naive reinsertion from the same
199 // FIXME(Gankro, pczarn): review the proof and put it all in a separate README.md
201 /// A hash map implementation which uses linear probing with Robin
202 /// Hood bucket stealing.
204 /// The hashes are all keyed by the thread-local random number generator
205 /// on creation by default. This means that the ordering of the keys is
206 /// randomized, but makes the tables more resistant to
207 /// denial-of-service attacks (Hash DoS). This behavior can be
208 /// 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.
345 fn search_hashed<K, V, M, F>(table: M,
348 -> SearchResult<K, V, M> where
349 M: Deref<Target=RawTable<K, V>>,
350 F: FnMut(&K) -> bool,
352 // This is the only function where capacity can be zero. To avoid
353 // undefined behavior when Bucket::new gets the raw bucket in this
354 // case, immediately return the appropriate search result.
355 if table.capacity() == 0 {
356 return TableRef(table);
359 let size = table.size();
360 let mut probe = Bucket::new(table, hash);
361 let ib = probe.index();
363 while probe.index() != ib + size {
364 let full = match probe.peek() {
365 Empty(b) => return TableRef(b.into_table()), // hit an empty bucket
369 if full.distance() + ib < full.index() {
370 // We can finish the search early if we hit any bucket
371 // with a lower distance to initial bucket than we've probed.
372 return TableRef(full.into_table());
375 // If the hash doesn't match, it can't be this one..
376 if hash == full.hash() {
377 // If the key doesn't match, it can't be this one..
378 if is_match(full.read().0) {
379 return FoundExisting(full);
386 TableRef(probe.into_table())
389 fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) {
390 let (empty, retkey, retval) = starting_bucket.take();
391 let mut gap = match empty.gap_peek() {
393 None => return (retkey, retval)
396 while gap.full().distance() != 0 {
397 gap = match gap.shift() {
403 // Now we've done all our shifting. Return the value we grabbed earlier.
407 /// Perform robin hood bucket stealing at the given `bucket`. You must
408 /// also pass the position of that bucket's initial bucket so we don't have
409 /// to recalculate it.
411 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
412 fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>,
418 let starting_index = bucket.index();
420 let table = bucket.table(); // FIXME "lifetime too short".
423 // There can be at most `size - dib` buckets to displace, because
424 // in the worst case, there are `size` elements and we already are
425 // `distance` buckets away from the initial one.
426 let idx_end = starting_index + size - bucket.distance();
429 let (old_hash, old_key, old_val) = bucket.replace(hash, k, v);
431 let probe = bucket.next();
432 assert!(probe.index() != idx_end);
434 let full_bucket = match probe.peek() {
437 let b = bucket.put(old_hash, old_key, old_val);
438 // Now that it's stolen, just read the value's pointer
439 // right out of the table!
440 return Bucket::at_index(b.into_table(), starting_index)
446 Full(bucket) => bucket
449 let probe_ib = full_bucket.index() - full_bucket.distance();
451 bucket = full_bucket;
453 // Robin hood! Steal the spot.
465 /// A result that works like Option<FullBucket<..>> but preserves
466 /// the reference that grants us access to the table in any case.
467 enum SearchResult<K, V, M> {
468 // This is an entry that holds the given key:
469 FoundExisting(FullBucket<K, V, M>),
471 // There was no such entry. The reference is given back:
475 impl<K, V, M> SearchResult<K, V, M> {
476 fn into_option(self) -> Option<FullBucket<K, V, M>> {
478 FoundExisting(bucket) => Some(bucket),
484 impl<K, V, S> HashMap<K, V, S>
485 where K: Eq + Hash, S: BuildHasher
487 fn make_hash<X: ?Sized>(&self, x: &X) -> SafeHash where X: Hash {
488 table::make_hash(&self.hash_builder, x)
491 /// Search for a key, yielding the index if it's found in the hashtable.
492 /// If you already have the hash for the key lying around, use
494 fn search<'a, Q: ?Sized>(&'a self, q: &Q) -> Option<FullBucketImm<'a, K, V>>
495 where K: Borrow<Q>, Q: Eq + Hash
497 let hash = self.make_hash(q);
498 search_hashed(&self.table, hash, |k| q.eq(k.borrow()))
502 fn search_mut<'a, Q: ?Sized>(&'a mut self, q: &Q) -> Option<FullBucketMut<'a, K, V>>
503 where K: Borrow<Q>, Q: Eq + Hash
505 let hash = self.make_hash(q);
506 search_hashed(&mut self.table, hash, |k| q.eq(k.borrow()))
510 // The caller should ensure that invariants by Robin Hood Hashing hold.
511 fn insert_hashed_ordered(&mut self, hash: SafeHash, k: K, v: V) {
512 let cap = self.table.capacity();
513 let mut buckets = Bucket::new(&mut self.table, hash);
514 let ib = buckets.index();
516 while buckets.index() != ib + cap {
517 // We don't need to compare hashes for value swap.
518 // Not even DIBs for Robin Hood.
519 buckets = match buckets.peek() {
521 empty.put(hash, k, v);
524 Full(b) => b.into_bucket()
528 panic!("Internal HashMap error: Out of space.");
532 impl<K: Hash + Eq, V> HashMap<K, V, RandomState> {
533 /// Creates an empty HashMap.
538 /// use std::collections::HashMap;
539 /// let mut map: HashMap<&str, isize> = HashMap::new();
542 #[stable(feature = "rust1", since = "1.0.0")]
543 pub fn new() -> HashMap<K, V, RandomState> {
547 /// Creates an empty hash map with the given initial capacity.
552 /// use std::collections::HashMap;
553 /// let mut map: HashMap<&str, isize> = HashMap::with_capacity(10);
556 #[stable(feature = "rust1", since = "1.0.0")]
557 pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> {
558 HashMap::with_capacity_and_hasher(capacity, Default::default())
562 impl<K, V, S> HashMap<K, V, S>
563 where K: Eq + Hash, S: BuildHasher
565 /// Creates an empty hashmap which will use the given hash builder to hash
568 /// The created map has the default initial capacity.
570 /// Warning: `hash_builder` is normally randomly generated, and
571 /// is designed to allow HashMaps to be resistant to attacks that
572 /// cause many collisions and very poor performance. Setting it
573 /// manually using this function can expose a DoS attack vector.
578 /// use std::collections::HashMap;
579 /// use std::collections::hash_map::RandomState;
581 /// let s = RandomState::new();
582 /// let mut map = HashMap::with_hasher(s);
583 /// map.insert(1, 2);
586 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
587 pub fn with_hasher(hash_builder: S) -> HashMap<K, V, S> {
589 hash_builder: hash_builder,
590 resize_policy: DefaultResizePolicy::new(),
591 table: RawTable::new(0),
595 /// Creates an empty HashMap with space for at least `capacity`
596 /// elements, using `hasher` to hash the keys.
598 /// Warning: `hasher` is normally randomly generated, and
599 /// is designed to allow HashMaps to be resistant to attacks that
600 /// cause many collisions and very poor performance. Setting it
601 /// manually using this function can expose a DoS attack vector.
606 /// use std::collections::HashMap;
607 /// use std::collections::hash_map::RandomState;
609 /// let s = RandomState::new();
610 /// let mut map = HashMap::with_capacity_and_hasher(10, s);
611 /// map.insert(1, 2);
614 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
615 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S)
616 -> HashMap<K, V, S> {
617 let resize_policy = DefaultResizePolicy::new();
618 let min_cap = max(INITIAL_CAPACITY, resize_policy.min_capacity(capacity));
619 let internal_cap = min_cap.checked_next_power_of_two().expect("capacity overflow");
620 assert!(internal_cap >= capacity, "capacity overflow");
622 hash_builder: hash_builder,
623 resize_policy: resize_policy,
624 table: RawTable::new(internal_cap),
628 /// Returns a reference to the map's hasher.
629 #[unstable(feature = "hashmap_public_hasher", reason = "don't want to make insta-stable",
631 pub fn hasher(&self) -> &S {
635 /// Returns the number of elements the map can hold without reallocating.
637 /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
638 /// more, but is guaranteed to be able to hold at least this many.
643 /// use std::collections::HashMap;
644 /// let map: HashMap<isize, isize> = HashMap::with_capacity(100);
645 /// assert!(map.capacity() >= 100);
648 #[stable(feature = "rust1", since = "1.0.0")]
649 pub fn capacity(&self) -> usize {
650 self.resize_policy.usable_capacity(self.table.capacity())
653 /// Reserves capacity for at least `additional` more elements to be inserted
654 /// in the `HashMap`. The collection may reserve more space to avoid
655 /// frequent reallocations.
659 /// Panics if the new allocation size overflows `usize`.
664 /// use std::collections::HashMap;
665 /// let mut map: HashMap<&str, isize> = HashMap::new();
668 #[stable(feature = "rust1", since = "1.0.0")]
669 pub fn reserve(&mut self, additional: usize) {
670 let new_size = self.len().checked_add(additional).expect("capacity overflow");
671 let min_cap = self.resize_policy.min_capacity(new_size);
673 // An invalid value shouldn't make us run out of space. This includes
674 // an overflow check.
675 assert!(new_size <= min_cap);
677 if self.table.capacity() < min_cap {
678 let new_capacity = max(min_cap.next_power_of_two(), INITIAL_CAPACITY);
679 self.resize(new_capacity);
683 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
684 /// 1) Make sure the new capacity is enough for all the elements, accounting
685 /// for the load factor.
686 /// 2) Ensure new_capacity is a power of two or zero.
687 fn resize(&mut self, new_capacity: usize) {
688 assert!(self.table.size() <= new_capacity);
689 assert!(new_capacity.is_power_of_two() || new_capacity == 0);
691 let mut old_table = replace(&mut self.table, RawTable::new(new_capacity));
692 let old_size = old_table.size();
694 if old_table.capacity() == 0 || old_table.size() == 0 {
699 // Specialization of the other branch.
700 let mut bucket = Bucket::first(&mut old_table);
702 // "So a few of the first shall be last: for many be called,
705 // We'll most likely encounter a few buckets at the beginning that
706 // have their initial buckets near the end of the table. They were
707 // placed at the beginning as the probe wrapped around the table
708 // during insertion. We must skip forward to a bucket that won't
709 // get reinserted too early and won't unfairly steal others spot.
710 // This eliminates the need for robin hood.
712 bucket = match bucket.peek() {
714 if full.distance() == 0 {
715 // This bucket occupies its ideal spot.
716 // It indicates the start of another "cluster".
717 bucket = full.into_bucket();
720 // Leaving this bucket in the last cluster for later.
724 // Encountered a hole between clusters.
731 // This is how the buckets might be laid out in memory:
732 // ($ marks an initialized bucket)
734 // |$$$_$$$$$$_$$$$$|
736 // But we've skipped the entire initial cluster of buckets
737 // and will continue iteration in this order:
740 // ^ wrap around once end is reached
743 // ^ exit once table.size == 0
745 bucket = match bucket.peek() {
747 let h = bucket.hash();
748 let (b, k, v) = bucket.take();
749 self.insert_hashed_ordered(h, k, v);
751 let t = b.table(); // FIXME "lifetime too short".
752 if t.size() == 0 { break }
756 Empty(b) => b.into_bucket()
761 assert_eq!(self.table.size(), old_size);
764 /// Shrinks the capacity of the map as much as possible. It will drop
765 /// down as much as possible while maintaining the internal rules
766 /// and possibly leaving some space in accordance with the resize policy.
771 /// use std::collections::HashMap;
773 /// let mut map: HashMap<isize, isize> = HashMap::with_capacity(100);
774 /// map.insert(1, 2);
775 /// map.insert(3, 4);
776 /// assert!(map.capacity() >= 100);
777 /// map.shrink_to_fit();
778 /// assert!(map.capacity() >= 2);
780 #[stable(feature = "rust1", since = "1.0.0")]
781 pub fn shrink_to_fit(&mut self) {
782 let min_capacity = self.resize_policy.min_capacity(self.len());
783 let min_capacity = max(min_capacity.next_power_of_two(), INITIAL_CAPACITY);
785 // An invalid value shouldn't make us run out of space.
786 debug_assert!(self.len() <= min_capacity);
788 if self.table.capacity() != min_capacity {
789 let old_table = replace(&mut self.table, RawTable::new(min_capacity));
790 let old_size = old_table.size();
792 // Shrink the table. Naive algorithm for resizing:
793 for (h, k, v) in old_table.into_iter() {
794 self.insert_hashed_nocheck(h, k, v);
797 debug_assert_eq!(self.table.size(), old_size);
801 /// Insert a pre-hashed key-value pair, without first checking
802 /// that there's enough room in the buckets. Returns a reference to the
803 /// newly insert value.
805 /// If the key already exists, the hashtable will be returned untouched
806 /// and a reference to the existing element will be returned.
807 fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> &mut V {
808 self.insert_or_replace_with(hash, k, v, |_, _, _, _| ())
811 fn insert_or_replace_with<'a, F>(&'a mut self,
815 mut found_existing: F)
817 F: FnMut(&mut K, &mut V, K, V),
819 // Worst case, we'll find one empty bucket among `size + 1` buckets.
820 let size = self.table.size();
821 let mut probe = Bucket::new(&mut self.table, hash);
822 let ib = probe.index();
825 let mut bucket = match probe.peek() {
828 return bucket.put(hash, k, v).into_mut_refs().1;
830 Full(bucket) => bucket
834 if bucket.hash() == hash {
836 if k == *bucket.read_mut().0 {
837 let (bucket_k, bucket_v) = bucket.into_mut_refs();
838 debug_assert!(k == *bucket_k);
839 // Key already exists. Get its reference.
840 found_existing(bucket_k, bucket_v, k, v);
845 let robin_ib = bucket.index() as isize - bucket.distance() as isize;
847 if (ib as isize) < robin_ib {
848 // Found a luckier bucket than me. Better steal his spot.
849 return robin_hood(bucket, robin_ib as usize, hash, k, v);
852 probe = bucket.next();
853 assert!(probe.index() != ib + size + 1);
857 /// An iterator visiting all keys in arbitrary order.
858 /// Iterator element type is `&'a K`.
863 /// use std::collections::HashMap;
865 /// let mut map = HashMap::new();
866 /// map.insert("a", 1);
867 /// map.insert("b", 2);
868 /// map.insert("c", 3);
870 /// for key in map.keys() {
871 /// println!("{}", key);
874 #[stable(feature = "rust1", since = "1.0.0")]
875 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
876 fn first<A, B>((a, _): (A, B)) -> A { a }
877 let first: fn((&'a K,&'a V)) -> &'a K = first; // coerce to fn ptr
879 Keys { inner: self.iter().map(first) }
882 /// An iterator visiting all values in arbitrary order.
883 /// Iterator element type is `&'a V`.
888 /// use std::collections::HashMap;
890 /// let mut map = HashMap::new();
891 /// map.insert("a", 1);
892 /// map.insert("b", 2);
893 /// map.insert("c", 3);
895 /// for val in map.values() {
896 /// println!("{}", val);
899 #[stable(feature = "rust1", since = "1.0.0")]
900 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
901 fn second<A, B>((_, b): (A, B)) -> B { b }
902 let second: fn((&'a K,&'a V)) -> &'a V = second; // coerce to fn ptr
904 Values { inner: self.iter().map(second) }
907 /// An iterator visiting all key-value pairs in arbitrary order.
908 /// Iterator element type is `(&'a K, &'a V)`.
913 /// use std::collections::HashMap;
915 /// let mut map = HashMap::new();
916 /// map.insert("a", 1);
917 /// map.insert("b", 2);
918 /// map.insert("c", 3);
920 /// for (key, val) in map.iter() {
921 /// println!("key: {} val: {}", key, val);
924 #[stable(feature = "rust1", since = "1.0.0")]
925 pub fn iter(&self) -> Iter<K, V> {
926 Iter { inner: self.table.iter() }
929 /// An iterator visiting all key-value pairs in arbitrary order,
930 /// with mutable references to the values.
931 /// Iterator element type is `(&'a K, &'a mut V)`.
936 /// use std::collections::HashMap;
938 /// let mut map = HashMap::new();
939 /// map.insert("a", 1);
940 /// map.insert("b", 2);
941 /// map.insert("c", 3);
943 /// // Update all values
944 /// for (_, val) in map.iter_mut() {
948 /// for (key, val) in &map {
949 /// println!("key: {} val: {}", key, val);
952 #[stable(feature = "rust1", since = "1.0.0")]
953 pub fn iter_mut(&mut self) -> IterMut<K, V> {
954 IterMut { inner: self.table.iter_mut() }
957 /// Gets the given key's corresponding entry in the map for in-place manipulation.
962 /// use std::collections::HashMap;
964 /// let mut letters = HashMap::new();
966 /// for ch in "a short treatise on fungi".chars() {
967 /// let counter = letters.entry(ch).or_insert(0);
971 /// assert_eq!(letters[&'s'], 2);
972 /// assert_eq!(letters[&'t'], 3);
973 /// assert_eq!(letters[&'u'], 1);
974 /// assert_eq!(letters.get(&'y'), None);
976 #[stable(feature = "rust1", since = "1.0.0")]
977 pub fn entry(&mut self, key: K) -> Entry<K, V> {
981 let hash = self.make_hash(&key);
982 search_entry_hashed(&mut self.table, hash, key)
985 /// Returns the number of elements in the map.
990 /// use std::collections::HashMap;
992 /// let mut a = HashMap::new();
993 /// assert_eq!(a.len(), 0);
994 /// a.insert(1, "a");
995 /// assert_eq!(a.len(), 1);
997 #[stable(feature = "rust1", since = "1.0.0")]
998 pub fn len(&self) -> usize { self.table.size() }
1000 /// Returns true if the map contains no elements.
1005 /// use std::collections::HashMap;
1007 /// let mut a = HashMap::new();
1008 /// assert!(a.is_empty());
1009 /// a.insert(1, "a");
1010 /// assert!(!a.is_empty());
1013 #[stable(feature = "rust1", since = "1.0.0")]
1014 pub fn is_empty(&self) -> bool { self.len() == 0 }
1016 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
1017 /// allocated memory for reuse.
1022 /// use std::collections::HashMap;
1024 /// let mut a = HashMap::new();
1025 /// a.insert(1, "a");
1026 /// a.insert(2, "b");
1028 /// for (k, v) in a.drain().take(1) {
1029 /// assert!(k == 1 || k == 2);
1030 /// assert!(v == "a" || v == "b");
1033 /// assert!(a.is_empty());
1036 #[stable(feature = "drain", since = "1.6.0")]
1037 pub fn drain(&mut self) -> Drain<K, V> {
1038 fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) }
1039 let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two; // coerce to fn pointer
1042 inner: self.table.drain().map(last_two),
1046 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
1052 /// use std::collections::HashMap;
1054 /// let mut a = HashMap::new();
1055 /// a.insert(1, "a");
1057 /// assert!(a.is_empty());
1059 #[stable(feature = "rust1", since = "1.0.0")]
1061 pub fn clear(&mut self) {
1065 /// Returns a reference to the value corresponding to the key.
1067 /// The key may be any borrowed form of the map's key type, but
1068 /// `Hash` and `Eq` on the borrowed form *must* match those for
1074 /// use std::collections::HashMap;
1076 /// let mut map = HashMap::new();
1077 /// map.insert(1, "a");
1078 /// assert_eq!(map.get(&1), Some(&"a"));
1079 /// assert_eq!(map.get(&2), None);
1081 #[stable(feature = "rust1", since = "1.0.0")]
1082 pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
1083 where K: Borrow<Q>, Q: Hash + Eq
1085 self.search(k).map(|bucket| bucket.into_refs().1)
1088 /// Returns true if the map contains a value for the specified key.
1090 /// The key may be any borrowed form of the map's key type, but
1091 /// `Hash` and `Eq` on the borrowed form *must* match those for
1097 /// use std::collections::HashMap;
1099 /// let mut map = HashMap::new();
1100 /// map.insert(1, "a");
1101 /// assert_eq!(map.contains_key(&1), true);
1102 /// assert_eq!(map.contains_key(&2), false);
1104 #[stable(feature = "rust1", since = "1.0.0")]
1105 pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
1106 where K: Borrow<Q>, Q: Hash + Eq
1108 self.search(k).is_some()
1111 /// Returns a mutable reference to the value corresponding to the key.
1113 /// The key may be any borrowed form of the map's key type, but
1114 /// `Hash` and `Eq` on the borrowed form *must* match those for
1120 /// use std::collections::HashMap;
1122 /// let mut map = HashMap::new();
1123 /// map.insert(1, "a");
1124 /// if let Some(x) = map.get_mut(&1) {
1127 /// assert_eq!(map[&1], "b");
1129 #[stable(feature = "rust1", since = "1.0.0")]
1130 pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
1131 where K: Borrow<Q>, Q: Hash + Eq
1133 self.search_mut(k).map(|bucket| bucket.into_mut_refs().1)
1136 /// Inserts a key-value pair into the map.
1138 /// If the map did not have this key present, `None` is returned.
1140 /// If the map did have this key present, the value is updated, and the old
1141 /// value is returned. The key is not updated, though; this matters for
1142 /// types that can be `==` without being identical. See the [module-level
1143 /// documentation] for more.
1145 /// [module-level documentation]: index.html#insert-and-complex-keys
1150 /// use std::collections::HashMap;
1152 /// let mut map = HashMap::new();
1153 /// assert_eq!(map.insert(37, "a"), None);
1154 /// assert_eq!(map.is_empty(), false);
1156 /// map.insert(37, "b");
1157 /// assert_eq!(map.insert(37, "c"), Some("b"));
1158 /// assert_eq!(map[&37], "c");
1160 #[stable(feature = "rust1", since = "1.0.0")]
1161 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
1162 let hash = self.make_hash(&k);
1165 let mut retval = None;
1166 self.insert_or_replace_with(hash, k, v, |_, val_ref, _, val| {
1167 retval = Some(replace(val_ref, val));
1172 /// Removes a key from the map, returning the value at the key if the key
1173 /// was previously in the map.
1175 /// The key may be any borrowed form of the map's key type, but
1176 /// `Hash` and `Eq` on the borrowed form *must* match those for
1182 /// use std::collections::HashMap;
1184 /// let mut map = HashMap::new();
1185 /// map.insert(1, "a");
1186 /// assert_eq!(map.remove(&1), Some("a"));
1187 /// assert_eq!(map.remove(&1), None);
1189 #[stable(feature = "rust1", since = "1.0.0")]
1190 pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
1191 where K: Borrow<Q>, Q: Hash + Eq
1193 if self.table.size() == 0 {
1197 self.search_mut(k).map(|bucket| pop_internal(bucket).1)
1201 fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHash, k: K)
1204 // Worst case, we'll find one empty bucket among `size + 1` buckets.
1205 let size = table.size();
1206 let mut probe = Bucket::new(table, hash);
1207 let ib = probe.index();
1210 let bucket = match probe.peek() {
1213 return Vacant(VacantEntry {
1216 elem: NoElem(bucket),
1219 Full(bucket) => bucket
1223 if bucket.hash() == hash {
1225 if k == *bucket.read().0 {
1226 return Occupied(OccupiedEntry{
1232 let robin_ib = bucket.index() as isize - bucket.distance() as isize;
1234 if (ib as isize) < robin_ib {
1235 // Found a luckier bucket than me. Better steal his spot.
1236 return Vacant(VacantEntry {
1239 elem: NeqElem(bucket, robin_ib as usize),
1243 probe = bucket.next();
1244 assert!(probe.index() != ib + size + 1);
1248 #[stable(feature = "rust1", since = "1.0.0")]
1249 impl<K, V, S> PartialEq for HashMap<K, V, S>
1250 where K: Eq + Hash, V: PartialEq, S: BuildHasher
1252 fn eq(&self, other: &HashMap<K, V, S>) -> bool {
1253 if self.len() != other.len() { return false; }
1255 self.iter().all(|(key, value)|
1256 other.get(key).map_or(false, |v| *value == *v)
1261 #[stable(feature = "rust1", since = "1.0.0")]
1262 impl<K, V, S> Eq for HashMap<K, V, S>
1263 where K: Eq + Hash, V: Eq, S: BuildHasher
1266 #[stable(feature = "rust1", since = "1.0.0")]
1267 impl<K, V, S> Debug for HashMap<K, V, S>
1268 where K: Eq + Hash + Debug, V: Debug, S: BuildHasher
1270 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1271 f.debug_map().entries(self.iter()).finish()
1275 #[stable(feature = "rust1", since = "1.0.0")]
1276 impl<K, V, S> Default for HashMap<K, V, S>
1278 S: BuildHasher + Default,
1280 fn default() -> HashMap<K, V, S> {
1281 HashMap::with_hasher(Default::default())
1285 #[stable(feature = "rust1", since = "1.0.0")]
1286 impl<'a, K, Q: ?Sized, V, S> Index<&'a Q> for HashMap<K, V, S>
1287 where K: Eq + Hash + Borrow<Q>,
1294 fn index(&self, index: &Q) -> &V {
1295 self.get(index).expect("no entry found for key")
1299 /// HashMap iterator.
1300 #[stable(feature = "rust1", since = "1.0.0")]
1301 pub struct Iter<'a, K: 'a, V: 'a> {
1302 inner: table::Iter<'a, K, V>
1305 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1306 #[stable(feature = "rust1", since = "1.0.0")]
1307 impl<'a, K, V> Clone for Iter<'a, K, V> {
1308 fn clone(&self) -> Iter<'a, K, V> {
1310 inner: self.inner.clone()
1315 /// HashMap mutable values iterator.
1316 #[stable(feature = "rust1", since = "1.0.0")]
1317 pub struct IterMut<'a, K: 'a, V: 'a> {
1318 inner: table::IterMut<'a, K, V>
1321 /// HashMap move iterator.
1322 #[stable(feature = "rust1", since = "1.0.0")]
1323 pub struct IntoIter<K, V> {
1324 inner: iter::Map<table::IntoIter<K, V>, fn((SafeHash, K, V)) -> (K, V)>
1327 /// HashMap keys iterator.
1328 #[stable(feature = "rust1", since = "1.0.0")]
1329 pub struct Keys<'a, K: 'a, V: 'a> {
1330 inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
1333 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1334 #[stable(feature = "rust1", since = "1.0.0")]
1335 impl<'a, K, V> Clone for Keys<'a, K, V> {
1336 fn clone(&self) -> Keys<'a, K, V> {
1338 inner: self.inner.clone()
1343 /// HashMap values iterator.
1344 #[stable(feature = "rust1", since = "1.0.0")]
1345 pub struct Values<'a, K: 'a, V: 'a> {
1346 inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
1349 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1350 #[stable(feature = "rust1", since = "1.0.0")]
1351 impl<'a, K, V> Clone for Values<'a, K, V> {
1352 fn clone(&self) -> Values<'a, K, V> {
1354 inner: self.inner.clone()
1359 /// HashMap drain iterator.
1360 #[stable(feature = "drain", since = "1.6.0")]
1361 pub struct Drain<'a, K: 'a, V: 'a> {
1362 inner: iter::Map<table::Drain<'a, K, V>, fn((SafeHash, K, V)) -> (K, V)>
1365 /// A view into a single occupied location in a HashMap.
1366 #[stable(feature = "rust1", since = "1.0.0")]
1367 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
1368 elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
1371 /// A view into a single empty location in a HashMap.
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 /// A view into a single location in a map, which may be vacant or occupied.
1380 #[stable(feature = "rust1", since = "1.0.0")]
1381 pub enum Entry<'a, K: 'a, V: 'a> {
1382 /// An occupied Entry.
1383 #[stable(feature = "rust1", since = "1.0.0")]
1385 #[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>
1389 #[stable(feature = "rust1", since = "1.0.0")]
1391 #[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>
1395 /// Possible states of a VacantEntry.
1396 enum VacantEntryState<K, V, M> {
1397 /// The index is occupied, but the key to insert has precedence,
1398 /// and will kick the current one out on insertion.
1399 NeqElem(FullBucket<K, V, M>, usize),
1400 /// The index is genuinely vacant.
1401 NoElem(EmptyBucket<K, V, M>),
1404 #[stable(feature = "rust1", since = "1.0.0")]
1405 impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S>
1406 where K: Eq + Hash, S: BuildHasher
1408 type Item = (&'a K, &'a V);
1409 type IntoIter = Iter<'a, K, V>;
1411 fn into_iter(self) -> Iter<'a, K, V> {
1416 #[stable(feature = "rust1", since = "1.0.0")]
1417 impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S>
1418 where K: Eq + Hash, S: BuildHasher
1420 type Item = (&'a K, &'a mut V);
1421 type IntoIter = IterMut<'a, K, V>;
1423 fn into_iter(mut self) -> IterMut<'a, K, V> {
1428 #[stable(feature = "rust1", since = "1.0.0")]
1429 impl<K, V, S> IntoIterator for HashMap<K, V, S>
1430 where K: Eq + Hash, S: BuildHasher
1433 type IntoIter = IntoIter<K, V>;
1435 /// Creates a consuming iterator, that is, one that moves each key-value
1436 /// pair out of the map in arbitrary order. The map cannot be used after
1442 /// use std::collections::HashMap;
1444 /// let mut map = HashMap::new();
1445 /// map.insert("a", 1);
1446 /// map.insert("b", 2);
1447 /// map.insert("c", 3);
1449 /// // Not possible with .iter()
1450 /// let vec: Vec<(&str, isize)> = map.into_iter().collect();
1452 fn into_iter(self) -> IntoIter<K, V> {
1453 fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) }
1454 let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two;
1457 inner: self.table.into_iter().map(last_two)
1462 #[stable(feature = "rust1", since = "1.0.0")]
1463 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1464 type Item = (&'a K, &'a V);
1466 #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1467 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1469 #[stable(feature = "rust1", since = "1.0.0")]
1470 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
1471 #[inline] fn len(&self) -> usize { self.inner.len() }
1474 #[stable(feature = "rust1", since = "1.0.0")]
1475 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1476 type Item = (&'a K, &'a mut V);
1478 #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1479 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1481 #[stable(feature = "rust1", since = "1.0.0")]
1482 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
1483 #[inline] fn len(&self) -> usize { self.inner.len() }
1486 #[stable(feature = "rust1", since = "1.0.0")]
1487 impl<K, V> Iterator for IntoIter<K, V> {
1490 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1491 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1493 #[stable(feature = "rust1", since = "1.0.0")]
1494 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
1495 #[inline] fn len(&self) -> usize { self.inner.len() }
1498 #[stable(feature = "rust1", since = "1.0.0")]
1499 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1502 #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
1503 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1505 #[stable(feature = "rust1", since = "1.0.0")]
1506 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
1507 #[inline] fn len(&self) -> usize { self.inner.len() }
1510 #[stable(feature = "rust1", since = "1.0.0")]
1511 impl<'a, K, V> Iterator for Values<'a, K, V> {
1514 #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
1515 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1517 #[stable(feature = "rust1", since = "1.0.0")]
1518 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
1519 #[inline] fn len(&self) -> usize { self.inner.len() }
1522 #[stable(feature = "rust1", since = "1.0.0")]
1523 impl<'a, K, V> Iterator for Drain<'a, K, V> {
1526 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1527 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1529 #[stable(feature = "rust1", since = "1.0.0")]
1530 impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> {
1531 #[inline] fn len(&self) -> usize { self.inner.len() }
1534 impl<'a, K, V> Entry<'a, K, V> {
1535 #[stable(feature = "rust1", since = "1.0.0")]
1536 /// Ensures a value is in the entry by inserting the default if empty, and returns
1537 /// a mutable reference to the value in the entry.
1538 pub fn or_insert(self, default: V) -> &'a mut V {
1540 Occupied(entry) => entry.into_mut(),
1541 Vacant(entry) => entry.insert(default),
1545 #[stable(feature = "rust1", since = "1.0.0")]
1546 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1547 /// and returns a mutable reference to the value in the entry.
1548 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1550 Occupied(entry) => entry.into_mut(),
1551 Vacant(entry) => entry.insert(default()),
1556 impl<'a, K, V> OccupiedEntry<'a, K, V> {
1557 /// Gets a reference to the key in the entry.
1558 #[unstable(feature = "map_entry_keys", issue = "32281")]
1559 pub fn key(&self) -> &K {
1563 /// Gets a reference to the value in the entry.
1564 #[stable(feature = "rust1", since = "1.0.0")]
1565 pub fn get(&self) -> &V {
1569 /// Gets a mutable reference to the value in the entry.
1570 #[stable(feature = "rust1", since = "1.0.0")]
1571 pub fn get_mut(&mut self) -> &mut V {
1572 self.elem.read_mut().1
1575 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1576 /// with a lifetime bound to the map itself
1577 #[stable(feature = "rust1", since = "1.0.0")]
1578 pub fn into_mut(self) -> &'a mut V {
1579 self.elem.into_mut_refs().1
1582 /// Sets the value of the entry, and returns the entry's old value
1583 #[stable(feature = "rust1", since = "1.0.0")]
1584 pub fn insert(&mut self, mut value: V) -> V {
1585 let old_value = self.get_mut();
1586 mem::swap(&mut value, old_value);
1590 /// Takes the value out of the entry, and returns it
1591 #[stable(feature = "rust1", since = "1.0.0")]
1592 pub fn remove(self) -> V {
1593 pop_internal(self.elem).1
1597 impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
1598 /// Gets a reference to the key that would be used when inserting a value
1599 /// through the VacantEntry.
1600 #[unstable(feature = "map_entry_keys", issue = "32281")]
1601 pub fn key(&self) -> &K {
1605 /// Sets the value of the entry with the VacantEntry's key,
1606 /// and returns a mutable reference to it
1607 #[stable(feature = "rust1", since = "1.0.0")]
1608 pub fn insert(self, value: V) -> &'a mut V {
1610 NeqElem(bucket, ib) => {
1611 robin_hood(bucket, ib, self.hash, self.key, value)
1614 bucket.put(self.hash, self.key, value).into_mut_refs().1
1620 #[stable(feature = "rust1", since = "1.0.0")]
1621 impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
1622 where K: Eq + Hash, S: BuildHasher + Default
1624 fn from_iter<T: IntoIterator<Item=(K, V)>>(iterable: T) -> HashMap<K, V, S> {
1625 let iter = iterable.into_iter();
1626 let lower = iter.size_hint().0;
1627 let mut map = HashMap::with_capacity_and_hasher(lower, Default::default());
1633 #[stable(feature = "rust1", since = "1.0.0")]
1634 impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S>
1635 where K: Eq + Hash, S: BuildHasher
1637 fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
1638 for (k, v) in iter {
1644 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
1645 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S>
1646 where K: Eq + Hash + Copy, V: Copy, S: BuildHasher
1648 fn extend<T: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: T) {
1649 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1653 /// `RandomState` is the default state for `HashMap` types.
1655 /// A particular instance `RandomState` will create the same instances of
1656 /// `Hasher`, but the hashers created by two different `RandomState`
1657 /// instances are unlikely to produce the same result for the same values.
1659 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1660 pub struct RandomState {
1666 /// Constructs a new `RandomState` that is initialized with random keys.
1668 #[allow(deprecated)] // rand
1669 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1670 pub fn new() -> RandomState {
1671 let mut r = rand::thread_rng();
1672 RandomState { k0: r.gen(), k1: r.gen() }
1676 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1677 impl BuildHasher for RandomState {
1678 type Hasher = SipHasher;
1680 fn build_hasher(&self) -> SipHasher {
1681 SipHasher::new_with_keys(self.k0, self.k1)
1685 #[stable(feature = "rust1", since = "1.0.0")]
1686 impl Default for RandomState {
1688 fn default() -> RandomState {
1693 impl<K, S, Q: ?Sized> super::Recover<Q> for HashMap<K, (), S>
1694 where K: Eq + Hash + Borrow<Q>, S: BuildHasher, Q: Eq + Hash
1698 fn get(&self, key: &Q) -> Option<&K> {
1699 self.search(key).map(|bucket| bucket.into_refs().0)
1702 fn take(&mut self, key: &Q) -> Option<K> {
1703 if self.table.size() == 0 {
1707 self.search_mut(key).map(|bucket| pop_internal(bucket).0)
1710 fn replace(&mut self, key: K) -> Option<K> {
1711 let hash = self.make_hash(&key);
1714 let mut retkey = None;
1715 self.insert_or_replace_with(hash, key, (), |key_ref, _, key, _| {
1716 retkey = Some(replace(key_ref, key));
1727 use super::Entry::{Occupied, Vacant};
1729 use rand::{thread_rng, Rng};
1732 fn test_create_capacity_zero() {
1733 let mut m = HashMap::with_capacity(0);
1735 assert!(m.insert(1, 1).is_none());
1737 assert!(m.contains_key(&1));
1738 assert!(!m.contains_key(&0));
1743 let mut m = HashMap::new();
1744 assert_eq!(m.len(), 0);
1745 assert!(m.insert(1, 2).is_none());
1746 assert_eq!(m.len(), 1);
1747 assert!(m.insert(2, 4).is_none());
1748 assert_eq!(m.len(), 2);
1749 assert_eq!(*m.get(&1).unwrap(), 2);
1750 assert_eq!(*m.get(&2).unwrap(), 4);
1753 thread_local! { static DROP_VECTOR: RefCell<Vec<isize>> = RefCell::new(Vec::new()) }
1755 #[derive(Hash, PartialEq, Eq)]
1761 fn new(k: usize) -> Dropable {
1762 DROP_VECTOR.with(|slot| {
1763 slot.borrow_mut()[k] += 1;
1770 impl Drop for Dropable {
1771 fn drop(&mut self) {
1772 DROP_VECTOR.with(|slot| {
1773 slot.borrow_mut()[self.k] -= 1;
1778 impl Clone for Dropable {
1779 fn clone(&self) -> Dropable {
1780 Dropable::new(self.k)
1786 DROP_VECTOR.with(|slot| {
1787 *slot.borrow_mut() = vec![0; 200];
1791 let mut m = HashMap::new();
1793 DROP_VECTOR.with(|v| {
1795 assert_eq!(v.borrow()[i], 0);
1800 let d1 = Dropable::new(i);
1801 let d2 = Dropable::new(i+100);
1805 DROP_VECTOR.with(|v| {
1807 assert_eq!(v.borrow()[i], 1);
1812 let k = Dropable::new(i);
1813 let v = m.remove(&k);
1815 assert!(v.is_some());
1817 DROP_VECTOR.with(|v| {
1818 assert_eq!(v.borrow()[i], 1);
1819 assert_eq!(v.borrow()[i+100], 1);
1823 DROP_VECTOR.with(|v| {
1825 assert_eq!(v.borrow()[i], 0);
1826 assert_eq!(v.borrow()[i+100], 0);
1830 assert_eq!(v.borrow()[i], 1);
1831 assert_eq!(v.borrow()[i+100], 1);
1836 DROP_VECTOR.with(|v| {
1838 assert_eq!(v.borrow()[i], 0);
1844 fn test_move_iter_drops() {
1845 DROP_VECTOR.with(|v| {
1846 *v.borrow_mut() = vec![0; 200];
1850 let mut hm = HashMap::new();
1852 DROP_VECTOR.with(|v| {
1854 assert_eq!(v.borrow()[i], 0);
1859 let d1 = Dropable::new(i);
1860 let d2 = Dropable::new(i+100);
1864 DROP_VECTOR.with(|v| {
1866 assert_eq!(v.borrow()[i], 1);
1873 // By the way, ensure that cloning doesn't screw up the dropping.
1877 let mut half = hm.into_iter().take(50);
1879 DROP_VECTOR.with(|v| {
1881 assert_eq!(v.borrow()[i], 1);
1885 for _ in half.by_ref() {}
1887 DROP_VECTOR.with(|v| {
1888 let nk = (0..100).filter(|&i| {
1892 let nv = (0..100).filter(|&i| {
1893 v.borrow()[i+100] == 1
1901 DROP_VECTOR.with(|v| {
1903 assert_eq!(v.borrow()[i], 0);
1909 fn test_empty_pop() {
1910 let mut m: HashMap<isize, bool> = HashMap::new();
1911 assert_eq!(m.remove(&0), None);
1915 fn test_lots_of_insertions() {
1916 let mut m = HashMap::new();
1918 // Try this a few times to make sure we never screw up the hashmap's
1921 assert!(m.is_empty());
1924 assert!(m.insert(i, i).is_none());
1928 assert_eq!(r, Some(&j));
1931 for j in i+1..1001 {
1933 assert_eq!(r, None);
1937 for i in 1001..2001 {
1938 assert!(!m.contains_key(&i));
1943 assert!(m.remove(&i).is_some());
1946 assert!(!m.contains_key(&j));
1949 for j in i+1..1001 {
1950 assert!(m.contains_key(&j));
1955 assert!(!m.contains_key(&i));
1959 assert!(m.insert(i, i).is_none());
1963 for i in (1..1001).rev() {
1964 assert!(m.remove(&i).is_some());
1967 assert!(!m.contains_key(&j));
1971 assert!(m.contains_key(&j));
1978 fn test_find_mut() {
1979 let mut m = HashMap::new();
1980 assert!(m.insert(1, 12).is_none());
1981 assert!(m.insert(2, 8).is_none());
1982 assert!(m.insert(5, 14).is_none());
1984 match m.get_mut(&5) {
1985 None => panic!(), Some(x) => *x = new
1987 assert_eq!(m.get(&5), Some(&new));
1991 fn test_insert_overwrite() {
1992 let mut m = HashMap::new();
1993 assert!(m.insert(1, 2).is_none());
1994 assert_eq!(*m.get(&1).unwrap(), 2);
1995 assert!(!m.insert(1, 3).is_none());
1996 assert_eq!(*m.get(&1).unwrap(), 3);
2000 fn test_insert_conflicts() {
2001 let mut m = HashMap::with_capacity(4);
2002 assert!(m.insert(1, 2).is_none());
2003 assert!(m.insert(5, 3).is_none());
2004 assert!(m.insert(9, 4).is_none());
2005 assert_eq!(*m.get(&9).unwrap(), 4);
2006 assert_eq!(*m.get(&5).unwrap(), 3);
2007 assert_eq!(*m.get(&1).unwrap(), 2);
2011 fn test_conflict_remove() {
2012 let mut m = HashMap::with_capacity(4);
2013 assert!(m.insert(1, 2).is_none());
2014 assert_eq!(*m.get(&1).unwrap(), 2);
2015 assert!(m.insert(5, 3).is_none());
2016 assert_eq!(*m.get(&1).unwrap(), 2);
2017 assert_eq!(*m.get(&5).unwrap(), 3);
2018 assert!(m.insert(9, 4).is_none());
2019 assert_eq!(*m.get(&1).unwrap(), 2);
2020 assert_eq!(*m.get(&5).unwrap(), 3);
2021 assert_eq!(*m.get(&9).unwrap(), 4);
2022 assert!(m.remove(&1).is_some());
2023 assert_eq!(*m.get(&9).unwrap(), 4);
2024 assert_eq!(*m.get(&5).unwrap(), 3);
2028 fn test_is_empty() {
2029 let mut m = HashMap::with_capacity(4);
2030 assert!(m.insert(1, 2).is_none());
2031 assert!(!m.is_empty());
2032 assert!(m.remove(&1).is_some());
2033 assert!(m.is_empty());
2038 let mut m = HashMap::new();
2040 assert_eq!(m.remove(&1), Some(2));
2041 assert_eq!(m.remove(&1), None);
2046 let mut m = HashMap::with_capacity(4);
2048 assert!(m.insert(i, i*2).is_none());
2050 assert_eq!(m.len(), 32);
2052 let mut observed: u32 = 0;
2055 assert_eq!(*v, *k * 2);
2056 observed |= 1 << *k;
2058 assert_eq!(observed, 0xFFFF_FFFF);
2063 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
2064 let map: HashMap<_, _> = vec.into_iter().collect();
2065 let keys: Vec<_> = map.keys().cloned().collect();
2066 assert_eq!(keys.len(), 3);
2067 assert!(keys.contains(&1));
2068 assert!(keys.contains(&2));
2069 assert!(keys.contains(&3));
2074 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
2075 let map: HashMap<_, _> = vec.into_iter().collect();
2076 let values: Vec<_> = map.values().cloned().collect();
2077 assert_eq!(values.len(), 3);
2078 assert!(values.contains(&'a'));
2079 assert!(values.contains(&'b'));
2080 assert!(values.contains(&'c'));
2085 let mut m = HashMap::new();
2086 assert!(m.get(&1).is_none());
2090 Some(v) => assert_eq!(*v, 2)
2096 let mut m1 = HashMap::new();
2101 let mut m2 = HashMap::new();
2114 let mut map = HashMap::new();
2115 let empty: HashMap<i32, i32> = HashMap::new();
2120 let map_str = format!("{:?}", map);
2122 assert!(map_str == "{1: 2, 3: 4}" ||
2123 map_str == "{3: 4, 1: 2}");
2124 assert_eq!(format!("{:?}", empty), "{}");
2129 let mut m = HashMap::new();
2131 assert_eq!(m.len(), 0);
2132 assert!(m.is_empty());
2135 let old_cap = m.table.capacity();
2136 while old_cap == m.table.capacity() {
2141 assert_eq!(m.len(), i);
2142 assert!(!m.is_empty());
2146 fn test_behavior_resize_policy() {
2147 let mut m = HashMap::new();
2149 assert_eq!(m.len(), 0);
2150 assert_eq!(m.table.capacity(), 0);
2151 assert!(m.is_empty());
2155 assert!(m.is_empty());
2156 let initial_cap = m.table.capacity();
2157 m.reserve(initial_cap);
2158 let cap = m.table.capacity();
2160 assert_eq!(cap, initial_cap * 2);
2163 for _ in 0..cap * 3 / 4 {
2167 // three quarters full
2169 assert_eq!(m.len(), i);
2170 assert_eq!(m.table.capacity(), cap);
2172 for _ in 0..cap / 4 {
2178 let new_cap = m.table.capacity();
2179 assert_eq!(new_cap, cap * 2);
2181 for _ in 0..cap / 2 - 1 {
2184 assert_eq!(m.table.capacity(), new_cap);
2186 // A little more than one quarter full.
2188 assert_eq!(m.table.capacity(), cap);
2189 // again, a little more than half full
2190 for _ in 0..cap / 2 - 1 {
2196 assert_eq!(m.len(), i);
2197 assert!(!m.is_empty());
2198 assert_eq!(m.table.capacity(), initial_cap);
2202 fn test_reserve_shrink_to_fit() {
2203 let mut m = HashMap::new();
2206 assert!(m.capacity() >= m.len());
2212 let usable_cap = m.capacity();
2213 for i in 128..(128 + 256) {
2215 assert_eq!(m.capacity(), usable_cap);
2218 for i in 100..(128 + 256) {
2219 assert_eq!(m.remove(&i), Some(i));
2223 assert_eq!(m.len(), 100);
2224 assert!(!m.is_empty());
2225 assert!(m.capacity() >= m.len());
2228 assert_eq!(m.remove(&i), Some(i));
2233 assert_eq!(m.len(), 1);
2234 assert!(m.capacity() >= m.len());
2235 assert_eq!(m.remove(&0), Some(0));
2239 fn test_from_iter() {
2240 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2242 let map: HashMap<_, _> = xs.iter().cloned().collect();
2244 for &(k, v) in &xs {
2245 assert_eq!(map.get(&k), Some(&v));
2250 fn test_size_hint() {
2251 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2253 let map: HashMap<_, _> = xs.iter().cloned().collect();
2255 let mut iter = map.iter();
2257 for _ in iter.by_ref().take(3) {}
2259 assert_eq!(iter.size_hint(), (3, Some(3)));
2263 fn test_iter_len() {
2264 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2266 let map: HashMap<_, _> = xs.iter().cloned().collect();
2268 let mut iter = map.iter();
2270 for _ in iter.by_ref().take(3) {}
2272 assert_eq!(iter.len(), 3);
2276 fn test_mut_size_hint() {
2277 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2279 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2281 let mut iter = map.iter_mut();
2283 for _ in iter.by_ref().take(3) {}
2285 assert_eq!(iter.size_hint(), (3, Some(3)));
2289 fn test_iter_mut_len() {
2290 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2292 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2294 let mut iter = map.iter_mut();
2296 for _ in iter.by_ref().take(3) {}
2298 assert_eq!(iter.len(), 3);
2303 let mut map = HashMap::new();
2309 assert_eq!(map[&2], 1);
2314 fn test_index_nonexistent() {
2315 let mut map = HashMap::new();
2326 let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2328 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2330 // Existing key (insert)
2331 match map.entry(1) {
2332 Vacant(_) => unreachable!(),
2333 Occupied(mut view) => {
2334 assert_eq!(view.get(), &10);
2335 assert_eq!(view.insert(100), 10);
2338 assert_eq!(map.get(&1).unwrap(), &100);
2339 assert_eq!(map.len(), 6);
2342 // Existing key (update)
2343 match map.entry(2) {
2344 Vacant(_) => unreachable!(),
2345 Occupied(mut view) => {
2346 let v = view.get_mut();
2347 let new_v = (*v) * 10;
2351 assert_eq!(map.get(&2).unwrap(), &200);
2352 assert_eq!(map.len(), 6);
2354 // Existing key (take)
2355 match map.entry(3) {
2356 Vacant(_) => unreachable!(),
2358 assert_eq!(view.remove(), 30);
2361 assert_eq!(map.get(&3), None);
2362 assert_eq!(map.len(), 5);
2365 // Inexistent key (insert)
2366 match map.entry(10) {
2367 Occupied(_) => unreachable!(),
2369 assert_eq!(*view.insert(1000), 1000);
2372 assert_eq!(map.get(&10).unwrap(), &1000);
2373 assert_eq!(map.len(), 6);
2377 fn test_entry_take_doesnt_corrupt() {
2378 #![allow(deprecated)] //rand
2380 fn check(m: &HashMap<isize, ()>) {
2382 assert!(m.contains_key(k),
2383 "{} is in keys() but not in the map?", k);
2387 let mut m = HashMap::new();
2388 let mut rng = thread_rng();
2390 // Populate the map with some items.
2392 let x = rng.gen_range(-10, 10);
2397 let x = rng.gen_range(-10, 10);
2401 println!("{}: remove {}", i, x);
2411 fn test_extend_ref() {
2412 let mut a = HashMap::new();
2414 let mut b = HashMap::new();
2416 b.insert(3, "three");
2420 assert_eq!(a.len(), 3);
2421 assert_eq!(a[&1], "one");
2422 assert_eq!(a[&2], "two");
2423 assert_eq!(a[&3], "three");
2427 fn test_capacity_not_less_than_len() {
2428 let mut a = HashMap::new();
2436 assert!(a.capacity() > a.len());
2438 let free = a.capacity() - a.len();
2444 assert_eq!(a.len(), a.capacity());
2446 // Insert at capacity should cause allocation.
2448 assert!(a.capacity() > a.len());
2452 fn test_occupied_entry_key() {
2453 let mut a = HashMap::new();
2454 let key = "hello there";
2455 let value = "value goes here";
2456 assert!(a.is_empty());
2457 a.insert(key.clone(), value.clone());
2458 assert_eq!(a.len(), 1);
2459 assert_eq!(a[key], value);
2461 match a.entry(key.clone()) {
2462 Vacant(_) => panic!(),
2463 Occupied(e) => assert_eq!(key, *e.key()),
2465 assert_eq!(a.len(), 1);
2466 assert_eq!(a[key], value);
2470 fn test_vacant_entry_key() {
2471 let mut a = HashMap::new();
2472 let key = "hello there";
2473 let value = "value goes here";
2475 assert!(a.is_empty());
2476 match a.entry(key.clone()) {
2477 Occupied(_) => panic!(),
2479 assert_eq!(key, *e.key());
2480 e.insert(value.clone());
2483 assert_eq!(a.len(), 1);
2484 assert_eq!(a[key], value);