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 cmp
::{max, Eq, PartialEq}
;
19 use fmt
::{self, Debug}
;
20 use hash
::{Hash, SipHasher}
;
21 use iter
::{self, Iterator, ExactSizeIterator, IntoIterator, FromIterator, Extend, Map}
;
23 use mem
::{self, replace}
;
24 use ops
::{Deref, FnMut, FnOnce, Index}
;
25 use option
::Option
::{self, Some, None}
;
26 use rand
::{self, Rng}
;
27 use result
::Result
::{self, Ok, Err}
;
39 use super::table
::BucketState
::{
43 use super::state
::HashState
;
45 const INITIAL_LOG2_CAP
: usize = 5;
46 const INITIAL_CAPACITY
: usize = 1 << INITIAL_LOG2_CAP
; // 2^5
48 /// The default behavior of HashMap implements a load factor of 90.9%.
49 /// This behavior is characterized by the following condition:
51 /// - if size > 0.909 * capacity: grow the map
53 struct DefaultResizePolicy
;
55 impl DefaultResizePolicy
{
56 fn new() -> DefaultResizePolicy
{
61 fn min_capacity(&self, usable_size
: usize) -> usize {
62 // Here, we are rephrasing the logic by specifying the lower limit
65 // - if `cap < size * 1.1`: grow the map
69 /// An inverse of `min_capacity`, approximately.
71 fn usable_capacity(&self, cap
: usize) -> usize {
72 // As the number of entries approaches usable capacity,
73 // min_capacity(size) must be smaller than the internal capacity,
74 // so that the map is not resized:
75 // `min_capacity(usable_capacity(x)) <= x`.
76 // The left-hand side can only be smaller due to flooring by integer
79 // This doesn't have to be checked for overflow since allocation size
80 // in bytes will overflow earlier than multiplication by 10.
86 fn test_resize_policy() {
87 let rp
= DefaultResizePolicy
;
89 assert
!(rp
.min_capacity(rp
.usable_capacity(n
)) <= n
);
90 assert
!(rp
.usable_capacity(rp
.min_capacity(n
)) <= n
);
94 // The main performance trick in this hashmap is called Robin Hood Hashing.
95 // It gains its excellent performance from one essential operation:
97 // If an insertion collides with an existing element, and that element's
98 // "probe distance" (how far away the element is from its ideal location)
99 // is higher than how far we've already probed, swap the elements.
101 // This massively lowers variance in probe distance, and allows us to get very
102 // high load factors with good performance. The 90% load factor I use is rather
105 // > Why a load factor of approximately 90%?
107 // In general, all the distances to initial buckets will converge on the mean.
108 // At a load factor of α, the odds of finding the target bucket after k
109 // probes is approximately 1-α^k. If we set this equal to 50% (since we converge
110 // on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round
111 // this down to make the math easier on the CPU and avoid its FPU.
112 // Since on average we start the probing in the middle of a cache line, this
113 // strategy pulls in two cache lines of hashes on every lookup. I think that's
114 // pretty good, but if you want to trade off some space, it could go down to one
115 // cache line on average with an α of 0.84.
117 // > Wait, what? Where did you get 1-α^k from?
119 // On the first probe, your odds of a collision with an existing element is α.
120 // The odds of doing this twice in a row is approximately α^2. For three times,
121 // α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT
122 // colliding after k tries is 1-α^k.
124 // The paper from 1986 cited below mentions an implementation which keeps track
125 // of the distance-to-initial-bucket histogram. This approach is not suitable
126 // for modern architectures because it requires maintaining an internal data
127 // structure. This allows very good first guesses, but we are most concerned
128 // with guessing entire cache lines, not individual indexes. Furthermore, array
129 // accesses are no longer linear and in one direction, as we have now. There
130 // is also memory and cache pressure that this would entail that would be very
131 // difficult to properly see in a microbenchmark.
133 // ## Future Improvements (FIXME!)
135 // Allow the load factor to be changed dynamically and/or at initialization.
137 // Also, would it be possible for us to reuse storage when growing the
138 // underlying table? This is exactly the use case for 'realloc', and may
139 // be worth exploring.
141 // ## Future Optimizations (FIXME!)
143 // Another possible design choice that I made without any real reason is
144 // parameterizing the raw table over keys and values. Technically, all we need
145 // is the size and alignment of keys and values, and the code should be just as
146 // efficient (well, we might need one for power-of-two size and one for not...).
147 // This has the potential to reduce code bloat in rust executables, without
148 // really losing anything except 4 words (key size, key alignment, val size,
149 // val alignment) which can be passed in to every call of a `RawTable` function.
150 // This would definitely be an avenue worth exploring if people start complaining
151 // about the size of rust executables.
153 // Annotate exceedingly likely branches in `table::make_hash`
154 // and `search_hashed` to reduce instruction cache pressure
155 // and mispredictions once it becomes possible (blocked on issue #11092).
157 // Shrinking the table could simply reallocate in place after moving buckets
158 // to the first half.
160 // The growth algorithm (fragment of the Proof of Correctness)
161 // --------------------
163 // The growth algorithm is basically a fast path of the naive reinsertion-
164 // during-resize algorithm. Other paths should never be taken.
166 // Consider growing a robin hood hashtable of capacity n. Normally, we do this
167 // by allocating a new table of capacity `2n`, and then individually reinsert
168 // each element in the old table into the new one. This guarantees that the
169 // new table is a valid robin hood hashtable with all the desired statistical
170 // properties. Remark that the order we reinsert the elements in should not
171 // matter. For simplicity and efficiency, we will consider only linear
172 // reinsertions, which consist of reinserting all elements in the old table
173 // into the new one by increasing order of index. However we will not be
174 // starting our reinsertions from index 0 in general. If we start from index
175 // i, for the purpose of reinsertion we will consider all elements with real
176 // index j < i to have virtual index n + j.
178 // Our hash generation scheme consists of generating a 64-bit hash and
179 // truncating the most significant bits. When moving to the new table, we
180 // simply introduce a new bit to the front of the hash. Therefore, if an
181 // elements has ideal index i in the old table, it can have one of two ideal
182 // locations in the new table. If the new bit is 0, then the new ideal index
183 // is i. If the new bit is 1, then the new ideal index is n + i. Intuitively,
184 // we are producing two independent tables of size n, and for each element we
185 // independently choose which table to insert it into with equal probability.
186 // However the rather than wrapping around themselves on overflowing their
187 // indexes, the first table overflows into the first, and the first into the
188 // second. Visually, our new table will look something like:
190 // [yy_xxx_xxxx_xxx|xx_yyy_yyyy_yyy]
192 // Where x's are elements inserted into the first table, y's are elements
193 // inserted into the second, and _'s are empty sections. We now define a few
194 // key concepts that we will use later. Note that this is a very abstract
195 // perspective of the table. A real resized table would be at least half
198 // Theorem: A linear robin hood reinsertion from the first ideal element
199 // produces identical results to a linear naive reinsertion from the same
202 // FIXME(Gankro, pczarn): review the proof and put it all in a separate README.md
204 /// A hash map implementation which uses linear probing with Robin
205 /// Hood bucket stealing.
207 /// The hashes are all keyed by the thread-local random number generator
208 /// on creation by default. This means that the ordering of the keys is
209 /// randomized, but makes the tables more resistant to
210 /// denial-of-service attacks (Hash DoS). This behaviour can be
211 /// overridden with one of the constructors.
213 /// It is required that the keys implement the `Eq` and `Hash` traits, although
214 /// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
215 /// If you implement these yourself, it is important that the following
219 /// k1 == k2 -> hash(k1) == hash(k2)
222 /// In other words, if two keys are equal, their hashes must be equal.
224 /// It is a logic error for a key to be modified in such a way that the key's
225 /// hash, as determined by the `Hash` trait, or its equality, as determined by
226 /// the `Eq` trait, changes while it is in the map. This is normally only
227 /// possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
229 /// Relevant papers/articles:
231 /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)
232 /// 2. Emmanuel Goossaert. ["Robin Hood
233 /// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/)
234 /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift
235 /// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)
240 /// use std::collections::HashMap;
242 /// // type inference lets us omit an explicit type signature (which
243 /// // would be `HashMap<&str, &str>` in this example).
244 /// let mut book_reviews = HashMap::new();
246 /// // review some books.
247 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
248 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
249 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
250 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
252 /// // check for a specific one.
253 /// if !book_reviews.contains_key("Les Misérables") {
254 /// println!("We've got {} reviews, but Les Misérables ain't one.",
255 /// book_reviews.len());
258 /// // oops, this review has a lot of spelling mistakes, let's delete it.
259 /// book_reviews.remove("The Adventures of Sherlock Holmes");
261 /// // look up the values associated with some keys.
262 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
263 /// for book in &to_find {
264 /// match book_reviews.get(book) {
265 /// Some(review) => println!("{}: {}", book, review),
266 /// None => println!("{} is unreviewed.", book)
270 /// // iterate over everything.
271 /// for (book, review) in &book_reviews {
272 /// println!("{}: \"{}\"", book, review);
276 /// The easiest way to use `HashMap` with a custom type as key is to derive `Eq` and `Hash`.
277 /// We must also derive `PartialEq`.
280 /// use std::collections::HashMap;
282 /// #[derive(Hash, Eq, PartialEq, Debug)]
289 /// /// Create a new Viking.
290 /// fn new(name: &str, country: &str) -> Viking {
291 /// Viking { name: name.to_string(), country: country.to_string() }
295 /// // Use a HashMap to store the vikings' health points.
296 /// let mut vikings = HashMap::new();
298 /// vikings.insert(Viking::new("Einar", "Norway"), 25);
299 /// vikings.insert(Viking::new("Olaf", "Denmark"), 24);
300 /// vikings.insert(Viking::new("Harald", "Iceland"), 12);
302 /// // Use derived implementation to print the status of the vikings.
303 /// for (viking, health) in &vikings {
304 /// println!("{:?} has {} hp", viking, health);
308 #[stable(feature = "rust1", since = "1.0.0")]
309 pub struct HashMap
<K
, V
, S
= RandomState
> {
310 // All hashes are keyed on these values, to prevent hash collision attacks.
313 table
: RawTable
<K
, V
>,
315 resize_policy
: DefaultResizePolicy
,
318 /// Search for a pre-hashed key.
319 fn search_hashed
<K
, V
, M
, F
>(table
: M
,
322 -> SearchResult
<K
, V
, M
> where
323 M
: Deref
<Target
=RawTable
<K
, V
>>,
324 F
: FnMut(&K
) -> bool
,
326 // This is the only function where capacity can be zero. To avoid
327 // undefined behaviour when Bucket::new gets the raw bucket in this
328 // case, immediately return the appropriate search result.
329 if table
.capacity() == 0 {
330 return TableRef(table
);
333 let size
= table
.size();
334 let mut probe
= Bucket
::new(table
, hash
);
335 let ib
= probe
.index();
337 while probe
.index() != ib
+ size
{
338 let full
= match probe
.peek() {
339 Empty(b
) => return TableRef(b
.into_table()), // hit an empty bucket
343 if full
.distance() + ib
< full
.index() {
344 // We can finish the search early if we hit any bucket
345 // with a lower distance to initial bucket than we've probed.
346 return TableRef(full
.into_table());
349 // If the hash doesn't match, it can't be this one..
350 if hash
== full
.hash() {
351 // If the key doesn't match, it can't be this one..
352 if is_match(full
.read().0) {
353 return FoundExisting(full
);
360 TableRef(probe
.into_table())
363 fn pop_internal
<K
, V
>(starting_bucket
: FullBucketMut
<K
, V
>) -> (K
, V
) {
364 let (empty
, retkey
, retval
) = starting_bucket
.take();
365 let mut gap
= match empty
.gap_peek() {
367 None
=> return (retkey
, retval
)
370 while gap
.full().distance() != 0 {
371 gap
= match gap
.shift() {
377 // Now we've done all our shifting. Return the value we grabbed earlier.
381 /// Perform robin hood bucket stealing at the given `bucket`. You must
382 /// also pass the position of that bucket's initial bucket so we don't have
383 /// to recalculate it.
385 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
386 fn robin_hood
<'a
, K
: 'a
, V
: 'a
>(mut bucket
: FullBucketMut
<'a
, K
, V
>,
392 let starting_index
= bucket
.index();
394 let table
= bucket
.table(); // FIXME "lifetime too short".
397 // There can be at most `size - dib` buckets to displace, because
398 // in the worst case, there are `size` elements and we already are
399 // `distance` buckets away from the initial one.
400 let idx_end
= starting_index
+ size
- bucket
.distance();
403 let (old_hash
, old_key
, old_val
) = bucket
.replace(hash
, k
, v
);
405 let probe
= bucket
.next();
406 assert
!(probe
.index() != idx_end
);
408 let full_bucket
= match probe
.peek() {
411 let b
= bucket
.put(old_hash
, old_key
, old_val
);
412 // Now that it's stolen, just read the value's pointer
413 // right out of the table!
414 return Bucket
::at_index(b
.into_table(), starting_index
)
420 Full(bucket
) => bucket
423 let probe_ib
= full_bucket
.index() - full_bucket
.distance();
425 bucket
= full_bucket
;
427 // Robin hood! Steal the spot.
439 /// A result that works like Option<FullBucket<..>> but preserves
440 /// the reference that grants us access to the table in any case.
441 enum SearchResult
<K
, V
, M
> {
442 // This is an entry that holds the given key:
443 FoundExisting(FullBucket
<K
, V
, M
>),
445 // There was no such entry. The reference is given back:
449 impl<K
, V
, M
> SearchResult
<K
, V
, M
> {
450 fn into_option(self) -> Option
<FullBucket
<K
, V
, M
>> {
452 FoundExisting(bucket
) => Some(bucket
),
458 impl<K
, V
, S
> HashMap
<K
, V
, S
>
459 where K
: Eq
+ Hash
, S
: HashState
461 fn make_hash
<X
: ?Sized
>(&self, x
: &X
) -> SafeHash
where X
: Hash
{
462 table
::make_hash(&self.hash_state
, x
)
465 /// Search for a key, yielding the index if it's found in the hashtable.
466 /// If you already have the hash for the key lying around, use
468 fn search
<'a
, Q
: ?Sized
>(&'a
self, q
: &Q
) -> Option
<FullBucketImm
<'a
, K
, V
>>
469 where K
: Borrow
<Q
>, Q
: Eq
+ Hash
471 let hash
= self.make_hash(q
);
472 search_hashed(&self.table
, hash
, |k
| q
.eq(k
.borrow()))
476 fn search_mut
<'a
, Q
: ?Sized
>(&'a
mut self, q
: &Q
) -> Option
<FullBucketMut
<'a
, K
, V
>>
477 where K
: Borrow
<Q
>, Q
: Eq
+ Hash
479 let hash
= self.make_hash(q
);
480 search_hashed(&mut self.table
, hash
, |k
| q
.eq(k
.borrow()))
484 // The caller should ensure that invariants by Robin Hood Hashing hold.
485 fn insert_hashed_ordered(&mut self, hash
: SafeHash
, k
: K
, v
: V
) {
486 let cap
= self.table
.capacity();
487 let mut buckets
= Bucket
::new(&mut self.table
, hash
);
488 let ib
= buckets
.index();
490 while buckets
.index() != ib
+ cap
{
491 // We don't need to compare hashes for value swap.
492 // Not even DIBs for Robin Hood.
493 buckets
= match buckets
.peek() {
495 empty
.put(hash
, k
, v
);
498 Full(b
) => b
.into_bucket()
502 panic
!("Internal HashMap error: Out of space.");
506 impl<K
: Hash
+ Eq
, V
> HashMap
<K
, V
, RandomState
> {
507 /// Creates an empty HashMap.
512 /// use std::collections::HashMap;
513 /// let mut map: HashMap<&str, isize> = HashMap::new();
516 #[stable(feature = "rust1", since = "1.0.0")]
517 pub fn new() -> HashMap
<K
, V
, RandomState
> {
521 /// Creates an empty hash map with the given initial capacity.
526 /// use std::collections::HashMap;
527 /// let mut map: HashMap<&str, isize> = HashMap::with_capacity(10);
530 #[stable(feature = "rust1", since = "1.0.0")]
531 pub fn with_capacity(capacity
: usize) -> HashMap
<K
, V
, RandomState
> {
532 HashMap
::with_capacity_and_hash_state(capacity
, Default
::default())
536 impl<K
, V
, S
> HashMap
<K
, V
, S
>
537 where K
: Eq
+ Hash
, S
: HashState
539 /// Creates an empty hashmap which will use the given hasher to hash keys.
541 /// The created map has the default initial capacity.
546 /// # #![feature(hashmap_hasher)]
547 /// use std::collections::HashMap;
548 /// use std::collections::hash_map::RandomState;
550 /// let s = RandomState::new();
551 /// let mut map = HashMap::with_hash_state(s);
552 /// map.insert(1, 2);
555 #[unstable(feature = "hashmap_hasher", reason = "hasher stuff is unclear")]
556 pub fn with_hash_state(hash_state
: S
) -> HashMap
<K
, V
, S
> {
558 hash_state
: hash_state
,
559 resize_policy
: DefaultResizePolicy
::new(),
560 table
: RawTable
::new(0),
564 /// Creates an empty HashMap with space for at least `capacity`
565 /// elements, using `hasher` to hash the keys.
567 /// Warning: `hasher` is normally randomly generated, and
568 /// is designed to allow HashMaps to be resistant to attacks that
569 /// cause many collisions and very poor performance. Setting it
570 /// manually using this function can expose a DoS attack vector.
575 /// # #![feature(hashmap_hasher)]
576 /// use std::collections::HashMap;
577 /// use std::collections::hash_map::RandomState;
579 /// let s = RandomState::new();
580 /// let mut map = HashMap::with_capacity_and_hash_state(10, s);
581 /// map.insert(1, 2);
584 #[unstable(feature = "hashmap_hasher", reason = "hasher stuff is unclear")]
585 pub fn with_capacity_and_hash_state(capacity
: usize, hash_state
: S
)
586 -> HashMap
<K
, V
, S
> {
587 let resize_policy
= DefaultResizePolicy
::new();
588 let min_cap
= max(INITIAL_CAPACITY
, resize_policy
.min_capacity(capacity
));
589 let internal_cap
= min_cap
.checked_next_power_of_two().expect("capacity overflow");
590 assert
!(internal_cap
>= capacity
, "capacity overflow");
592 hash_state
: hash_state
,
593 resize_policy
: resize_policy
,
594 table
: RawTable
::new(internal_cap
),
598 /// Returns the number of elements the map can hold without reallocating.
603 /// use std::collections::HashMap;
604 /// let map: HashMap<isize, isize> = HashMap::with_capacity(100);
605 /// assert!(map.capacity() >= 100);
608 #[stable(feature = "rust1", since = "1.0.0")]
609 pub fn capacity(&self) -> usize {
610 self.resize_policy
.usable_capacity(self.table
.capacity())
613 /// Reserves capacity for at least `additional` more elements to be inserted
614 /// in the `HashMap`. The collection may reserve more space to avoid
615 /// frequent reallocations.
619 /// Panics if the new allocation size overflows `usize`.
624 /// use std::collections::HashMap;
625 /// let mut map: HashMap<&str, isize> = HashMap::new();
628 #[stable(feature = "rust1", since = "1.0.0")]
629 pub fn reserve(&mut self, additional
: usize) {
630 let new_size
= self.len().checked_add(additional
).expect("capacity overflow");
631 let min_cap
= self.resize_policy
.min_capacity(new_size
);
633 // An invalid value shouldn't make us run out of space. This includes
634 // an overflow check.
635 assert
!(new_size
<= min_cap
);
637 if self.table
.capacity() < min_cap
{
638 let new_capacity
= max(min_cap
.next_power_of_two(), INITIAL_CAPACITY
);
639 self.resize(new_capacity
);
643 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
644 /// 1) Make sure the new capacity is enough for all the elements, accounting
645 /// for the load factor.
646 /// 2) Ensure new_capacity is a power of two or zero.
647 fn resize(&mut self, new_capacity
: usize) {
648 assert
!(self.table
.size() <= new_capacity
);
649 assert
!(new_capacity
.is_power_of_two() || new_capacity
== 0);
651 let mut old_table
= replace(&mut self.table
, RawTable
::new(new_capacity
));
652 let old_size
= old_table
.size();
654 if old_table
.capacity() == 0 || old_table
.size() == 0 {
659 // Specialization of the other branch.
660 let mut bucket
= Bucket
::first(&mut old_table
);
662 // "So a few of the first shall be last: for many be called,
665 // We'll most likely encounter a few buckets at the beginning that
666 // have their initial buckets near the end of the table. They were
667 // placed at the beginning as the probe wrapped around the table
668 // during insertion. We must skip forward to a bucket that won't
669 // get reinserted too early and won't unfairly steal others spot.
670 // This eliminates the need for robin hood.
672 bucket
= match bucket
.peek() {
674 if full
.distance() == 0 {
675 // This bucket occupies its ideal spot.
676 // It indicates the start of another "cluster".
677 bucket
= full
.into_bucket();
680 // Leaving this bucket in the last cluster for later.
684 // Encountered a hole between clusters.
691 // This is how the buckets might be laid out in memory:
692 // ($ marks an initialized bucket)
694 // |$$$_$$$$$$_$$$$$|
696 // But we've skipped the entire initial cluster of buckets
697 // and will continue iteration in this order:
700 // ^ wrap around once end is reached
703 // ^ exit once table.size == 0
705 bucket
= match bucket
.peek() {
707 let h
= bucket
.hash();
708 let (b
, k
, v
) = bucket
.take();
709 self.insert_hashed_ordered(h
, k
, v
);
711 let t
= b
.table(); // FIXME "lifetime too short".
712 if t
.size() == 0 { break }
716 Empty(b
) => b
.into_bucket()
721 assert_eq
!(self.table
.size(), old_size
);
724 /// Shrinks the capacity of the map as much as possible. It will drop
725 /// down as much as possible while maintaining the internal rules
726 /// and possibly leaving some space in accordance with the resize policy.
731 /// use std::collections::HashMap;
733 /// let mut map: HashMap<isize, isize> = HashMap::with_capacity(100);
734 /// map.insert(1, 2);
735 /// map.insert(3, 4);
736 /// assert!(map.capacity() >= 100);
737 /// map.shrink_to_fit();
738 /// assert!(map.capacity() >= 2);
740 #[stable(feature = "rust1", since = "1.0.0")]
741 pub fn shrink_to_fit(&mut self) {
742 let min_capacity
= self.resize_policy
.min_capacity(self.len());
743 let min_capacity
= max(min_capacity
.next_power_of_two(), INITIAL_CAPACITY
);
745 // An invalid value shouldn't make us run out of space.
746 debug_assert
!(self.len() <= min_capacity
);
748 if self.table
.capacity() != min_capacity
{
749 let old_table
= replace(&mut self.table
, RawTable
::new(min_capacity
));
750 let old_size
= old_table
.size();
752 // Shrink the table. Naive algorithm for resizing:
753 for (h
, k
, v
) in old_table
.into_iter() {
754 self.insert_hashed_nocheck(h
, k
, v
);
757 debug_assert_eq
!(self.table
.size(), old_size
);
761 /// Insert a pre-hashed key-value pair, without first checking
762 /// that there's enough room in the buckets. Returns a reference to the
763 /// newly insert value.
765 /// If the key already exists, the hashtable will be returned untouched
766 /// and a reference to the existing element will be returned.
767 fn insert_hashed_nocheck(&mut self, hash
: SafeHash
, k
: K
, v
: V
) -> &mut V
{
768 self.insert_or_replace_with(hash
, k
, v
, |_
, _
, _
| ())
771 fn insert_or_replace_with
<'a
, F
>(&'a
mut self,
775 mut found_existing
: F
)
777 F
: FnMut(&mut K
, &mut V
, V
),
779 // Worst case, we'll find one empty bucket among `size + 1` buckets.
780 let size
= self.table
.size();
781 let mut probe
= Bucket
::new(&mut self.table
, hash
);
782 let ib
= probe
.index();
785 let mut bucket
= match probe
.peek() {
788 return bucket
.put(hash
, k
, v
).into_mut_refs().1;
790 Full(bucket
) => bucket
794 if bucket
.hash() == hash
{
796 if k
== *bucket
.read_mut().0 {
797 let (bucket_k
, bucket_v
) = bucket
.into_mut_refs();
798 debug_assert
!(k
== *bucket_k
);
799 // Key already exists. Get its reference.
800 found_existing(bucket_k
, bucket_v
, v
);
805 let robin_ib
= bucket
.index() as isize - bucket
.distance() as isize;
807 if (ib
as isize) < robin_ib
{
808 // Found a luckier bucket than me. Better steal his spot.
809 return robin_hood(bucket
, robin_ib
as usize, hash
, k
, v
);
812 probe
= bucket
.next();
813 assert
!(probe
.index() != ib
+ size
+ 1);
817 /// An iterator visiting all keys in arbitrary order.
818 /// Iterator element type is `&'a K`.
823 /// use std::collections::HashMap;
825 /// let mut map = HashMap::new();
826 /// map.insert("a", 1);
827 /// map.insert("b", 2);
828 /// map.insert("c", 3);
830 /// for key in map.keys() {
831 /// println!("{}", key);
834 #[stable(feature = "rust1", since = "1.0.0")]
835 pub fn keys
<'a
>(&'a
self) -> Keys
<'a
, K
, V
> {
836 fn first
<A
, B
>((a
, _
): (A
, B
)) -> A { a }
837 let first
: fn((&'a K
,&'a V
)) -> &'a K
= first
; // coerce to fn ptr
839 Keys { inner: self.iter().map(first) }
842 /// An iterator visiting all values in arbitrary order.
843 /// Iterator element type is `&'a V`.
848 /// use std::collections::HashMap;
850 /// let mut map = HashMap::new();
851 /// map.insert("a", 1);
852 /// map.insert("b", 2);
853 /// map.insert("c", 3);
855 /// for val in map.values() {
856 /// println!("{}", val);
859 #[stable(feature = "rust1", since = "1.0.0")]
860 pub fn values
<'a
>(&'a
self) -> Values
<'a
, K
, V
> {
861 fn second
<A
, B
>((_
, b
): (A
, B
)) -> B { b }
862 let second
: fn((&'a K
,&'a V
)) -> &'a V
= second
; // coerce to fn ptr
864 Values { inner: self.iter().map(second) }
867 /// An iterator visiting all key-value pairs in arbitrary order.
868 /// Iterator element type is `(&'a K, &'a V)`.
873 /// use std::collections::HashMap;
875 /// let mut map = HashMap::new();
876 /// map.insert("a", 1);
877 /// map.insert("b", 2);
878 /// map.insert("c", 3);
880 /// for (key, val) in map.iter() {
881 /// println!("key: {} val: {}", key, val);
884 #[stable(feature = "rust1", since = "1.0.0")]
885 pub fn iter(&self) -> Iter
<K
, V
> {
886 Iter { inner: self.table.iter() }
889 /// An iterator visiting all key-value pairs in arbitrary order,
890 /// with mutable references to the values.
891 /// Iterator element type is `(&'a K, &'a mut V)`.
896 /// use std::collections::HashMap;
898 /// let mut map = HashMap::new();
899 /// map.insert("a", 1);
900 /// map.insert("b", 2);
901 /// map.insert("c", 3);
903 /// // Update all values
904 /// for (_, val) in map.iter_mut() {
908 /// for (key, val) in &map {
909 /// println!("key: {} val: {}", key, val);
912 #[stable(feature = "rust1", since = "1.0.0")]
913 pub fn iter_mut(&mut self) -> IterMut
<K
, V
> {
914 IterMut { inner: self.table.iter_mut() }
917 /// Gets the given key's corresponding entry in the map for in-place manipulation.
922 /// use std::collections::HashMap;
924 /// let mut letters = HashMap::new();
926 /// for ch in "a short treatise on fungi".chars() {
927 /// let counter = letters.entry(ch).or_insert(0);
931 /// assert_eq!(letters[&'s'], 2);
932 /// assert_eq!(letters[&'t'], 3);
933 /// assert_eq!(letters[&'u'], 1);
934 /// assert_eq!(letters.get(&'y'), None);
936 #[stable(feature = "rust1", since = "1.0.0")]
937 pub fn entry(&mut self, key
: K
) -> Entry
<K
, V
> {
941 let hash
= self.make_hash(&key
);
942 search_entry_hashed(&mut self.table
, hash
, key
)
945 /// Returns the number of elements in the map.
950 /// use std::collections::HashMap;
952 /// let mut a = HashMap::new();
953 /// assert_eq!(a.len(), 0);
954 /// a.insert(1, "a");
955 /// assert_eq!(a.len(), 1);
957 #[stable(feature = "rust1", since = "1.0.0")]
958 pub fn len(&self) -> usize { self.table.size() }
960 /// Returns true if the map contains no elements.
965 /// use std::collections::HashMap;
967 /// let mut a = HashMap::new();
968 /// assert!(a.is_empty());
969 /// a.insert(1, "a");
970 /// assert!(!a.is_empty());
973 #[stable(feature = "rust1", since = "1.0.0")]
974 pub fn is_empty(&self) -> bool { self.len() == 0 }
976 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
977 /// allocated memory for reuse.
982 /// # #![feature(drain)]
983 /// use std::collections::HashMap;
985 /// let mut a = HashMap::new();
986 /// a.insert(1, "a");
987 /// a.insert(2, "b");
989 /// for (k, v) in a.drain().take(1) {
990 /// assert!(k == 1 || k == 2);
991 /// assert!(v == "a" || v == "b");
994 /// assert!(a.is_empty());
997 #[unstable(feature = "drain",
998 reason
= "matches collection reform specification, waiting for dust to settle")]
999 pub fn drain(&mut self) -> Drain
<K
, V
> {
1000 fn last_two
<A
, B
, C
>((_
, b
, c
): (A
, B
, C
)) -> (B
, C
) { (b, c) }
1001 let last_two
: fn((SafeHash
, K
, V
)) -> (K
, V
) = last_two
; // coerce to fn pointer
1004 inner
: self.table
.drain().map(last_two
),
1008 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
1014 /// use std::collections::HashMap;
1016 /// let mut a = HashMap::new();
1017 /// a.insert(1, "a");
1019 /// assert!(a.is_empty());
1021 #[stable(feature = "rust1", since = "1.0.0")]
1023 pub fn clear(&mut self) {
1027 /// Returns a reference to the value corresponding to the key.
1029 /// The key may be any borrowed form of the map's key type, but
1030 /// `Hash` and `Eq` on the borrowed form *must* match those for
1036 /// use std::collections::HashMap;
1038 /// let mut map = HashMap::new();
1039 /// map.insert(1, "a");
1040 /// assert_eq!(map.get(&1), Some(&"a"));
1041 /// assert_eq!(map.get(&2), None);
1043 #[stable(feature = "rust1", since = "1.0.0")]
1044 pub fn get
<Q
: ?Sized
>(&self, k
: &Q
) -> Option
<&V
>
1045 where K
: Borrow
<Q
>, Q
: Hash
+ Eq
1047 self.search(k
).map(|bucket
| bucket
.into_refs().1)
1050 /// Returns true if the map contains a value for the specified key.
1052 /// The key may be any borrowed form of the map's key type, but
1053 /// `Hash` and `Eq` on the borrowed form *must* match those for
1059 /// use std::collections::HashMap;
1061 /// let mut map = HashMap::new();
1062 /// map.insert(1, "a");
1063 /// assert_eq!(map.contains_key(&1), true);
1064 /// assert_eq!(map.contains_key(&2), false);
1066 #[stable(feature = "rust1", since = "1.0.0")]
1067 pub fn contains_key
<Q
: ?Sized
>(&self, k
: &Q
) -> bool
1068 where K
: Borrow
<Q
>, Q
: Hash
+ Eq
1070 self.search(k
).is_some()
1073 /// Returns a mutable reference to the value corresponding to the key.
1075 /// The key may be any borrowed form of the map's key type, but
1076 /// `Hash` and `Eq` on the borrowed form *must* match those for
1082 /// use std::collections::HashMap;
1084 /// let mut map = HashMap::new();
1085 /// map.insert(1, "a");
1086 /// if let Some(x) = map.get_mut(&1) {
1089 /// assert_eq!(map[&1], "b");
1091 #[stable(feature = "rust1", since = "1.0.0")]
1092 pub fn get_mut
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<&mut V
>
1093 where K
: Borrow
<Q
>, Q
: Hash
+ Eq
1095 self.search_mut(k
).map(|bucket
| bucket
.into_mut_refs().1)
1098 /// Inserts a key-value pair into the map. If the key already had a value
1099 /// present in the map, that value is returned. Otherwise, `None` is returned.
1104 /// use std::collections::HashMap;
1106 /// let mut map = HashMap::new();
1107 /// assert_eq!(map.insert(37, "a"), None);
1108 /// assert_eq!(map.is_empty(), false);
1110 /// map.insert(37, "b");
1111 /// assert_eq!(map.insert(37, "c"), Some("b"));
1112 /// assert_eq!(map[&37], "c");
1114 #[stable(feature = "rust1", since = "1.0.0")]
1115 pub fn insert(&mut self, k
: K
, v
: V
) -> Option
<V
> {
1116 let hash
= self.make_hash(&k
);
1119 let mut retval
= None
;
1120 self.insert_or_replace_with(hash
, k
, v
, |_
, val_ref
, val
| {
1121 retval
= Some(replace(val_ref
, val
));
1126 /// Removes a key from the map, returning the value at the key if the key
1127 /// was previously in the map.
1129 /// The key may be any borrowed form of the map's key type, but
1130 /// `Hash` and `Eq` on the borrowed form *must* match those for
1136 /// use std::collections::HashMap;
1138 /// let mut map = HashMap::new();
1139 /// map.insert(1, "a");
1140 /// assert_eq!(map.remove(&1), Some("a"));
1141 /// assert_eq!(map.remove(&1), None);
1143 #[stable(feature = "rust1", since = "1.0.0")]
1144 pub fn remove
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<V
>
1145 where K
: Borrow
<Q
>, Q
: Hash
+ Eq
1147 if self.table
.size() == 0 {
1151 self.search_mut(k
).map(|bucket
| pop_internal(bucket
).1)
1155 fn search_entry_hashed
<'a
, K
: Eq
, V
>(table
: &'a
mut RawTable
<K
,V
>, hash
: SafeHash
, k
: K
)
1158 // Worst case, we'll find one empty bucket among `size + 1` buckets.
1159 let size
= table
.size();
1160 let mut probe
= Bucket
::new(table
, hash
);
1161 let ib
= probe
.index();
1164 let bucket
= match probe
.peek() {
1167 return Vacant(VacantEntry
{
1170 elem
: NoElem(bucket
),
1173 Full(bucket
) => bucket
1177 if bucket
.hash() == hash
{
1179 if k
== *bucket
.read().0 {
1180 return Occupied(OccupiedEntry
{
1186 let robin_ib
= bucket
.index() as isize - bucket
.distance() as isize;
1188 if (ib
as isize) < robin_ib
{
1189 // Found a luckier bucket than me. Better steal his spot.
1190 return Vacant(VacantEntry
{
1193 elem
: NeqElem(bucket
, robin_ib
as usize),
1197 probe
= bucket
.next();
1198 assert
!(probe
.index() != ib
+ size
+ 1);
1202 impl<K
, V
, S
> PartialEq
for HashMap
<K
, V
, S
>
1203 where K
: Eq
+ Hash
, V
: PartialEq
, S
: HashState
1205 fn eq(&self, other
: &HashMap
<K
, V
, S
>) -> bool
{
1206 if self.len() != other
.len() { return false; }
1208 self.iter().all(|(key
, value
)|
1209 other
.get(key
).map_or(false, |v
| *value
== *v
)
1214 #[stable(feature = "rust1", since = "1.0.0")]
1215 impl<K
, V
, S
> Eq
for HashMap
<K
, V
, S
>
1216 where K
: Eq
+ Hash
, V
: Eq
, S
: HashState
1219 #[stable(feature = "rust1", since = "1.0.0")]
1220 impl<K
, V
, S
> Debug
for HashMap
<K
, V
, S
>
1221 where K
: Eq
+ Hash
+ Debug
, V
: Debug
, S
: HashState
1223 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1224 f
.debug_map().entries(self.iter()).finish()
1228 #[stable(feature = "rust1", since = "1.0.0")]
1229 impl<K
, V
, S
> Default
for HashMap
<K
, V
, S
>
1231 S
: HashState
+ Default
,
1233 fn default() -> HashMap
<K
, V
, S
> {
1234 HashMap
::with_hash_state(Default
::default())
1238 #[stable(feature = "rust1", since = "1.0.0")]
1239 impl<'a
, K
, Q
: ?Sized
, V
, S
> Index
<&'a Q
> for HashMap
<K
, V
, S
>
1240 where K
: Eq
+ Hash
+ Borrow
<Q
>,
1247 fn index(&self, index
: &Q
) -> &V
{
1248 self.get(index
).expect("no entry found for key")
1252 /// HashMap iterator.
1253 #[stable(feature = "rust1", since = "1.0.0")]
1254 pub struct Iter
<'a
, K
: 'a
, V
: 'a
> {
1255 inner
: table
::Iter
<'a
, K
, V
>
1258 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1259 impl<'a
, K
, V
> Clone
for Iter
<'a
, K
, V
> {
1260 fn clone(&self) -> Iter
<'a
, K
, V
> {
1262 inner
: self.inner
.clone()
1267 /// HashMap mutable values iterator.
1268 #[stable(feature = "rust1", since = "1.0.0")]
1269 pub struct IterMut
<'a
, K
: 'a
, V
: 'a
> {
1270 inner
: table
::IterMut
<'a
, K
, V
>
1273 /// HashMap move iterator.
1274 #[stable(feature = "rust1", since = "1.0.0")]
1275 pub struct IntoIter
<K
, V
> {
1276 inner
: iter
::Map
<table
::IntoIter
<K
, V
>, fn((SafeHash
, K
, V
)) -> (K
, V
)>
1279 /// HashMap keys iterator.
1280 #[stable(feature = "rust1", since = "1.0.0")]
1281 pub struct Keys
<'a
, K
: 'a
, V
: 'a
> {
1282 inner
: Map
<Iter
<'a
, K
, V
>, fn((&'a K
, &'a V
)) -> &'a K
>
1285 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1286 impl<'a
, K
, V
> Clone
for Keys
<'a
, K
, V
> {
1287 fn clone(&self) -> Keys
<'a
, K
, V
> {
1289 inner
: self.inner
.clone()
1294 /// HashMap values iterator.
1295 #[stable(feature = "rust1", since = "1.0.0")]
1296 pub struct Values
<'a
, K
: 'a
, V
: 'a
> {
1297 inner
: Map
<Iter
<'a
, K
, V
>, fn((&'a K
, &'a V
)) -> &'a V
>
1300 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1301 impl<'a
, K
, V
> Clone
for Values
<'a
, K
, V
> {
1302 fn clone(&self) -> Values
<'a
, K
, V
> {
1304 inner
: self.inner
.clone()
1309 /// HashMap drain iterator.
1310 #[unstable(feature = "drain",
1311 reason
= "matches collection reform specification, waiting for dust to settle")]
1312 pub struct Drain
<'a
, K
: 'a
, V
: 'a
> {
1313 inner
: iter
::Map
<table
::Drain
<'a
, K
, V
>, fn((SafeHash
, K
, V
)) -> (K
, V
)>
1316 /// A view into a single occupied location in a HashMap.
1317 #[stable(feature = "rust1", since = "1.0.0")]
1318 pub struct OccupiedEntry
<'a
, K
: 'a
, V
: 'a
> {
1319 elem
: FullBucket
<K
, V
, &'a
mut RawTable
<K
, V
>>,
1322 /// A view into a single empty location in a HashMap.
1323 #[stable(feature = "rust1", since = "1.0.0")]
1324 pub struct VacantEntry
<'a
, K
: 'a
, V
: 'a
> {
1327 elem
: VacantEntryState
<K
, V
, &'a
mut RawTable
<K
, V
>>,
1330 /// A view into a single location in a map, which may be vacant or occupied.
1331 #[stable(feature = "rust1", since = "1.0.0")]
1332 pub enum Entry
<'a
, K
: 'a
, V
: 'a
> {
1333 /// An occupied Entry.
1334 #[stable(feature = "rust1", since = "1.0.0")]
1335 Occupied(OccupiedEntry
<'a
, K
, V
>),
1338 #[stable(feature = "rust1", since = "1.0.0")]
1339 Vacant(VacantEntry
<'a
, K
, V
>),
1342 /// Possible states of a VacantEntry.
1343 enum VacantEntryState
<K
, V
, M
> {
1344 /// The index is occupied, but the key to insert has precedence,
1345 /// and will kick the current one out on insertion.
1346 NeqElem(FullBucket
<K
, V
, M
>, usize),
1347 /// The index is genuinely vacant.
1348 NoElem(EmptyBucket
<K
, V
, M
>),
1351 #[stable(feature = "rust1", since = "1.0.0")]
1352 impl<'a
, K
, V
, S
> IntoIterator
for &'a HashMap
<K
, V
, S
>
1353 where K
: Eq
+ Hash
, S
: HashState
1355 type Item
= (&'a K
, &'a V
);
1356 type IntoIter
= Iter
<'a
, K
, V
>;
1358 fn into_iter(self) -> Iter
<'a
, K
, V
> {
1363 #[stable(feature = "rust1", since = "1.0.0")]
1364 impl<'a
, K
, V
, S
> IntoIterator
for &'a
mut HashMap
<K
, V
, S
>
1365 where K
: Eq
+ Hash
, S
: HashState
1367 type Item
= (&'a K
, &'a
mut V
);
1368 type IntoIter
= IterMut
<'a
, K
, V
>;
1370 fn into_iter(mut self) -> IterMut
<'a
, K
, V
> {
1375 #[stable(feature = "rust1", since = "1.0.0")]
1376 impl<K
, V
, S
> IntoIterator
for HashMap
<K
, V
, S
>
1377 where K
: Eq
+ Hash
, S
: HashState
1380 type IntoIter
= IntoIter
<K
, V
>;
1382 /// Creates a consuming iterator, that is, one that moves each key-value
1383 /// pair out of the map in arbitrary order. The map cannot be used after
1389 /// use std::collections::HashMap;
1391 /// let mut map = HashMap::new();
1392 /// map.insert("a", 1);
1393 /// map.insert("b", 2);
1394 /// map.insert("c", 3);
1396 /// // Not possible with .iter()
1397 /// let vec: Vec<(&str, isize)> = map.into_iter().collect();
1399 fn into_iter(self) -> IntoIter
<K
, V
> {
1400 fn last_two
<A
, B
, C
>((_
, b
, c
): (A
, B
, C
)) -> (B
, C
) { (b, c) }
1401 let last_two
: fn((SafeHash
, K
, V
)) -> (K
, V
) = last_two
;
1404 inner
: self.table
.into_iter().map(last_two
)
1409 #[stable(feature = "rust1", since = "1.0.0")]
1410 impl<'a
, K
, V
> Iterator
for Iter
<'a
, K
, V
> {
1411 type Item
= (&'a K
, &'a V
);
1413 #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1414 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1416 #[stable(feature = "rust1", since = "1.0.0")]
1417 impl<'a
, K
, V
> ExactSizeIterator
for Iter
<'a
, K
, V
> {
1418 #[inline] fn len(&self) -> usize { self.inner.len() }
1421 #[stable(feature = "rust1", since = "1.0.0")]
1422 impl<'a
, K
, V
> Iterator
for IterMut
<'a
, K
, V
> {
1423 type Item
= (&'a K
, &'a
mut V
);
1425 #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1426 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1428 #[stable(feature = "rust1", since = "1.0.0")]
1429 impl<'a
, K
, V
> ExactSizeIterator
for IterMut
<'a
, K
, V
> {
1430 #[inline] fn len(&self) -> usize { self.inner.len() }
1433 #[stable(feature = "rust1", since = "1.0.0")]
1434 impl<K
, V
> Iterator
for IntoIter
<K
, V
> {
1437 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1438 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1440 #[stable(feature = "rust1", since = "1.0.0")]
1441 impl<K
, V
> ExactSizeIterator
for IntoIter
<K
, V
> {
1442 #[inline] fn len(&self) -> usize { self.inner.len() }
1445 #[stable(feature = "rust1", since = "1.0.0")]
1446 impl<'a
, K
, V
> Iterator
for Keys
<'a
, K
, V
> {
1449 #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
1450 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1452 #[stable(feature = "rust1", since = "1.0.0")]
1453 impl<'a
, K
, V
> ExactSizeIterator
for Keys
<'a
, K
, V
> {
1454 #[inline] fn len(&self) -> usize { self.inner.len() }
1457 #[stable(feature = "rust1", since = "1.0.0")]
1458 impl<'a
, K
, V
> Iterator
for Values
<'a
, K
, V
> {
1461 #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
1462 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1464 #[stable(feature = "rust1", since = "1.0.0")]
1465 impl<'a
, K
, V
> ExactSizeIterator
for Values
<'a
, K
, V
> {
1466 #[inline] fn len(&self) -> usize { self.inner.len() }
1469 #[stable(feature = "rust1", since = "1.0.0")]
1470 impl<'a
, K
, V
> Iterator
for Drain
<'a
, K
, V
> {
1473 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1474 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1476 #[stable(feature = "rust1", since = "1.0.0")]
1477 impl<'a
, K
, V
> ExactSizeIterator
for Drain
<'a
, K
, V
> {
1478 #[inline] fn len(&self) -> usize { self.inner.len() }
1481 impl<'a
, K
, V
> Entry
<'a
, K
, V
> {
1482 #[unstable(feature = "entry",
1483 reason
= "will soon be replaced by or_insert")]
1484 #[deprecated(since = "1.0",
1485 reason
= "replaced with more ergonomic `or_insert` and `or_insert_with`")]
1486 /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant
1487 pub fn get(self) -> Result
<&'a
mut V
, VacantEntry
<'a
, K
, V
>> {
1489 Occupied(entry
) => Ok(entry
.into_mut()),
1490 Vacant(entry
) => Err(entry
),
1494 #[stable(feature = "rust1", since = "1.0.0")]
1495 /// Ensures a value is in the entry by inserting the default if empty, and returns
1496 /// a mutable reference to the value in the entry.
1497 pub fn or_insert(self, default: V
) -> &'a
mut V
{
1499 Occupied(entry
) => entry
.into_mut(),
1500 Vacant(entry
) => entry
.insert(default),
1504 #[stable(feature = "rust1", since = "1.0.0")]
1505 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1506 /// and returns a mutable reference to the value in the entry.
1507 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
{
1509 Occupied(entry
) => entry
.into_mut(),
1510 Vacant(entry
) => entry
.insert(default()),
1515 impl<'a
, K
, V
> OccupiedEntry
<'a
, K
, V
> {
1516 /// Gets a reference to the value in the entry.
1517 #[stable(feature = "rust1", since = "1.0.0")]
1518 pub fn get(&self) -> &V
{
1522 /// Gets a mutable reference to the value in the entry.
1523 #[stable(feature = "rust1", since = "1.0.0")]
1524 pub fn get_mut(&mut self) -> &mut V
{
1525 self.elem
.read_mut().1
1528 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1529 /// with a lifetime bound to the map itself
1530 #[stable(feature = "rust1", since = "1.0.0")]
1531 pub fn into_mut(self) -> &'a
mut V
{
1532 self.elem
.into_mut_refs().1
1535 /// Sets the value of the entry, and returns the entry's old value
1536 #[stable(feature = "rust1", since = "1.0.0")]
1537 pub fn insert(&mut self, mut value
: V
) -> V
{
1538 let old_value
= self.get_mut();
1539 mem
::swap(&mut value
, old_value
);
1543 /// Takes the value out of the entry, and returns it
1544 #[stable(feature = "rust1", since = "1.0.0")]
1545 pub fn remove(self) -> V
{
1546 pop_internal(self.elem
).1
1550 impl<'a
, K
: 'a
, V
: 'a
> VacantEntry
<'a
, K
, V
> {
1551 /// Sets the value of the entry with the VacantEntry's key,
1552 /// and returns a mutable reference to it
1553 #[stable(feature = "rust1", since = "1.0.0")]
1554 pub fn insert(self, value
: V
) -> &'a
mut V
{
1556 NeqElem(bucket
, ib
) => {
1557 robin_hood(bucket
, ib
, self.hash
, self.key
, value
)
1560 bucket
.put(self.hash
, self.key
, value
).into_mut_refs().1
1566 #[stable(feature = "rust1", since = "1.0.0")]
1567 impl<K
, V
, S
> FromIterator
<(K
, V
)> for HashMap
<K
, V
, S
>
1568 where K
: Eq
+ Hash
, S
: HashState
+ Default
1570 fn from_iter
<T
: IntoIterator
<Item
=(K
, V
)>>(iterable
: T
) -> HashMap
<K
, V
, S
> {
1571 let iter
= iterable
.into_iter();
1572 let lower
= iter
.size_hint().0;
1573 let mut map
= HashMap
::with_capacity_and_hash_state(lower
,
1574 Default
::default());
1580 #[stable(feature = "rust1", since = "1.0.0")]
1581 impl<K
, V
, S
> Extend
<(K
, V
)> for HashMap
<K
, V
, S
>
1582 where K
: Eq
+ Hash
, S
: HashState
1584 fn extend
<T
: IntoIterator
<Item
=(K
, V
)>>(&mut self, iter
: T
) {
1585 for (k
, v
) in iter
{
1592 /// `RandomState` is the default state for `HashMap` types.
1594 /// A particular instance `RandomState` will create the same instances of
1595 /// `Hasher`, but the hashers created by two different `RandomState`
1596 /// instances are unlikely to produce the same result for the same values.
1598 #[unstable(feature = "hashmap_hasher",
1599 reason
= "hashing an hash maps may be altered")]
1600 pub struct RandomState
{
1605 #[unstable(feature = "hashmap_hasher",
1606 reason
= "hashing an hash maps may be altered")]
1608 /// Constructs a new `RandomState` that is initialized with random keys.
1610 #[allow(deprecated)]
1611 pub fn new() -> RandomState
{
1612 let mut r
= rand
::thread_rng();
1613 RandomState { k0: r.gen(), k1: r.gen() }
1617 #[unstable(feature = "hashmap_hasher",
1618 reason
= "hashing an hash maps may be altered")]
1619 impl HashState
for RandomState
{
1620 type Hasher
= SipHasher
;
1622 fn hasher(&self) -> SipHasher
{
1623 SipHasher
::new_with_keys(self.k0
, self.k1
)
1627 #[stable(feature = "rust1", since = "1.0.0")]
1628 impl Default
for RandomState
{
1630 fn default() -> RandomState
{
1640 use super::Entry
::{Occupied, Vacant}
;
1641 use iter
::{range_inclusive, repeat}
;
1643 use rand
::{thread_rng, Rng}
;
1646 fn test_create_capacity_zero() {
1647 let mut m
= HashMap
::with_capacity(0);
1649 assert
!(m
.insert(1, 1).is_none());
1651 assert
!(m
.contains_key(&1));
1652 assert
!(!m
.contains_key(&0));
1657 let mut m
= HashMap
::new();
1658 assert_eq
!(m
.len(), 0);
1659 assert
!(m
.insert(1, 2).is_none());
1660 assert_eq
!(m
.len(), 1);
1661 assert
!(m
.insert(2, 4).is_none());
1662 assert_eq
!(m
.len(), 2);
1663 assert_eq
!(*m
.get(&1).unwrap(), 2);
1664 assert_eq
!(*m
.get(&2).unwrap(), 4);
1667 thread_local
! { static DROP_VECTOR: RefCell<Vec<isize>> = RefCell::new(Vec::new()) }
1669 #[derive(Hash, PartialEq, Eq)]
1675 fn new(k
: usize) -> Dropable
{
1676 DROP_VECTOR
.with(|slot
| {
1677 slot
.borrow_mut()[k
] += 1;
1684 impl Drop
for Dropable
{
1685 fn drop(&mut self) {
1686 DROP_VECTOR
.with(|slot
| {
1687 slot
.borrow_mut()[self.k
] -= 1;
1692 impl Clone
for Dropable
{
1693 fn clone(&self) -> Dropable
{
1694 Dropable
::new(self.k
)
1700 DROP_VECTOR
.with(|slot
| {
1701 *slot
.borrow_mut() = repeat(0).take(200).collect();
1705 let mut m
= HashMap
::new();
1707 DROP_VECTOR
.with(|v
| {
1709 assert_eq
!(v
.borrow()[i
], 0);
1714 let d1
= Dropable
::new(i
);
1715 let d2
= Dropable
::new(i
+100);
1719 DROP_VECTOR
.with(|v
| {
1721 assert_eq
!(v
.borrow()[i
], 1);
1726 let k
= Dropable
::new(i
);
1727 let v
= m
.remove(&k
);
1729 assert
!(v
.is_some());
1731 DROP_VECTOR
.with(|v
| {
1732 assert_eq
!(v
.borrow()[i
], 1);
1733 assert_eq
!(v
.borrow()[i
+100], 1);
1737 DROP_VECTOR
.with(|v
| {
1739 assert_eq
!(v
.borrow()[i
], 0);
1740 assert_eq
!(v
.borrow()[i
+100], 0);
1744 assert_eq
!(v
.borrow()[i
], 1);
1745 assert_eq
!(v
.borrow()[i
+100], 1);
1750 DROP_VECTOR
.with(|v
| {
1752 assert_eq
!(v
.borrow()[i
], 0);
1758 fn test_move_iter_drops() {
1759 DROP_VECTOR
.with(|v
| {
1760 *v
.borrow_mut() = repeat(0).take(200).collect();
1764 let mut hm
= HashMap
::new();
1766 DROP_VECTOR
.with(|v
| {
1768 assert_eq
!(v
.borrow()[i
], 0);
1773 let d1
= Dropable
::new(i
);
1774 let d2
= Dropable
::new(i
+100);
1778 DROP_VECTOR
.with(|v
| {
1780 assert_eq
!(v
.borrow()[i
], 1);
1787 // By the way, ensure that cloning doesn't screw up the dropping.
1791 let mut half
= hm
.into_iter().take(50);
1793 DROP_VECTOR
.with(|v
| {
1795 assert_eq
!(v
.borrow()[i
], 1);
1799 for _
in half
.by_ref() {}
1801 DROP_VECTOR
.with(|v
| {
1802 let nk
= (0..100).filter(|&i
| {
1806 let nv
= (0..100).filter(|&i
| {
1807 v
.borrow()[i
+100] == 1
1815 DROP_VECTOR
.with(|v
| {
1817 assert_eq
!(v
.borrow()[i
], 0);
1823 fn test_empty_pop() {
1824 let mut m
: HashMap
<isize, bool
> = HashMap
::new();
1825 assert_eq
!(m
.remove(&0), None
);
1829 fn test_lots_of_insertions() {
1830 let mut m
= HashMap
::new();
1832 // Try this a few times to make sure we never screw up the hashmap's
1835 assert
!(m
.is_empty());
1837 for i
in range_inclusive(1, 1000) {
1838 assert
!(m
.insert(i
, i
).is_none());
1840 for j
in range_inclusive(1, i
) {
1842 assert_eq
!(r
, Some(&j
));
1845 for j
in range_inclusive(i
+1, 1000) {
1847 assert_eq
!(r
, None
);
1851 for i
in range_inclusive(1001, 2000) {
1852 assert
!(!m
.contains_key(&i
));
1856 for i
in range_inclusive(1, 1000) {
1857 assert
!(m
.remove(&i
).is_some());
1859 for j
in range_inclusive(1, i
) {
1860 assert
!(!m
.contains_key(&j
));
1863 for j
in range_inclusive(i
+1, 1000) {
1864 assert
!(m
.contains_key(&j
));
1868 for i
in range_inclusive(1, 1000) {
1869 assert
!(!m
.contains_key(&i
));
1872 for i
in range_inclusive(1, 1000) {
1873 assert
!(m
.insert(i
, i
).is_none());
1877 for i
in (1..1001).rev() {
1878 assert
!(m
.remove(&i
).is_some());
1880 for j
in range_inclusive(i
, 1000) {
1881 assert
!(!m
.contains_key(&j
));
1884 for j
in range_inclusive(1, i
-1) {
1885 assert
!(m
.contains_key(&j
));
1892 fn test_find_mut() {
1893 let mut m
= HashMap
::new();
1894 assert
!(m
.insert(1, 12).is_none());
1895 assert
!(m
.insert(2, 8).is_none());
1896 assert
!(m
.insert(5, 14).is_none());
1898 match m
.get_mut(&5) {
1899 None
=> panic
!(), Some(x
) => *x
= new
1901 assert_eq
!(m
.get(&5), Some(&new
));
1905 fn test_insert_overwrite() {
1906 let mut m
= HashMap
::new();
1907 assert
!(m
.insert(1, 2).is_none());
1908 assert_eq
!(*m
.get(&1).unwrap(), 2);
1909 assert
!(!m
.insert(1, 3).is_none());
1910 assert_eq
!(*m
.get(&1).unwrap(), 3);
1914 fn test_insert_conflicts() {
1915 let mut m
= HashMap
::with_capacity(4);
1916 assert
!(m
.insert(1, 2).is_none());
1917 assert
!(m
.insert(5, 3).is_none());
1918 assert
!(m
.insert(9, 4).is_none());
1919 assert_eq
!(*m
.get(&9).unwrap(), 4);
1920 assert_eq
!(*m
.get(&5).unwrap(), 3);
1921 assert_eq
!(*m
.get(&1).unwrap(), 2);
1925 fn test_conflict_remove() {
1926 let mut m
= HashMap
::with_capacity(4);
1927 assert
!(m
.insert(1, 2).is_none());
1928 assert_eq
!(*m
.get(&1).unwrap(), 2);
1929 assert
!(m
.insert(5, 3).is_none());
1930 assert_eq
!(*m
.get(&1).unwrap(), 2);
1931 assert_eq
!(*m
.get(&5).unwrap(), 3);
1932 assert
!(m
.insert(9, 4).is_none());
1933 assert_eq
!(*m
.get(&1).unwrap(), 2);
1934 assert_eq
!(*m
.get(&5).unwrap(), 3);
1935 assert_eq
!(*m
.get(&9).unwrap(), 4);
1936 assert
!(m
.remove(&1).is_some());
1937 assert_eq
!(*m
.get(&9).unwrap(), 4);
1938 assert_eq
!(*m
.get(&5).unwrap(), 3);
1942 fn test_is_empty() {
1943 let mut m
= HashMap
::with_capacity(4);
1944 assert
!(m
.insert(1, 2).is_none());
1945 assert
!(!m
.is_empty());
1946 assert
!(m
.remove(&1).is_some());
1947 assert
!(m
.is_empty());
1952 let mut m
= HashMap
::new();
1954 assert_eq
!(m
.remove(&1), Some(2));
1955 assert_eq
!(m
.remove(&1), None
);
1960 let mut m
= HashMap
::with_capacity(4);
1962 assert
!(m
.insert(i
, i
*2).is_none());
1964 assert_eq
!(m
.len(), 32);
1966 let mut observed
: u32 = 0;
1969 assert_eq
!(*v
, *k
* 2);
1970 observed
|= 1 << *k
;
1972 assert_eq
!(observed
, 0xFFFF_FFFF);
1977 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
1978 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
1979 let keys
: Vec
<_
> = map
.keys().cloned().collect();
1980 assert_eq
!(keys
.len(), 3);
1981 assert
!(keys
.contains(&1));
1982 assert
!(keys
.contains(&2));
1983 assert
!(keys
.contains(&3));
1988 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
1989 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
1990 let values
: Vec
<_
> = map
.values().cloned().collect();
1991 assert_eq
!(values
.len(), 3);
1992 assert
!(values
.contains(&'a'
));
1993 assert
!(values
.contains(&'b'
));
1994 assert
!(values
.contains(&'c'
));
1999 let mut m
= HashMap
::new();
2000 assert
!(m
.get(&1).is_none());
2004 Some(v
) => assert_eq
!(*v
, 2)
2010 let mut m1
= HashMap
::new();
2015 let mut m2
= HashMap
::new();
2028 let mut map
= HashMap
::new();
2029 let empty
: HashMap
<i32, i32> = HashMap
::new();
2034 let map_str
= format
!("{:?}", map
);
2036 assert
!(map_str
== "{1: 2, 3: 4}" ||
2037 map_str
== "{3: 4, 1: 2}");
2038 assert_eq
!(format
!("{:?}", empty
), "{}");
2043 let mut m
= HashMap
::new();
2045 assert_eq
!(m
.len(), 0);
2046 assert
!(m
.is_empty());
2049 let old_cap
= m
.table
.capacity();
2050 while old_cap
== m
.table
.capacity() {
2055 assert_eq
!(m
.len(), i
);
2056 assert
!(!m
.is_empty());
2060 fn test_behavior_resize_policy() {
2061 let mut m
= HashMap
::new();
2063 assert_eq
!(m
.len(), 0);
2064 assert_eq
!(m
.table
.capacity(), 0);
2065 assert
!(m
.is_empty());
2069 assert
!(m
.is_empty());
2070 let initial_cap
= m
.table
.capacity();
2071 m
.reserve(initial_cap
);
2072 let cap
= m
.table
.capacity();
2074 assert_eq
!(cap
, initial_cap
* 2);
2077 for _
in 0..cap
* 3 / 4 {
2081 // three quarters full
2083 assert_eq
!(m
.len(), i
);
2084 assert_eq
!(m
.table
.capacity(), cap
);
2086 for _
in 0..cap
/ 4 {
2092 let new_cap
= m
.table
.capacity();
2093 assert_eq
!(new_cap
, cap
* 2);
2095 for _
in 0..cap
/ 2 - 1 {
2098 assert_eq
!(m
.table
.capacity(), new_cap
);
2100 // A little more than one quarter full.
2102 assert_eq
!(m
.table
.capacity(), cap
);
2103 // again, a little more than half full
2104 for _
in 0..cap
/ 2 - 1 {
2110 assert_eq
!(m
.len(), i
);
2111 assert
!(!m
.is_empty());
2112 assert_eq
!(m
.table
.capacity(), initial_cap
);
2116 fn test_reserve_shrink_to_fit() {
2117 let mut m
= HashMap
::new();
2120 assert
!(m
.capacity() >= m
.len());
2126 let usable_cap
= m
.capacity();
2127 for i
in 128..(128 + 256) {
2129 assert_eq
!(m
.capacity(), usable_cap
);
2132 for i
in 100..(128 + 256) {
2133 assert_eq
!(m
.remove(&i
), Some(i
));
2137 assert_eq
!(m
.len(), 100);
2138 assert
!(!m
.is_empty());
2139 assert
!(m
.capacity() >= m
.len());
2142 assert_eq
!(m
.remove(&i
), Some(i
));
2147 assert_eq
!(m
.len(), 1);
2148 assert
!(m
.capacity() >= m
.len());
2149 assert_eq
!(m
.remove(&0), Some(0));
2153 fn test_from_iter() {
2154 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2156 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2158 for &(k
, v
) in &xs
{
2159 assert_eq
!(map
.get(&k
), Some(&v
));
2164 fn test_size_hint() {
2165 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2167 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2169 let mut iter
= map
.iter();
2171 for _
in iter
.by_ref().take(3) {}
2173 assert_eq
!(iter
.size_hint(), (3, Some(3)));
2177 fn test_iter_len() {
2178 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2180 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2182 let mut iter
= map
.iter();
2184 for _
in iter
.by_ref().take(3) {}
2186 assert_eq
!(iter
.len(), 3);
2190 fn test_mut_size_hint() {
2191 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2193 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2195 let mut iter
= map
.iter_mut();
2197 for _
in iter
.by_ref().take(3) {}
2199 assert_eq
!(iter
.size_hint(), (3, Some(3)));
2203 fn test_iter_mut_len() {
2204 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2206 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2208 let mut iter
= map
.iter_mut();
2210 for _
in iter
.by_ref().take(3) {}
2212 assert_eq
!(iter
.len(), 3);
2217 let mut map
= HashMap
::new();
2223 assert_eq
!(map
[&2], 1);
2228 fn test_index_nonexistent() {
2229 let mut map
= HashMap
::new();
2240 let xs
= [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2242 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2244 // Existing key (insert)
2245 match map
.entry(1) {
2246 Vacant(_
) => unreachable
!(),
2247 Occupied(mut view
) => {
2248 assert_eq
!(view
.get(), &10);
2249 assert_eq
!(view
.insert(100), 10);
2252 assert_eq
!(map
.get(&1).unwrap(), &100);
2253 assert_eq
!(map
.len(), 6);
2256 // Existing key (update)
2257 match map
.entry(2) {
2258 Vacant(_
) => unreachable
!(),
2259 Occupied(mut view
) => {
2260 let v
= view
.get_mut();
2261 let new_v
= (*v
) * 10;
2265 assert_eq
!(map
.get(&2).unwrap(), &200);
2266 assert_eq
!(map
.len(), 6);
2268 // Existing key (take)
2269 match map
.entry(3) {
2270 Vacant(_
) => unreachable
!(),
2272 assert_eq
!(view
.remove(), 30);
2275 assert_eq
!(map
.get(&3), None
);
2276 assert_eq
!(map
.len(), 5);
2279 // Inexistent key (insert)
2280 match map
.entry(10) {
2281 Occupied(_
) => unreachable
!(),
2283 assert_eq
!(*view
.insert(1000), 1000);
2286 assert_eq
!(map
.get(&10).unwrap(), &1000);
2287 assert_eq
!(map
.len(), 6);
2291 fn test_entry_take_doesnt_corrupt() {
2292 #![allow(deprecated)] //rand
2294 fn check(m
: &HashMap
<isize, ()>) {
2296 assert
!(m
.contains_key(k
),
2297 "{} is in keys() but not in the map?", k
);
2301 let mut m
= HashMap
::new();
2302 let mut rng
= thread_rng();
2304 // Populate the map with some items.
2306 let x
= rng
.gen_range(-10, 10);
2311 let x
= rng
.gen_range(-10, 10);
2315 println
!("{}: remove {}", i
, x
);