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 /// Deprecated, renamed to `with_hasher`
597 #[unstable(feature = "hashmap_hasher", reason = "hasher stuff is unclear",
599 #[rustc_deprecated(since = "1.7.0", reason = "renamed to with_hasher")]
600 pub fn with_hash_state(hash_state: S) -> HashMap<K, V, S> {
601 HashMap::with_hasher(hash_state)
604 /// Creates an empty HashMap with space for at least `capacity`
605 /// elements, using `hasher` to hash the keys.
607 /// Warning: `hasher` is normally randomly generated, and
608 /// is designed to allow HashMaps to be resistant to attacks that
609 /// cause many collisions and very poor performance. Setting it
610 /// manually using this function can expose a DoS attack vector.
615 /// use std::collections::HashMap;
616 /// use std::collections::hash_map::RandomState;
618 /// let s = RandomState::new();
619 /// let mut map = HashMap::with_capacity_and_hasher(10, s);
620 /// map.insert(1, 2);
623 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
624 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S)
625 -> HashMap<K, V, S> {
626 let resize_policy = DefaultResizePolicy::new();
627 let min_cap = max(INITIAL_CAPACITY, resize_policy.min_capacity(capacity));
628 let internal_cap = min_cap.checked_next_power_of_two().expect("capacity overflow");
629 assert!(internal_cap >= capacity, "capacity overflow");
631 hash_builder: hash_builder,
632 resize_policy: resize_policy,
633 table: RawTable::new(internal_cap),
637 /// Deprecated, renamed to `with_capacity_and_hasher`
639 #[unstable(feature = "hashmap_hasher", reason = "hasher stuff is unclear",
641 #[rustc_deprecated(since = "1.7.0",
642 reason = "renamed to with_capacity_and_hasher")]
643 pub fn with_capacity_and_hash_state(capacity: usize, hash_state: S)
644 -> HashMap<K, V, S> {
645 HashMap::with_capacity_and_hasher(capacity, hash_state)
648 /// Returns a reference to the map's hasher.
649 #[unstable(feature = "hashmap_public_hasher", reason = "don't want to make insta-stable",
651 pub fn hasher(&self) -> &S {
655 /// Returns the number of elements the map can hold without reallocating.
657 /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
658 /// more, but is guaranteed to be able to hold at least this many.
663 /// use std::collections::HashMap;
664 /// let map: HashMap<isize, isize> = HashMap::with_capacity(100);
665 /// assert!(map.capacity() >= 100);
668 #[stable(feature = "rust1", since = "1.0.0")]
669 pub fn capacity(&self) -> usize {
670 self.resize_policy.usable_capacity(self.table.capacity())
673 /// Reserves capacity for at least `additional` more elements to be inserted
674 /// in the `HashMap`. The collection may reserve more space to avoid
675 /// frequent reallocations.
679 /// Panics if the new allocation size overflows `usize`.
684 /// use std::collections::HashMap;
685 /// let mut map: HashMap<&str, isize> = HashMap::new();
688 #[stable(feature = "rust1", since = "1.0.0")]
689 pub fn reserve(&mut self, additional: usize) {
690 let new_size = self.len().checked_add(additional).expect("capacity overflow");
691 let min_cap = self.resize_policy.min_capacity(new_size);
693 // An invalid value shouldn't make us run out of space. This includes
694 // an overflow check.
695 assert!(new_size <= min_cap);
697 if self.table.capacity() < min_cap {
698 let new_capacity = max(min_cap.next_power_of_two(), INITIAL_CAPACITY);
699 self.resize(new_capacity);
703 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
704 /// 1) Make sure the new capacity is enough for all the elements, accounting
705 /// for the load factor.
706 /// 2) Ensure new_capacity is a power of two or zero.
707 fn resize(&mut self, new_capacity: usize) {
708 assert!(self.table.size() <= new_capacity);
709 assert!(new_capacity.is_power_of_two() || new_capacity == 0);
711 let mut old_table = replace(&mut self.table, RawTable::new(new_capacity));
712 let old_size = old_table.size();
714 if old_table.capacity() == 0 || old_table.size() == 0 {
719 // Specialization of the other branch.
720 let mut bucket = Bucket::first(&mut old_table);
722 // "So a few of the first shall be last: for many be called,
725 // We'll most likely encounter a few buckets at the beginning that
726 // have their initial buckets near the end of the table. They were
727 // placed at the beginning as the probe wrapped around the table
728 // during insertion. We must skip forward to a bucket that won't
729 // get reinserted too early and won't unfairly steal others spot.
730 // This eliminates the need for robin hood.
732 bucket = match bucket.peek() {
734 if full.distance() == 0 {
735 // This bucket occupies its ideal spot.
736 // It indicates the start of another "cluster".
737 bucket = full.into_bucket();
740 // Leaving this bucket in the last cluster for later.
744 // Encountered a hole between clusters.
751 // This is how the buckets might be laid out in memory:
752 // ($ marks an initialized bucket)
754 // |$$$_$$$$$$_$$$$$|
756 // But we've skipped the entire initial cluster of buckets
757 // and will continue iteration in this order:
760 // ^ wrap around once end is reached
763 // ^ exit once table.size == 0
765 bucket = match bucket.peek() {
767 let h = bucket.hash();
768 let (b, k, v) = bucket.take();
769 self.insert_hashed_ordered(h, k, v);
771 let t = b.table(); // FIXME "lifetime too short".
772 if t.size() == 0 { break }
776 Empty(b) => b.into_bucket()
781 assert_eq!(self.table.size(), old_size);
784 /// Shrinks the capacity of the map as much as possible. It will drop
785 /// down as much as possible while maintaining the internal rules
786 /// and possibly leaving some space in accordance with the resize policy.
791 /// use std::collections::HashMap;
793 /// let mut map: HashMap<isize, isize> = HashMap::with_capacity(100);
794 /// map.insert(1, 2);
795 /// map.insert(3, 4);
796 /// assert!(map.capacity() >= 100);
797 /// map.shrink_to_fit();
798 /// assert!(map.capacity() >= 2);
800 #[stable(feature = "rust1", since = "1.0.0")]
801 pub fn shrink_to_fit(&mut self) {
802 let min_capacity = self.resize_policy.min_capacity(self.len());
803 let min_capacity = max(min_capacity.next_power_of_two(), INITIAL_CAPACITY);
805 // An invalid value shouldn't make us run out of space.
806 debug_assert!(self.len() <= min_capacity);
808 if self.table.capacity() != min_capacity {
809 let old_table = replace(&mut self.table, RawTable::new(min_capacity));
810 let old_size = old_table.size();
812 // Shrink the table. Naive algorithm for resizing:
813 for (h, k, v) in old_table.into_iter() {
814 self.insert_hashed_nocheck(h, k, v);
817 debug_assert_eq!(self.table.size(), old_size);
821 /// Insert a pre-hashed key-value pair, without first checking
822 /// that there's enough room in the buckets. Returns a reference to the
823 /// newly insert value.
825 /// If the key already exists, the hashtable will be returned untouched
826 /// and a reference to the existing element will be returned.
827 fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> &mut V {
828 self.insert_or_replace_with(hash, k, v, |_, _, _, _| ())
831 fn insert_or_replace_with<'a, F>(&'a mut self,
835 mut found_existing: F)
837 F: FnMut(&mut K, &mut V, K, V),
839 // Worst case, we'll find one empty bucket among `size + 1` buckets.
840 let size = self.table.size();
841 let mut probe = Bucket::new(&mut self.table, hash);
842 let ib = probe.index();
845 let mut bucket = match probe.peek() {
848 return bucket.put(hash, k, v).into_mut_refs().1;
850 Full(bucket) => bucket
854 if bucket.hash() == hash {
856 if k == *bucket.read_mut().0 {
857 let (bucket_k, bucket_v) = bucket.into_mut_refs();
858 debug_assert!(k == *bucket_k);
859 // Key already exists. Get its reference.
860 found_existing(bucket_k, bucket_v, k, v);
865 let robin_ib = bucket.index() as isize - bucket.distance() as isize;
867 if (ib as isize) < robin_ib {
868 // Found a luckier bucket than me. Better steal his spot.
869 return robin_hood(bucket, robin_ib as usize, hash, k, v);
872 probe = bucket.next();
873 assert!(probe.index() != ib + size + 1);
877 /// An iterator visiting all keys in arbitrary order.
878 /// Iterator element type is `&'a K`.
883 /// use std::collections::HashMap;
885 /// let mut map = HashMap::new();
886 /// map.insert("a", 1);
887 /// map.insert("b", 2);
888 /// map.insert("c", 3);
890 /// for key in map.keys() {
891 /// println!("{}", key);
894 #[stable(feature = "rust1", since = "1.0.0")]
895 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
896 fn first<A, B>((a, _): (A, B)) -> A { a }
897 let first: fn((&'a K,&'a V)) -> &'a K = first; // coerce to fn ptr
899 Keys { inner: self.iter().map(first) }
902 /// An iterator visiting all values in arbitrary order.
903 /// Iterator element type is `&'a V`.
908 /// use std::collections::HashMap;
910 /// let mut map = HashMap::new();
911 /// map.insert("a", 1);
912 /// map.insert("b", 2);
913 /// map.insert("c", 3);
915 /// for val in map.values() {
916 /// println!("{}", val);
919 #[stable(feature = "rust1", since = "1.0.0")]
920 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
921 fn second<A, B>((_, b): (A, B)) -> B { b }
922 let second: fn((&'a K,&'a V)) -> &'a V = second; // coerce to fn ptr
924 Values { inner: self.iter().map(second) }
927 /// An iterator visiting all key-value pairs in arbitrary order.
928 /// Iterator element type is `(&'a K, &'a V)`.
933 /// use std::collections::HashMap;
935 /// let mut map = HashMap::new();
936 /// map.insert("a", 1);
937 /// map.insert("b", 2);
938 /// map.insert("c", 3);
940 /// for (key, val) in map.iter() {
941 /// println!("key: {} val: {}", key, val);
944 #[stable(feature = "rust1", since = "1.0.0")]
945 pub fn iter(&self) -> Iter<K, V> {
946 Iter { inner: self.table.iter() }
949 /// An iterator visiting all key-value pairs in arbitrary order,
950 /// with mutable references to the values.
951 /// Iterator element type is `(&'a K, &'a mut V)`.
956 /// use std::collections::HashMap;
958 /// let mut map = HashMap::new();
959 /// map.insert("a", 1);
960 /// map.insert("b", 2);
961 /// map.insert("c", 3);
963 /// // Update all values
964 /// for (_, val) in map.iter_mut() {
968 /// for (key, val) in &map {
969 /// println!("key: {} val: {}", key, val);
972 #[stable(feature = "rust1", since = "1.0.0")]
973 pub fn iter_mut(&mut self) -> IterMut<K, V> {
974 IterMut { inner: self.table.iter_mut() }
977 /// Gets the given key's corresponding entry in the map for in-place manipulation.
982 /// use std::collections::HashMap;
984 /// let mut letters = HashMap::new();
986 /// for ch in "a short treatise on fungi".chars() {
987 /// let counter = letters.entry(ch).or_insert(0);
991 /// assert_eq!(letters[&'s'], 2);
992 /// assert_eq!(letters[&'t'], 3);
993 /// assert_eq!(letters[&'u'], 1);
994 /// assert_eq!(letters.get(&'y'), None);
996 #[stable(feature = "rust1", since = "1.0.0")]
997 pub fn entry(&mut self, key: K) -> Entry<K, V> {
1001 let hash = self.make_hash(&key);
1002 search_entry_hashed(&mut self.table, hash, key)
1005 /// Returns the number of elements in the map.
1010 /// use std::collections::HashMap;
1012 /// let mut a = HashMap::new();
1013 /// assert_eq!(a.len(), 0);
1014 /// a.insert(1, "a");
1015 /// assert_eq!(a.len(), 1);
1017 #[stable(feature = "rust1", since = "1.0.0")]
1018 pub fn len(&self) -> usize { self.table.size() }
1020 /// Returns true if the map contains no elements.
1025 /// use std::collections::HashMap;
1027 /// let mut a = HashMap::new();
1028 /// assert!(a.is_empty());
1029 /// a.insert(1, "a");
1030 /// assert!(!a.is_empty());
1033 #[stable(feature = "rust1", since = "1.0.0")]
1034 pub fn is_empty(&self) -> bool { self.len() == 0 }
1036 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
1037 /// allocated memory for reuse.
1042 /// use std::collections::HashMap;
1044 /// let mut a = HashMap::new();
1045 /// a.insert(1, "a");
1046 /// a.insert(2, "b");
1048 /// for (k, v) in a.drain().take(1) {
1049 /// assert!(k == 1 || k == 2);
1050 /// assert!(v == "a" || v == "b");
1053 /// assert!(a.is_empty());
1056 #[stable(feature = "drain", since = "1.6.0")]
1057 pub fn drain(&mut self) -> Drain<K, V> {
1058 fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) }
1059 let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two; // coerce to fn pointer
1062 inner: self.table.drain().map(last_two),
1066 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
1072 /// use std::collections::HashMap;
1074 /// let mut a = HashMap::new();
1075 /// a.insert(1, "a");
1077 /// assert!(a.is_empty());
1079 #[stable(feature = "rust1", since = "1.0.0")]
1081 pub fn clear(&mut self) {
1085 /// Returns a reference to the value corresponding to the key.
1087 /// The key may be any borrowed form of the map's key type, but
1088 /// `Hash` and `Eq` on the borrowed form *must* match those for
1094 /// use std::collections::HashMap;
1096 /// let mut map = HashMap::new();
1097 /// map.insert(1, "a");
1098 /// assert_eq!(map.get(&1), Some(&"a"));
1099 /// assert_eq!(map.get(&2), None);
1101 #[stable(feature = "rust1", since = "1.0.0")]
1102 pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
1103 where K: Borrow<Q>, Q: Hash + Eq
1105 self.search(k).map(|bucket| bucket.into_refs().1)
1108 /// Returns true if the map contains a value for the specified key.
1110 /// The key may be any borrowed form of the map's key type, but
1111 /// `Hash` and `Eq` on the borrowed form *must* match those for
1117 /// use std::collections::HashMap;
1119 /// let mut map = HashMap::new();
1120 /// map.insert(1, "a");
1121 /// assert_eq!(map.contains_key(&1), true);
1122 /// assert_eq!(map.contains_key(&2), false);
1124 #[stable(feature = "rust1", since = "1.0.0")]
1125 pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
1126 where K: Borrow<Q>, Q: Hash + Eq
1128 self.search(k).is_some()
1131 /// Returns a mutable reference to the value corresponding to the key.
1133 /// The key may be any borrowed form of the map's key type, but
1134 /// `Hash` and `Eq` on the borrowed form *must* match those for
1140 /// use std::collections::HashMap;
1142 /// let mut map = HashMap::new();
1143 /// map.insert(1, "a");
1144 /// if let Some(x) = map.get_mut(&1) {
1147 /// assert_eq!(map[&1], "b");
1149 #[stable(feature = "rust1", since = "1.0.0")]
1150 pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
1151 where K: Borrow<Q>, Q: Hash + Eq
1153 self.search_mut(k).map(|bucket| bucket.into_mut_refs().1)
1156 /// Inserts a key-value pair into the map.
1158 /// If the map did not have this key present, `None` is returned.
1160 /// If the map did have this key present, the value is updated, and the old
1161 /// value is returned. The key is not updated, though; this matters for
1162 /// types that can be `==` without being identical. See the [module-level
1163 /// documentation] for more.
1165 /// [module-level documentation]: index.html#insert-and-complex-keys
1170 /// use std::collections::HashMap;
1172 /// let mut map = HashMap::new();
1173 /// assert_eq!(map.insert(37, "a"), None);
1174 /// assert_eq!(map.is_empty(), false);
1176 /// map.insert(37, "b");
1177 /// assert_eq!(map.insert(37, "c"), Some("b"));
1178 /// assert_eq!(map[&37], "c");
1180 #[stable(feature = "rust1", since = "1.0.0")]
1181 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
1182 let hash = self.make_hash(&k);
1185 let mut retval = None;
1186 self.insert_or_replace_with(hash, k, v, |_, val_ref, _, val| {
1187 retval = Some(replace(val_ref, val));
1192 /// Removes a key from the map, returning the value at the key if the key
1193 /// was previously in the map.
1195 /// The key may be any borrowed form of the map's key type, but
1196 /// `Hash` and `Eq` on the borrowed form *must* match those for
1202 /// use std::collections::HashMap;
1204 /// let mut map = HashMap::new();
1205 /// map.insert(1, "a");
1206 /// assert_eq!(map.remove(&1), Some("a"));
1207 /// assert_eq!(map.remove(&1), None);
1209 #[stable(feature = "rust1", since = "1.0.0")]
1210 pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
1211 where K: Borrow<Q>, Q: Hash + Eq
1213 if self.table.size() == 0 {
1217 self.search_mut(k).map(|bucket| pop_internal(bucket).1)
1221 fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHash, k: K)
1224 // Worst case, we'll find one empty bucket among `size + 1` buckets.
1225 let size = table.size();
1226 let mut probe = Bucket::new(table, hash);
1227 let ib = probe.index();
1230 let bucket = match probe.peek() {
1233 return Vacant(VacantEntry {
1236 elem: NoElem(bucket),
1239 Full(bucket) => bucket
1243 if bucket.hash() == hash {
1245 if k == *bucket.read().0 {
1246 return Occupied(OccupiedEntry{
1252 let robin_ib = bucket.index() as isize - bucket.distance() as isize;
1254 if (ib as isize) < robin_ib {
1255 // Found a luckier bucket than me. Better steal his spot.
1256 return Vacant(VacantEntry {
1259 elem: NeqElem(bucket, robin_ib as usize),
1263 probe = bucket.next();
1264 assert!(probe.index() != ib + size + 1);
1268 #[stable(feature = "rust1", since = "1.0.0")]
1269 impl<K, V, S> PartialEq for HashMap<K, V, S>
1270 where K: Eq + Hash, V: PartialEq, S: BuildHasher
1272 fn eq(&self, other: &HashMap<K, V, S>) -> bool {
1273 if self.len() != other.len() { return false; }
1275 self.iter().all(|(key, value)|
1276 other.get(key).map_or(false, |v| *value == *v)
1281 #[stable(feature = "rust1", since = "1.0.0")]
1282 impl<K, V, S> Eq for HashMap<K, V, S>
1283 where K: Eq + Hash, V: Eq, S: BuildHasher
1286 #[stable(feature = "rust1", since = "1.0.0")]
1287 impl<K, V, S> Debug for HashMap<K, V, S>
1288 where K: Eq + Hash + Debug, V: Debug, S: BuildHasher
1290 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1291 f.debug_map().entries(self.iter()).finish()
1295 #[stable(feature = "rust1", since = "1.0.0")]
1296 impl<K, V, S> Default for HashMap<K, V, S>
1298 S: BuildHasher + Default,
1300 fn default() -> HashMap<K, V, S> {
1301 HashMap::with_hasher(Default::default())
1305 #[stable(feature = "rust1", since = "1.0.0")]
1306 impl<'a, K, Q: ?Sized, V, S> Index<&'a Q> for HashMap<K, V, S>
1307 where K: Eq + Hash + Borrow<Q>,
1314 fn index(&self, index: &Q) -> &V {
1315 self.get(index).expect("no entry found for key")
1319 /// HashMap iterator.
1320 #[stable(feature = "rust1", since = "1.0.0")]
1321 pub struct Iter<'a, K: 'a, V: 'a> {
1322 inner: table::Iter<'a, K, V>
1325 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1326 #[stable(feature = "rust1", since = "1.0.0")]
1327 impl<'a, K, V> Clone for Iter<'a, K, V> {
1328 fn clone(&self) -> Iter<'a, K, V> {
1330 inner: self.inner.clone()
1335 /// HashMap mutable values iterator.
1336 #[stable(feature = "rust1", since = "1.0.0")]
1337 pub struct IterMut<'a, K: 'a, V: 'a> {
1338 inner: table::IterMut<'a, K, V>
1341 /// HashMap move iterator.
1342 #[stable(feature = "rust1", since = "1.0.0")]
1343 pub struct IntoIter<K, V> {
1344 inner: iter::Map<table::IntoIter<K, V>, fn((SafeHash, K, V)) -> (K, V)>
1347 /// HashMap keys iterator.
1348 #[stable(feature = "rust1", since = "1.0.0")]
1349 pub struct Keys<'a, K: 'a, V: 'a> {
1350 inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
1353 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1354 #[stable(feature = "rust1", since = "1.0.0")]
1355 impl<'a, K, V> Clone for Keys<'a, K, V> {
1356 fn clone(&self) -> Keys<'a, K, V> {
1358 inner: self.inner.clone()
1363 /// HashMap values iterator.
1364 #[stable(feature = "rust1", since = "1.0.0")]
1365 pub struct Values<'a, K: 'a, V: 'a> {
1366 inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
1369 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1370 #[stable(feature = "rust1", since = "1.0.0")]
1371 impl<'a, K, V> Clone for Values<'a, K, V> {
1372 fn clone(&self) -> Values<'a, K, V> {
1374 inner: self.inner.clone()
1379 /// HashMap drain iterator.
1380 #[stable(feature = "drain", since = "1.6.0")]
1381 pub struct Drain<'a, K: 'a, V: 'a> {
1382 inner: iter::Map<table::Drain<'a, K, V>, fn((SafeHash, K, V)) -> (K, V)>
1385 /// A view into a single occupied location in a HashMap.
1386 #[stable(feature = "rust1", since = "1.0.0")]
1387 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
1388 elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
1391 /// A view into a single empty location in a HashMap.
1392 #[stable(feature = "rust1", since = "1.0.0")]
1393 pub struct VacantEntry<'a, K: 'a, V: 'a> {
1396 elem: VacantEntryState<K, V, &'a mut RawTable<K, V>>,
1399 /// A view into a single location in a map, which may be vacant or occupied.
1400 #[stable(feature = "rust1", since = "1.0.0")]
1401 pub enum Entry<'a, K: 'a, V: 'a> {
1402 /// An occupied Entry.
1403 #[stable(feature = "rust1", since = "1.0.0")]
1405 #[cfg_attr(not(stage0), stable(feature = "rust1", since = "1.0.0"))] OccupiedEntry<'a, K, V>
1409 #[stable(feature = "rust1", since = "1.0.0")]
1411 #[cfg_attr(not(stage0), stable(feature = "rust1", since = "1.0.0"))] VacantEntry<'a, K, V>
1415 /// Possible states of a VacantEntry.
1416 enum VacantEntryState<K, V, M> {
1417 /// The index is occupied, but the key to insert has precedence,
1418 /// and will kick the current one out on insertion.
1419 NeqElem(FullBucket<K, V, M>, usize),
1420 /// The index is genuinely vacant.
1421 NoElem(EmptyBucket<K, V, M>),
1424 #[stable(feature = "rust1", since = "1.0.0")]
1425 impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S>
1426 where K: Eq + Hash, S: BuildHasher
1428 type Item = (&'a K, &'a V);
1429 type IntoIter = Iter<'a, K, V>;
1431 fn into_iter(self) -> Iter<'a, K, V> {
1436 #[stable(feature = "rust1", since = "1.0.0")]
1437 impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S>
1438 where K: Eq + Hash, S: BuildHasher
1440 type Item = (&'a K, &'a mut V);
1441 type IntoIter = IterMut<'a, K, V>;
1443 fn into_iter(mut self) -> IterMut<'a, K, V> {
1448 #[stable(feature = "rust1", since = "1.0.0")]
1449 impl<K, V, S> IntoIterator for HashMap<K, V, S>
1450 where K: Eq + Hash, S: BuildHasher
1453 type IntoIter = IntoIter<K, V>;
1455 /// Creates a consuming iterator, that is, one that moves each key-value
1456 /// pair out of the map in arbitrary order. The map cannot be used after
1462 /// use std::collections::HashMap;
1464 /// let mut map = HashMap::new();
1465 /// map.insert("a", 1);
1466 /// map.insert("b", 2);
1467 /// map.insert("c", 3);
1469 /// // Not possible with .iter()
1470 /// let vec: Vec<(&str, isize)> = map.into_iter().collect();
1472 fn into_iter(self) -> IntoIter<K, V> {
1473 fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) }
1474 let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two;
1477 inner: self.table.into_iter().map(last_two)
1482 #[stable(feature = "rust1", since = "1.0.0")]
1483 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1484 type Item = (&'a K, &'a V);
1486 #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1487 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1489 #[stable(feature = "rust1", since = "1.0.0")]
1490 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
1491 #[inline] fn len(&self) -> usize { self.inner.len() }
1494 #[stable(feature = "rust1", since = "1.0.0")]
1495 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1496 type Item = (&'a K, &'a mut V);
1498 #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1499 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1501 #[stable(feature = "rust1", since = "1.0.0")]
1502 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
1503 #[inline] fn len(&self) -> usize { self.inner.len() }
1506 #[stable(feature = "rust1", since = "1.0.0")]
1507 impl<K, V> Iterator for IntoIter<K, V> {
1510 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1511 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1513 #[stable(feature = "rust1", since = "1.0.0")]
1514 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
1515 #[inline] fn len(&self) -> usize { self.inner.len() }
1518 #[stable(feature = "rust1", since = "1.0.0")]
1519 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1522 #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
1523 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1525 #[stable(feature = "rust1", since = "1.0.0")]
1526 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
1527 #[inline] fn len(&self) -> usize { self.inner.len() }
1530 #[stable(feature = "rust1", since = "1.0.0")]
1531 impl<'a, K, V> Iterator for Values<'a, K, V> {
1534 #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
1535 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1537 #[stable(feature = "rust1", since = "1.0.0")]
1538 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
1539 #[inline] fn len(&self) -> usize { self.inner.len() }
1542 #[stable(feature = "rust1", since = "1.0.0")]
1543 impl<'a, K, V> Iterator for Drain<'a, K, V> {
1546 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1547 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1549 #[stable(feature = "rust1", since = "1.0.0")]
1550 impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> {
1551 #[inline] fn len(&self) -> usize { self.inner.len() }
1554 impl<'a, K, V> Entry<'a, K, V> {
1555 #[stable(feature = "rust1", since = "1.0.0")]
1556 /// Ensures a value is in the entry by inserting the default if empty, and returns
1557 /// a mutable reference to the value in the entry.
1558 pub fn or_insert(self, default: V) -> &'a mut V {
1560 Occupied(entry) => entry.into_mut(),
1561 Vacant(entry) => entry.insert(default),
1565 #[stable(feature = "rust1", since = "1.0.0")]
1566 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1567 /// and returns a mutable reference to the value in the entry.
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()),
1576 impl<'a, K, V> OccupiedEntry<'a, K, V> {
1577 /// Gets a reference to the value in the entry.
1578 #[stable(feature = "rust1", since = "1.0.0")]
1579 pub fn get(&self) -> &V {
1583 /// Gets a mutable reference to the value in the entry.
1584 #[stable(feature = "rust1", since = "1.0.0")]
1585 pub fn get_mut(&mut self) -> &mut V {
1586 self.elem.read_mut().1
1589 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1590 /// with a lifetime bound to the map itself
1591 #[stable(feature = "rust1", since = "1.0.0")]
1592 pub fn into_mut(self) -> &'a mut V {
1593 self.elem.into_mut_refs().1
1596 /// Sets the value of the entry, and returns the entry's old value
1597 #[stable(feature = "rust1", since = "1.0.0")]
1598 pub fn insert(&mut self, mut value: V) -> V {
1599 let old_value = self.get_mut();
1600 mem::swap(&mut value, old_value);
1604 /// Takes the value out of the entry, and returns it
1605 #[stable(feature = "rust1", since = "1.0.0")]
1606 pub fn remove(self) -> V {
1607 pop_internal(self.elem).1
1611 impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
1612 /// Sets the value of the entry with the VacantEntry's key,
1613 /// and returns a mutable reference to it
1614 #[stable(feature = "rust1", since = "1.0.0")]
1615 pub fn insert(self, value: V) -> &'a mut V {
1617 NeqElem(bucket, ib) => {
1618 robin_hood(bucket, ib, self.hash, self.key, value)
1621 bucket.put(self.hash, self.key, value).into_mut_refs().1
1627 #[stable(feature = "rust1", since = "1.0.0")]
1628 impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
1629 where K: Eq + Hash, S: BuildHasher + Default
1631 fn from_iter<T: IntoIterator<Item=(K, V)>>(iterable: T) -> HashMap<K, V, S> {
1632 let iter = iterable.into_iter();
1633 let lower = iter.size_hint().0;
1634 let mut map = HashMap::with_capacity_and_hasher(lower, Default::default());
1640 #[stable(feature = "rust1", since = "1.0.0")]
1641 impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S>
1642 where K: Eq + Hash, S: BuildHasher
1644 fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
1645 for (k, v) in iter {
1651 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
1652 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S>
1653 where K: Eq + Hash + Copy, V: Copy, S: BuildHasher
1655 fn extend<T: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: T) {
1656 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1660 /// `RandomState` is the default state for `HashMap` types.
1662 /// A particular instance `RandomState` will create the same instances of
1663 /// `Hasher`, but the hashers created by two different `RandomState`
1664 /// instances are unlikely to produce the same result for the same values.
1666 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1667 pub struct RandomState {
1673 /// Constructs a new `RandomState` that is initialized with random keys.
1675 #[allow(deprecated)] // rand
1676 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1677 pub fn new() -> RandomState {
1678 let mut r = rand::thread_rng();
1679 RandomState { k0: r.gen(), k1: r.gen() }
1683 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1684 impl BuildHasher for RandomState {
1685 type Hasher = SipHasher;
1687 fn build_hasher(&self) -> SipHasher {
1688 SipHasher::new_with_keys(self.k0, self.k1)
1692 #[stable(feature = "rust1", since = "1.0.0")]
1693 impl Default for RandomState {
1695 fn default() -> RandomState {
1700 impl<K, S, Q: ?Sized> super::Recover<Q> for HashMap<K, (), S>
1701 where K: Eq + Hash + Borrow<Q>, S: BuildHasher, Q: Eq + Hash
1705 fn get(&self, key: &Q) -> Option<&K> {
1706 self.search(key).map(|bucket| bucket.into_refs().0)
1709 fn take(&mut self, key: &Q) -> Option<K> {
1710 if self.table.size() == 0 {
1714 self.search_mut(key).map(|bucket| pop_internal(bucket).0)
1717 fn replace(&mut self, key: K) -> Option<K> {
1718 let hash = self.make_hash(&key);
1721 let mut retkey = None;
1722 self.insert_or_replace_with(hash, key, (), |key_ref, _, key, _| {
1723 retkey = Some(replace(key_ref, key));
1734 use super::Entry::{Occupied, Vacant};
1736 use rand::{thread_rng, Rng};
1739 fn test_create_capacity_zero() {
1740 let mut m = HashMap::with_capacity(0);
1742 assert!(m.insert(1, 1).is_none());
1744 assert!(m.contains_key(&1));
1745 assert!(!m.contains_key(&0));
1750 let mut m = HashMap::new();
1751 assert_eq!(m.len(), 0);
1752 assert!(m.insert(1, 2).is_none());
1753 assert_eq!(m.len(), 1);
1754 assert!(m.insert(2, 4).is_none());
1755 assert_eq!(m.len(), 2);
1756 assert_eq!(*m.get(&1).unwrap(), 2);
1757 assert_eq!(*m.get(&2).unwrap(), 4);
1760 thread_local! { static DROP_VECTOR: RefCell<Vec<isize>> = RefCell::new(Vec::new()) }
1762 #[derive(Hash, PartialEq, Eq)]
1768 fn new(k: usize) -> Dropable {
1769 DROP_VECTOR.with(|slot| {
1770 slot.borrow_mut()[k] += 1;
1777 impl Drop for Dropable {
1778 fn drop(&mut self) {
1779 DROP_VECTOR.with(|slot| {
1780 slot.borrow_mut()[self.k] -= 1;
1785 impl Clone for Dropable {
1786 fn clone(&self) -> Dropable {
1787 Dropable::new(self.k)
1793 DROP_VECTOR.with(|slot| {
1794 *slot.borrow_mut() = vec![0; 200];
1798 let mut m = HashMap::new();
1800 DROP_VECTOR.with(|v| {
1802 assert_eq!(v.borrow()[i], 0);
1807 let d1 = Dropable::new(i);
1808 let d2 = Dropable::new(i+100);
1812 DROP_VECTOR.with(|v| {
1814 assert_eq!(v.borrow()[i], 1);
1819 let k = Dropable::new(i);
1820 let v = m.remove(&k);
1822 assert!(v.is_some());
1824 DROP_VECTOR.with(|v| {
1825 assert_eq!(v.borrow()[i], 1);
1826 assert_eq!(v.borrow()[i+100], 1);
1830 DROP_VECTOR.with(|v| {
1832 assert_eq!(v.borrow()[i], 0);
1833 assert_eq!(v.borrow()[i+100], 0);
1837 assert_eq!(v.borrow()[i], 1);
1838 assert_eq!(v.borrow()[i+100], 1);
1843 DROP_VECTOR.with(|v| {
1845 assert_eq!(v.borrow()[i], 0);
1851 fn test_move_iter_drops() {
1852 DROP_VECTOR.with(|v| {
1853 *v.borrow_mut() = vec![0; 200];
1857 let mut hm = HashMap::new();
1859 DROP_VECTOR.with(|v| {
1861 assert_eq!(v.borrow()[i], 0);
1866 let d1 = Dropable::new(i);
1867 let d2 = Dropable::new(i+100);
1871 DROP_VECTOR.with(|v| {
1873 assert_eq!(v.borrow()[i], 1);
1880 // By the way, ensure that cloning doesn't screw up the dropping.
1884 let mut half = hm.into_iter().take(50);
1886 DROP_VECTOR.with(|v| {
1888 assert_eq!(v.borrow()[i], 1);
1892 for _ in half.by_ref() {}
1894 DROP_VECTOR.with(|v| {
1895 let nk = (0..100).filter(|&i| {
1899 let nv = (0..100).filter(|&i| {
1900 v.borrow()[i+100] == 1
1908 DROP_VECTOR.with(|v| {
1910 assert_eq!(v.borrow()[i], 0);
1916 fn test_empty_pop() {
1917 let mut m: HashMap<isize, bool> = HashMap::new();
1918 assert_eq!(m.remove(&0), None);
1922 fn test_lots_of_insertions() {
1923 let mut m = HashMap::new();
1925 // Try this a few times to make sure we never screw up the hashmap's
1928 assert!(m.is_empty());
1931 assert!(m.insert(i, i).is_none());
1935 assert_eq!(r, Some(&j));
1938 for j in i+1..1001 {
1940 assert_eq!(r, None);
1944 for i in 1001..2001 {
1945 assert!(!m.contains_key(&i));
1950 assert!(m.remove(&i).is_some());
1953 assert!(!m.contains_key(&j));
1956 for j in i+1..1001 {
1957 assert!(m.contains_key(&j));
1962 assert!(!m.contains_key(&i));
1966 assert!(m.insert(i, i).is_none());
1970 for i in (1..1001).rev() {
1971 assert!(m.remove(&i).is_some());
1974 assert!(!m.contains_key(&j));
1978 assert!(m.contains_key(&j));
1985 fn test_find_mut() {
1986 let mut m = HashMap::new();
1987 assert!(m.insert(1, 12).is_none());
1988 assert!(m.insert(2, 8).is_none());
1989 assert!(m.insert(5, 14).is_none());
1991 match m.get_mut(&5) {
1992 None => panic!(), Some(x) => *x = new
1994 assert_eq!(m.get(&5), Some(&new));
1998 fn test_insert_overwrite() {
1999 let mut m = HashMap::new();
2000 assert!(m.insert(1, 2).is_none());
2001 assert_eq!(*m.get(&1).unwrap(), 2);
2002 assert!(!m.insert(1, 3).is_none());
2003 assert_eq!(*m.get(&1).unwrap(), 3);
2007 fn test_insert_conflicts() {
2008 let mut m = HashMap::with_capacity(4);
2009 assert!(m.insert(1, 2).is_none());
2010 assert!(m.insert(5, 3).is_none());
2011 assert!(m.insert(9, 4).is_none());
2012 assert_eq!(*m.get(&9).unwrap(), 4);
2013 assert_eq!(*m.get(&5).unwrap(), 3);
2014 assert_eq!(*m.get(&1).unwrap(), 2);
2018 fn test_conflict_remove() {
2019 let mut m = HashMap::with_capacity(4);
2020 assert!(m.insert(1, 2).is_none());
2021 assert_eq!(*m.get(&1).unwrap(), 2);
2022 assert!(m.insert(5, 3).is_none());
2023 assert_eq!(*m.get(&1).unwrap(), 2);
2024 assert_eq!(*m.get(&5).unwrap(), 3);
2025 assert!(m.insert(9, 4).is_none());
2026 assert_eq!(*m.get(&1).unwrap(), 2);
2027 assert_eq!(*m.get(&5).unwrap(), 3);
2028 assert_eq!(*m.get(&9).unwrap(), 4);
2029 assert!(m.remove(&1).is_some());
2030 assert_eq!(*m.get(&9).unwrap(), 4);
2031 assert_eq!(*m.get(&5).unwrap(), 3);
2035 fn test_is_empty() {
2036 let mut m = HashMap::with_capacity(4);
2037 assert!(m.insert(1, 2).is_none());
2038 assert!(!m.is_empty());
2039 assert!(m.remove(&1).is_some());
2040 assert!(m.is_empty());
2045 let mut m = HashMap::new();
2047 assert_eq!(m.remove(&1), Some(2));
2048 assert_eq!(m.remove(&1), None);
2053 let mut m = HashMap::with_capacity(4);
2055 assert!(m.insert(i, i*2).is_none());
2057 assert_eq!(m.len(), 32);
2059 let mut observed: u32 = 0;
2062 assert_eq!(*v, *k * 2);
2063 observed |= 1 << *k;
2065 assert_eq!(observed, 0xFFFF_FFFF);
2070 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
2071 let map: HashMap<_, _> = vec.into_iter().collect();
2072 let keys: Vec<_> = map.keys().cloned().collect();
2073 assert_eq!(keys.len(), 3);
2074 assert!(keys.contains(&1));
2075 assert!(keys.contains(&2));
2076 assert!(keys.contains(&3));
2081 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
2082 let map: HashMap<_, _> = vec.into_iter().collect();
2083 let values: Vec<_> = map.values().cloned().collect();
2084 assert_eq!(values.len(), 3);
2085 assert!(values.contains(&'a'));
2086 assert!(values.contains(&'b'));
2087 assert!(values.contains(&'c'));
2092 let mut m = HashMap::new();
2093 assert!(m.get(&1).is_none());
2097 Some(v) => assert_eq!(*v, 2)
2103 let mut m1 = HashMap::new();
2108 let mut m2 = HashMap::new();
2121 let mut map = HashMap::new();
2122 let empty: HashMap<i32, i32> = HashMap::new();
2127 let map_str = format!("{:?}", map);
2129 assert!(map_str == "{1: 2, 3: 4}" ||
2130 map_str == "{3: 4, 1: 2}");
2131 assert_eq!(format!("{:?}", empty), "{}");
2136 let mut m = HashMap::new();
2138 assert_eq!(m.len(), 0);
2139 assert!(m.is_empty());
2142 let old_cap = m.table.capacity();
2143 while old_cap == m.table.capacity() {
2148 assert_eq!(m.len(), i);
2149 assert!(!m.is_empty());
2153 fn test_behavior_resize_policy() {
2154 let mut m = HashMap::new();
2156 assert_eq!(m.len(), 0);
2157 assert_eq!(m.table.capacity(), 0);
2158 assert!(m.is_empty());
2162 assert!(m.is_empty());
2163 let initial_cap = m.table.capacity();
2164 m.reserve(initial_cap);
2165 let cap = m.table.capacity();
2167 assert_eq!(cap, initial_cap * 2);
2170 for _ in 0..cap * 3 / 4 {
2174 // three quarters full
2176 assert_eq!(m.len(), i);
2177 assert_eq!(m.table.capacity(), cap);
2179 for _ in 0..cap / 4 {
2185 let new_cap = m.table.capacity();
2186 assert_eq!(new_cap, cap * 2);
2188 for _ in 0..cap / 2 - 1 {
2191 assert_eq!(m.table.capacity(), new_cap);
2193 // A little more than one quarter full.
2195 assert_eq!(m.table.capacity(), cap);
2196 // again, a little more than half full
2197 for _ in 0..cap / 2 - 1 {
2203 assert_eq!(m.len(), i);
2204 assert!(!m.is_empty());
2205 assert_eq!(m.table.capacity(), initial_cap);
2209 fn test_reserve_shrink_to_fit() {
2210 let mut m = HashMap::new();
2213 assert!(m.capacity() >= m.len());
2219 let usable_cap = m.capacity();
2220 for i in 128..(128 + 256) {
2222 assert_eq!(m.capacity(), usable_cap);
2225 for i in 100..(128 + 256) {
2226 assert_eq!(m.remove(&i), Some(i));
2230 assert_eq!(m.len(), 100);
2231 assert!(!m.is_empty());
2232 assert!(m.capacity() >= m.len());
2235 assert_eq!(m.remove(&i), Some(i));
2240 assert_eq!(m.len(), 1);
2241 assert!(m.capacity() >= m.len());
2242 assert_eq!(m.remove(&0), Some(0));
2246 fn test_from_iter() {
2247 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2249 let map: HashMap<_, _> = xs.iter().cloned().collect();
2251 for &(k, v) in &xs {
2252 assert_eq!(map.get(&k), Some(&v));
2257 fn test_size_hint() {
2258 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2260 let map: HashMap<_, _> = xs.iter().cloned().collect();
2262 let mut iter = map.iter();
2264 for _ in iter.by_ref().take(3) {}
2266 assert_eq!(iter.size_hint(), (3, Some(3)));
2270 fn test_iter_len() {
2271 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2273 let map: HashMap<_, _> = xs.iter().cloned().collect();
2275 let mut iter = map.iter();
2277 for _ in iter.by_ref().take(3) {}
2279 assert_eq!(iter.len(), 3);
2283 fn test_mut_size_hint() {
2284 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2286 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2288 let mut iter = map.iter_mut();
2290 for _ in iter.by_ref().take(3) {}
2292 assert_eq!(iter.size_hint(), (3, Some(3)));
2296 fn test_iter_mut_len() {
2297 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2299 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2301 let mut iter = map.iter_mut();
2303 for _ in iter.by_ref().take(3) {}
2305 assert_eq!(iter.len(), 3);
2310 let mut map = HashMap::new();
2316 assert_eq!(map[&2], 1);
2321 fn test_index_nonexistent() {
2322 let mut map = HashMap::new();
2333 let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2335 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2337 // Existing key (insert)
2338 match map.entry(1) {
2339 Vacant(_) => unreachable!(),
2340 Occupied(mut view) => {
2341 assert_eq!(view.get(), &10);
2342 assert_eq!(view.insert(100), 10);
2345 assert_eq!(map.get(&1).unwrap(), &100);
2346 assert_eq!(map.len(), 6);
2349 // Existing key (update)
2350 match map.entry(2) {
2351 Vacant(_) => unreachable!(),
2352 Occupied(mut view) => {
2353 let v = view.get_mut();
2354 let new_v = (*v) * 10;
2358 assert_eq!(map.get(&2).unwrap(), &200);
2359 assert_eq!(map.len(), 6);
2361 // Existing key (take)
2362 match map.entry(3) {
2363 Vacant(_) => unreachable!(),
2365 assert_eq!(view.remove(), 30);
2368 assert_eq!(map.get(&3), None);
2369 assert_eq!(map.len(), 5);
2372 // Inexistent key (insert)
2373 match map.entry(10) {
2374 Occupied(_) => unreachable!(),
2376 assert_eq!(*view.insert(1000), 1000);
2379 assert_eq!(map.get(&10).unwrap(), &1000);
2380 assert_eq!(map.len(), 6);
2384 fn test_entry_take_doesnt_corrupt() {
2385 #![allow(deprecated)] //rand
2387 fn check(m: &HashMap<isize, ()>) {
2389 assert!(m.contains_key(k),
2390 "{} is in keys() but not in the map?", k);
2394 let mut m = HashMap::new();
2395 let mut rng = thread_rng();
2397 // Populate the map with some items.
2399 let x = rng.gen_range(-10, 10);
2404 let x = rng.gen_range(-10, 10);
2408 println!("{}: remove {}", i, x);
2418 fn test_extend_ref() {
2419 let mut a = HashMap::new();
2421 let mut b = HashMap::new();
2423 b.insert(3, "three");
2427 assert_eq!(a.len(), 3);
2428 assert_eq!(a[&1], "one");
2429 assert_eq!(a[&2], "two");
2430 assert_eq!(a[&3], "three");
2434 fn test_capacity_not_less_than_len() {
2435 let mut a = HashMap::new();
2443 assert!(a.capacity() > a.len());
2445 let free = a.capacity() - a.len();
2451 assert_eq!(a.len(), a.capacity());
2453 // Insert at capacity should cause allocation.
2455 assert!(a.capacity() > a.len());