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.
11 // ignore-lexer-test FIXME #15883
14 use self::SearchResult
::*;
15 use self::VacantEntryState
::*;
19 use cmp
::{max, Eq, PartialEq}
;
21 use fmt
::{self, Debug}
;
22 use hash
::{Hash, SipHasher}
;
23 use iter
::{self, Iterator, ExactSizeIterator, IntoIterator, FromIterator, Extend, Map}
;
25 use mem
::{self, replace}
;
26 use ops
::{Deref, FnMut, FnOnce, Index}
;
27 use option
::Option
::{self, Some, None}
;
28 use rand
::{self, Rng}
;
29 use result
::Result
::{self, Ok, Err}
;
41 use super::table
::BucketState
::{
45 use super::state
::HashState
;
47 const INITIAL_LOG2_CAP
: usize = 5;
48 #[unstable(feature = "std_misc")]
49 pub const INITIAL_CAPACITY
: usize = 1 << INITIAL_LOG2_CAP
; // 2^5
51 /// The default behavior of HashMap implements a load factor of 90.9%.
52 /// This behavior is characterized by the following condition:
54 /// - if size > 0.909 * capacity: grow the map
56 struct DefaultResizePolicy
;
58 impl DefaultResizePolicy
{
59 fn new() -> DefaultResizePolicy
{
64 fn min_capacity(&self, usable_size
: usize) -> usize {
65 // Here, we are rephrasing the logic by specifying the lower limit
68 // - if `cap < size * 1.1`: grow the map
72 /// An inverse of `min_capacity`, approximately.
74 fn usable_capacity(&self, cap
: usize) -> usize {
75 // As the number of entries approaches usable capacity,
76 // min_capacity(size) must be smaller than the internal capacity,
77 // so that the map is not resized:
78 // `min_capacity(usable_capacity(x)) <= x`.
79 // The left-hand side can only be smaller due to flooring by integer
82 // This doesn't have to be checked for overflow since allocation size
83 // in bytes will overflow earlier than multiplication by 10.
89 fn test_resize_policy() {
90 let rp
= DefaultResizePolicy
;
92 assert
!(rp
.min_capacity(rp
.usable_capacity(n
)) <= n
);
93 assert
!(rp
.usable_capacity(rp
.min_capacity(n
)) <= n
);
97 // The main performance trick in this hashmap is called Robin Hood Hashing.
98 // It gains its excellent performance from one essential operation:
100 // If an insertion collides with an existing element, and that element's
101 // "probe distance" (how far away the element is from its ideal location)
102 // is higher than how far we've already probed, swap the elements.
104 // This massively lowers variance in probe distance, and allows us to get very
105 // high load factors with good performance. The 90% load factor I use is rather
108 // > Why a load factor of approximately 90%?
110 // In general, all the distances to initial buckets will converge on the mean.
111 // At a load factor of α, the odds of finding the target bucket after k
112 // probes is approximately 1-α^k. If we set this equal to 50% (since we converge
113 // on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round
114 // this down to make the math easier on the CPU and avoid its FPU.
115 // Since on average we start the probing in the middle of a cache line, this
116 // strategy pulls in two cache lines of hashes on every lookup. I think that's
117 // pretty good, but if you want to trade off some space, it could go down to one
118 // cache line on average with an α of 0.84.
120 // > Wait, what? Where did you get 1-α^k from?
122 // On the first probe, your odds of a collision with an existing element is α.
123 // The odds of doing this twice in a row is approximately α^2. For three times,
124 // α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT
125 // colliding after k tries is 1-α^k.
127 // The paper from 1986 cited below mentions an implementation which keeps track
128 // of the distance-to-initial-bucket histogram. This approach is not suitable
129 // for modern architectures because it requires maintaining an internal data
130 // structure. This allows very good first guesses, but we are most concerned
131 // with guessing entire cache lines, not individual indexes. Furthermore, array
132 // accesses are no longer linear and in one direction, as we have now. There
133 // is also memory and cache pressure that this would entail that would be very
134 // difficult to properly see in a microbenchmark.
136 // ## Future Improvements (FIXME!)
138 // Allow the load factor to be changed dynamically and/or at initialization.
140 // Also, would it be possible for us to reuse storage when growing the
141 // underlying table? This is exactly the use case for 'realloc', and may
142 // be worth exploring.
144 // ## Future Optimizations (FIXME!)
146 // Another possible design choice that I made without any real reason is
147 // parameterizing the raw table over keys and values. Technically, all we need
148 // is the size and alignment of keys and values, and the code should be just as
149 // efficient (well, we might need one for power-of-two size and one for not...).
150 // This has the potential to reduce code bloat in rust executables, without
151 // really losing anything except 4 words (key size, key alignment, val size,
152 // val alignment) which can be passed in to every call of a `RawTable` function.
153 // This would definitely be an avenue worth exploring if people start complaining
154 // about the size of rust executables.
156 // Annotate exceedingly likely branches in `table::make_hash`
157 // and `search_hashed` to reduce instruction cache pressure
158 // and mispredictions once it becomes possible (blocked on issue #11092).
160 // Shrinking the table could simply reallocate in place after moving buckets
161 // to the first half.
163 // The growth algorithm (fragment of the Proof of Correctness)
164 // --------------------
166 // The growth algorithm is basically a fast path of the naive reinsertion-
167 // during-resize algorithm. Other paths should never be taken.
169 // Consider growing a robin hood hashtable of capacity n. Normally, we do this
170 // by allocating a new table of capacity `2n`, and then individually reinsert
171 // each element in the old table into the new one. This guarantees that the
172 // new table is a valid robin hood hashtable with all the desired statistical
173 // properties. Remark that the order we reinsert the elements in should not
174 // matter. For simplicity and efficiency, we will consider only linear
175 // reinsertions, which consist of reinserting all elements in the old table
176 // into the new one by increasing order of index. However we will not be
177 // starting our reinsertions from index 0 in general. If we start from index
178 // i, for the purpose of reinsertion we will consider all elements with real
179 // index j < i to have virtual index n + j.
181 // Our hash generation scheme consists of generating a 64-bit hash and
182 // truncating the most significant bits. When moving to the new table, we
183 // simply introduce a new bit to the front of the hash. Therefore, if an
184 // elements has ideal index i in the old table, it can have one of two ideal
185 // locations in the new table. If the new bit is 0, then the new ideal index
186 // is i. If the new bit is 1, then the new ideal index is n + i. Intuitively,
187 // we are producing two independent tables of size n, and for each element we
188 // independently choose which table to insert it into with equal probability.
189 // However the rather than wrapping around themselves on overflowing their
190 // indexes, the first table overflows into the first, and the first into the
191 // second. Visually, our new table will look something like:
193 // [yy_xxx_xxxx_xxx|xx_yyy_yyyy_yyy]
195 // Where x's are elements inserted into the first table, y's are elements
196 // inserted into the second, and _'s are empty sections. We now define a few
197 // key concepts that we will use later. Note that this is a very abstract
198 // perspective of the table. A real resized table would be at least half
201 // Theorem: A linear robin hood reinsertion from the first ideal element
202 // produces identical results to a linear naive reinsertion from the same
205 // FIXME(Gankro, pczarn): review the proof and put it all in a separate README.md
207 /// A hash map implementation which uses linear probing with Robin
208 /// Hood bucket stealing.
210 /// The hashes are all keyed by the task-local random number generator
211 /// on creation by default. This means that the ordering of the keys is
212 /// randomized, but makes the tables more resistant to
213 /// denial-of-service attacks (Hash DoS). This behaviour can be
214 /// overridden with one of the constructors.
216 /// It is required that the keys implement the `Eq` and `Hash` traits, although
217 /// this can frequently be achieved by using `#[derive(Eq, Hash)]`. If you
218 /// implement these yourself, it is important that the following property holds:
221 /// k1 == k2 -> hash(k1) == hash(k2)
224 /// In other words, if two keys are equal, their hashes must be equal.
226 /// It is a logic error for a key to be modified in such a way that the key's
227 /// hash, as determined by the `Hash` trait, or its equality, as determined by
228 /// the `Eq` trait, changes while it is in the map. This is normally only
229 /// possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
231 /// Relevant papers/articles:
233 /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)
234 /// 2. Emmanuel Goossaert. ["Robin Hood
235 /// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/)
236 /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift
237 /// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)
242 /// use std::collections::HashMap;
244 /// // type inference lets us omit an explicit type signature (which
245 /// // would be `HashMap<&str, &str>` in this example).
246 /// let mut book_reviews = HashMap::new();
248 /// // review some books.
249 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
250 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
251 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
252 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
254 /// // check for a specific one.
255 /// if !book_reviews.contains_key(&("Les Misérables")) {
256 /// println!("We've got {} reviews, but Les Misérables ain't one.",
257 /// book_reviews.len());
260 /// // oops, this review has a lot of spelling mistakes, let's delete it.
261 /// book_reviews.remove(&("The Adventures of Sherlock Holmes"));
263 /// // look up the values associated with some keys.
264 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
265 /// for book in to_find.iter() {
266 /// match book_reviews.get(book) {
267 /// Some(review) => println!("{}: {}", *book, *review),
268 /// None => println!("{} is unreviewed.", *book)
272 /// // iterate over everything.
273 /// for (book, review) in book_reviews.iter() {
274 /// println!("{}: \"{}\"", *book, *review);
278 /// The easiest way to use `HashMap` with a custom type as key is to derive `Eq` and `Hash`.
279 /// We must also derive `PartialEq`.
282 /// use std::collections::HashMap;
284 /// #[derive(Hash, Eq, PartialEq, Debug)]
291 /// /// Create a new Viking.
292 /// fn new(name: &str, country: &str) -> Viking {
293 /// Viking { name: name.to_string(), country: country.to_string() }
297 /// // Use a HashMap to store the vikings' health points.
298 /// let mut vikings = HashMap::new();
300 /// vikings.insert(Viking::new("Einar", "Norway"), 25);
301 /// vikings.insert(Viking::new("Olaf", "Denmark"), 24);
302 /// vikings.insert(Viking::new("Harald", "Iceland"), 12);
304 /// // Use derived implementation to print the status of the vikings.
305 /// for (viking, health) in vikings.iter() {
306 /// println!("{:?} has {} hp", viking, health);
310 #[stable(feature = "rust1", since = "1.0.0")]
311 pub struct HashMap
<K
, V
, S
= RandomState
> {
312 // All hashes are keyed on these values, to prevent hash collision attacks.
315 table
: RawTable
<K
, V
>,
317 resize_policy
: DefaultResizePolicy
,
320 /// Search for a pre-hashed key.
321 fn search_hashed
<K
, V
, M
, F
>(table
: M
,
324 -> SearchResult
<K
, V
, M
> where
325 M
: Deref
<Target
=RawTable
<K
, V
>>,
326 F
: FnMut(&K
) -> bool
,
328 // This is the only function where capacity can be zero. To avoid
329 // undefined behaviour when Bucket::new gets the raw bucket in this
330 // case, immediately return the appropriate search result.
331 if table
.capacity() == 0 {
332 return TableRef(table
);
335 let size
= table
.size();
336 let mut probe
= Bucket
::new(table
, hash
);
337 let ib
= probe
.index();
339 while probe
.index() != ib
+ size
{
340 let full
= match probe
.peek() {
341 Empty(b
) => return TableRef(b
.into_table()), // hit an empty bucket
345 if full
.distance() + ib
< full
.index() {
346 // We can finish the search early if we hit any bucket
347 // with a lower distance to initial bucket than we've probed.
348 return TableRef(full
.into_table());
351 // If the hash doesn't match, it can't be this one..
352 if hash
== full
.hash() {
353 // If the key doesn't match, it can't be this one..
354 if is_match(full
.read().0) {
355 return FoundExisting(full
);
362 TableRef(probe
.into_table())
365 fn pop_internal
<K
, V
>(starting_bucket
: FullBucketMut
<K
, V
>) -> (K
, V
) {
366 let (empty
, retkey
, retval
) = starting_bucket
.take();
367 let mut gap
= match empty
.gap_peek() {
369 None
=> return (retkey
, retval
)
372 while gap
.full().distance() != 0 {
373 gap
= match gap
.shift() {
379 // Now we've done all our shifting. Return the value we grabbed earlier.
383 /// Perform robin hood bucket stealing at the given `bucket`. You must
384 /// also pass the position of that bucket's initial bucket so we don't have
385 /// to recalculate it.
387 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
388 fn robin_hood
<'a
, K
: 'a
, V
: 'a
>(mut bucket
: FullBucketMut
<'a
, K
, V
>,
394 let starting_index
= bucket
.index();
396 let table
= bucket
.table(); // FIXME "lifetime too short".
399 // There can be at most `size - dib` buckets to displace, because
400 // in the worst case, there are `size` elements and we already are
401 // `distance` buckets away from the initial one.
402 let idx_end
= starting_index
+ size
- bucket
.distance();
405 let (old_hash
, old_key
, old_val
) = bucket
.replace(hash
, k
, v
);
407 let probe
= bucket
.next();
408 assert
!(probe
.index() != idx_end
);
410 let full_bucket
= match probe
.peek() {
413 let b
= bucket
.put(old_hash
, old_key
, old_val
);
414 // Now that it's stolen, just read the value's pointer
415 // right out of the table!
416 return Bucket
::at_index(b
.into_table(), starting_index
)
422 Full(bucket
) => bucket
425 let probe_ib
= full_bucket
.index() - full_bucket
.distance();
427 bucket
= full_bucket
;
429 // Robin hood! Steal the spot.
441 /// A result that works like Option<FullBucket<..>> but preserves
442 /// the reference that grants us access to the table in any case.
443 enum SearchResult
<K
, V
, M
> {
444 // This is an entry that holds the given key:
445 FoundExisting(FullBucket
<K
, V
, M
>),
447 // There was no such entry. The reference is given back:
451 impl<K
, V
, M
> SearchResult
<K
, V
, M
> {
452 fn into_option(self) -> Option
<FullBucket
<K
, V
, M
>> {
454 FoundExisting(bucket
) => Some(bucket
),
460 impl<K
, V
, S
> HashMap
<K
, V
, S
>
461 where K
: Eq
+ Hash
, S
: HashState
463 fn make_hash
<X
: ?Sized
>(&self, x
: &X
) -> SafeHash
where X
: Hash
{
464 table
::make_hash(&self.hash_state
, x
)
467 /// Search for a key, yielding the index if it's found in the hashtable.
468 /// If you already have the hash for the key lying around, use
470 fn search
<'a
, Q
: ?Sized
>(&'a
self, q
: &Q
) -> Option
<FullBucketImm
<'a
, K
, V
>>
471 where K
: Borrow
<Q
>, Q
: Eq
+ Hash
473 let hash
= self.make_hash(q
);
474 search_hashed(&self.table
, hash
, |k
| q
.eq(k
.borrow()))
478 fn search_mut
<'a
, Q
: ?Sized
>(&'a
mut self, q
: &Q
) -> Option
<FullBucketMut
<'a
, K
, V
>>
479 where K
: Borrow
<Q
>, Q
: Eq
+ Hash
481 let hash
= self.make_hash(q
);
482 search_hashed(&mut self.table
, hash
, |k
| q
.eq(k
.borrow()))
486 // The caller should ensure that invariants by Robin Hood Hashing hold.
487 fn insert_hashed_ordered(&mut self, hash
: SafeHash
, k
: K
, v
: V
) {
488 let cap
= self.table
.capacity();
489 let mut buckets
= Bucket
::new(&mut self.table
, hash
);
490 let ib
= buckets
.index();
492 while buckets
.index() != ib
+ cap
{
493 // We don't need to compare hashes for value swap.
494 // Not even DIBs for Robin Hood.
495 buckets
= match buckets
.peek() {
497 empty
.put(hash
, k
, v
);
500 Full(b
) => b
.into_bucket()
504 panic
!("Internal HashMap error: Out of space.");
508 impl<K
: Hash
+ Eq
, V
> HashMap
<K
, V
, RandomState
> {
509 /// Create an empty HashMap.
514 /// use std::collections::HashMap;
515 /// let mut map: HashMap<&str, isize> = HashMap::new();
518 #[stable(feature = "rust1", since = "1.0.0")]
519 pub fn new() -> HashMap
<K
, V
, RandomState
> {
523 /// Creates an empty hash map with the given initial capacity.
528 /// use std::collections::HashMap;
529 /// let mut map: HashMap<&str, isize> = HashMap::with_capacity(10);
532 #[stable(feature = "rust1", since = "1.0.0")]
533 pub fn with_capacity(capacity
: usize) -> HashMap
<K
, V
, RandomState
> {
534 HashMap
::with_capacity_and_hash_state(capacity
, Default
::default())
538 impl<K
, V
, S
> HashMap
<K
, V
, S
>
539 where K
: Eq
+ Hash
, S
: HashState
541 /// Creates an empty hashmap which will use the given hasher to hash keys.
543 /// The creates map has the default initial capacity.
548 /// # #![feature(std_misc)]
549 /// use std::collections::HashMap;
550 /// use std::collections::hash_map::RandomState;
552 /// let s = RandomState::new();
553 /// let mut map = HashMap::with_hash_state(s);
554 /// map.insert(1, 2);
557 #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")]
558 pub fn with_hash_state(hash_state
: S
) -> HashMap
<K
, V
, S
> {
560 hash_state
: hash_state
,
561 resize_policy
: DefaultResizePolicy
::new(),
562 table
: RawTable
::new(0),
566 /// Create an empty HashMap with space for at least `capacity`
567 /// elements, using `hasher` to hash the keys.
569 /// Warning: `hasher` is normally randomly generated, and
570 /// is designed to allow HashMaps to be resistant to attacks that
571 /// cause many collisions and very poor performance. Setting it
572 /// manually using this function can expose a DoS attack vector.
577 /// # #![feature(std_misc)]
578 /// use std::collections::HashMap;
579 /// use std::collections::hash_map::RandomState;
581 /// let s = RandomState::new();
582 /// let mut map = HashMap::with_capacity_and_hash_state(10, s);
583 /// map.insert(1, 2);
586 #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")]
587 pub fn with_capacity_and_hash_state(capacity
: usize, hash_state
: S
)
588 -> HashMap
<K
, V
, S
> {
589 let resize_policy
= DefaultResizePolicy
::new();
590 let min_cap
= max(INITIAL_CAPACITY
, resize_policy
.min_capacity(capacity
));
591 let internal_cap
= min_cap
.checked_next_power_of_two().expect("capacity overflow");
592 assert
!(internal_cap
>= capacity
, "capacity overflow");
594 hash_state
: hash_state
,
595 resize_policy
: resize_policy
,
596 table
: RawTable
::new(internal_cap
),
600 /// Returns the number of elements the map can hold without reallocating.
605 /// use std::collections::HashMap;
606 /// let map: HashMap<isize, isize> = HashMap::with_capacity(100);
607 /// assert!(map.capacity() >= 100);
610 #[stable(feature = "rust1", since = "1.0.0")]
611 pub fn capacity(&self) -> usize {
612 self.resize_policy
.usable_capacity(self.table
.capacity())
615 /// Reserves capacity for at least `additional` more elements to be inserted
616 /// in the `HashMap`. The collection may reserve more space to avoid
617 /// frequent reallocations.
621 /// Panics if the new allocation size overflows `usize`.
626 /// use std::collections::HashMap;
627 /// let mut map: HashMap<&str, isize> = HashMap::new();
630 #[stable(feature = "rust1", since = "1.0.0")]
631 pub fn reserve(&mut self, additional
: usize) {
632 let new_size
= self.len().checked_add(additional
).expect("capacity overflow");
633 let min_cap
= self.resize_policy
.min_capacity(new_size
);
635 // An invalid value shouldn't make us run out of space. This includes
636 // an overflow check.
637 assert
!(new_size
<= min_cap
);
639 if self.table
.capacity() < min_cap
{
640 let new_capacity
= max(min_cap
.next_power_of_two(), INITIAL_CAPACITY
);
641 self.resize(new_capacity
);
645 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
646 /// 1) Make sure the new capacity is enough for all the elements, accounting
647 /// for the load factor.
648 /// 2) Ensure new_capacity is a power of two or zero.
649 fn resize(&mut self, new_capacity
: usize) {
650 assert
!(self.table
.size() <= new_capacity
);
651 assert
!(new_capacity
.is_power_of_two() || new_capacity
== 0);
653 let mut old_table
= replace(&mut self.table
, RawTable
::new(new_capacity
));
654 let old_size
= old_table
.size();
656 if old_table
.capacity() == 0 || old_table
.size() == 0 {
661 // Specialization of the other branch.
662 let mut bucket
= Bucket
::first(&mut old_table
);
664 // "So a few of the first shall be last: for many be called,
667 // We'll most likely encounter a few buckets at the beginning that
668 // have their initial buckets near the end of the table. They were
669 // placed at the beginning as the probe wrapped around the table
670 // during insertion. We must skip forward to a bucket that won't
671 // get reinserted too early and won't unfairly steal others spot.
672 // This eliminates the need for robin hood.
674 bucket
= match bucket
.peek() {
676 if full
.distance() == 0 {
677 // This bucket occupies its ideal spot.
678 // It indicates the start of another "cluster".
679 bucket
= full
.into_bucket();
682 // Leaving this bucket in the last cluster for later.
686 // Encountered a hole between clusters.
693 // This is how the buckets might be laid out in memory:
694 // ($ marks an initialized bucket)
696 // |$$$_$$$$$$_$$$$$|
698 // But we've skipped the entire initial cluster of buckets
699 // and will continue iteration in this order:
702 // ^ wrap around once end is reached
705 // ^ exit once table.size == 0
707 bucket
= match bucket
.peek() {
709 let h
= bucket
.hash();
710 let (b
, k
, v
) = bucket
.take();
711 self.insert_hashed_ordered(h
, k
, v
);
713 let t
= b
.table(); // FIXME "lifetime too short".
714 if t
.size() == 0 { break }
718 Empty(b
) => b
.into_bucket()
723 assert_eq
!(self.table
.size(), old_size
);
726 /// Shrinks the capacity of the map as much as possible. It will drop
727 /// down as much as possible while maintaining the internal rules
728 /// and possibly leaving some space in accordance with the resize policy.
733 /// use std::collections::HashMap;
735 /// let mut map: HashMap<isize, isize> = HashMap::with_capacity(100);
736 /// map.insert(1, 2);
737 /// map.insert(3, 4);
738 /// assert!(map.capacity() >= 100);
739 /// map.shrink_to_fit();
740 /// assert!(map.capacity() >= 2);
742 #[stable(feature = "rust1", since = "1.0.0")]
743 pub fn shrink_to_fit(&mut self) {
744 let min_capacity
= self.resize_policy
.min_capacity(self.len());
745 let min_capacity
= max(min_capacity
.next_power_of_two(), INITIAL_CAPACITY
);
747 // An invalid value shouldn't make us run out of space.
748 debug_assert
!(self.len() <= min_capacity
);
750 if self.table
.capacity() != min_capacity
{
751 let old_table
= replace(&mut self.table
, RawTable
::new(min_capacity
));
752 let old_size
= old_table
.size();
754 // Shrink the table. Naive algorithm for resizing:
755 for (h
, k
, v
) in old_table
.into_iter() {
756 self.insert_hashed_nocheck(h
, k
, v
);
759 debug_assert_eq
!(self.table
.size(), old_size
);
763 /// Insert a pre-hashed key-value pair, without first checking
764 /// that there's enough room in the buckets. Returns a reference to the
765 /// newly insert value.
767 /// If the key already exists, the hashtable will be returned untouched
768 /// and a reference to the existing element will be returned.
769 fn insert_hashed_nocheck(&mut self, hash
: SafeHash
, k
: K
, v
: V
) -> &mut V
{
770 self.insert_or_replace_with(hash
, k
, v
, |_
, _
, _
| ())
773 fn insert_or_replace_with
<'a
, F
>(&'a
mut self,
777 mut found_existing
: F
)
779 F
: FnMut(&mut K
, &mut V
, V
),
781 // Worst case, we'll find one empty bucket among `size + 1` buckets.
782 let size
= self.table
.size();
783 let mut probe
= Bucket
::new(&mut self.table
, hash
);
784 let ib
= probe
.index();
787 let mut bucket
= match probe
.peek() {
790 return bucket
.put(hash
, k
, v
).into_mut_refs().1;
792 Full(bucket
) => bucket
796 if bucket
.hash() == hash
{
798 if k
== *bucket
.read_mut().0 {
799 let (bucket_k
, bucket_v
) = bucket
.into_mut_refs();
800 debug_assert
!(k
== *bucket_k
);
801 // Key already exists. Get its reference.
802 found_existing(bucket_k
, bucket_v
, v
);
807 let robin_ib
= bucket
.index() as isize - bucket
.distance() as isize;
809 if (ib
as isize) < robin_ib
{
810 // Found a luckier bucket than me. Better steal his spot.
811 return robin_hood(bucket
, robin_ib
as usize, hash
, k
, v
);
814 probe
= bucket
.next();
815 assert
!(probe
.index() != ib
+ size
+ 1);
819 /// An iterator visiting all keys in arbitrary order.
820 /// Iterator element type is `&'a K`.
825 /// use std::collections::HashMap;
827 /// let mut map = HashMap::new();
828 /// map.insert("a", 1);
829 /// map.insert("b", 2);
830 /// map.insert("c", 3);
832 /// for key in map.keys() {
833 /// println!("{}", key);
836 #[stable(feature = "rust1", since = "1.0.0")]
837 pub fn keys
<'a
>(&'a
self) -> Keys
<'a
, K
, V
> {
838 fn first
<A
, B
>((a
, _
): (A
, B
)) -> A { a }
839 let first
: fn((&'a K
,&'a V
)) -> &'a K
= first
; // coerce to fn ptr
841 Keys { inner: self.iter().map(first) }
844 /// An iterator visiting all values in arbitrary order.
845 /// Iterator element type is `&'a V`.
850 /// use std::collections::HashMap;
852 /// let mut map = HashMap::new();
853 /// map.insert("a", 1);
854 /// map.insert("b", 2);
855 /// map.insert("c", 3);
857 /// for val in map.values() {
858 /// println!("{}", val);
861 #[stable(feature = "rust1", since = "1.0.0")]
862 pub fn values
<'a
>(&'a
self) -> Values
<'a
, K
, V
> {
863 fn second
<A
, B
>((_
, b
): (A
, B
)) -> B { b }
864 let second
: fn((&'a K
,&'a V
)) -> &'a V
= second
; // coerce to fn ptr
866 Values { inner: self.iter().map(second) }
869 /// An iterator visiting all key-value pairs in arbitrary order.
870 /// Iterator element type is `(&'a K, &'a V)`.
875 /// use std::collections::HashMap;
877 /// let mut map = HashMap::new();
878 /// map.insert("a", 1);
879 /// map.insert("b", 2);
880 /// map.insert("c", 3);
882 /// for (key, val) in map.iter() {
883 /// println!("key: {} val: {}", key, val);
886 #[stable(feature = "rust1", since = "1.0.0")]
887 pub fn iter(&self) -> Iter
<K
, V
> {
888 Iter { inner: self.table.iter() }
891 /// An iterator visiting all key-value pairs in arbitrary order,
892 /// with mutable references to the values.
893 /// Iterator element type is `(&'a K, &'a mut V)`.
898 /// use std::collections::HashMap;
900 /// let mut map = HashMap::new();
901 /// map.insert("a", 1);
902 /// map.insert("b", 2);
903 /// map.insert("c", 3);
905 /// // Update all values
906 /// for (_, val) in map.iter_mut() {
910 /// for (key, val) in map.iter() {
911 /// println!("key: {} val: {}", key, val);
914 #[stable(feature = "rust1", since = "1.0.0")]
915 pub fn iter_mut(&mut self) -> IterMut
<K
, V
> {
916 IterMut { inner: self.table.iter_mut() }
919 /// Creates a consuming iterator, that is, one that moves each key-value
920 /// pair out of the map in arbitrary order. The map cannot be used after
926 /// use std::collections::HashMap;
928 /// let mut map = HashMap::new();
929 /// map.insert("a", 1);
930 /// map.insert("b", 2);
931 /// map.insert("c", 3);
933 /// // Not possible with .iter()
934 /// let vec: Vec<(&str, isize)> = map.into_iter().collect();
936 #[stable(feature = "rust1", since = "1.0.0")]
937 pub fn into_iter(self) -> IntoIter
<K
, V
> {
938 fn last_two
<A
, B
, C
>((_
, b
, c
): (A
, B
, C
)) -> (B
, C
) { (b, c) }
939 let last_two
: fn((SafeHash
, K
, V
)) -> (K
, V
) = last_two
;
942 inner
: self.table
.into_iter().map(last_two
)
946 /// Gets the given key's corresponding entry in the map for in-place manipulation.
947 #[stable(feature = "rust1", since = "1.0.0")]
948 pub fn entry(&mut self, key
: K
) -> Entry
<K
, V
> {
952 let hash
= self.make_hash(&key
);
953 search_entry_hashed(&mut self.table
, hash
, key
)
956 /// Returns the number of elements in the map.
961 /// use std::collections::HashMap;
963 /// let mut a = HashMap::new();
964 /// assert_eq!(a.len(), 0);
965 /// a.insert(1, "a");
966 /// assert_eq!(a.len(), 1);
968 #[stable(feature = "rust1", since = "1.0.0")]
969 pub fn len(&self) -> usize { self.table.size() }
971 /// Returns true if the map contains no elements.
976 /// use std::collections::HashMap;
978 /// let mut a = HashMap::new();
979 /// assert!(a.is_empty());
980 /// a.insert(1, "a");
981 /// assert!(!a.is_empty());
984 #[stable(feature = "rust1", since = "1.0.0")]
985 pub fn is_empty(&self) -> bool { self.len() == 0 }
987 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
988 /// allocated memory for reuse.
993 /// # #![feature(std_misc)]
994 /// use std::collections::HashMap;
996 /// let mut a = HashMap::new();
997 /// a.insert(1, "a");
998 /// a.insert(2, "b");
1000 /// for (k, v) in a.drain().take(1) {
1001 /// assert!(k == 1 || k == 2);
1002 /// assert!(v == "a" || v == "b");
1005 /// assert!(a.is_empty());
1008 #[unstable(feature = "std_misc",
1009 reason
= "matches collection reform specification, waiting for dust to settle")]
1010 pub fn drain(&mut self) -> Drain
<K
, V
> {
1011 fn last_two
<A
, B
, C
>((_
, b
, c
): (A
, B
, C
)) -> (B
, C
) { (b, c) }
1012 let last_two
: fn((SafeHash
, K
, V
)) -> (K
, V
) = last_two
; // coerce to fn pointer
1015 inner
: self.table
.drain().map(last_two
),
1019 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
1025 /// use std::collections::HashMap;
1027 /// let mut a = HashMap::new();
1028 /// a.insert(1, "a");
1030 /// assert!(a.is_empty());
1032 #[stable(feature = "rust1", since = "1.0.0")]
1034 pub fn clear(&mut self) {
1038 /// Returns a reference to the value corresponding to the key.
1040 /// The key may be any borrowed form of the map's key type, but
1041 /// `Hash` and `Eq` on the borrowed form *must* match those for
1047 /// use std::collections::HashMap;
1049 /// let mut map = HashMap::new();
1050 /// map.insert(1, "a");
1051 /// assert_eq!(map.get(&1), Some(&"a"));
1052 /// assert_eq!(map.get(&2), None);
1054 #[stable(feature = "rust1", since = "1.0.0")]
1055 pub fn get
<Q
: ?Sized
>(&self, k
: &Q
) -> Option
<&V
>
1056 where K
: Borrow
<Q
>, Q
: Hash
+ Eq
1058 self.search(k
).map(|bucket
| bucket
.into_refs().1)
1061 /// Returns true if the map contains a value for the specified key.
1063 /// The key may be any borrowed form of the map's key type, but
1064 /// `Hash` and `Eq` on the borrowed form *must* match those for
1070 /// use std::collections::HashMap;
1072 /// let mut map = HashMap::new();
1073 /// map.insert(1, "a");
1074 /// assert_eq!(map.contains_key(&1), true);
1075 /// assert_eq!(map.contains_key(&2), false);
1077 #[stable(feature = "rust1", since = "1.0.0")]
1078 pub fn contains_key
<Q
: ?Sized
>(&self, k
: &Q
) -> bool
1079 where K
: Borrow
<Q
>, Q
: Hash
+ Eq
1081 self.search(k
).is_some()
1084 /// Returns a mutable reference to the value corresponding to the key.
1086 /// The key may be any borrowed form of the map's key type, but
1087 /// `Hash` and `Eq` on the borrowed form *must* match those for
1093 /// use std::collections::HashMap;
1095 /// let mut map = HashMap::new();
1096 /// map.insert(1, "a");
1097 /// match map.get_mut(&1) {
1098 /// Some(x) => *x = "b",
1101 /// assert_eq!(map[&1], "b");
1103 #[stable(feature = "rust1", since = "1.0.0")]
1104 pub fn get_mut
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<&mut V
>
1105 where K
: Borrow
<Q
>, Q
: Hash
+ Eq
1107 self.search_mut(k
).map(|bucket
| bucket
.into_mut_refs().1)
1110 /// Inserts a key-value pair from the map. If the key already had a value
1111 /// present in the map, that value is returned. Otherwise, `None` is returned.
1116 /// use std::collections::HashMap;
1118 /// let mut map = HashMap::new();
1119 /// assert_eq!(map.insert(37, "a"), None);
1120 /// assert_eq!(map.is_empty(), false);
1122 /// map.insert(37, "b");
1123 /// assert_eq!(map.insert(37, "c"), Some("b"));
1124 /// assert_eq!(map[&37], "c");
1126 #[stable(feature = "rust1", since = "1.0.0")]
1127 pub fn insert(&mut self, k
: K
, v
: V
) -> Option
<V
> {
1128 let hash
= self.make_hash(&k
);
1131 let mut retval
= None
;
1132 self.insert_or_replace_with(hash
, k
, v
, |_
, val_ref
, val
| {
1133 retval
= Some(replace(val_ref
, val
));
1138 /// Removes a key from the map, returning the value at the key if the key
1139 /// was previously in the map.
1141 /// The key may be any borrowed form of the map's key type, but
1142 /// `Hash` and `Eq` on the borrowed form *must* match those for
1148 /// use std::collections::HashMap;
1150 /// let mut map = HashMap::new();
1151 /// map.insert(1, "a");
1152 /// assert_eq!(map.remove(&1), Some("a"));
1153 /// assert_eq!(map.remove(&1), None);
1155 #[stable(feature = "rust1", since = "1.0.0")]
1156 pub fn remove
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<V
>
1157 where K
: Borrow
<Q
>, Q
: Hash
+ Eq
1159 if self.table
.size() == 0 {
1163 self.search_mut(k
).map(|bucket
| pop_internal(bucket
).1)
1167 fn search_entry_hashed
<'a
, K
: Eq
, V
>(table
: &'a
mut RawTable
<K
,V
>, hash
: SafeHash
, k
: K
)
1170 // Worst case, we'll find one empty bucket among `size + 1` buckets.
1171 let size
= table
.size();
1172 let mut probe
= Bucket
::new(table
, hash
);
1173 let ib
= probe
.index();
1176 let bucket
= match probe
.peek() {
1179 return Vacant(VacantEntry
{
1182 elem
: NoElem(bucket
),
1185 Full(bucket
) => bucket
1189 if bucket
.hash() == hash
{
1191 if k
== *bucket
.read().0 {
1192 return Occupied(OccupiedEntry
{
1198 let robin_ib
= bucket
.index() as isize - bucket
.distance() as isize;
1200 if (ib
as isize) < robin_ib
{
1201 // Found a luckier bucket than me. Better steal his spot.
1202 return Vacant(VacantEntry
{
1205 elem
: NeqElem(bucket
, robin_ib
as usize),
1209 probe
= bucket
.next();
1210 assert
!(probe
.index() != ib
+ size
+ 1);
1214 impl<K
, V
, S
> PartialEq
for HashMap
<K
, V
, S
>
1215 where K
: Eq
+ Hash
, V
: PartialEq
, S
: HashState
1217 fn eq(&self, other
: &HashMap
<K
, V
, S
>) -> bool
{
1218 if self.len() != other
.len() { return false; }
1220 self.iter().all(|(key
, value
)|
1221 other
.get(key
).map_or(false, |v
| *value
== *v
)
1226 #[stable(feature = "rust1", since = "1.0.0")]
1227 impl<K
, V
, S
> Eq
for HashMap
<K
, V
, S
>
1228 where K
: Eq
+ Hash
, V
: Eq
, S
: HashState
1231 #[stable(feature = "rust1", since = "1.0.0")]
1232 impl<K
, V
, S
> Debug
for HashMap
<K
, V
, S
>
1233 where K
: Eq
+ Hash
+ Debug
, V
: Debug
, S
: HashState
1235 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1236 self.iter().fold(f
.debug_map(), |b
, (k
, v
)| b
.entry(k
, v
)).finish()
1240 #[stable(feature = "rust1", since = "1.0.0")]
1241 impl<K
, V
, S
> Default
for HashMap
<K
, V
, S
>
1243 S
: HashState
+ Default
,
1245 fn default() -> HashMap
<K
, V
, S
> {
1246 HashMap
::with_hash_state(Default
::default())
1250 #[stable(feature = "rust1", since = "1.0.0")]
1251 impl<'a
, K
, Q
: ?Sized
, V
, S
> Index
<&'a Q
> for HashMap
<K
, V
, S
>
1252 where K
: Eq
+ Hash
+ Borrow
<Q
>,
1259 fn index(&self, index
: &Q
) -> &V
{
1260 self.get(index
).expect("no entry found for key")
1264 /// HashMap iterator.
1265 #[stable(feature = "rust1", since = "1.0.0")]
1266 pub struct Iter
<'a
, K
: 'a
, V
: 'a
> {
1267 inner
: table
::Iter
<'a
, K
, V
>
1270 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1271 impl<'a
, K
, V
> Clone
for Iter
<'a
, K
, V
> {
1272 fn clone(&self) -> Iter
<'a
, K
, V
> {
1274 inner
: self.inner
.clone()
1279 /// HashMap mutable values iterator.
1280 #[stable(feature = "rust1", since = "1.0.0")]
1281 pub struct IterMut
<'a
, K
: 'a
, V
: 'a
> {
1282 inner
: table
::IterMut
<'a
, K
, V
>
1285 /// HashMap move iterator.
1286 #[stable(feature = "rust1", since = "1.0.0")]
1287 pub struct IntoIter
<K
, V
> {
1288 inner
: iter
::Map
<table
::IntoIter
<K
, V
>, fn((SafeHash
, K
, V
)) -> (K
, V
)>
1291 /// HashMap keys iterator.
1292 #[stable(feature = "rust1", since = "1.0.0")]
1293 pub struct Keys
<'a
, K
: 'a
, V
: 'a
> {
1294 inner
: Map
<Iter
<'a
, K
, V
>, fn((&'a K
, &'a V
)) -> &'a K
>
1297 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1298 impl<'a
, K
, V
> Clone
for Keys
<'a
, K
, V
> {
1299 fn clone(&self) -> Keys
<'a
, K
, V
> {
1301 inner
: self.inner
.clone()
1306 /// HashMap values iterator.
1307 #[stable(feature = "rust1", since = "1.0.0")]
1308 pub struct Values
<'a
, K
: 'a
, V
: 'a
> {
1309 inner
: Map
<Iter
<'a
, K
, V
>, fn((&'a K
, &'a V
)) -> &'a V
>
1312 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1313 impl<'a
, K
, V
> Clone
for Values
<'a
, K
, V
> {
1314 fn clone(&self) -> Values
<'a
, K
, V
> {
1316 inner
: self.inner
.clone()
1321 /// HashMap drain iterator.
1322 #[unstable(feature = "std_misc",
1323 reason
= "matches collection reform specification, waiting for dust to settle")]
1324 pub struct Drain
<'a
, K
: 'a
, V
: 'a
> {
1325 inner
: iter
::Map
<table
::Drain
<'a
, K
, V
>, fn((SafeHash
, K
, V
)) -> (K
, V
)>
1328 /// A view into a single occupied location in a HashMap.
1329 #[stable(feature = "rust1", since = "1.0.0")]
1330 pub struct OccupiedEntry
<'a
, K
: 'a
, V
: 'a
> {
1331 elem
: FullBucket
<K
, V
, &'a
mut RawTable
<K
, V
>>,
1334 /// A view into a single empty location in a HashMap.
1335 #[stable(feature = "rust1", since = "1.0.0")]
1336 pub struct VacantEntry
<'a
, K
: 'a
, V
: 'a
> {
1339 elem
: VacantEntryState
<K
, V
, &'a
mut RawTable
<K
, V
>>,
1342 /// A view into a single location in a map, which may be vacant or occupied.
1343 #[stable(feature = "rust1", since = "1.0.0")]
1344 pub enum Entry
<'a
, K
: 'a
, V
: 'a
> {
1345 /// An occupied Entry.
1346 #[stable(feature = "rust1", since = "1.0.0")]
1347 Occupied(OccupiedEntry
<'a
, K
, V
>),
1350 #[stable(feature = "rust1", since = "1.0.0")]
1351 Vacant(VacantEntry
<'a
, K
, V
>),
1354 /// Possible states of a VacantEntry.
1355 enum VacantEntryState
<K
, V
, M
> {
1356 /// The index is occupied, but the key to insert has precedence,
1357 /// and will kick the current one out on insertion.
1358 NeqElem(FullBucket
<K
, V
, M
>, usize),
1359 /// The index is genuinely vacant.
1360 NoElem(EmptyBucket
<K
, V
, M
>),
1363 #[stable(feature = "rust1", since = "1.0.0")]
1364 impl<'a
, K
, V
, S
> IntoIterator
for &'a HashMap
<K
, V
, S
>
1365 where K
: Eq
+ Hash
, S
: HashState
1367 type Item
= (&'a K
, &'a V
);
1368 type IntoIter
= Iter
<'a
, K
, V
>;
1370 fn into_iter(self) -> Iter
<'a
, K
, V
> {
1375 #[stable(feature = "rust1", since = "1.0.0")]
1376 impl<'a
, K
, V
, S
> IntoIterator
for &'a
mut HashMap
<K
, V
, S
>
1377 where K
: Eq
+ Hash
, S
: HashState
1379 type Item
= (&'a K
, &'a
mut V
);
1380 type IntoIter
= IterMut
<'a
, K
, V
>;
1382 fn into_iter(mut self) -> IterMut
<'a
, K
, V
> {
1387 #[stable(feature = "rust1", since = "1.0.0")]
1388 impl<K
, V
, S
> IntoIterator
for HashMap
<K
, V
, S
>
1389 where K
: Eq
+ Hash
, S
: HashState
1392 type IntoIter
= IntoIter
<K
, V
>;
1394 fn into_iter(self) -> IntoIter
<K
, V
> {
1399 #[stable(feature = "rust1", since = "1.0.0")]
1400 impl<'a
, K
, V
> Iterator
for Iter
<'a
, K
, V
> {
1401 type Item
= (&'a K
, &'a V
);
1403 #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1404 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1406 #[stable(feature = "rust1", since = "1.0.0")]
1407 impl<'a
, K
, V
> ExactSizeIterator
for Iter
<'a
, K
, V
> {
1408 #[inline] fn len(&self) -> usize { self.inner.len() }
1411 #[stable(feature = "rust1", since = "1.0.0")]
1412 impl<'a
, K
, V
> Iterator
for IterMut
<'a
, K
, V
> {
1413 type Item
= (&'a K
, &'a
mut V
);
1415 #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1416 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1418 #[stable(feature = "rust1", since = "1.0.0")]
1419 impl<'a
, K
, V
> ExactSizeIterator
for IterMut
<'a
, K
, V
> {
1420 #[inline] fn len(&self) -> usize { self.inner.len() }
1423 #[stable(feature = "rust1", since = "1.0.0")]
1424 impl<K
, V
> Iterator
for IntoIter
<K
, V
> {
1427 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1428 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1430 #[stable(feature = "rust1", since = "1.0.0")]
1431 impl<K
, V
> ExactSizeIterator
for IntoIter
<K
, V
> {
1432 #[inline] fn len(&self) -> usize { self.inner.len() }
1435 #[stable(feature = "rust1", since = "1.0.0")]
1436 impl<'a
, K
, V
> Iterator
for Keys
<'a
, K
, V
> {
1439 #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
1440 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1442 #[stable(feature = "rust1", since = "1.0.0")]
1443 impl<'a
, K
, V
> ExactSizeIterator
for Keys
<'a
, K
, V
> {
1444 #[inline] fn len(&self) -> usize { self.inner.len() }
1447 #[stable(feature = "rust1", since = "1.0.0")]
1448 impl<'a
, K
, V
> Iterator
for Values
<'a
, K
, V
> {
1451 #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
1452 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1454 #[stable(feature = "rust1", since = "1.0.0")]
1455 impl<'a
, K
, V
> ExactSizeIterator
for Values
<'a
, K
, V
> {
1456 #[inline] fn len(&self) -> usize { self.inner.len() }
1459 #[stable(feature = "rust1", since = "1.0.0")]
1460 impl<'a
, K
, V
> Iterator
for Drain
<'a
, K
, V
> {
1463 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1464 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1466 #[stable(feature = "rust1", since = "1.0.0")]
1467 impl<'a
, K
, V
> ExactSizeIterator
for Drain
<'a
, K
, V
> {
1468 #[inline] fn len(&self) -> usize { self.inner.len() }
1471 impl<'a
, K
, V
> Entry
<'a
, K
, V
> {
1472 /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant.
1473 #[unstable(feature = "std_misc",
1474 reason
= "will soon be replaced by or_insert")]
1475 #[deprecated(since = "1.0",
1476 reason
= "replaced with more ergonomic `or_insert` and `or_insert_with`")]
1477 /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant
1478 pub fn get(self) -> Result
<&'a
mut V
, VacantEntry
<'a
, K
, V
>> {
1480 Occupied(entry
) => Ok(entry
.into_mut()),
1481 Vacant(entry
) => Err(entry
),
1485 #[stable(feature = "rust1", since = "1.0.0")]
1486 /// Ensures a value is in the entry by inserting the default if empty, and returns
1487 /// a mutable reference to the value in the entry.
1488 pub fn or_insert(self, default: V
) -> &'a
mut V
{
1490 Occupied(entry
) => entry
.into_mut(),
1491 Vacant(entry
) => entry
.insert(default),
1495 #[stable(feature = "rust1", since = "1.0.0")]
1496 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1497 /// and returns a mutable reference to the value in the entry.
1498 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
{
1500 Occupied(entry
) => entry
.into_mut(),
1501 Vacant(entry
) => entry
.insert(default()),
1506 impl<'a
, K
, V
> OccupiedEntry
<'a
, K
, V
> {
1507 /// Gets a reference to the value in the entry.
1508 #[stable(feature = "rust1", since = "1.0.0")]
1509 pub fn get(&self) -> &V
{
1513 /// Gets a mutable reference to the value in the entry.
1514 #[stable(feature = "rust1", since = "1.0.0")]
1515 pub fn get_mut(&mut self) -> &mut V
{
1516 self.elem
.read_mut().1
1519 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1520 /// with a lifetime bound to the map itself
1521 #[stable(feature = "rust1", since = "1.0.0")]
1522 pub fn into_mut(self) -> &'a
mut V
{
1523 self.elem
.into_mut_refs().1
1526 /// Sets the value of the entry, and returns the entry's old value
1527 #[stable(feature = "rust1", since = "1.0.0")]
1528 pub fn insert(&mut self, mut value
: V
) -> V
{
1529 let old_value
= self.get_mut();
1530 mem
::swap(&mut value
, old_value
);
1534 /// Takes the value out of the entry, and returns it
1535 #[stable(feature = "rust1", since = "1.0.0")]
1536 pub fn remove(self) -> V
{
1537 pop_internal(self.elem
).1
1541 impl<'a
, K
: 'a
, V
: 'a
> VacantEntry
<'a
, K
, V
> {
1542 /// Sets the value of the entry with the VacantEntry's key,
1543 /// and returns a mutable reference to it
1544 #[stable(feature = "rust1", since = "1.0.0")]
1545 pub fn insert(self, value
: V
) -> &'a
mut V
{
1547 NeqElem(bucket
, ib
) => {
1548 robin_hood(bucket
, ib
, self.hash
, self.key
, value
)
1551 bucket
.put(self.hash
, self.key
, value
).into_mut_refs().1
1557 #[stable(feature = "rust1", since = "1.0.0")]
1558 impl<K
, V
, S
> FromIterator
<(K
, V
)> for HashMap
<K
, V
, S
>
1559 where K
: Eq
+ Hash
, S
: HashState
+ Default
1561 fn from_iter
<T
: IntoIterator
<Item
=(K
, V
)>>(iterable
: T
) -> HashMap
<K
, V
, S
> {
1562 let iter
= iterable
.into_iter();
1563 let lower
= iter
.size_hint().0;
1564 let mut map
= HashMap
::with_capacity_and_hash_state(lower
,
1565 Default
::default());
1571 #[stable(feature = "rust1", since = "1.0.0")]
1572 impl<K
, V
, S
> Extend
<(K
, V
)> for HashMap
<K
, V
, S
>
1573 where K
: Eq
+ Hash
, S
: HashState
1575 fn extend
<T
: IntoIterator
<Item
=(K
, V
)>>(&mut self, iter
: T
) {
1576 for (k
, v
) in iter
{
1583 /// `RandomState` is the default state for `HashMap` types.
1585 /// A particular instance `RandomState` will create the same instances of
1586 /// `Hasher`, but the hashers created by two different `RandomState`
1587 /// instances are unlikely to produce the same result for the same values.
1589 #[unstable(feature = "std_misc",
1590 reason
= "hashing an hash maps may be altered")]
1591 pub struct RandomState
{
1596 #[unstable(feature = "std_misc",
1597 reason
= "hashing an hash maps may be altered")]
1599 /// Construct a new `RandomState` that is initialized with random keys.
1601 #[allow(deprecated)]
1602 pub fn new() -> RandomState
{
1603 let mut r
= rand
::thread_rng();
1604 RandomState { k0: r.gen(), k1: r.gen() }
1608 #[unstable(feature = "std_misc",
1609 reason
= "hashing an hash maps may be altered")]
1610 impl HashState
for RandomState
{
1611 type Hasher
= SipHasher
;
1612 fn hasher(&self) -> SipHasher
{
1613 SipHasher
::new_with_keys(self.k0
, self.k1
)
1617 #[unstable(feature = "std_misc",
1618 reason
= "hashing an hash maps may be altered")]
1619 impl Default
for RandomState
{
1621 fn default() -> RandomState
{
1631 use super::Entry
::{Occupied, Vacant}
;
1632 use iter
::{range_inclusive, range_step_inclusive, repeat}
;
1634 use rand
::{weak_rng, Rng}
;
1637 fn test_create_capacity_zero() {
1638 let mut m
= HashMap
::with_capacity(0);
1640 assert
!(m
.insert(1, 1).is_none());
1642 assert
!(m
.contains_key(&1));
1643 assert
!(!m
.contains_key(&0));
1648 let mut m
= HashMap
::new();
1649 assert_eq
!(m
.len(), 0);
1650 assert
!(m
.insert(1, 2).is_none());
1651 assert_eq
!(m
.len(), 1);
1652 assert
!(m
.insert(2, 4).is_none());
1653 assert_eq
!(m
.len(), 2);
1654 assert_eq
!(*m
.get(&1).unwrap(), 2);
1655 assert_eq
!(*m
.get(&2).unwrap(), 4);
1658 thread_local
! { static DROP_VECTOR: RefCell<Vec<isize>> = RefCell::new(Vec::new()) }
1660 #[derive(Hash, PartialEq, Eq)]
1666 fn new(k
: usize) -> Dropable
{
1667 DROP_VECTOR
.with(|slot
| {
1668 slot
.borrow_mut()[k
] += 1;
1675 impl Drop
for Dropable
{
1676 fn drop(&mut self) {
1677 DROP_VECTOR
.with(|slot
| {
1678 slot
.borrow_mut()[self.k
] -= 1;
1683 impl Clone
for Dropable
{
1684 fn clone(&self) -> Dropable
{
1685 Dropable
::new(self.k
)
1691 DROP_VECTOR
.with(|slot
| {
1692 *slot
.borrow_mut() = repeat(0).take(200).collect();
1696 let mut m
= HashMap
::new();
1698 DROP_VECTOR
.with(|v
| {
1700 assert_eq
!(v
.borrow()[i
], 0);
1705 let d1
= Dropable
::new(i
);
1706 let d2
= Dropable
::new(i
+100);
1710 DROP_VECTOR
.with(|v
| {
1712 assert_eq
!(v
.borrow()[i
], 1);
1717 let k
= Dropable
::new(i
);
1718 let v
= m
.remove(&k
);
1720 assert
!(v
.is_some());
1722 DROP_VECTOR
.with(|v
| {
1723 assert_eq
!(v
.borrow()[i
], 1);
1724 assert_eq
!(v
.borrow()[i
+100], 1);
1728 DROP_VECTOR
.with(|v
| {
1730 assert_eq
!(v
.borrow()[i
], 0);
1731 assert_eq
!(v
.borrow()[i
+100], 0);
1735 assert_eq
!(v
.borrow()[i
], 1);
1736 assert_eq
!(v
.borrow()[i
+100], 1);
1741 DROP_VECTOR
.with(|v
| {
1743 assert_eq
!(v
.borrow()[i
], 0);
1749 fn test_move_iter_drops() {
1750 DROP_VECTOR
.with(|v
| {
1751 *v
.borrow_mut() = repeat(0).take(200).collect();
1755 let mut hm
= HashMap
::new();
1757 DROP_VECTOR
.with(|v
| {
1759 assert_eq
!(v
.borrow()[i
], 0);
1764 let d1
= Dropable
::new(i
);
1765 let d2
= Dropable
::new(i
+100);
1769 DROP_VECTOR
.with(|v
| {
1771 assert_eq
!(v
.borrow()[i
], 1);
1778 // By the way, ensure that cloning doesn't screw up the dropping.
1782 let mut half
= hm
.into_iter().take(50);
1784 DROP_VECTOR
.with(|v
| {
1786 assert_eq
!(v
.borrow()[i
], 1);
1790 for _
in half
.by_ref() {}
1792 DROP_VECTOR
.with(|v
| {
1793 let nk
= (0..100).filter(|&i
| {
1797 let nv
= (0..100).filter(|&i
| {
1798 v
.borrow()[i
+100] == 1
1806 DROP_VECTOR
.with(|v
| {
1808 assert_eq
!(v
.borrow()[i
], 0);
1814 fn test_empty_pop() {
1815 let mut m
: HashMap
<isize, bool
> = HashMap
::new();
1816 assert_eq
!(m
.remove(&0), None
);
1820 fn test_lots_of_insertions() {
1821 let mut m
= HashMap
::new();
1823 // Try this a few times to make sure we never screw up the hashmap's
1826 assert
!(m
.is_empty());
1828 for i
in range_inclusive(1, 1000) {
1829 assert
!(m
.insert(i
, i
).is_none());
1831 for j
in range_inclusive(1, i
) {
1833 assert_eq
!(r
, Some(&j
));
1836 for j
in range_inclusive(i
+1, 1000) {
1838 assert_eq
!(r
, None
);
1842 for i
in range_inclusive(1001, 2000) {
1843 assert
!(!m
.contains_key(&i
));
1847 for i
in range_inclusive(1, 1000) {
1848 assert
!(m
.remove(&i
).is_some());
1850 for j
in range_inclusive(1, i
) {
1851 assert
!(!m
.contains_key(&j
));
1854 for j
in range_inclusive(i
+1, 1000) {
1855 assert
!(m
.contains_key(&j
));
1859 for i
in range_inclusive(1, 1000) {
1860 assert
!(!m
.contains_key(&i
));
1863 for i
in range_inclusive(1, 1000) {
1864 assert
!(m
.insert(i
, i
).is_none());
1868 for i
in range_step_inclusive(1000, 1, -1) {
1869 assert
!(m
.remove(&i
).is_some());
1871 for j
in range_inclusive(i
, 1000) {
1872 assert
!(!m
.contains_key(&j
));
1875 for j
in range_inclusive(1, i
-1) {
1876 assert
!(m
.contains_key(&j
));
1883 fn test_find_mut() {
1884 let mut m
= HashMap
::new();
1885 assert
!(m
.insert(1, 12).is_none());
1886 assert
!(m
.insert(2, 8).is_none());
1887 assert
!(m
.insert(5, 14).is_none());
1889 match m
.get_mut(&5) {
1890 None
=> panic
!(), Some(x
) => *x
= new
1892 assert_eq
!(m
.get(&5), Some(&new
));
1896 fn test_insert_overwrite() {
1897 let mut m
= HashMap
::new();
1898 assert
!(m
.insert(1, 2).is_none());
1899 assert_eq
!(*m
.get(&1).unwrap(), 2);
1900 assert
!(!m
.insert(1, 3).is_none());
1901 assert_eq
!(*m
.get(&1).unwrap(), 3);
1905 fn test_insert_conflicts() {
1906 let mut m
= HashMap
::with_capacity(4);
1907 assert
!(m
.insert(1, 2).is_none());
1908 assert
!(m
.insert(5, 3).is_none());
1909 assert
!(m
.insert(9, 4).is_none());
1910 assert_eq
!(*m
.get(&9).unwrap(), 4);
1911 assert_eq
!(*m
.get(&5).unwrap(), 3);
1912 assert_eq
!(*m
.get(&1).unwrap(), 2);
1916 fn test_conflict_remove() {
1917 let mut m
= HashMap
::with_capacity(4);
1918 assert
!(m
.insert(1, 2).is_none());
1919 assert_eq
!(*m
.get(&1).unwrap(), 2);
1920 assert
!(m
.insert(5, 3).is_none());
1921 assert_eq
!(*m
.get(&1).unwrap(), 2);
1922 assert_eq
!(*m
.get(&5).unwrap(), 3);
1923 assert
!(m
.insert(9, 4).is_none());
1924 assert_eq
!(*m
.get(&1).unwrap(), 2);
1925 assert_eq
!(*m
.get(&5).unwrap(), 3);
1926 assert_eq
!(*m
.get(&9).unwrap(), 4);
1927 assert
!(m
.remove(&1).is_some());
1928 assert_eq
!(*m
.get(&9).unwrap(), 4);
1929 assert_eq
!(*m
.get(&5).unwrap(), 3);
1933 fn test_is_empty() {
1934 let mut m
= HashMap
::with_capacity(4);
1935 assert
!(m
.insert(1, 2).is_none());
1936 assert
!(!m
.is_empty());
1937 assert
!(m
.remove(&1).is_some());
1938 assert
!(m
.is_empty());
1943 let mut m
= HashMap
::new();
1945 assert_eq
!(m
.remove(&1), Some(2));
1946 assert_eq
!(m
.remove(&1), None
);
1951 let mut m
= HashMap
::with_capacity(4);
1953 assert
!(m
.insert(i
, i
*2).is_none());
1955 assert_eq
!(m
.len(), 32);
1957 let mut observed
: u32 = 0;
1960 assert_eq
!(*v
, *k
* 2);
1961 observed
|= 1 << *k
;
1963 assert_eq
!(observed
, 0xFFFF_FFFF);
1968 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
1969 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
1970 let keys
: Vec
<_
> = map
.keys().cloned().collect();
1971 assert_eq
!(keys
.len(), 3);
1972 assert
!(keys
.contains(&1));
1973 assert
!(keys
.contains(&2));
1974 assert
!(keys
.contains(&3));
1979 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
1980 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
1981 let values
: Vec
<_
> = map
.values().cloned().collect();
1982 assert_eq
!(values
.len(), 3);
1983 assert
!(values
.contains(&'a'
));
1984 assert
!(values
.contains(&'b'
));
1985 assert
!(values
.contains(&'c'
));
1990 let mut m
= HashMap
::new();
1991 assert
!(m
.get(&1).is_none());
1995 Some(v
) => assert_eq
!(*v
, 2)
2001 let mut m1
= HashMap
::new();
2006 let mut m2
= HashMap
::new();
2019 let mut map
= HashMap
::new();
2020 let empty
: HashMap
<i32, i32> = HashMap
::new();
2025 let map_str
= format
!("{:?}", map
);
2027 assert
!(map_str
== "{1: 2, 3: 4}" ||
2028 map_str
== "{3: 4, 1: 2}");
2029 assert_eq
!(format
!("{:?}", empty
), "{}");
2034 let mut m
= HashMap
::new();
2036 assert_eq
!(m
.len(), 0);
2037 assert
!(m
.is_empty());
2040 let old_cap
= m
.table
.capacity();
2041 while old_cap
== m
.table
.capacity() {
2046 assert_eq
!(m
.len(), i
);
2047 assert
!(!m
.is_empty());
2051 fn test_behavior_resize_policy() {
2052 let mut m
= HashMap
::new();
2054 assert_eq
!(m
.len(), 0);
2055 assert_eq
!(m
.table
.capacity(), 0);
2056 assert
!(m
.is_empty());
2060 assert
!(m
.is_empty());
2061 let initial_cap
= m
.table
.capacity();
2062 m
.reserve(initial_cap
);
2063 let cap
= m
.table
.capacity();
2065 assert_eq
!(cap
, initial_cap
* 2);
2068 for _
in 0..cap
* 3 / 4 {
2072 // three quarters full
2074 assert_eq
!(m
.len(), i
);
2075 assert_eq
!(m
.table
.capacity(), cap
);
2077 for _
in 0..cap
/ 4 {
2083 let new_cap
= m
.table
.capacity();
2084 assert_eq
!(new_cap
, cap
* 2);
2086 for _
in 0..cap
/ 2 - 1 {
2089 assert_eq
!(m
.table
.capacity(), new_cap
);
2091 // A little more than one quarter full.
2093 assert_eq
!(m
.table
.capacity(), cap
);
2094 // again, a little more than half full
2095 for _
in 0..cap
/ 2 - 1 {
2101 assert_eq
!(m
.len(), i
);
2102 assert
!(!m
.is_empty());
2103 assert_eq
!(m
.table
.capacity(), initial_cap
);
2107 fn test_reserve_shrink_to_fit() {
2108 let mut m
= HashMap
::new();
2111 assert
!(m
.capacity() >= m
.len());
2117 let usable_cap
= m
.capacity();
2118 for i
in 128..(128 + 256) {
2120 assert_eq
!(m
.capacity(), usable_cap
);
2123 for i
in 100..(128 + 256) {
2124 assert_eq
!(m
.remove(&i
), Some(i
));
2128 assert_eq
!(m
.len(), 100);
2129 assert
!(!m
.is_empty());
2130 assert
!(m
.capacity() >= m
.len());
2133 assert_eq
!(m
.remove(&i
), Some(i
));
2138 assert_eq
!(m
.len(), 1);
2139 assert
!(m
.capacity() >= m
.len());
2140 assert_eq
!(m
.remove(&0), Some(0));
2144 fn test_from_iter() {
2145 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2147 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2149 for &(k
, v
) in &xs
{
2150 assert_eq
!(map
.get(&k
), Some(&v
));
2155 fn test_size_hint() {
2156 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2158 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2160 let mut iter
= map
.iter();
2162 for _
in iter
.by_ref().take(3) {}
2164 assert_eq
!(iter
.size_hint(), (3, Some(3)));
2168 fn test_iter_len() {
2169 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2171 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2173 let mut iter
= map
.iter();
2175 for _
in iter
.by_ref().take(3) {}
2177 assert_eq
!(iter
.len(), 3);
2181 fn test_mut_size_hint() {
2182 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2184 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2186 let mut iter
= map
.iter_mut();
2188 for _
in iter
.by_ref().take(3) {}
2190 assert_eq
!(iter
.size_hint(), (3, Some(3)));
2194 fn test_iter_mut_len() {
2195 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2197 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2199 let mut iter
= map
.iter_mut();
2201 for _
in iter
.by_ref().take(3) {}
2203 assert_eq
!(iter
.len(), 3);
2208 let mut map
= HashMap
::new();
2214 assert_eq
!(map
[&2], 1);
2219 fn test_index_nonexistent() {
2220 let mut map
= HashMap
::new();
2231 let xs
= [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2233 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2235 // Existing key (insert)
2236 match map
.entry(1) {
2237 Vacant(_
) => unreachable
!(),
2238 Occupied(mut view
) => {
2239 assert_eq
!(view
.get(), &10);
2240 assert_eq
!(view
.insert(100), 10);
2243 assert_eq
!(map
.get(&1).unwrap(), &100);
2244 assert_eq
!(map
.len(), 6);
2247 // Existing key (update)
2248 match map
.entry(2) {
2249 Vacant(_
) => unreachable
!(),
2250 Occupied(mut view
) => {
2251 let v
= view
.get_mut();
2252 let new_v
= (*v
) * 10;
2256 assert_eq
!(map
.get(&2).unwrap(), &200);
2257 assert_eq
!(map
.len(), 6);
2259 // Existing key (take)
2260 match map
.entry(3) {
2261 Vacant(_
) => unreachable
!(),
2263 assert_eq
!(view
.remove(), 30);
2266 assert_eq
!(map
.get(&3), None
);
2267 assert_eq
!(map
.len(), 5);
2270 // Inexistent key (insert)
2271 match map
.entry(10) {
2272 Occupied(_
) => unreachable
!(),
2274 assert_eq
!(*view
.insert(1000), 1000);
2277 assert_eq
!(map
.get(&10).unwrap(), &1000);
2278 assert_eq
!(map
.len(), 6);
2282 fn test_entry_take_doesnt_corrupt() {
2283 #![allow(deprecated)] //rand
2285 fn check(m
: &HashMap
<isize, ()>) {
2287 assert
!(m
.contains_key(k
),
2288 "{} is in keys() but not in the map?", k
);
2292 let mut m
= HashMap
::new();
2293 let mut rng
= weak_rng();
2295 // Populate the map with some items.
2297 let x
= rng
.gen_range(-10, 10);
2302 let x
= rng
.gen_range(-10, 10);
2306 println
!("{}: remove {}", i
, x
);